ref (664672), страница 25

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

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

(* Начало древовидного алгоритма *)

while # {q : rec_p[q]} > 1 do

begin receive <tok,r> from q ; rec_p[q] := true ;

v_p := min (v_p,r)

end ;

send <tok,v_p> to q₀ with rec_p[q₀] ;

receive <tok,r> from q₀ ;

v_p := min (v_p,r) ; (* decide с ответом v_p *)

if v_p = p then state_p := leader else state_p := lost ;

forall q  Neigh_p, q  q₀ do send <tok,v_p> to q

end

Алгоритм 7.1 Алгоритм выборов для деревьев.

Теорема 7.2 Алгоритм 7.1 решает задачу выбора на деревьях, используя O(N) сообщений и O(D) единиц времени.

Доказательство. Когда хотя бы один процесс инициирует выполнение алгоритма, все процессы посылают сообщения <wakeup> всем своим соседям, и каждый процесс начинает выполнение древовидного алгоритма после получения сообщения <wakeup> от каждого соседа. Все процессы завершают древовидный алгоритм с одним и тем же значением v, а именно, наименьшим идентификатором процесса. Единственный процесс с этим идентификатором закончит выполнение в состоянии лидер, а все остальные процессы - в состоянии проигравший.

Через каждый канал пересылается по два сообщения <wakeup> и по два сообщения <tok,r>, откуда сложность сообщений равна 4N-4. В течение D единиц времени после того, как первый процесс начал алгоритм, каждый процесс послал сообщения <wakeup>, следовательно, в течение D+1 единиц времени каждый процесс начал волну. Легко заметить, что первое решение принимается не позднее, чем через D единиц времени после начала волны, а последнее решение принимается не позднее D единиц времени после первого, откуда полное время равно 3D+1. Более тщательный анализ показывает, что алгоритм всегда завершается за 2D единиц времени, но доказательство этого оставлено читателю; см. Упражнение 7.2.

Если порядок сообщений в канале может быть изменен (т.е. канал - не FIFO), процесс может получить сообщение <tok,r> от соседа прежде чем он получил сообщение <wakeup> от этого соседа. В этом случае сообщение <tok,r> может быть временно сохранено или обработано как сообщения <tok,r>, прибывающие позднее.

Количество сообщений может быть уменьшено с помощью двух модификаций. Во-первых, можно устроить так, чтобы не-инициатор не посылал сообщение <wakeup> процессу, от которого он получил первое сообщение <wakeup>. Во-вторых, сообщение <wakeup>, посылаемое листом, может быть объединено с сообщением <tok,r>, посылаемым этим листом. С этими изменениями количество сообщений, требуемое алгоритмом, уменьшается до 3N-4+k, где k - количество нелистовых стартеров [Tel91b, с.139].

Выбор с помощью фазового алгоритма. Фазовый алгоритм можно использовать для выбора, позволив ему вычислять наименьший идентификатор за одну волну, как в Теореме 6.12.

Теорема 7.3 С помощью фазового алгоритма (Алгоритм 6.7) можно провести выбор в произвольных сетях, используя O(D*|E|) сообщений и O(D) единиц времени.

Алгоритм Пелега [Peleg; Pel90] основан на фазовом алгоритме; он использует O(D*|E|) сообщений и O(D) времени, но не требует знания D, т.к. включает в себя вычисление диаметра.

Выбор с помощью алгоритма Финна. Алгоритм Финна (Алгоритм 6.9) не требует, чтобы диаметр сети был известен заранее. Длина O(N*|E|) сообщений, используемых в алгоритме Финна, гораздо больше, чем допускаемая предположениями в этой главе. Следовательно, каждое сообщение в алгоритме Финна должно считаться за O(N) сообщений, откуда сложность сообщений составляет O(N²|E|).

7.2 Кольцевые сети

