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

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

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

Так как каж­дый процесс отправляет не более одного сообщения (см. описание алгоритма),заключительная конфигурация будет достигнута и в этом случае. Если в заклю­чительной конфигурации выполняется равенство resultp = true, то справедливотакже и равенство resultnextp = true, поскольку сообщение, отправленное про­цессом р будет получено процессом Nextp. Значит, если resultp = true хотя быдля одного процесса р, то и для каждого процесса р будет выполняться равенствоresultp = true, и поэтому в этом случае алгоритм завершит работу с правильнымответом для каждого процесса.Вычисление функции AND проводится аналогично, но при этом все вхожде­ния true и false следует поменять местами.□Частичная осведомленность о размере кольца.

В качестве компромиссамежду полной осведомленостью и неосведомленностью о размере кольца можнорассмотреть такую ситуацию, при которой точное значение N неизвестно, но за­то известны пределы, в которых оно заключено. Модифицировав доказательства,приведенные в настоящем параграфе, можно показать справедливость следую­щих утверждений.1. Не существует детерминированного алгоритма вычисления функции SUM,который был бы корректным для двух колец разного размера.2. Не существует детерминированного алгоритма вычисления функции XOR,который был бы корректным для колец, размер которых задается как четным,так и нечетным числом.3. Если известна верхняя оценка S размера кольца, то функции AND и ORмогут быть вычислены детерминированно с использованием N (S — 1) сообщений.Другие топологии. Метод воспроизведения можно применять и для другихклассов сетевых топологий, но при этом требуется, чтобы небольшой граф мож­но было «обернуть» несколько раз вокруг графа большего размер.

Такой типотображения одного графа в другой называется покрытием.Алгоритмы вычисления функций на анонимных сетях были построены такжеи для других топологий. Бем и Бодлаендер в работе [25] показали, что детерми­нированный сбор входных данных возможен на торе размера п х п с использо­ванием 0(п3) сообщений, а также, что величина Q(n3) является нижней оценкойсложности по числу сообщений для некоторых функций, включая AND и OR.Кранакис и Кризанц установили, что сбор входных данных возможен на я-мерном гиперкубе с использованием 0 (2 " п4) битов (см.

[ 1 2 1 ]).9.3. Вероятностный алгоритм избрания лидераЕсли размер сети известен, то можно построить частично корректный алго­ритм избрания, который завершает работу с вероятностью, равной единице, т. е.9.3. Вероятностный алгоритм избрания лидера339относится к типу Лас-Вегас. Поскольку детерминированных алгоритмов не суще­ствует (см. теорему 9.5), алгоритм типа Лас-Вегас является наилучшим возмож­ным.

Мы приведем также алгоритм проведения выборов на анонимных кольцахнеизвестного размера, предложенный Айтаи и Роде в работе [111]. В основу дан­ного алгоритма положены те же принципы, которые использовались в алгоритмеЧеня—Робертса (алгоритм 7.3), но для его применения потребуются некоторыеизменения.Поскольку в алгоритме Ченя—Робертса предполагается доступность отли­чительных признаков, всякий (анонимный) процесс р, который выступает в ролиинициатора, прежде всего выбирает отличительный признак idp случайным обра­зом из множества {1, .

. . , N}. Благодаря этому становится возможным проводитьсравнение между маркерами различных процессов, но вместе с тем возникаюти дополнительные трудности, связанные с тем, что несколько процессов могутвыбрать один и тот же отличительный признак. В алгоритме Ченя—Робертсапроцесс узнает, что он получил свой собственный маркер, если отличительныйпризнак маркера совпадает с отличительным признаком самого процесса, и этослужит достаточным условием для того, чтобы процесс стал лидером.Так как несколько процессов могут выбрать один и тот же отличительныйпризнак, встроенный в маркер счетчик передач позволяет процессам распозна­вать получение их собственных маркеров; процесс р получает свой собственныймаркер, если показатель счетчика переходов равен N.

Получение такого маркераозначает, что ни один процесс не выбрал меньший отличительный признак; ноэтого недостаточно, чтобы считаться избранным лидером, поскольку может ока­заться так, что существует еще один процесс с тем же отличительным признаком.Чтобы распознать такую ситуацию, каждый маркер снабжен булевой переменнойип, которая при генерации маркера имеет значение true и принимает значениеfalse, если маркер передается процессом с тем же отличительным признаком. Та­ким образом, процесс становится лидером, когда он получает свой собственныймаркер и при этом выполняется равенство ип = true.Последнее затруднение возникает в случае, когда процесс получает свой соб­ственный маркер, но при этом выполняется равенство ип = false ; это означает,что процесс имеет минимальный отличительный признак, но при этом существуети другой процесс с тем же отличительным признаком. Все процессы с минималь­ным отличительным признаком могут получить свой собственный маркер и стать«победителями» алгоритма Ченя—Робертса.

