Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 65
Текст из файла (страница 65)
упражнение 7.2).Если сообщения в канале могут быть переупорядочены (т. е. канал не является очередью), то процесс может получить сообщение htok, ri от соседа, преждечем он получит сообщение hwakeupi от того же соседа. В таком случае сообщение htok, ri можно временно сохранить или обработать, подобно тому как этоделается для более поздних сообщений htok, ri.Число обменов сообщениями можно сократить, воспользовавшись двумя модификациями. Во-первых, можно сделать так, чтобы неинициатор не отправлялсообщение hwakeupi тому процессу, от которого он получил первое сообщениеhwakeupi. Во-вторых, сообщение hwakeupi, отправляемое из листового узла,можно сочетать с сообщением htok, ri, отправляемым из того же листового узла.При помощи этих улучшений число обменов сообщениями, которые требуются244Гл.
7. Алгоритмы избрания лидера7.2. Кольцевые сети245нашему алгоритму, можно сократить до 3N − 4 + k, где k обозначает число нелистовых вершин-стартеров; см. [187, p. 139] .так и для однонаправленных колец. Эти результаты о нижних оценках будут изучены в § 7.2.3.Избрание посредством фазового алгоритма. Фазовый алгоритм можно приспособить для выборов, позволив ему вычислять наименьший отличительныйпризнак по ходу одной волны, как указано в теореме 6.12.7.2.1. Алгоритмы Ле-Ланна и Ченя—РобертсаТеорема 7.3. При помощи фазового алгоритма (алгоритм 6.6) выборыможно провести в произвольных сетях, используя O(D|E|) обменов сообщениями и затрачивая O(D) единиц времени.В основу алгоритма Пелега (см.
[158]) положен фазовый алгоритм; ему требуется O(D|E|) обменов сообщениями и O(D) единиц времени, но знание D длянего не нужно, так как в нем предусмотрено вычисление диаметра в режиме online.Избрание посредством алгоритма Финна. Алгоритму Финна (алгоритм 6.8)не требуется предварительных сведений о диаметре сети. В алгоритме Финнапроводится O(N|E|) обменов сообщениями, но сами сообщения гораздо длиннеетого, что позволяют нам допущения, сделанные в этой главе. Поэтому каждоесообщение в алгоритме Финна следует рассматривать как O(N) сообщений; такимобразом, сложность по числу обменов сообщениями становится равной O(N 2 |E|).7.2. Кольцевые сетиВ этом параграфе рассматриваются некоторые алгоритмы избрания для неориентированных колец. Задача о выборах применительно к кольцевым сетям былавпервые поставлена Ле-Ланном в работе [131] , ему же удалось найти ее решениесо сложностью O(N2) по числу обменов сообщениями.
Это решение было улучшено Ченем и Робертсом (см. [40]); они предложили алгоритм, который имеетсложность O(N2) в наихудшем случае, но зато его сложность в среднем составляет всего лишь O(N log N). Решения Ле-Ланна и решения Ченя—Робертса обсуждаются в § 7.2.1. Вопрос о существовании алгоритма со сложностью O(N log N)в наихудшем случае оставался открытым до 1980 г., когда такой алгоритм былпредложен Хиршбергом и Синклейром в работе [105] .
В отличие от более ранних решений, в алгоритме Хиршберга—Синклейра требуется, чтобы каналы былидвунаправленными. Какое-то время предполагалось, что Ω (N 2) обменов сообщениями составляют нижнюю оценку для однонаправленных колец, но Петерсон,а также Долев, Клейв и Роде (см. [159] и [69]) независимо предложили решениесложности O(N log N) для однонаправленного кольца. Их решение исследуетсяв § 7.2.2.Почти в то же самое время указанные алгоритмы были дополнены согласованными нижними оценками.
Нижняя оценка ≈0.34N log N сложности по числу обменов сообщениями в наихудшем случае для двунаправленных колец былаобоснована Бодлаендэром; см. [31] . Пачль, Корач и Ротем в работе [156] доказали нижнюю оценку Ω (N log N) сложности в среднем как для двунаправленных,В алгоритме Ле-Ланна (см. [131]) каждый инициатор вычисляет список отличительных признаков всех инициаторов, после чего лидером избирается инициатор с наименьшим признаком. Каждый инициатор отправляет по кольцу маркер,в который вложен отличительный признак инициатора, и все процессы передаютдалее этот маркер. Предполагается, что в каналах соблюдается очередность сообщений и всякий инициатор должен создать свой маркер, прежде чем получитмаркер от всякого другого инициатора.
(Как только процесс получает маркер, онуже не может впоследствии инициировать выполнение алгоритма.) Когда инициатор p получает свой собственный маркер обратно, маркеры всех инициаторовуже прошли через p, и p будет избран лидером в том и только том случае, еслиp — наименьший процесс среди всех инициаторов (см. алгоритм 7.2).var Listpstatep ;: подмножество Pinit{p} ;begin if p is initiator thenbegin statep := cand ; send htok, pi to Nextp ; receive htok, qi ;while q 6= p dobegin Listp := Listp ∪ {q} ;send htok, qi to Nextp ; receive htok, qiend;if p = min(Listp) then statep := leaderelse statep := lostendelse while true dobegin receive htok, qi ; send htok, qi to Nextp ;if statep = sleep then statep := lostendendАлгоритм 7.2.
Алгоритм Ле-Ланна избрания лидераТеорема 7.4. Алгоритм Ле-Ланна (алгоритм 7.2) решает задачу о выборах на кольцах с использованием O(N 2) обменов сообщениями за O(N)единиц времени.Д о к а з а т е л ь с т в о. Так как порядок следования маркеров по кольцуостается неизменным (вследствие допущения очередности в каналах) и инициаторq отправляет htok, qi ранее, нежели q получает htok, pi, инициатор p получаетhtok, qi, до того как p получит htok, pi обратно. Отсюда следует, что каждыйинициатор p завершает работу со списком Listp , представляющим множество246Гл. 7.
Алгоритмы избрания лидеравсех инициаторов, и инициатор с наименьшим отличительным признаком становится единственным процессом, избранным на роль лидера. Всего оказываютсязадействованными не более N различных маркеров, и каждый из них совершает N шагов, что приводит к сложности O(N 2) по числу обменов сообщениями.Спустя самое позднее N − 1 единиц времени, после того как первый инициаторотправил свой маркер, каждый инициатор проделает то же самое. При этом каждый инициатор получит свой маркер обратно в течение N единиц времени послесоздания этого маркера.
Значит, наш алгоритм завершит работу не позднее, чемспустя 2N − 1 единиц времени.Все неинициаторы переходят в состояние lost, но будут пребывать сколь угодно долго в ожидании сообщений htok, ri. Ожидание можно прервать, если заставить лидера отправить специальный маркер по кольцу для оповещения о том,что выборы завершены.Алгоритм Ченя—Робертса [40] улучшает алгоритм Ле-Ланна за счет того,что из кольца изымаются все маркеры тех процессов, относительно которых ужестановится ясно, что они проиграют выборы. А именно, инициатор p изымаетмаркер htok, qi из кольца, если q > p. Инициатор p обретает статус lost, едвалишь получает маркер с отличительным признаком q < p, и статус leader, кактолько получает маркер с отличительным признаком p (см.
алгоритм 7.3).7.2. Кольцевые сетиТеорема 7.5. Алгоритм Ченя—Робертса (алгоритм 7.3) решает задачуо выборах для колец, используя в худшем случае Θ (N 2) обменов сообщениями за O(N) единиц времени.Д о к а з а т е л ь с т в о. Обозначим символом p0 инициатор с наименьшимотличительным признаком. Всякий другой процесс может быть либо неинициатором, либо инициатором с отличительным признаком, превышающим p 0 , и поэтому все процессы передадут далее маркер htok, p 0 i, выпущенный p0 .
Значит,p0 получит свой маркер обратно и будет избран лидером.Неинициаторы не будут избраны, но все они перейдут в состояние lost самоепозднее к моменту передачи маркера, который выпустил процесс p 0 . Инициаторp, для которого p > p0 , не будет избран лидером; p0 не передаст далее маркер htok, pi, и поэтому p никогда не получит свой собственный маркер.
Такойинициатор p перейдет в состояние lostсамое позднее в тот момент, когда будетпередавать далее htok, p0 i. Это и служит обоснованием того, что наш алгоритмрешает задачу о выборах.var statep ;Алгоритм 7.3. Алгоритм Ченя—Робертса избрания лидераtN−1begin if p is initiator thenbegin statep := cand ; send htok, pi to nextp ;while statep 6= leader dobegin receive htok, qi ;if q = p then statep := leaderelse if q < p thenbegin if statep = cand then statep := lost ;send htok, qi to nextpendendendelse while true dobegin receive htok, qi ; send htok, qi to nextp ;if statep = sleep then statep := lostendend(* Только лидер завершает выполнение программы. Он отправляетсообщение всем процессам, информируя их об отличительных признакахлидера и о завершении выборов *)247AAHHtHHt1AA0tСообщения передаютсяпо часовой стрелкеiРис.
7.4. Наихудший возможный сценарий для алгоритма Ченя—РобертсаВ алгоритме задействовано не более N различных маркеров, и каждый маркер передается не более N раз; этим и обосновывается оценка O(N 2) сложности по числу обменов сообщениями. Чтобы убедиться в том, что иногда может понадобиться передать Ω (N 2) сообщений, рассмотрим начальную конфигурацию, в которой отличительные признаки расположены в кольце по возрастанию(см. рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