В этом разделе рассматриваются некоторые алгоритмы выбора для однонаправленных колец. Задача выбора в контексте кольцевых сетей была впервые изложена ЛеЛанном [LeLann; LeL77], который также дал решение со сложностью сообщений O(N²). Это решение было улучшено Чангом (Chang) и Робертсом (Roberts) [CR79], которые привели алгоритм с наихудшей сложностью O(N²), но со средней сложностью только O(N logN). Решения ЛеЛанна и Чанга-Робертса обсуждаются в Подразделе 7.2.1. Вопрос о существовании алгоритма с наихудшей сложностью O(N logN) оставался открытым до 1980 г., когда такой алгоритм был приведен Hirschberg и Sinclair [HS80]. В отличие от более ранних решений, в решении Hirschberg-Sinclair требуется, чтобы каналы были двунаправленными. Предполагалось, что нижняя граница для однонаправленных колец равна (N²), но Petersen [Pet82] и Dolev, Klawe и Rodeh [DKR82] независимо друг от друга предложили решение, составляющее O(N log N) для однонаправленного кольца. Это решение рассматривается в Подразделе 7.2.2.

Алгоритмы были дополнены соответствующими нижними границами примерно в то же время. Нижняя граница для наихудшего случая для двунаправленных колец, равная  0.34N logN сообщений, была доказана Бодлендером [Bodlaender; Bod88]. Pachl, Korach и Rotem [PKR84] доказали нижние границы в (N logN) для средней сложности, как для двунаправленных так и для однонаправленных колец. Их результаты по нижним границам будут рассмотрены в Подразделе 7.2.3.

7.2.1 Алгоритмы ЛеЛанна и Чанга-Робертса

В алгоритме ЛеЛанна [LeL77] каждый инициатор вычисляет список идентификаторов всех инициаторов, после чего выбирается инициатор с наименьшим идентификатором. Каждый инициатор посылает маркер, содержащий его идентификатор, по кольцу, и этот маркер передается всеми процессами. Предполагается, что каналы подчиняются дисциплине FIFO, и что инициатор должен сгенерировать свой маркер до того, как он получит маркер другого инициатора. (Когда процесс получает маркер, он после этого не инициирует алгоритм.) Когда инициатор p получает свой собственный маркер, маркеры всех инициаторов прошли через p, и p выбирается лишь в том случае, если p - наименьший среди инициаторов; см. Алгоритм 7.2.

var List_p : set of P init {p} ;

state_p ;

begin if p - инициатор then

begin state_p := cand ; send <tok,p> to Next_p ; receive <tok,q> ;

while q  p do

begin List_p := List_p  {q} ;

send <tok,q> to Next_p ; receive <tok,q> ;

end ;

if p = min (List_p) then state_p := leader

else state_p := lost

end

else repeat receive <tok,q> ; send <tok,q> to Next_p ;

if state_p = sleep then state_p := lost

until false

end

Алгоритм 7.2 Алгоритм выбора ЛеЛанна.

Теорема 7.4 Алгоритм ЛеЛанна (Алгоритм 7.2) решает задачу выбора для колец, используя O(N²) сообщений и O(N) единиц времени.

Доказательство. Так как порядок маркеров в кольце сохраняется (из предположения о каналах FIFO), и инициатор q отправляет <tok,q> до того как получит <tok,p>, то инициатор p получает <tok,q> прежде, чем вернется <tok,p>. Отсюда следует, что каждый инициатор p заканчивается со списком List_p, совпадающим с множеством всех инициаторов, и единственным выбираемым процессом становится инициатор с наименьшим идентификатором. Всего получается не больше N маркеров и каждый делает N шагов, что приводит к сложности сообщений в O(N²). Не позднее чем через N-1 единицу времени после того, как первый инициатор отправил свой маркер, это сделали все инициаторы. Каждый инициатор получает свой маркер обратно не позднее, чем через N единиц времени с момента генерации этого маркера. Отсюда следует, что алгоритм завершается в течение 2N-1 единиц времени.

Все не-инициаторы приходят в состояние проигравший, но навсегда остаются в ожидании сообщений <tok,r>. Ожидание может быть прервано, если лидер посылает по кольцу специальный маркер, чтобы объявить об окончании выбора.

