Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 89
Текст из файла (страница 89)
9. Анонимные сети9.2. Детерминированные алгоритмыРассмотрим кольцо большего размера, содержащее сегмент S из K + 1 процессов, который обладает следующим свойством. Последний процесс сегмента S(т. е. процесс, расположенный в самом дальнем конце сегмента при его обходепо направлению часовой стрелки) получает на входе точно такое же значение,что и процесс p в ходе вычисления Cx ; обозначим этот процесс символом p0 .При этом i-й по порядку сосед процесса p0 , отстоящий от него против хода часовой стрелки, получает на входе такое же значение, что и i-й по порядку соседпроцесса p, отстоящий от него против хода часовой стрелки, в вычислении C x .Соответствие между процессами сегмента S и процессами рассмотренного ранеекольца с входными данными x представлено на рис.
9.2.Алгоритм A, функционируя на кольце, содержащем сегмент S, допускает вычисление, обладающее следующим свойством. Для каждого i, не превосходящегоK, i-й по порядку сосед процесса p0 , отстоящий от него против хода часовойстрелки, отправляет все те же сообщения, имеющие трассы длины не большеK + 1 − i, которые отправлялись i-м по порядку соседом процесса p, отстоящегоот него против хода часовой стрелки, на протяжении вычисления C x . Обоснуемэто свойство при помощи нисходящей индукции.u@pq u@@x@ur@@usp s ru qq u u Huuur s uup q ueSHHupA usAAuruqup (Процесс p0)Рис. 9.2.
Построение неправильного вычисленияСлучай i = K. Отметим, что K-й по порядку сосед q процесса p0 , отстоящийот него против хода часовой стрелки, имеет то же самое начальное состояние,какое в вычислении Cx имеет K-й по порядку сосед процесса p, отстоящий отнего против хода часовой стрелки; поэтому существует вычисление, в котором qотправляет то же самое множество сообщений с трассами единичной длины.Индуктивный переход.
Предположим, что в некотором вычислении (i + 1) -йпо порядку сосед процесса p0 , отстоящий от него против хода часовой стрелки,отправляет все те же самые сообщения, трассы которых имеют длину, не превосходящую K − i, что и i-й по порядку сосед процесса p, отстоящий от него противхода часовой стрелки, в вычислении Cx . В этом вычислении i-й по порядку соседq процесса p0 , отстоящий от него против хода часовой стрелки, имеет такое женачальное состояние, какое в вычислении Cx имеет i-й по порядку сосед процесса p, отстоящий от него против хода часовой стрелки, и при этом получает то жесамое множество сообщений, трассы которых имеют длину, не превосходящуюK − i. Поэтому существует вычисление, в котором процесс q отправляет такое жемножество сообщений, трассы которых имеют длину, не превосходящую K + 1 − i,337какое в вычислении Cx отправляет i-й по порядку сосед процесса p, отстоящийот него против хода часовой стрелки.В построенном вычислении процесс p0 получает такое же множество сообщений,какое в вычислении Cx получает процесс p, и при этом p0 имеет то же самоеначальное состояние, что и p; следовательно, существует вычисление, в которомp0 завершает работу с результатом resultp0 = a.Построенное нами вычисление «вводит в заблуждение» процесс p0 , заставляяего завершать работу с результатом resultp0 = f(x), хотя на самом деле входныеданные представлены более протяженной последовательностью x 0 , отличной отx.
Вычисление привело бы к правильному ответу, если бы имело место равенство f(x0) = f(x). Чтобы выявить противоречие, рассмотрим кольцо, содержащеесегмент, процессы которого моделируют вычисление C y , а процесс q0 при этомзавершает вычисление с результатом resultq0 = b. Для такого кольца существуетвычисление, в котором два процесса завершают работу с разными значениямиresult; и это является противоречием, ибо самое большее один из них можетбыть правильным.Теорема 9.9.
Функции OR и AND вычислимы детерминированным алгоритмом, завершающим вычисление по признаку окончания обмена сообщениями, с использованием не более N сообщений в случае, когда размеркольца заранее неизвестен.Д о к а з а т е л ь с т в о. Значение функции OR равно true, если на вход хотя бы одного процесса подается true; значение этой функции равно false, еслина вход всех процессов подается false. При инициализации процесс p выполняет присваивание resultp := xp и в том случае, когда xp равно true, отправляетсообщение hyesi своему соседу по ходу часовой стрелки. Когда такое сообщение поступает процессу p, то оно игнорируется, если result p имеет значение true;в противном случае resultp полагается равным true, а само сообщение отправляется далее по часовой стрелке (см.
алгоритм 9.3).var resultpxp: bool;: bool;(* Результат вычисления *)(* Входные данные процесса p *)begin resultp := xp ;if xp is true then send hyesi to Nextp ;receive hyesi ;if resultp is false thenbegin resultp := true ; send hyesi to Nextp endendАлгоритм 9.3. Детерминированное вычисление функции ORРассмотрим вначале случай, когда на вход каждого процесса подается false.Каждый процесс p присваивает переменной result p значение false и начинаетожидать поступления сообщения. Коль скоро ни один процесс не отправляет никакого сообщения, конфигурация, в которой все процессы ожидают поступления338Гл.
9. Анонимные сетисообщения, является заключительной, и, помимо того, в этом случае значениемпеременной resultp является правильный ответ false.Теперь рассмотрим случай, когда есть процесс, на вход которого подаетсяtrue. Процесс p, на вход которого поступает true, присваивает переменной result pзначение true и отправляет следующему процессу сообщение hyesi. Так как каждый процесс отправляет не более одного сообщения (см. описание алгоритма),заключительная конфигурация будет достигнута и в этом случае. Если в заключительной конфигурации выполняется равенство result p = true, то справедливотакже и равенство resultNextp = true, поскольку сообщение, отправленное процессом p будет получено процессом Nextp .
Значит, если resultp = true хотя быдля одного процесса p, то и для каждого процесса p будет выполняться равенствоresultp = true, и поэтому в этом случае алгоритм завершит работу с правильнымответом для каждого процесса.Вычисление функции AND проводится аналогично, но при этом все вхождения true и false следует поменять местами.Частичная осведомленность о размере кольца. В качестве компромиссамежду полной осведомленостью и неосведомленностью о размере кольца можнорассмотреть такую ситуацию, при которой точное значение N неизвестно, но зато известны пределы, в которых оно заключено. Модифицировав доказательства,приведенные в настоящем параграфе, можно показать справедливость следующих утверждений.1.
Не существует детерминированного алгоритма вычисления функции SUM,который был бы корректным для двух колец разного размера.2. Не существует детерминированного алгоритма вычисления функции XOR,который был бы корректным для колец, размер которых задается как четным,так и нечетным числом.3. Если известна верхняя оценка S размера кольца, то функции AND и ORмогут быть вычислены детерминированно с использованием N(S − 1) сообщений.Другие топологии.
Метод воспроизведения можно применять и для другихклассов сетевых топологий, но при этом требуется, чтобы небольшой граф можно было «обернуть» несколько раз вокруг графа большего размер. Такой типотображения одного графа в другой называется покрытием.Алгоритмы вычисления функций на анонимных сетях были построены такжеи для других топологий. Бем и Бодлаендер в работе [25] показали, что детерминированный сбор входных данных возможен на торе размера n × n с использованием O(n3) сообщений, а также, что величина Ω (n3) является нижней оценкойсложности по числу сообщений для некоторых функций, включая AND и OR.Кранакис и Кризанц установили, что сбор входных данных возможен на n-мерном гиперкубе с использованием O(2n n4) битов (см. [121]).9.3.
Вероятностный алгоритм избрания лидераЕсли размер сети известен, то можно построить частично корректный алгоритм избрания, который завершает работу с вероятностью, равной единице, т. е.9.3. Вероятностный алгоритм избрания лидера339относится к типу Лас-Вегас. Поскольку детерминированных алгоритмов не существует (см. теорему 9.5), алгоритм типа Лас-Вегас является наилучшим возможным. Мы приведем также алгоритм проведения выборов на анонимных кольцахнеизвестного размера, предложенный Айтаи и Роде в работе [111] . В основу данного алгоритма положены те же принципы, которые использовались в алгоритмеЧеня—Робертса (алгоритм 7.3), но для его применения потребуются некоторыеизменения.Поскольку в алгоритме Ченя—Робертса предполагается доступность отличительных признаков, всякий (анонимный) процесс p, который выступает в ролиинициатора, прежде всего выбирает отличительный признак id p случайным образом из множества {1, .
. . , N}. Благодаря этому становится возможным проводитьсравнение между маркерами различных процессов, но вместе с тем возникаюти дополнительные трудности, связанные с тем, что несколько процессов могутвыбрать один и тот же отличительный признак. В алгоритме Ченя —Робертсапроцесс узнает, что он получил свой собственный маркер, если отличительныйпризнак маркера совпадает с отличительным признаком самого процесса, и этослужит достаточным условием для того, чтобы процесс стал лидером.Так как несколько процессов могут выбрать один и тот же отличительныйпризнак, встроенный в маркер счетчик передач позволяет процессам распознавать получение их собственных маркеров; процесс p получает свой собственныймаркер, если показатель счетчика переходов равен N.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