Если такое случится, то каждый«победитель» алгоритма Ченя—Робертса переходит в следующий тур и вновьзапускает алгоритм Ченя—Робертса. Чтобы предотвратить очередную «ничью»,каждый процесс начинает новый тур с того, что выбирает новый отличительныйпризнак. Порядковый номер тура также отражен в маркере, и маркеры того илииного уровня пресекают всякую деятельность, относящуюся к турам с меньшимпорядковым номером.Подводя итог, заметим, что получение процессом р своего собственного мар­кера приводит к тому, что он становится победителем алгоритма Ченя—Робертса,если этот процесс пребывает в состоянии cand.

Если р — единственный победи­тель, то он становится лидером; в противном случае р запускает алгоритм Че-Гл. 9. Анонимные сети340init s l e e p ;integerinit 0 ;levelpinteger;id pboolinit false ;stoppbegin if p is initiator thene p : = c a n d ; i d p := rand({l, . . . ,begin l e v e l p .— i1 ;, «s t «a t‘cpsend (tok, l e v e l p , i d p , 1, t r u e ) to N e x t pvar s t a t e P(sleep , c a n d , le a d e r , lo st)N });end;while not s t o p p dobegin receive a message ; (* это либо маркер, либо сообщение о готовности*)if it is a token (tok, l e v e l , i d , h o p s , u n ) thenif h o p s = N and s t a t e p = c a n d thenif u n then (* считается избранным *)begin s t a t e p := l e a d e r ; send (ready) to N e x t p ;receive (ready) ; s t o p ptru eendelse (* на этом уровне есть и другие победители *)begin l e v e l p := l e v e l p + 1 ; i d p := rand({l, . .

. , N }) ;send (tok, l e v e l p , i d p , 1, t r u e ) to N e x t pendelse if l e v e l > l e v e l p or ( l e v e l = l e v e l p and i d < i d p ) thenbegin l e v e l p : = l e v e l ; s t a t e p : = l o s t ;send (tok, l e v e l , i d , h o p s + 1, u n ) to N e x t pendelse if l e v e l = l e v e l p and i d = i d p thensend (tok, l e v e l , i d , h o p s + 1, f a l s e ) to N e x t pelse skip (* очистить маркер *)else begin send (ready) to N e x t p ; s t o p p : = t r u e endsndendАлгоритм 9.4. Алгоритм Айтаи—Роде избрания лидераня—Робертса в следующем туре.

Если процесс р получает маркер, порожденныйдругим процессом, то р переходит в состояние lost в том случае, когда этот мар­кер был порожден в одном из последющих туров или был порожден в том жетуре, но при этом имеет меньший отличительный признак; маркер при этом пере­дается далее по кругу. Маркер, порожденный в том же туре и несущий такой жеотличительный признак, передается, но переменной ип придается значение false.Маркер, порожденный в одном предыдущих туров, или порожденный в том жетуре, но несущий меньший отличительный признак, изымается из обращения (т. е.его передача прекращается); см. алгоритм 9.4. Далее мы покажем, что алгоритмчастично корректен и завершает работу с вероятностью, равной единице.Лемма 9.10.

Если хотя бы один процесс порождает маркер в туре I,то либо один процесс будет избран лидером в этом туре и ни один процесс9.3. Вероятностный алгоритм избрания лидера341не порождает маркера в следующем туре 1+1, либо хотя бы один процесспорождает маркер в туре I + 1 .Д о к а з а т е л ь с т в о . Процесс р порождает маркер в (/ + 1)-м туре, еслион получает свой собственный маркер (в l-м туре).Допустим, что процесс р порождает маркер в l-м туре, но отличительныйпризнак процесса не является минимальным среди отличительных признаков,которые были задействованы в l-м туре. В таком случае маркер не вернетсяк процессу р\ если этот маркер не будет устранен процессом, прошедшим в бо­лее высокий тур, он будет доставлен процессу, оперирующему в том же туреи имеющему меньший отличительный признак, где и будет устранен.

(Обращаемвнимание на то, что все процессы, которые порождают маркер в l-м туре, совер­шают это до того, как получат маркер процесса р в l-м туре.) Отсюда следует,что только тот процесс, которому достался минимальный отличительный признакв /-м туре, может быть избран в том же туре или получает право выработать мар­кер в (/ + 1 )-м туре.Допустим, что процесс р порождает маркер в l-м туре и отличительный при­знак этого процесса является минимальным среди отличительных признаков, ко­торые были задействованы в l-м туре.

Если данный маркер не будет устраненкаким-либо процессом, участвующим в более высоком туре (в таком случае хо­тя бы один процесс порождает маркер в (/ + 1 )-м туре), то этот маркер будетвозвращен процессу р. Возможны два случая: либо р является единственнымпроцессом, которому достался минимальный отличительный признак в l-м ту­ре, либо имеются еще и другие процессы, обладающие таким же отличительнымпризнаком.

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

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