Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 88
Текст из файла (страница 88)
е.∀i, j : (ci = cj ∧ Mi = Mj).Для каждого алгоритма на данном кольце строится такое вычисление C = ( 0 , 1 , . . .),что каждая конфигурация kN в последовательности C является симметрической.Обозначим символом 0 симметрическую начальную конфигурацию. Такая конфигурация существует, поскольку каждый процесс имеет одно и то же множествоначальных состояний и первоначально все множества M i — пустые.Если конфигурация kN является терминальной, то построение завершено;вычисление C завершается симметрической конфигурацией.
В противном случаеkN является симметрической конфигурацией, в которой по меньшей мере однособытие осуществимо; предположим, что это событие e i в процессе pi . Симметричность конфигурации позволяет заключить, что такое же событие осуществимо9.2. Детерминированные алгоритмы333в каждом процессе.
Из теоремы 2.19 следует, что это событие может быть осуществлено параллельно всеми процессами, и после выполнения этих N переходовобразуется симметрическая конфигурация. Действительно, все процессы перешли из одинаковых состояний в одинаковые же состояния. Если событие предполагает прием сообщения, то это сообщение изымается из каждого из идентичныхмножеств Mi , а если происходит отправление сообщения, то оно добавляется ккаждому из идентичных множеств Mi . Следовательно, продолжив наше вычисление и совершив N шагов, мы вновь придем к симметрической конфигурации(k+1)N .Таким образом, каждый алгоритм для данного анонимного кольца имеет вычисление, которое либо является бесконечным, либо завершается симметрической конфигурацией.
В симметрической конфигурации либо все процессы пребывают в состоянии leader, либо ни один процесс не пребывает в этом состоянии;значит, в симметрической конфигурации один единственный процесс не можетпребывать в состоянии leader. Для детерминированного алгоритма избрания лидера все конфигурации завершаются терминальной конфигурацией, в которойровно один процесс пребывает в состоянии leader.
Это означает, что таких алгоритмов для нашего кольца не существует.Из теоремы 9.5 следует, что и более общая задача о выборах в произвольныхсетях или кольцах неизвестного размера также неразрешима детерминированными алгоритмами.9.2.2. Вычисление функций на кольцеВ связи с невозможностью проведения выборов возникает вопрос о том, существуют ли более простые задачи, которые можно решить даже в том случае,если избрание лидера невозможно. В этом параграфе рассматривается задачавычисления значения функции на ориентированном анонимном кольце.
Предположим, что на вход процесса pi подаются данные xi ∈ X, и пусть SX обозначаетмножество всех последовательностей элементов из X. Функцию f, определеннуюна SX, назовем циклической, если она инвариантна относительно циклическихсдвигов входных данных, т. е. f(y) = f(x) для всех циклических сдвигов y последовательности x. Примерами циклических функций могут служить функции суммирования, максимума и минимума на целых числах, булевы функции дизъюнкции,конъюнкции и сложения по модулю два, а также функция вычисления длины входа. Предположим, что процесс p наделен переменной result p ; тогда постусловиевсякого алгоритма вычисления f имеет вид «resultp = f(x0 , .
. . , xN−1)».Результаты этого параграфа свидетельствуют о том, насколько важна информация о размере кольца, а также о том, насколько существенны различияв завершении вычисления по признаку окончания работы процессов и окончанияприема сообщений.Размер кольца известен.
Если размер кольца известен, то всякая циклическая функция может быть вычислена некоторым детерминированным алгоритмомпутем накопления всех входных данных каждым процессом. Такое решение носит334Гл. 9. Анонимные сетиназвание накопление входов. Для накопления входов требутся N(N − 1) сообщений, и эта величина служит нижней оценкой сложности вычисления некоторыхфункций детерминированными алгоритмами.Теорема 9.6. Если размер кольца известен, то всякая циклическая функция f может быть вычислена некоторым детерминированным алгоритмом, завершающим вычисление по признаку окончания работы процессов,с использованием N(N − 1) сообщений.Д о к а з а т е л ь с т в о.
Чтобы сделать наше обоснование более наглядным,будем считать, что в каналах поддерживается очередность сообщений. По ходуработы алгоритма сообщения отправляются на протяжении N − 1 этапов. На первом этапе каждый процесс отправляет свои собственные входные данные соседуслева и принимает входные данные своего соседа справа. На каждом последующем этапе всякий процесс отправляет соседу слева данные, полученные им напредыдущем этапе, и принимает от соседа справа новые данные.
Поскольку каждая порция входных данных на каждом этапе достигает всякий раз еще одногопроцесса, на i-м этапе всякий процесс принимает данные, принадлежащие егоi-му по порядку соседу справа; таким образом, каждый процесс сумеет накопитьвсе входные данные (в том порядке, в котором они располагаются относительноэтого процесса на кольце) за N − 1 этапов. После окончания коммуникационнойфазы каждый процесс вычисляет локально значение функции и завершает своюработу.Теорема 9.7. Всякий детерминированный алгоритм, завершающий вычисление функций AND, OR или SUM по признаку окончания работы процессов, использует N(N − 1) сообщений в худшем случае.Д о к а з а т е л ь с т в о. Рассмотрим детерминированный алгоритм A, завершающий вычисление по признаку окончания работы процессов и решающий однуиз указанных задач. Определим трассу сообщений, подобно тому как это былосделано в определении и § 7.2.3.
Если процесс p отправляет сообщение передтем, как впервые осуществить прием какого-либо сообщения, то для обозначения трассы этого сообщения будем использовать запись (p). Если процесс pотправляет сообщение m в тот момент, когда самая длинная трасса полученногоим ранее сообщения равна (p1 , . .
. , pk), то трассой сообщения m будет запись(p1 , . . . , pk , p).Все три задачи, упомянутые в формулировке теоремы, имеют одно общее качество: хотя бы для одной симметрической начальной конфигурации какой-либоиз процессов, до того как он прекратит работу, должен получить сообщение, трасса которого имеет длину N − 1. Для задачи SUM это справедливо применительнок любой начальной конфигурации. Для задачи AND это будет иметь место, когдакаждый процесс получает на входе значение true, а для задачи OR — когда каждый процесс получает на входе значение false. Чтобы убедиться, что сообщение,имеющее трассу длины N − 1, обязательно будет принято, рассмотрим вычислениеAND в случае, когда каждый процесс получает на входе значение true; в такомслучае будет вычислен ответ true.
Допустим, что некоторый процесс завершает9.2. Детерминированные алгоритмы335работу, вычислив результат true, в то время, когда самая длинная трасса полученного этим процессом сообщения имеет длину k < N − 1. То событие, котороесовершается в момент прекращения работы этого процесса, зависит только отсобытий, которые произошли в каких-либо k + 1 процессах, и, следовательно,оно произойдет и в ходе вычисления, в начальной конфигурации которого указанные k + 1 процессов получили на входе значение true, а остальные — false.Как и прежде, назовем конфигурацию симметрической, если все процессыпребывают в одном и том же состоянии и в каждом канале содержится одно и тоже множество сообщений.
Точно так же, как и при доказательстве теоремы 9.5,строится вычисление, в котором симметрическая конфигурация образуется черезкаждые N шагов и в ходе которого в каждом процессе происходит одно и то жемножество событий. Начальная конфигурация может быть выбрана таким образом, чтобы в ходе работы алгоритма было отправлено хотя бы одно сообщение,трасса которого имеет длину N − 1. В ходе такого вычисления для каждого натурального i, i 6 N − 1, будет отправлено сообщение, трасса которого имеетдлину i.
Но коль скоро в каждом процессе осуществляется одно и то же множество событий, общее число сообщений, трасса которых имеет длину i, кратно N,а значит, не может быть меньше N. Следовательно, суммарное число сообщенийне может быть меньше N(N − 1).Размер кольца неизвестен. Если размер кольца неизвестен, то функции,отличные от констант, не могут быть вычислены никаким детерминированнымалгоритмом, завершающим вычисление по признаку окончания работы процессов.
Доказательство этого результата опирается на метод воспроизведения (правильного) вычисления алгоритма в различных частях кольца. Если же функция fравна константе (т. е., f(x) = c для каждого x), то вычисление может быть выполнено тривиальным алгоритмом, который немедленно останавливается в каждомпроцессе p и выдает результат resultp = c; отрицательный результат относитсятолько к тем функциям, которые не являются константами.Теорема 9.8. Если размер кольца заранее не известен, то не существует детерминированного алгоритма, завершающего вычисление по признаку окончания работы процессов и вычисляющего отличную от константы функцию.Д о к а з а т е л ь с т в о. Так как функция f отлична от константы, существуют такие входные данные x = (x0 , . .
. , xk−1) и y = (y0 , . . . , yl−1), что f(x) 6= f(y);например, f(x) = a и f(y) = b. Допуситим, что A — это такой детерминированныйалгоритм, завершающий вычисление по признаку окончания работы процессов,который допускает вычисление Cx на кольце с входными данными x, и при этомодин из процессов p останавливается с результатом result p = a, а также допускает вычисление Cy с входными данными y и один из процессов q останавливаетсяс результатом resultq = b.Допустим, что в ходе вычисления Cx самая длинная трасса сообщения, принятого процессом p, имеет длину K; не исключено, что K > k, поскольку A можетпередавать сообщение по кругу несколько раз, прежде чем p прекратит работу.336Гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
