Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 88

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 88)

После окончания коммуникационнойфазы каждый процесс вычисляет локально значение функции и завершает своюработу.□Теорема 9.7. В с я к и й д е т е р м и н и р о в а н н ы й а л г о р и т м , з а в е р ш а ю щ и й в ы ­числение ф ун кц и й A N D , O R или SU M по п р и зн а к у о к о н ч а н и я работ ы п р о ­ц е с с о в , и с п о л ь з у е т N ( N - 1) с о о б щ е н и й в х у д ш е м с л у ч а е .Д о к а з а т е л ь с т в о .

Рассмотрим детерминированный алгоритм А , завер­шающий вычисление по признаку окончания работы процессов и решающий однуиз указанных задач. Определим т р а с с у сообщений, подобно тому как это былосделано в определении и §7.2.3. Если процесс р отправляет сообщение передтем, как впервые осуществить прием какого-либо сообщения, то для обозна­чения трассы этого сообщения будем использовать запись {р). Если процесс ротправляет сообщение т в тот момент, когда самая длинная трасса полученногоим ранее сообщения равна ( р \, . . . , pk), то трассой сообщения т будет записьi pьPk, Р).Все три задачи, упомянутые в формулировке теоремы, имеют одно общее ка­чество: хотя бы для одной симметрической начальной конфигурации какой-либоиз процессов, до того как он прекратит работу, должен получить сообщение, трас­са которого имеет длину N —\.

Для задачи SUM это справедливо применительнок любой начальной конфигурации. Для задачи AND это будет иметь место, когдакаждый процесс получает на входе значение tr u e , а для задачи OR — когда каж­дый процесс получает на входе значение f a l s e . Чтобы убедиться, что сообщение,имеющее трассу длины N — 1 , обязательно будет принято, рассмотрим вычислениеAND в случае, когда каждый процесс получает на входе значение t r u e ’, в такомслучае будет вычислен ответ tr u e .

Допустим, что некоторый процесс завершает9.2. Детерминированные алгоритмы335работу, вычислив результат tr u e , в то время, когда самая длинная трасса полу­ченного этим процессом сообщения имеет длину k < N — 1. То событие, котороесовершается в момент прекращения работы этого процесса, зависит только отсобытий, которые произошли в каких-либо k + 1 процессах, и, следовательно,оно произойдет и в ходе вычисления, в начальной конфигурации которого ука­занные k + 1 процессов получили на входе значение tr u e , а остальные — fa l s e .Как и прежде, назовем конфигурацию симметрической, если все процессыпребывают в одном и том же состоянии и в каждом канале содержится одно и тоже множество сообщений.

Точно так же, как и при доказательстве теоремы 9.5,строится вычисление, в котором симметрическая конфигурация образуется черезкаждые N шагов и в ходе которого в каждом процессе происходит одно и то жемножество событий. Начальная конфигурация может быть выбрана таким обра­зом, чтобы в ходе работы алгоритма было отправлено хотя бы одно сообщение,трасса которого имеет длину N — 1. В ходе такого вычисления для каждого на­турального i, i ^ jV — 1 , будет отправлено сообщение, трасса которого имеетдлину г.

Но коль скоро в каждом процессе осуществляется одно и то же множе­ство событий, общее число сообщений, трасса которых имеет длину г, кратно N ,а значит, не может быть меньше N . Следовательно, суммарное число сообщенийне может быть меньше N ( N — 1).□Размер кольца неизвестен.

Если размер кольца неизвестен, то функции,отличные от констант, не могут быть вычислены никаким детерминированнымалгоритмом, завершающим вычисление по признаку окончания работы процес­сов. Доказательство этого результата опирается на метод воспроизведения (пра­вильного) вычисления алгоритма в различных частях кольца. Если же функция /равна константе (т. е., f ( x ) = с для каждого х ), то вычисление может быть выпол­нено тривиальным алгоритмом, который немедленно останавливается в каждомпроцессе р и выдает результат r e s u l t р = с; отрицательный результат относитсятолько к тем функциям, которые не являются константами.Теорема 9.8.

Е с л и р а з м е р к о л ь ц а з а р а н е е н е и з в е с т е н , т о н е с у щ е с т в у ­ет дет ерм инированн ого алгорит м а, заверш аю щ его вы числение по п р и ­зн а к у о к о н ч а н и я раб от ы процессов и вы числяю щ его о т ли ч н ую о т к о н ­ст ант ы ф ункцию .Д о к а з а т е л ь с т в о . Так как функция / отлична от константы, существу­ют такие входные данные х = (хо, .

. . , x*_i) и у = (у 0 , . . . , yi-\), что /(х) ^ f(y);например, /(х) = а и f(y) = b. Допуситим, что А — это такой детерминированныйалгоритм, завершающий вычисление по признаку окончания работы процессов,который допускает вычисление С х на кольце с входными данными х, и при этомодин из процессов р останавливается с результатом r e s u l t р = а, а также допуска­ет вычисление С у с входными данными у и один из процессов q останавливаетсяс результатом r e s u l t q = b.Допустим, что в ходе вычисления С х самая длинная трасса сообщения, при­нятого процессом р , имеет длину К', не исключено, что К > k , поскольку А можетпередавать сообщение по кругу несколько раз, прежде чем р прекратит работу.336Гл.