Алгоритм Чанга-Робертса [CR79] улучшает алгоритм ЛеЛанна, устраняя из кольца маркеры тех процессов, для которых очевидно, что они проиграют выборы. Т.е. инициатор p удаляет из кольца маркер <tok,q>, если q > p. Инициатор p становится проигравшим, когда получает маркер с идентификатором q < p, или лидером, когда он получает маркер с идентификатором p; см. Алгоритм 7.3.

var state_p ;

begin if p - инициатор then

begin state_p := cand ; send <tok,p> to Next_p ;

repeat receive <tok,q> ;

if q = p then state_p := leader

else if q < p then

begin if state_p = cand then state_p := lost ;

send <tok,q> to Next_p

end

until state_p = leader

end

else repeat receive <tok,q> ; send <tok,q> to Next_p ;

if state_p = sleep then state_p := lost

until false

end

(* Только лидер завершает выполнение программы. Он передает сообщение всем процессам, чтобы сообщить им идентификатор лидера и завершить их *)

Алгоритм 7.3 Алгоритм выбора Чанга-Робертса.

Теорема 7.5 Алгоритм Чанга-Робертса (Алгоритм 7.3) решает задачу выбора для колец, используя (N²) сообщений в наихудшем случае и O(N) единиц времени.

Доказательство. Пусть p₀ - инициатор с наименьшим идентификатором. Все процессы являются либо не-инициаторами, либо инициаторами с идентификаторами большими p₀, поэтому все процессы передают дальше маркер <tok,p₀>, отправленный p₀. Следовательно, p₀ получает свой маркер обратно и становится выбранным.

Не-инициаторы не могут быть выбраны, т.к. все они приходят в состояние проигравший самое позднее, когда через них передается маркер p₀. Инициатор p с p > p₀ не может быть выбран; p₀ не передаст дальше маркер <tok,p>, поэтому p никогда не получит свой собственный маркер. Такой инициатор p приходит в состояние проигравший самое позднее, когда через него передается маркер <tok,p₀>. Таким образом доказано, что алгоритм решает задачу выбора.

Рис.7.4 Наихудший случай для алгоритма Чанга-Робертса.

Всего используется не более N различных маркеров и каждый маркер делает не более N переходов, что подтверждает границу сложности сообщений O(N²). Чтобы показать, что в самом деле можно использовать (N²) сообщений, рассмотрим начальную конфигурацию, где все идентификаторы расположены в возрастающем порядке вдоль кольца (см. Рис. 7.4) и каждый процесс является инициатором. Маркер каждого процесса удаляется из кольца процессом 0, таким образом маркер процесса i совершает N-i переходов, откуда следует, что количество пересылок сообщений равно .

Алгоритм Чанга-Робертса не улучшает алгоритм ЛеЛанна в отношении временной сложности или наихудшего случая сложности сообщений. Улучшение касается только среднего случая, где усреднение ведется по всевозможным расположениям идентификаторов вдоль кольца.

Теорема 7.6 Алгоритм Чанга-Робертса в среднем случае, когда все процессы являются инициаторами, требует только O(N logN) пересылок сообщений.

Доказательство. (Это доказательство основано на предложении Friedemann Mattern.)

Предположив, что все процессы являются инициаторами, вычислим среднее количество пересылок маркера по всем круговым расположениям N различных идентификаторов. Рассмотрим фиксированное множество из N идентификаторов, и пусть s будет наименьшим идентификатором. Существует (N-1)! различных круговых расположений идентификаторов; в данном круговом расположении пусть p_i - идентификатор, находящийся за i шагов до s; см. Рис. 7.5.

Рис.7.5 Расположение идентификаторов на кольце.

Чтобы вычислить суммарное количество пересылок маркера по всем расположениям, вычислим сначала суммарное количество пересылок маркера <tok,p_i> по всем расположениям, а потом просуммируем по i. Маркер <tok,s> при любом расположении передается N раз, следовательно, он пересылается всего N(N-1)! раз. Маркер <tok,p_i> передается не более i раз, так как он будет удален из кольца, если достигнет s. Пусть A_i,k - количество циклических расположений, при которых <tok,p_i> передается ровно k раз. Тогда суммарное число пересылок <tok,p_i> равно .

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

Список файлов реферата