Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 64
Текст из файла (страница 64)
алгоритм 7.1).Теорема 7.2. Алгоритм 7.1 решает задачу о выборах на древесных сетях с использованием 0(N ) обменов сообщениями, затрачивая при этом0(D) единиц времени.Д о к а з а т е л ь с т в о . Когда хоть один процесс запускает данный алгоритм, все процессы отправляют сообщение (wakeup) всем своим соседям, икаждый процесс запускает выполнение древесного алгоритма после получениясообщения (wakeup) от каждого соседа. Все процессы завершают выполнениедревесного алгоритма с одним и тем же значением переменной и, а именно снаименьшим отличительным признаком среди всех процессов.
И (единственный)процесс с таким признаком завершит работу в состоянии leader, а все прочиепроцессы — в состоянии lost.По каждому каналу передаются два сообщения (wakeup) и два сообщения(tok, г), и поэтому сложность по числу обменов сообщениями становится равной 4yV — 4. По истечении D единиц времени, после того как первый процессзапустил наш алгоритм, каждый процесс уже отправит сообщения (wakeup), и,следовательно, спустя D + 1 единиц времени каждый процесс уже запустит волну. И в самом деле, нетрудно увидеть, что первое решение будет принято спустяD единиц времени после начала движения волны, а последнее решение будетпринято спустя D единиц времени после первого, и поэтому общее затраченноевремя становится равным 3D+1. Более подробный анализ позволяет обнаружить,что алгоритм всегда завершается спустя 2D единиц времени, но это оставленочитателю в качестве упражнения (см.
упражнение 7.2).□Если сообщения в канале могут быть переупорядочены (т. е. канал не является очередью), то процесс может получить сообщение (tok, г) от соседа, преждечем он получит сообщение (wakeup) от того же соседа. В таком случае сообщение (tok, г) можно временно сохранить или обработать, подобно тому как этоделается для более поздних сообщений (tok, г).Число обменов сообщениями можно сократить, воспользовавшись двумя модификациями. Во-первых, можно сделать так, чтобы неинициатор не отправлялсообщение (wakeup) тому процессу, от которого он получил первое сообщение(wakeup).
Во-вторых, сообщение (wakeup), отправляемое из листового узла,можно сочетать с сообщением (tok, г), отправляемым из того же листового узла.При помощи этих улучшений число обменов сообщениями, которые требуются244Гл. 7. Алгоритмы избрания лидеранашему алгоритму, можно сократить до 3jV —4 + k, где k обозначает число нелистовых вершин-стартеров; см. [187, р.
139].Избрание посредством фазового алгоритма. Фазовый алгоритм можно приспособить для выборов, позволив ему вычислять наименьший отличительныйпризнак по ходу одной волны, как указано в теореме 6 . 1 2 .Теорема 7.3. При помощи фазового алгоритма (алгоритм 6 .6) выборыможно провести в произвольных сетях, используя 0(D\E\) обменов сообщениями и затрачивая 0(D) единиц времени.В основу алгоритма Пелега (см. [158]) положен фазовый алгоритм; ему требуется 0(D\E\) обменов сообщениями и 0(D) единиц времени, но знание D длянего не нужно, так как в нем предусмотрено вычисление диаметра в режиме online.Избрание посредством алгоритма Финна. Алгоритму Финна (алгоритм 6 .8)не требуется предварительных сведений о диаметре сети.
В алгоритме Финнапроводится 0 (/V|£|) обменов сообщениями, но сами сообщения гораздо длиннеетого, что позволяют нам допущения, сделанные в этой главе. Поэтому каждоесообщение в алгоритме Финна следует рассматривать как 0(N) сообщений; такимобразом, сложность по числу обменов сообщениями становится равной 0(N 2\E\).7.2. Кольцевые сетиВ этом параграфе рассматриваются некоторые алгоритмы избрания для неориентированных колец. Задача о выборах применительно к кольцевым сетям былавпервые поставлена Ле-Ланном в работе [131], ему же удалось найти ее решениесо сложностью 0(N2) по числу обменов сообщениями. Это решение было улучшено Ченем и Робертсом (см.
[40]); они предложили алгоритм, который имеетсложность 0(N2) в наихудшем случае, но зато его сложность в среднем составляет всего лишь O(AMogiV). Решения Ле-Ланна и решения Ченя—Робертса обсуждаются в §7.2.1. Вопрос о существовании алгоритма со сложностью O(AMogA)в наихудшем случае оставался открытым до 1980 г., когда такой алгоритм былпредложен Хиршбергом и Синклейром в работе [105]. В отличие от более ранних решений, в алгоритме Хиршберга—Синклейра требуется, чтобы каналы былидвунаправленными. Какое-то время предполагалось, что El(N2) обменов сообщениями составляют нижнюю оценку для однонаправленных колец, но Петерсон,а также Долев, Клейв и Роде (см. [159] и [69]) независимо предложили решениесложности 0(N\ogN) для однонаправленного кольца. Их решение исследуетсяв §7.2.2.Почти в то же самое время указанные алгоритмы были дополнены согласованными нижними оценками.
Нижняя оценка «0.34AMogjV сложности по числу обменов сообщениями в наихудшем случае для двунаправленных колец былаобоснована Бодлаендэром; см. [31]. Пачль, Корач и Ротем в работе [156] доказали нижнюю оценку El(N log N) сложности в среднем как для двунаправленных,2457.2. Кольцевые сетитак и для однонаправленных колец. Эти результаты о нижних оценках будут изучены в § 7.2.3.7.2.1. Алгоритмы Ле-Ланна и Ченя— РобертсаВ алгоритме Ле-Ланна (см.
[131]) каждый инициатор вычисляет список отличительных признаков всех инициаторов, после чего лидером избирается инициатор с наименьшим признаком. Каждый инициатор отправляет по кольцу маркер,в который вложен отличительный признак инициатора, и все процессы передаютдалее этот маркер. Предполагается, что в каналах соблюдается очередность сообщений и всякий инициатор должен создать свой маркер, прежде чем получитмаркер от всякого другого инициатора. (Как только процесс получает маркер, онуже не может впоследствии инициировать выполнение алгоритма.) Когда инициатор р получает свой собственный маркер обратно, маркеры всех инициаторовуже прошли через р, и р будет избран лидером в том и только том случае, еслир — наименьший процесс среди всех инициаторов (см. алгоритм 7.2).: подмножество Vvar L is t ps ta te pinit{p) ;;begin if p is initiator thenbegin s t a t e p := c a n d ; send (tok, p ) to N e x t p ; receive (tok,while q A p dobegin L is t p := L is t p U {<7} ;send (tok, q ) to N e x t p ; receive (tok, q )end;if p = min( L is t p ) then s t a t e p := le a d e relse s t a t e p := l o s tendelse while t r u e dobegin receive (tok, q ) ; send (tok, q ) to N e x t p ;if s t a t e p = s le e p then s t a t e p := l o s tendendq);Алгоритм 7.2.
Алгоритм Ле-Ланна избрания лидераТеорема 7.4. Алгоритм Ле-Ланна (алгоритм 7.2) решает задачу о выборах на кольцах с использованием 0(N 2) обменов сообщениями за 0(N)единиц времени.Д о к а з а т е л ь с т в о . Так как порядок следования маркеров по кольцуостается неизменным (вследствие допущения очередности в каналах) и инициаторq отправляет (tok, q) ранее, нежели q получает (tok, р), инициатор р получает(tok, q), до того как р получит (tok, р) обратно.
Отсюда следует, что каждыйинициатор р завершает работу со списком Listp, представляющим множество246Гл. 7. Алгоритмы избрания лидеравсех инициаторов, и инициатор с наименьшим отличительным признаком становится единственным процессом, избранным на роль лидера. Всего оказываютсязадействованными не более N различных маркеров, и каждый из них совершает N шагов, что приводит к сложности 0(N 2) по числу обменов сообщениями.Спустя самое позднее N — 1 единиц времени, после того как первый инициаторотправил свой маркер, каждый инициатор проделает то же самое. При этом каждый инициатор получит свой маркер обратно в течение N единиц времени послесоздания этого маркера. Значит, наш алгоритм завершит работу не позднее, чемспустя 2N — 1 единиц времени.□Все неинициаторы переходят в состояние lost, но будут пребывать сколь угодно долго в ожидании сообщений (tok, г).
Ожидание можно прервать, если заставить лидера отправить специальный маркер по кольцу для оповещения о том,что выборы завершены.Алгоритм Ченя—Робертса [40] улучшает алгоритм Ле-Ланна за счет того,что из кольца изымаются все маркеры тех процессов, относительно которых ужестановится ясно, что они проиграют выборы. А именно, инициатор р изымаетмаркер (tok, q) из кольца, если q > р. Инициатор р обретает статус lost, едвалишь получает маркер с отличительным признаком q < р, и статус leader, кактолько получает маркер с отличительным признаком р (см.
алгоритм 7.3).var statep ;begin if p is initiator thenbegin stateP := cand ; send (tok, p) to nextp ;while statep Ф leader dobegin receive (tok, q) ;if q = p then statep := leaderelse if q < p thenbegin if statep = cand then statep := lo st ;send (tok, q) to nextpendendendelse while true dobegin receive (tok, q) ; send (tok, q) to nextp ;if statep = sleep then statep := lostendend(* Только лидер завершает выполнение программы. Он отправляетсообщение всем процессам, информируя их об отличительных признакахлидера и о завершении выборов *)Алгоритм 7.3.
Алгоритм Ченя—Робертса избрания лидера2477.2. Кольцевые сетиТеорема 7.5. Алгоритм Ченя—Робертса (алгоритм 7.3) решает задачуо выборах для колец, используя в худшем случае Q(N2) обменов сообщениями за 0(N) единиц времени.Д о к а з а т е л ь с т в о . Обозначим символом ро инициатор с наименьшимотличительным признаком. Всякий другой процесс может быть либо неинициатором, либо инициатором с отличительным признаком, превышающим ро, и поэтому все процессы передадут далее маркер (tok, р0), выпущенный ро. Значит,ро получит свой маркер обратно и будет избран лидером.Неинициаторы не будут избраны, но все они перейдут в состояние lost самоепозднее к моменту передачи маркера, который выпустил процесс ро.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
