Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 66
Текст из файла (страница 66)
7.4), и каждый процесс является инициатором. Маркер каждого процесса изымается из кольца процессом 0, и поэтому маркер процесса i совершаетNP−1N − i переходов; поэтому число передач сообщений будет равно(N − i) =12= N(N + 1).i=0Если речь идет о сложности по времени или о сложности по числу обменов сообщениями в худшем случае, то алгоритм Ченя —Робертса не улучшаетуказанные параметры по сравнению с алгоритмом Ле-Ланна. Зато достигаетсяулучшение в среднем, если рассматривать все возможные распределения отличительных признаков по кольцу.248Гл.
7. Алгоритмы избрания лидера7.2. Кольцевые сетиТеорема 7.6. Алгоритму Ченя—Робертса в среднем требуется всеголишь O(N log N) обменов сообщениями, когда все процессы являются инициаторами.Д о к а з а т е л ь с т в о. (В основу этого доказательства положен замыселФридмана Маттерна.)Исходя из предположения о том, что все процессы являются инициаторами,мы подсчитаем среднее число передач маркеров по всем возможным циклическимперестановкам N различных отличительных признаков. Рассмотрим некотороефиксированное множество, состоящее из N отличительных признаков, и обозначим символом s наименьший признак. Тогда существуют (N − 1)! различныхраспределений отличительных признаков по кругу; для заданного распределенияобозначим символом pi отличительный признак процесса, отстоящего от s на iшагов против хода часовой стрелки (см.
рис. 7.5).Чтобы подсчитать общее число передач маркеров для всех возможных перестановок, мы сначала подсчитаем, сколько раз для всех возможных перестановокпередается маркер htok, pi i, а затем проведем суммирование по всем i. Для каждой перестановки маркер htok, si передается N раз; значит, всего он передаетсяN(N − 1)! раз. Маркер htok, pi i передается не более i раз, поскольку он будетудален из кольца, как только достигнет s. Будем использовать запись A i,k дляобозначения числа циклических перестановок, при которых htok, p i i передаетсяiPв точности k раз. Тогда общее число передач htok, p i i равно(k · Ai,k).Получается, что для всех возможных перестановок маркер htok, p i i передаетсявсегоi−1 X11k(N − 1)! + i (N − 1)!Ai,i1= (N − 1)!.iМаркер htok, pi i передается не менее k раз (где k 6 i), если вслед за процессомpi расположены k − 1 процессов, отличительные признаки которых превосходят pi .
Очевидно, что число перестановок, в которых p i является наименьшимиз k отличительных признаков pi−k+1 , . . . , pi , составляет 1/k-ю долю всех перестановок, т. е. (1/k) (N − 1)!. И, наконец, для k < i маркер htok, pi i передаетсяв точности k раз, если он передается не менее k раз, но и не более того, т. е.передается не менее k раз, но не передается не менее k + 1 раз. Следовательно,число перестановок, для которых это происходит, равно11(N − 1)! −(N − 1)!,kk+1k(k + 1)k=1раз, а это число равноPi 1k=1ki(N − 1)!.
СуммаPi 1k=1kизвестна под названи-ем i-го гармонического числа и обозначается Hi . В качестве упражнения 7.3предлагается доказать тождествоmXi=1p1p2 uup3 uAAHHk=1Маркер htok, pi i передается в точности i раз, если pi — наименьший отличительный признак среди всех признаков от p 1 до pi , что имеет место для(1/i) · (N − 1)! перестановок; таким образом,249Hi = (m + 1)Hm − m.uHHpuN−1AAusСообщения передаютсяпо часовой стрелкеpi uРис. 7.5. Распределение отличительных признаков по кольцуДалее мы суммируем количество прохождений маркеров через процесс i, чтобы получить общее количество передач маркеров (за исключением htok, si) длявсех перестановок.
Оно равноN−1Xi=1[Hi (N − 1)!] = (NHN−1 − (N − 1)) (N − 1)!.Добавив к нему N(N − 1)! передач маркера htok, si, мы получаем суммарноеколичество передач маркеров(NHN−1 + 1) (N − 1)! = (NHN) (N − 1)!.Так как мы имеем (N − 1)! различных перестановок, среднее число передач длявсех возможных распределений, очевидно, равно NH N и может быть оцененовеличиной ≈0.69N log N (см. упражнение 7.4).7.2.2. Алгоритм Петерсона/Долева—Клейва—Родеи поэтомуAi,k =1(N − 1)!k(k + 1)(для k < i).Сложность по числу обменов сообщениями алгоритма Ченя —Робертса составляет O(N log N) в среднем, но не в наихудшем случае. Алгоритм сложности250Гл. 7. Алгоритмы избрания лидераO(N log N) в наихудшем случае был предложен Франклином в работе [90] , однако в этом алгоритме требуется, чтобы каналы были двунаправленными, а такжеДолев, Клейв и Роде (см. Петерсон [159] и [69] независимо разработали весьма похожий алгоритм решения рассматриваемой задачи для однонаправленныхколец, и в этом алгоритме в худшем случае проводится всего лишь O(N log N) обменов сообщениями.
При этом требуется, чтобы в каналах связи поддерживаласьочередность сообщений.Вначале алгоритм вычисляет наименьший отличительный признак и доводитего до сведения всех процессов; затем процесс с указанным отличительным признаком становится лидером, а все остальные процессы признают свое поражениена выборах. Суть этого алгоритма будет проще понять, если взглянуть на неготак, как будто алгоритм выполняют не сами процессы, а их отличительные признаки. Первоначально каждый отличительный признак является активным, но,как мы увидим далее, в каждом туре некоторые отличительные признаки становятся пассивными.
В каждом туре всякий активный отличительный признаксравнивается с двумя соседними активными отличительными признаками, расположенными по ходу и против хода часовой стрелки. Если этот признак будетминимальным из трех, то он переходит в следующий тур, а иначе он становитсяпассивным. Так как все отличительные признаки попарно различны, отличительные признаки, расположенные по обе стороны от локального минимума, уже небудут образовывать такой локальный минимум, и поэтому по крайней мере половина отличительных признаков не перейдет в следующий тур.
Следовательно,спустя самое большее log N туров останется только один активный отличительный признак, который и будет признан победителем.er ue e He quHHeAeAAupu Активный процессe Пассивный процессРис. 7.6. Процесс p получает текущие отличительные признаки от процессов q и r7.2. Кольцевые сети251торого тура, то первый же признак, который будет передан q в этом туре, будетравен q (т. e.
в этом случае p = q). Как только сложится такая ситуация, данныйотличительный признак становится победителем на выборах.var cip :acnp :winp :statep :P init p ;(* Текущий признак процесса p *)Pinit udef ; (* Признак активного соседа против хода часовой стрелки*)Pinit udef ; (* Признак победителя *)(active, passive, leader, lost) init active ;begin if p is initiator then statep := active else statep := passive ;while winp = udef dobegin if statep = active thenbegin send hone, cip i ; receive hone, qi ; acnp := q ;if acnp = cip then (* acnp минимальный признак *)begin send hsmall, acnp i ; winp := acnp ;receive hsmall, qiendelse (* acnp — текущий признак соседа *)begin send htwo, acnp i ; receive htwo, qi ;if acnp < cip and acnp < qthen cip := acnpelse statep := passiveendendelse(* statep = passive *)begin receive hone, qi ; send hone, qi ;receive m ; send m ;(* m — это либо htwo, qi, либо hsmall, qi *)if m — это сообщение hsmall, qi then winp := qendend;if p = winp then statep := leader else statep := lostendАлгоритм 7.7.
Алгоритм Петерсона/Долева—Клейва—РодеЭтот принцип очень просто приспособить для двунаправленных сетей, как этосделано в алгоритме Франклина; см. [90] . В ориентированных сетях сообщенияможно передавать только по часовой стрелке, и это затрудняет получение первого соседнего по ходу часовой стрелки отличительного признака, см. рис. 7.6.Отличительный признак q необходимо сравнить с r и p; но если признак r можетбыть легко передан q, то признак p вынужден был бы двигаться в направлении,противоположном ориентации каналов, чтобы достичь q. Для того чтобы сделатьвозможным проведение сравнения с обоими признаками r и p, отличительныйпризнак q передается (по направлению каналов в кольце) тому процессу, который в этот момент является хранителем признака p, а r переправляется нетолько процессу, хранящему q, но также и далее процессу, хранящему p.
Еслиq остается единственным активным отличительным признаком в начале неко-Рассмотрим алгоритм избрания лидера в однонаправленном кольце (алгоритм 7.7). Процесс p является активным в некотором туре, если в начале тураон хранит активный отличительный признак cip . В противном случае p являетсяпассивным и просто ретранслирует все сообщения, которые он получает. Всякий активный процесс отправляет свой текущий отличительный признак следующему по порядку активному процессу и получает текущий отличительныйпризнак от предшествующего активного процесса, используя сообщения типаhonei.
Полученный признак сохраняется в памяти (в качестве значения переменной acnp), и если данный признак переживет этот тур, то он станет текущимотличительным признаком процесса p в следующем туре. Чтобы оценить, переживет ли отличительный признак acnp данный тур, этот признак нужно срав-252Гл. 7. Алгоритмы избрания лидеранить как с cip , так и с активным признаком, полученным в сообщении типаhtwoi .
Процесс p отправляет сообщение htwo, acnp i, чтобы предоставить такуювозможность следующему по порядку активному процессу. Исключительнымявляется тот случай, когда выполняется равенство acn p = cip ; тогда данный отличительный признак остается единственным активным признаком и сообщениеhsmall, acnp i оповещает об этом все процессы.Теорема 7.7. Алгоритм 7.7 решает задачу о выборах для однонаправленных колец с использованием O(N log N) обменов сообщениями.Д о к а з а т е л ь с т в о. Будем говорить, что процесс участвует в i-м туре,если основной цикл этого процесса выполняется i-й раз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
