Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 65
Текст из файла (страница 65)
Инициаторр, для которого р > ро, не будет избран лидером; р0 не передаст далее маркер (tok, р), и поэтому р никогда не получит свой собственный маркер. Такойинициатор р перейдет в состояние /os/самое позднее в тот момент, когда будетпередавать далее (tok, ро). Это и служит обоснованием того, что наш алгоритмрешает задачу о выборах.N—1ОСообщения передаютсяпо часовой стрелкеРис.
7.4. Наихудший возможный сценарий для алгоритма Ченя—РобертсаВ алгоритме задействовано не более N различных маркеров, и каждый маркер передается не более N раз; этим и обосновывается оценка 0(N 2) сложности по числу обменов сообщениями. Чтобы убедиться в том, что иногда может понадобиться передать Q(/V2) сообщений, рассмотрим начальную конфигурацию, в которой отличительные признаки расположены в кольце по возрастанию(см. рис. 7.4), и каждый процесс является инициатором. Маркер каждого процесса изымается из кольца процессом 0 , и поэтому маркер процесса i совершаетN- 1N — i переходов; поэтому число передач сообщений будет равно= \ N ( N + 1).(N — i) =!~°□Если речь идет о сложности по времени или о сложности по числу обменов сообщениями в худшем случае, то алгоритм Ченя—Робертса не улучшаетуказанные параметры по сравнению с алгоритмом Ле-Ланна. Зато достигаетсяулучшение в среднем, если рассматривать все возможные распределения отличительных признаков по кольцу.248Гл.
7. Алгоритмы избрания лидераТеорема 7.6. Алгоритму Ченя—Робертса в среднем требуется всего0 { N log N) обменов сообщениями, когда все процессы являются инилишьциаторами.Д о к а з а т е л ь с т в о . (В основу этого доказательства положен замыселФридмана Маттерна.)Исходя из предположения о том, что все процессы являются инициаторами,мы подсчитаем среднее число передач маркеров по всем возможным циклическимперестановкам N различных отличительных признаков. Рассмотрим некотороефиксированное множество, состоящее из N отличительных признаков, и обозначим символом s наименьший признак. Тогда существуют (N — 1)! различныхраспределений отличительных признаков по кругу; для заданного распределенияобозначим символом pi отличительный признак процесса, отстоящего от s на /шагов п р о т и в хода часовой стрелки (см.
рис. 7.5).Чтобы подсчитать общее число передач маркеров для всех возможных перестановок, мы сначала подсчитаем, сколько раз для всех возможных перестановокпередается маркер (tok, pi), а затем проведем суммирование по всем /. Для каждой перестановки маркер (tok, s) передается N раз; значит, всего он передаетсяN(N - 1)! раз. Маркер (tok, р ) передается не более i раз, поскольку он будетудален из кольца, как только достигнет s.
Будем использовать записьдляобозначения числа циклических перестановок, при которых (tok, pi) передаетсяiв точности k раз. Тогда общее число передач (tok, р ) равно £)(& ■Aik).k=\Маркер (tok, pi) передается в точности / раз, если pt — наименьший отличительный признак среди всех признаков от р\ до pt, что имеет место для(1/г) • ( N - 1)! перестановок; таким образом,Ац =4 (tV —1)!.Маркер (tok, р ) передается не менее k раз (где k Д г), если вслед за процессомPi расположены k — 1 процессов, отличительные признаки которых превосходят p i . Очевидно, что число перестановок, в которых p i является наименьшимиз k отличительных признаков pi-k+i, • • • , P i, составляет l / k -ю долю всех перестановок, т.
е. (1 /k)(N - 1)!. И, наконец, для k < i маркер (tok, р ) передаетсяв точности k раз, если он передается не менее k раз, но и не более того, т. е.передается не менее k раз, но не передается не менее k + 1 раз. Следовательно,число перестановок, для которых это происходит, равнои поэтому1Ai,k =k(k + l)(N -1)!(для k <i).7.2. Кольцевые сети249Получается, что для всех возможных перестановок маркер (tok, р{) передаетсявсегоg(sTFTTTT^ - 1)!) +4*" - 1)!- !)•• Сумма ( J2 г ) известна под названи-раз, а это число равно (ем /-го гармонического числа и обозначается Н,.
В качестве упражнения 7.3предлагается доказать тождествот= {т + 1)Нт - т.i= 1Р1SСообщения передаютсяпо часовой стрелкеРис. 7.5. Распределение отличительных признаков по кольцуДалее мы суммируем количество прохождений маркеров через процесс г, чтобы получить общее количество передач маркеров (за исключением (tok, s)) длявсех перестановок.
Оно равноN- 1£[Hi(tv - 1)!] = (tVHjv- 1 - ( N - 1))(N - 1)!.г=1Добавив к нему N(N — 1)! передач маркера (tok, s), мы получаем суммарноеколичество передач маркеров(jVH/v- i + 1)(N - 1)! = (NHn)(N - 1)!.Так как мы имеем (N — 1)! различных перестановок, среднее число передач длявсех возможных распределений, очевидно, равно N Нд/ и может быть оцененовеличиной «0.69jVlogjV (см. упражнение 7.4).□7.2.2. Алгоритм Петерсона/Долева—Клейва—РодеСложность по числу обменов сообщениями алгоритма Ченя—Робертса составляет 0 (N log N) в среднем, но не в наихудшем случае. Алгоритм сложности250Гл.
7. Алгоритмы избрания лидера0(N log N) в наихудшем случае был предложен Франклином в работе [90], однако в этом алгоритме требуется, чтобы каналы были двунаправленными, а такжеДол ев, Клейв и Роде (см. Петерсон [159] и [69] независимо разработали весьма похожий алгоритм решения рассматриваемой задачи для однонаправленныхколец, и в этом алгоритме в худшем случае проводится всего лишь 0 (N log N) обменов сообщениями. При этом требуется, чтобы в каналах связи поддерживаласьочередность сообщений.Вначале алгоритм вычисляет наименьший отличительный признак и доводитего до сведения всех процессов; затем процесс с указанным отличительным признаком становится лидером, а все остальные процессы признают свое поражениена выборах.
Суть этого алгоритма будет проще понять, если взглянуть на неготак, как будто алгоритм выполняют не сами процессы, а их отличительные признаки. Первоначально каждый отличительный признак является активным , но,как мы увидим далее, в каждом туре некоторые отличительные признаки становятся пассивными. В каждом туре всякий активный отличительный признаксравнивается с двумя соседними активными отличительными признаками, расположенными по ходу и против хода часовой стрелки. Если этот признак будетминимальным из трех, то он переходит в следующий тур, а иначе он становитсяпассивным. Так как все отличительные признаки попарно различны, отличительные признаки, расположенные по обе стороны от локального минимума, уже небудут образовывать такой локальный минимум, и поэтому по крайней мере половина отличительных признаков не перейдет в следующий тур. Следовательно,спустя самое большее log jV туров останется только один активный отличительный признак, который и будет признан победителем.гЯф Активный процессОПассивный процессШРРис.
7.6. Процесс р получает текущие отличительные признаки от процессов q и гЭтот принцип очень просто приспособить для двунаправленных сетей, как этосделано в алгоритме Франклина; см. [90]. В ориентированных сетях сообщенияможно передавать только по часовой стрелке, и это затрудняет получение первого соседнего по ходу часовой стрелки отличительного признака, см. рис.
7.6.Отличительный признак q необходимо сравнить с г и р\ но если признак г можетбыть легко передан q, то признак р вынужден был бы двигаться в направлении,противоположном ориентации каналов, чтобы достичь q. Для того чтобы сделатьвозможным проведение сравнения с обоими признаками г и р, отличительныйпризнак q передается (по направлению каналов в кольце) тому процессу, который в этот момент является хранителем признака р, а г переправляется нетолько процессу, хранящему q, но также и далее процессу, хранящему р.
Еслиq остается единственным активным отличительным признаком в начале неко7.2. Кольцевые сети251торого тура, то первый же признак, который будет передан q в этом туре, будетравен q (т. е. в этом случае р = q). Как только сложится такая ситуация, данныйотличительный признак становится победителем на выборах.var tip:V init р ;асПр :V init udef ;wirip :V init udef ;statep : (active, passive ,(* Текущий признак процесса р *)(* Признак активного соседа против хода часовой стрелки*)(* Признак победителя *)leader, lost) init active ;begin if p is initiator then statep := active else statep := passive ;while wirip = udef dobegin if statep = active thenbegin send (one, cip) ; receive (one, q) ; acnp := q ;if acrip = t i p then (* acnp минимальный признак *)begin send (small, acnp) ; winp := acnp ;receive (small, q)endelse (* acrip — текущий признак соседа *)begin send (two, acnp) ; receive (two, q) ;if actip < tip and acnp < qthen tip := acripelse statep := passiveendendelse(* statep = passive *)begin receive (one, q) ; send (one, q) ;receive m ; send m ;(* m — это либо (two, q), либо (small, q) *)if m — это сообщение (small, q) then winp := qendend;if p = wirip then statep := leader else statep := lostendАлгоритм 7.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