9. Анонимные сетиРассмотрим кольцо большего размера, содержащее сегмент S из К + 1 процес­сов, который обладает следующим свойством. Последний процесс сегмента S(т. е. процесс, расположенный в самом дальнем конце сегмента при его обходепо направлению часовой стрелки) получает на входе точно такое же значение,что и процесс р в ходе вычисления Сх; обозначим этот процесс символом р '.При этом /-й по порядку сосед процесса р \ отстоящий от него против хода ча­совой стрелки, получает на входе такое же значение, что и / - й по порядку соседпроцесса р , отстоящий от него против хода часовой стрелки, в вычислении Сх.Соответствие между процессами сегмента S и процессами рассмотренного ранеекольца с входными данными х представлено на рис.

9.2.Алгоритм А, функционируя на кольце, содержащем сегмент S, допускает вы­числение, обладающее следующим свойством. Для каждого /, не превосходящегоК, г-й по порядку сосед процесса р \ отстоящий от него против хода часовойстрелки, отправляет все те же сообщения, имеющие трассы длины не большеК+ 1 —г, которые отправлялись г'-м по порядку соседом процесса р, отстоящегоот него против хода часовой стрелки, на протяжении вычисления Сх.

Обоснуемэто свойство при помощи нисходящей индукции.Рис. 9.2. Построение неправильного вычисленияСлучай i = К. Отметим, что К-й по порядку сосед q процесса /У, отстоящийот него против хода часовой стрелки, имеет то же самое начальное состояние,какое в вычислении Сх имеет К- й по порядку сосед процесса р , отстоящий отнего против хода часовой стрелки; поэтому существует вычисление, в котором qотправляет то же самое множество сообщений с трассами единичной длины.Индуктивный переход.

Предположим, что в некотором вычислении (/+ 1)-йпо порядку сосед процесса р1, отстоящий от него против хода часовой стрелки,отправляет все те же самые сообщения, трассы которых имеют длину, не превос­ходящую /С —/, что и /- й по порядку сосед процесса р, отстоящий от него противхода часовой стрелки, в вычислении Сх.

В этом вычислении г-й по порядку соседq процесса р ' , отстоящий от него против хода часовой стрелки, имеет такое женачальное состояние, какое в вычислении Сх имеет г-й по порядку сосед процес­са р, отстоящий от него против хода часовой стрелки, и при этом получает то жесамое множество сообщений, трассы которых имеют длину, не превосходящуюК —г. Поэтому существует вычисление, в котором процесс q отправляет такое жемножество сообщений, трассы которых имеют длину, не превосходящую К+ 1 —г,9.2.

Детерминированные алгоритмы337какое в вычислении Сх отправляет г-й по порядку сосед процесса р, отстоящийот него против хода часовой стрелки.В построенном вычислении процесс р' получает такое же множество сообщений,какое в вычислении Сх получает процесс р, и при этом р' имеет то же самоеначальное состояние, что и р\ следовательно, существует вычисление, в которомр' завершает работу с результатом resultpi = а.Построенное нами вычисление «вводит в заблуждение» процесс р', заставляяего завершать работу с результатом resultр>= f(x), хотя на самом деле входныеданные представлены более протяженной последовательностью х ' , отличной отх.

Вычисление привело бы к правильному ответу, если бы имело место равен­ство f(x') = f(x). Чтобы выявить противоречие, рассмотрим кольцо, содержащеесегмент, процессы которого моделируют вычисление Су, а процесс q' при этомзавершает вычисление с результатом resultq>= b. Для такого кольца существуетвычисление, в котором два процесса завершают работу с разными значениямиresult', и это является противоречием, ибо самое большее один из них можетбыть правильным.□Теорема 9.9. Функции OR и AND вычислимы детерминированным ал­горитмом, завершающим вычисление по признаку окончания обмена со­общениями, с использованием не более N сообщений в случае, когда размеркольца заранее неизвестен.Д о к а з а т е л ь с т в о .

Значение функции OR равно true, если на вход хо­тя бы одного процесса подается true', значение этой функции равно false, еслина вход всех процессов подается false. При инициализации процесс р выполня­ет присваивание resultp := хр и в том случае, когда хр равно true, отправляетсообщение (yes) своему соседу по ходу часовой стрелки. Когда такое сообще­ние поступает процессу р, то оно игнорируется, если resultр имеет значение true',в противном случае resultр полагается равным true, а само сообщение отправ­ляется далее по часовой стрелке (см. алгоритм 9.3).varresultpхрb egin: bool;: bool;(* Результат вычисления *)(* Входные данные процесса р *)resultp := хр ;хр is true th en send (yes) to Nextp ;receive (yes) ;if resultp is false th enb egin resultp := true ; send (yes) to NextpifendendАлгоритм9.3.

Детерминированное вычисление функции ORРассмотрим вначале случай, когда на вход каждого процесса подается false.Каждый процесс р присваивает переменной resultp значение false и начинаетожидать поступления сообщения. Коль скоро ни один процесс не отправляет ни­какого сообщения, конфигурация, в которой все процессы ожидают поступления338Гл. 9. Анонимные сетисообщения, является заключительной, и, помимо того, в этом случае значениемпеременной resultp является правильный ответ false.Теперь рассмотрим случай, когда есть процесс, на вход которого подаетсяtrue. Процесс р, на вход которого поступает true, присваивает переменной resultpзначение true и отправляет следующему процессу сообщение (yes).

Характеристики

Список файлов книги