Предыдущая страница реферата | 25  26  27  28  29  30  31  32  33  34  35 | Следующая страница реферата



Алгоритм 6.16 Алгоритм поиска в глубину Сайдона (Часть 1).

Для каждого процесса при получении от q0: begin if mrsp ? udef and mrsp ? q0

(* это листовое ребро, интерпретируем как сообщение *) then usedp[q0] := true else (* действовать, как в предыдущем алгоритме *) begin if fatherp = udef then begin fatherp := q0 ; forall r ? Neighp {fatherp} do send to r ; end ; if p - инициатор and ?q ? Neighp : usedp[q] then decide else if ?q ? Neighp : (q ? fatherp & ¬usedp[q]) then begin if fatherp ? q0 & ¬usedp[q0] then q := q0 else выбор q ? Neighp {fatherp} с ¬usedp[q] ; usedp[q] := true ; mrsp := q ; send to q end else begin usedp[fatherp] := true ; send to fatherp end end end

Алгоритм 6.17 Алгоритм поиска в глубину Сайдона (Часть 2).
Во многих случаях этот алгоритм будет пересылать меньше сообщений, чем алгоритм Авербаха. Оценка количества сообщений в алгоритме Сайдона предполагает наихудший случай, а именно, когда маркер пересылается через каждое листовое ребро в обоих направлениях. Можно ожидать, что сообщения помогут избежать многих нежелательных пересылок, тогда через каждый канал будет передано только два или три сообщения.
Сайдон замечает, что хотя алгоритм может передать маркер в уже посещенную вершину, он обладает лучшей временной сложностью (и сложностью сообщений), чем Алгоритм 6.15, который предотвращает такие нежелательные передачи. Это означает, что на восстановление после ненужных действий может быть затрачено меньше времени и сообщений, чем на их предотвращение. Сайдон оставляет открытым вопрос о том, существует ли DFS-алгоритм, который достигает сложности сообщений классического алгоритма, т.е. 2|E|, и который затрачивает O(N) единиц времени.

6.4.3 Поиск в глубину со знанием соседей
Если процессам известны идентификаторы их соседей, проход листовых ребер можно предотвратить, включив в маркер список посещенных процессов. Процесс p, получая маркер с включенным в него списком L, не передает маркер процессам из L. Переменная usedp[q] не нужна, т.к. если p ранее передал маркер q, то q ? L; см. Алгоритм 6.18.
Теорема 6.36 DFS-алгоритм со знанием соседей является алгоритмом обхода и вычисляет дерево поиска в глубину, используя 2N-2 сообщений за 2N-2 единиц времени.
У этого алгоритма высокая битовая сложность; если w - количество бит, необходимых для представления одного идентификатора, список L может занять до Nw бит; см. Упражнение 6.14.

var fatherp : process init udef ;

Для инициатора (выполняется один раз): begin fatherp := p ; выбор q ? Neighp ; send to q end

Для каждого процесса при получении от q0: begin if fatherp = udef then fatherp := q0 ; if (q ? Neighp L then begin выбор q ? Neighp L ; send < tlist, L?{p} > to q end else if p - инициатор then decide else send < tlist, L?{p} > to fatherp end

Алгоритм 6.18 Алгоритм поиска в глубину со знанием соседей.

6.5 Остальные вопросы
6.5.1 Обзор волновых алгоритмов
В Таблице 6.19 дан список волновых алгоритмов, рассмотренных в этой главе.
В столбце «Номер» дана нумерация алгоритмов в главе; в столбце «C/D» отмечено, является ли алгоритм централизованным (C) или децентрализованным
(D); столбец «T» определяет, является ли алгоритм алгоритмом обхода; в столбце «Сообщения» дана сложность сообщений; в столбце «Время» дана временная сложность. В этих столбцах N - количество процессов, |E| - количество каналов, D - диаметр сети (в переходах).

|Алгоритм |Номер|Топология |C/D|T |Сообщения|Время |
|Раздел 6.2: Общие алгоритмы |
|Кольцевой |6.2 |кольцо |C |да |N |N |
|Древовидный |6.3 |дерево |D |нет |N |O(D) |
|Эхо-алгоритм |6.5 |произвольная|C |нет |2|E| |O(N) |
|Алгоритм |6.6 |клика |C |нет |2N-2 |2 |
|опроса | | | | | | |
|Фазовый |6.7 |произвольная|D |нет |2D|E| |2D |
|Фазовый на |6.8 |клика |D |нет |N(N-1) |2 |
|кликах | | | | | | |
|Финна |6.9 |произвольная|D |нет |?4N|E| |O(D) |
|Раздел 6.3: Алгоритмы обхода |
|Последовательн|6.10 |клика |C |да |2N-2 |2N-2 |
|ый опрос | | | | | | |
|Для торов |6.11 |тор |C |да |N |N |
|Для гиперкубов|6.12 |гиперкуб |C |да |N |N |
|Тарри |6.13 |произвольная|C |да |2|E| |2|E| |
|Раздел 6.4: Алгоритмы поиска в глубину |
|Классический |6.14 |произвольная|C |да |2|E| |2|E| |
|Авербаха |6.15 |произвольная|C |нет |4|E| |4N-2 |
|Сайдона |6.16/|произвольная|C |нет |4|E| |2N-2 |
| |6.17 | | | | | |
|Со знанием |6.18 |произвольная|C |да |2N-2 |2N-2 |
|соседей | | | | | | |

Замечание: фазовый алгоритм (6.7) и алгоритм Финна (6.9) подходят для ориентированных сетей.

Таблица 6.19 Волновые алгоритмы этой главы.
Сложность распространения волн в сетях большинства топологий значительно зависит от того, централизованный алгоритм или нет. В Таблице 6.20 приведена сложность сообщений централизованных и децентрализованных волновых алгоритмов для колец, произвольных сетей и деревьев. Таким же образом можно проанализировать зависимость сложности от других параметров, таких как знание соседей или чувство направления (Раздел B.3).

|Топология |C/D |Сложность |Ссылка |
|Кольцо |C |N |Алгоритм 6.2 |
| |D |O(N logN) |Алгоритм 7.7 |
|Произвольная|C |2|E| |Алгоритм 6.5 |
| |D |O(N logN + |E|)|Раздел 7.3 |
|Дерево |C |2(N-1) |Алгоритм 6.5 |
| |D |O(N) |Алгоритм 6.3 |

Таблица 6.20 Влияние централизации на сложность сообщений.

6.5.2 Вычисление сумм
В Подразделе 6.1.5 было показано, что за одну волну можно вычислить инфимум по входам всех процессов. Вычисление инфимума может быть использовано для вычисления коммутативного, ассоциативного и идемпотентного оператора, обобщенного на входы, такого как минимум, максимум, и др. (см. Заключение
6.14). Большое количество функций не вычислимо таким образом, среди них - сумма по всем входам, т.к. оператор суммирования не идемпотентен.
Суммирование входов может быть использовано для подсчета процессов с определенным свойством (путем присваивания входу 1, если процесс обладает свойством, и 0 в противном случае), и результаты этого подраздела могут быть распространены на другие операторы, являющиеся коммутативными и ассоциативными, такие как произведение целых чисел или объединение мультимножеств.
Оказывается, не существует общего метода вычисления сумм с использованием волнового алгоритма, но в некоторых случаях вычисление суммы возможно.
Например, в случае алгоритма обхода, или когда процессы имеют идентификаторы, или когда алгоритм порождает остовное дерево, которое может быть использовано для вычисления.
Невозможность существования общего метода. Невозможно дать общий метод вычисления сумм с использованием произвольного волнового алгоритма, подобного методу, использованному в Теореме 6.12 для вычисления инфимумов.
Это может быть показано следующим образом. Существует волновой алгоритм для класса сетей, включающего все неориентированные анонимные (anonymous) сети диаметра два, а именно, фазовый алгоритм (с параметром D=2). Не существует алгоритма, который может вычислить сумму по всем входам, и который является правильным для всех неориентированных анонимных (anonymous) сетей диаметра два. Этот класс сетей включает две сети, изображенные на Рис.6.21. Если предположить, что каждый процесс имеет вход 1, ответ будет 6 для левой сети и 8 - для правой. Воспользовавшись технологией, представленной в Главе 9, можно показать, что любой алгоритм даст для обеих сетей один и тот же результат, следовательно, будет работать неправильно. Детальное доказательство оставлено читателю в Упражнении 9.7.
[pic]
Рис.6.21 Две сети диаметра два и степени три.
Вычисление сумм с помощью алгоритма обхода. Если A - алгоритм обхода, сумма по всем входам может быть вычислена следующим образом. Процесс p содержит переменную jp, инициализированную значением входа p. Маркер содержит дополнительное поле s. Всякий раз, когда p передает маркер, p выполняет следующее: s := s + jp ; jp := 0 и затем можно показать, что в любое время для каждого ранее пройденного процесса p jp = 0 и s равно сумме входов всех пройденных процессов.
Следовательно, когда алгоритм завершается, s равно сумме по всем входам.
Вычисление суммы с использованием остовного дерева. Некоторые волновые алгоритмы предоставляют для каждого события принятия решения dp в процессе p остовное дерево с корнем в p, по которому сообщения передаются по направлению к p. Фактически, каждое вычисление любого волнового алгоритма содержит такие остовные деревья. Однако, может возникнуть ситуация, когда процесс q посылает несколько сообщений и не знает, какие из его исходящих ребер принадлежат к такому дереву. Если процессы знают, какое исходящее ребро является их родителем в таком дереве, дерево можно использовать для вычисления сумм. Каждый процесс посылает своему родителю в дереве сумму всех входов его поддерева.
Этот принцип может быть применен для древовидного алгоритма, эхо-алгоритма и фазового алгоритма для клик. Древовидный алгоритм легко может быть изменен так, чтобы включать сумму входов Tpq в сообщение, посылаемое от p к q. Процесс, который принимает решение, вычисляет окончательный результат, складывая величины из двух сообщений, которые встречаются на одном ребре.
Фазовый алгоритм изменяется так, чтобы в каждом сообщении от q к p пересылался вход q. Процесс p складывает все полученные величины и свой собственный вход, и результат является правильным ответом, когда p принимает решение. В эхо-алгоритме входы могут суммироваться с использованием остовного дерева T, построенного явным образом во время вычисления; см. Упражнение 6.15.
Вычисление суммы с использованием идентификации. Предположим, что каждый процесс имеет уникальный идентификатор. Сумма по всем входам может быть вычислена следующим образом. Каждый процесс помечает свой вход идентификатором, формируя пару (p, jp); заметим, что никакие два процесса не формируют одинаковые пары. Алгоритм гарантирует, что, когда процесс принимает решение, он знает каждый отдельный вход; S = {(p, jp): p ? P} - объединение по всем p множеств Sp = {(p, jp)}, которое может быть вычислено за одну волну. Требуемый результат вычисляется с помощью локальных операций на этом множестве.
Это решение требует доступности уникальных идентификаторов для каждого процесса, что значительно увеличивает битовую сложность. Каждое сообщение волнового алгоритма включает в себя подмножество S, которое занимает N*w бит, если для представления идентификатора и входа требуется w бит; см.
Упражнение 6.16.

6.5.3 Альтернативные определения временной сложности
Временную сложность распределенного алгоритма можно определить несколькими способами. В этой книге при рассмотрении временной сложности всегда имеется в виду Определение 6.31, но здесь обсуждаются другие возможные определения.
Определение, основанное на более строгих временных предположениях. Время, потребляемое распределенными вычислениями, можно оценить, используя более строгие временные предположения в системе.
Определение 6.37 Единичная сложность алгоритма (one-time complexity) - это максимальное время вычисления алгоритма при следующих предположениях.
O1. Процесс может выполнить любое конечное количество событий за нулевое время.
O2. Промежуток времени между отправлением и получением сообщения - ровно одна единица времени.
Сравним это определение с Определением 6.31 и заметим, что предположение O1 совпадает с T1. Т.к. время передачи сообщения, принятое в T2, меньше или равно времени, принятому в O2, можно подумать, что единичная сложность всегда больше или равна временной сложности. Далее можно подумать, что каждое вычисление при предположении T2 выполняется не дольше, чем при O2, и, следовательно, вычисление с максимальным временем также займет при T2 не больше времени, чем при O2. Упущение этого аргумента в том, что отклонения во времени передачи сообщения, допустимые при T2, порождают большой класс возможных вычислений, включая вычисления с плохим временем. Это иллюстрируется ниже для эхо-алгоритма.
Фактически, верно обратное: временная сложность алгоритма больше или равна единичной сложности этого алгоритма. Любое вычисление, допустимое при предположениях O1 и O2, также допустимо при T1 и T2 и занимает при этом такое же количество времени. Следовательно, наихудшее поведение алгоритма при O1 и O2 включено в Определение 6.31 и является нижней границей временной сложности.
Теорема 6.38 Единичная сложность эхо-алгоритма равна O(D). Временная сложность эхо-алгоритма равна ?(N), даже в сетях с диаметром 1.
Доказательство. Для анализа единичной сложности сделаем предположения O1 и
O2. Процесс на расстоянии d переходов от инициатора получает первое сообщение ровно через d единиц времени после начала вычисления и имеет глубину d в возникающем в результате дереве T. (Это можно доказать индукцией по d.) Пусть DT - глубина T; тогда DT ( D и процесс глубины d в T посылает сообщение своему родителю не позднее (2DT + 1) - d единиц времени после начала вычисления. (Это можно показать обратной индукцией по d.) Отсюда следует, что инициатор принимает решение не позднее 2DT + 1 единиц времени после начала вычисления.
Для анализа временной сложности сделаем предположения T1 и T2. Процесс на расстоянии d переходов от инициатора получает первое сообщение не позднее d единиц времени после начала вычисления. (Это можно доказать индукцией по d.) Предположим, что остовное дерево построено через F единиц времени после начала вычисления, тогда F ( D. В этом случае глубина остовного дерева DT необязательно ограничена диаметром (как будет показано в вычислении ниже), но т.к. всего N процессов, глубина ограничена N-1.
Процесс глубины d в T посылает сообщение своему родителю не позднее
(F+1)+(DT-d) единиц времени после начала вычисления. (Это можно показать обратной индукцией по d.) Отсюда следует, что инициатор принимает решение не позднее (F+1)+DT единиц времени после начала вычисления, т.е. O(N).
Чтобы показать, что ?(N) - нижняя граница временной сложности, построим на клике из N процессов вычисление, которое затрачивает время N. Зафиксируем в клике остовное дерево глубины N-1 (на самом деле, линейную цепочку вершин).
Предположим, что все сообщения , посланные вниз по ребрам дерева, будут получены спустя 1/N единиц времени после их отправления, а сообщения через листовые ребра будут получены спустя одну единицу времени. Эти задержки допустимы, согласно предположению T2, и в этом вычислении дерево полностью формируется в течение одной единицы времени, но имеет глубину N-
1. Допустим теперь, что все сообщения, посылаемые вверх по ребрам дерева также испытывают задержку в одну единицу времени; в этом случае решение принимается ровно через N единиц времени с начала вычисления.
Можно спорить о том, какое из двух определений предпочтительнее при обсуждении сложности распределенного алгоритма. Недостаток единичной сложности в том, что некоторые вычисления не учитываются, хотя они и допускаются алгоритмом. Среди игнорируемых вычислений могут быть такие, которые потребляют очень много времени. Предположения в Определении 6.31 не исключают ни одного вычисления; определение только устанавливает меру времени для каждого вычисления. Недостаток временной сложности в том, что результат определен вычислениями (как в доказательстве Теоремы 6.38), что хотя и возможно, но считается крайне маловероятным. Действительно, в этом вычислении одно сообщение «обгоняется» цепочкой из N-1 последовательно передаваемого сообщения.
В качестве компромисса между двумя определениями можно рассмотреть ?- временную сложность, которая определяется согласно предположению, что задержка каждого сообщения - величина между ? и 1 (? - константа ?1). К сожалению, этот компромисс обладает недостатками обоих определений.
Читатель может попытаться показать, что ?-временная сложность эхо-алгоритма равна O(min(N,D/?)).
Наиболее точная оценка временной сложности получается, когда можно задать распределение вероятностей задержек сообщений, откуда может быть вычислено ожидаемое время вычисления алгоритма. У этого варианта есть два основных недостатка. Во-первых, анализ алгоритма слишком зависит от системы, т.к. в каждой распределенной системе распределение задержек сообщений различно. Во- вторых, в большинстве случаев анализ слишком сложен для выполнения.
Определение, основанное на цепочках сообщений. Затраты времени на распределенное вычисление могут быть определены с использованием структурных свойств вычисления, а не идеализированных временных предположений. Пусть C - вычисление.
Определение 6.39 Цепочка сообщений в C - это последовательность сообщений m1, m2, ..., mk такая, что для любого i (0 ? i ? k) получение mi каузально предшествует отправлению mi+1.
Цепочечная сложность распределенного алгоритма (chain-time complexity) - это длина самой длинной цепочки сообщений во всех вычислениях алгоритма.
Это определение, как и Определение 6.31, рассматривает всевозможные выполнения алгоритма для определения его временной сложности, но определяет другую меру сложности для вычислений. Рассмотрим ситуацию (происходящую в вычислении, определенном в доказательстве теоремы 6.38), когда одно сообщение «обгоняется» цепочкой из k сообщений. Временная сложность этого
(под)вычисления равна 1, в то время, как цепочечная сложность того же самого (под)вычисления равна k. В системах, где гарантируется существование верхней границы задержек сообщений (как предполагается в определении временной сложности), временная сложность является правильным выбором. В системах, где большинство сообщений доставляется со «средней» задержкой, но небольшая часть сообщений может испытывать гораздо большую задержку, лучше выбрать цепочечную сложность.

Упражнения к Главе 6
Раздел 6.1
Упражнение 6.1 Приведите пример PIF-алгоритма для систем с синхронной передачей сообщений, который не позволяет вычислять функцию инфимума (см.
Теоремы 6.7 и 6.12). Пример может подходить только для конкретной топологии.
Упражнение 6.2 В частичном порядке (X, ?) элемент b называется дном, если для всех c ? X, b ? c.
В доказательстве Теоремы 6.11 используется то, что частичный порядок (X,?) не содержит дна. Где именно?
Можете ли вы привести алгоритм, который вычисляет функцию инфимума в частичном порядке с дном и не является волновым алгоритмом?
Упражнение 6.3 Приведите два частичных порядка на натуральных числах, для которых функция инфимума является (1) наибольшим общим делителем, и (2) наименьшим общим кратным (the least common ancestor).
Приведите частичные порядки на наборах подмножеств области U, для которых функция инфимума является (1) пересечением множеств, и (2) объединением множеств.
Упражнение 6.4 Докажите теорему об инфимуме (Теорему 6.13).
Раздел 6.2
Упражнение 6.5 Покажите, что в каждом вычислении древовидного алгоритма
(Алгоритм 6.3) решение принимают ровно два процесса.
Упражнение 6.6 Используя эхо-алгоритм (Алгоритм 6.5), составьте алгоритм, который вычисляет префиксную схему маркировки (см. Подраздел 4.4.3) для произвольной сети с использованием 2|E| сообщений и O(N) единиц времени.
Можете ли вы привести алгоритм, вычисляющий схему маркировки за время O(D)
? (D - диаметр сети.)
Упражнение 6.7 Покажите, что соотношение в Лемме 6.19 выполняется, если сообщение потерялось в канале pq, но не выполняется, если сообщения могут дублироваться. Какой шаг доказательства не действует, если сообщения могут дублироваться?
Упражнение 6.8 Примените построение в Теореме 6.12 к фазовому алгоритму так, чтобы получить алгоритм, вычисляющий максимум по целочисленным входам всех процессов.
Каковы сложность сообщений, временная и битовая сложность вашего алгоритма?

Упражнение 6.9 Предположим, вы хотите использовать волновой алгоритм в сети, где может произойти дублирование сообщений.
Какие изменения должны быть сделаны в эхо-алгоритме?
Какие изменения должны быть сделаны в алгоритме Финна?
Раздел 6.3
Упражнение 6.10 Полный двудольный граф - это граф G = (V,E), где V = V1 ?
V2 при V1 ? V2 = ? и E = V1 Ч V2.
Приведите алгоритм 2x-обхода для полных двудольных сетей.
Упражнение 6.11 Докажите или опровергните: Обход гиперкуба без чувства направления требует ?(N logN) сообщений.
Раздел 6.4
Упражнение 6.12 Приведите пример вычисления алгоритма Тарри, в котором в результате получается не DFS-дерево.
Упражнение 6.13 Составьте алгоритм, который вычисляет интервальные схемы маркировки поиска в глубину (см. Подраздел 4.4.2) для произвольных связных сетей.
Может ли это быть сделано за O(N) единиц времени? Может ли это быть сделано с использованием O(N) сообщений?
Упражнение 6.14 Предположим, что алгоритм поиска в глубину со знанием соседей используется в системе, где каждый процесс знает не только идентификаторы своих соседей, но и множество идентификаторов всех процессов
(P). Покажите, что в этом случае достаточно сообщений, состоящих из N бит.

Раздел 6.5
Упражнение 6.15 Адаптируйте эхо-алгоритм (Алгоритм 6.5) для вычисления суммы по входам всех процессов.
Упражнение 6.16 Предположим, что процессы в сетях, изображенных на
Рис.6.21, имеют уникальные идентификаторы, и каждый процесс имеет целочисленный вход. Смоделируйте на обеих сетях вычисление фазового алгоритма, вычисляя множество S = {(p, jp): p ? P} и сумму по входам.
Упражнение 6.17 Какова цепочечная сложность фазового алгоритма для клик
(Алгоритм 6.8) ?

7 Алгоритмы выбора
В этой главе будут обсуждаться проблемы выбора, также называемого нахождением лидера. Задача выбора впервые была изложена ЛеЛанном [LeLann;
LeL77], который предложил и первое решение; см. Подраздел 7.2.1. Задача начинается в конфигурации, где все процессы находятся в одинаковом состоянии, и приходит в конфигурацию, где ровно один процесс находится в состоянии лидера (leader), а все остальные - в состоянии проигравших
(lost).
Выбор среди процессов нужно проводить, если должен быть выполнен централизованный алгоритм и не существует заранее известного кандидата на роль инициатора алгоритма. Например, в случае процедуры инициализации системы, которая должна быть выполнена в начале или после сбоя системы.
Т.к. множество активных процессов может быть неизвестно заранее, невозможно назначить один процесс раз и навсегда на роль лидера.
Существует большое количество результатов о задаче выбора (как алгоритмы, так и более общие теоремы). Результаты для включения в эту главу выбирались по следующим критериям.
Синхронные системы, анонимные процессы, и отказоустойчивые алгоритмы обсуждаются в других главах. В этой главе всегда предполагается, что процессы и каналы надежны, система полностью асинхронна, и процессы различаются уникальными идентификаторами.
Мы сосредоточим внимание на результатах, касающихся сложности сообщений.
Алгоритмы с улучшенной временной сложностью или результаты, предполагающие компромисс между временной сложностью и сложностью сообщений, не обсуждаются.
Мы будем уделять внимание порядку величины сложности сообщений, и не будем рассматривать результаты, вносящие в сложность только постоянный множитель.
Т.к. результаты Кораха и др. (Раздел 7.4) подразумевают существование O(N logN)-алгоритмов для нескольких классов сетей, алгоритм для клики с этой сложностью не будет рассматриваться отдельно.

7.1 Введение

Задача выбора требует, чтобы из конфигурации, где все процессы находятся в одинаковом состоянии, система пришла в конфигурацию, где ровно один процесс находится в особом состоянии лидер (leader), а все остальные процессы - в состоянии проигравших (lost). Процесс, находящийся в состоянии лидер в конце вычисления, называется лидером и говорят, что он выбран алгоритмом.
Определение 7.1 Алгоритм выбора - это алгоритм, удовлетворяющий следующим требованиям.
Каждый процесс имеет один и тот же локальный алгоритм.
Алгоритм является децентрализованным, т.е. вычисление может быть начато произвольным непустым подмножеством процессов.
Алгоритм достигает заключительной конфигурации в каждом вычислении, и в каждой достижимой заключительной конфигурации существует ровно один процесс в состоянии лидера, а все остальные процессы - в состоянии проигравших.
Иногда последнее требование ослабляется и требуется только, чтобы ровно один процесс находился в состоянии лидера. В этом случае выбранный процесс знает, что он победил, но проигравшие (еще) не знают, что они проиграли.
Если дан алгоритм, удовлетворяющий этим ослабленным действиям, то его можно легко расширить, добавив инициируемую лидером рассылку сообщений всем процессам, при которой все процессы информируются о результатах выбора. В некоторых алгоритмах этой главы это дополнительное оповещение опущено.
Во всех алгоритмах этой главы процесс p имеет переменную statep с возможными значениями leader (лидер) и lost (проигравший). Иногда мы будем предполагать, что statep имеет значение sleep (спящий), когда p еще не выполнил ни одного шага алгоритма, и значение cand (кандидат), если p вступил в вычисление, но еще не знает, победил он или проиграл. Некоторые алгоритмы используют дополнительные состояния, такие как active, passive и др., которые будут указаны в самом алгоритме.

7.1.1 Предположения, используемые в этой главе
Рассмотрим предположения, при которых задача выбора изучалась в этой главе.
Система полностью асинхронна. Предполагается, что процессам недоступны общие часы, и что время передачи сообщения может быть произвольно долгим или коротким.
Оказывается, что предположение о синхронной передаче сообщений (т.е. когда отправление и получение сообщения считается единой передачей) незначительно влияет на результаты, полученные для задачи выбора. Читатель может сам убедиться, что алгоритмы, данные в этой главе, могут применяться в системах с синхронной передачей сообщений, и что полученные нижние границы также применимы в этом случае.
Предположение о существовании глобального времени, также как и предположение о том, что процессам доступно реальное время и что задержка сообщений ограничена, имеют важное влияние на решения задачи выбора.
Каждый процесс идентифицируется уникальным именем, своим идентификатором, который известен процессу изначально. Для простоты предполагается, что идентификатор процесса p - просто p. Идентификаторы извлекаются из совершенно упорядоченного множества P, т.е. для идентификаторов определено отношение ?. Количество бит, представляющих идентификатор, равно w.
Важность уникальных идентификаторов в задаче выбора состоит в том, что они могут использоваться не только для адресации сообщений, но и для нарушения симметрии между процессами. При разработке алгоритма выбора можно, например, потребовать, что процесс с наименьшим (или наоборот, с наибольшим) идентификатором должен победить. Тогда задача состоит в поиске наименьшего идентификатора с помощью децентрализованного алгоритма. В этом случае задачу выбора называют задачей поиска экстремума.
Хотя некоторые из алгоритмов, обсуждаемых в этой главе, изначально были изложены для нахождения наибольшего процесса, мы излагаем большинство алгоритмов для выбора наименьшего процесса. Во всех случаях алгоритм для выбора наибольшего процесса можно получить, изменив порядок сравнения идентификаторов.
Некоторые результаты этой главы относятся к алгоритмам сравнения. Алгоритмы сравнения - это алгоритмы, которые используют сравнение как единственную операцию над идентификаторами. Как мы увидим, все алгоритмы, представленные в этой главе, являются алгоритмами сравнения. Всякий раз, когда дается оценка нижней границы, мы явно отмечаем, касается ли она алгоритмов сравнения.
Было показано (например, Бодлендером [Bodlaender, Bod91b] для случая кольцевых сетей), что в асинхронных сетях произвольные алгоритмы не достигают лучшей сложности, чем алгоритмы сравнения. Это не так в случае синхронных систем, как будет показано в Главе 11; в этих системах произвольные алгоритмы могут достигать лучшей сложности, чем алгоритмы сравнения.
Каждое сообщение может содержать O(w) бит. Каждое сообщение может содержать не более постоянного числа идентификаторов процессов. Это предположение сделано для того, чтобы позволить справедливое сравнение сложности сообщений различных алгоритмов.

7.1.2 Выбор и волны
Уже было замечено, что идентификаторы процессов могут использоваться для нарушения симметрии между процессами. Можно разработать алгоритм выбора так, чтобы выбирался процесс с наименьшим идентификатором. Согласно результатам в Подразделе 6.1.5, наименьший идентификатор может быть вычислен за одну волну. Это означает, что выбор можно провести, выполняя волну, в которой вычисляется наименьший идентификатор, после чего процесс с этим идентификатором становится лидером. Т.к. алгоритм выбора должен быть децентрализованным, этот принцип может быть применен только к децентрализованным волновым алгоритмам (см. Таблицу 6.19).
Выбор с помощью древовидного алгоритма. Если топология сети - дерево или доступно остовное дерево сети, выбор можно провести с помощью древовидного алгоритма (Подраздел 6.2.2). В древовидном алгоритме требуется, чтобы хотя бы все листья были инициаторами алгоритма. Чтобы получить развитие алгоритма в случае, когда некоторые процессы также являются инициаторами, добавляется фаза wake-up. Процессы, которые хотят начать выбор, рассылают сообщение всем процессам. Логическая переменная ws используется, чтобы каждый процесс послал сообщения не более одного раза, а переменная wr используется для подсчета количества сообщений , полученных процессом. Когда процесс получит сообщение через каждый канал, он начинает выполнять Алгоритм 6.3, который расширен (как в Теореме
6.12) таким образом, чтобы вычислять наименьший идентификатор и чтобы каждый процесс принимал решение. Когда процесс принимает решение, он знает идентификатор лидера; если этот идентификатор совпадает с идентификатором процесса, он становится лидером, а если нет - проигравшим; см. Алгоритм
7.1.

var wsp : boolean init false ; wrp : integer init 0 ; recp[q] : boolean для всех q ? Neighp init false ; vp : P init p ; statep : (sleep, leader, lost) init sleep ;

begin if p - инициатор then begin wsp := true ; forall q ? Neighp do send to q end ; while wrp < # Neighp do begin receive ; wrp := wrp + 1 ; if not wsp then begin wsp := true ; forall q ? Neighp do send to q end end ;

(* Начало древовидного алгоритма *) while # {q : ¬recp[q]} > 1 do begin receive from q ; recp[q] := true ; vp := min (vp,r) end ; send to q0 with ¬recp[q0] ; receive from q0 ; vp := min (vp,r) ; (* decide с ответом vp *) if vp = p then statep := leader else statep := lost ; forall q ? Neighp, q ? q0 do send to q end

Алгоритм 7.1 Алгоритм выборов для деревьев.
Теорема 7.2 Алгоритм 7.1 решает задачу выбора на деревьях, используя O(N) сообщений и O(D) единиц времени.
Доказательство. Когда хотя бы один процесс инициирует выполнение алгоритма, все процессы посылают сообщения всем своим соседям, и каждый процесс начинает выполнение древовидного алгоритма после получения сообщения от каждого соседа. Все процессы завершают древовидный алгоритм с одним и тем же значением v, а именно, наименьшим идентификатором процесса. Единственный процесс с этим идентификатором закончит выполнение в состоянии лидер, а все остальные процессы - в состоянии проигравший.
Через каждый канал пересылается по два сообщения и по два сообщения , откуда сложность сообщений равна 4N-4. В течение D единиц времени после того, как первый процесс начал алгоритм, каждый процесс послал сообщения , следовательно, в течение D+1 единиц времени каждый процесс начал волну. Легко заметить, что первое решение принимается не позднее, чем через D единиц времени после начала волны, а последнее решение принимается не позднее D единиц времени после первого, откуда полное время равно 3D+1. Более тщательный анализ показывает, что алгоритм всегда завершается за 2D единиц времени, но доказательство этого оставлено читателю; см. Упражнение 7.2.
Если порядок сообщений в канале может быть изменен (т.е. канал - не FIFO), процесс может получить сообщение от соседа прежде чем он получил сообщение от этого соседа. В этом случае сообщение может быть временно сохранено или обработано как сообщения , прибывающие позднее.
Количество сообщений может быть уменьшено с помощью двух модификаций. Во- первых, можно устроить так, чтобы не-инициатор не посылал сообщение процессу, от которого он получил первое сообщение . Во- вторых, сообщение , посылаемое листом, может быть объединено с сообщением , посылаемым этим листом. С этими изменениями количество сообщений, требуемое алгоритмом, уменьшается до 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(N2|E|).

7.2 Кольцевые сети
В этом разделе рассматриваются некоторые алгоритмы выбора для однонаправленных колец. Задача выбора в контексте кольцевых сетей была впервые изложена ЛеЛанном [LeLann; LeL77], который также дал решение со сложностью сообщений O(N2). Это решение было улучшено Чангом (Chang) и
Робертсом (Roberts) [CR79], которые привели алгоритм с наихудшей сложностью
O(N2), но со средней сложностью только O(N logN). Решения ЛеЛанна и Чанга-
Робертса обсуждаются в Подразделе 7.2.1. Вопрос о существовании алгоритма с наихудшей сложностью O(N logN) оставался открытым до 1980 г., когда такой алгоритм был приведен Hirschberg и Sinclair [HS80]. В отличие от более ранних решений, в решении Hirschberg-Sinclair требуется, чтобы каналы были двунаправленными. Предполагалось, что нижняя граница для однонаправленных колец равна ?(N2), но 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 Listp : set of P init {p} ; statep ;

begin if p - инициатор then begin statep := cand ; send to Nextp ; receive ; while q ? p do begin Listp := Listp ? {q} ; send to Nextp ; receive ; end ; if p = min (Listp) then statep := leader else statep := lost end else repeat receive ; send to Nextp ; if statep = sleep then statep := lost until false end

Алгоритм 7.2 Алгоритм выбора ЛеЛанна.
Теорема 7.4 Алгоритм ЛеЛанна (Алгоритм 7.2) решает задачу выбора для колец, используя O(N2) сообщений и O(N) единиц времени.
Доказательство. Так как порядок маркеров в кольце сохраняется (из предположения о каналах FIFO), и инициатор q отправляет до того как получит , то инициатор p получает прежде, чем вернется
. Отсюда следует, что каждый инициатор p заканчивается со списком
Listp, совпадающим с множеством всех инициаторов, и единственным выбираемым процессом становится инициатор с наименьшим идентификатором. Всего получается не больше N маркеров и каждый делает N шагов, что приводит к сложности сообщений в O(N2). Не позднее чем через N-1 единицу времени после того, как первый инициатор отправил свой маркер, это сделали все инициаторы. Каждый инициатор получает свой маркер обратно не позднее, чем через N единиц времени с момента генерации этого маркера. Отсюда следует, что алгоритм завершается в течение 2N-1 единиц времени.
Все не-инициаторы приходят в состояние проигравший, но навсегда остаются в ожидании сообщений . Ожидание может быть прервано, если лидер посылает по кольцу специальный маркер, чтобы объявить об окончании выбора.
Алгоритм Чанга-Робертса [CR79] улучшает алгоритм ЛеЛанна, устраняя из кольца маркеры тех процессов, для которых очевидно, что они проиграют выборы. Т.е. инициатор p удаляет из кольца маркер , если q > p.
Инициатор p становится проигравшим, когда получает маркер с идентификатором q < p, или лидером, когда он получает маркер с идентификатором p; см.
Алгоритм 7.3.

var statep ;

begin if p - инициатор then begin statep := cand ; send to Nextp ; repeat receive ; if q = p then statep := leader else if q < p then begin if statep = cand then statep := lost ; send to Nextp end until statep = leader end else repeat receive ; send to Nextp ; if statep = sleep then statep := lost until false end
-'?[pic].
Алгоритм Чанга-Робертса не улучшает алгоритм ЛеЛанна в отношении временной сложности или наихудшего случая сложности сообщений. Улучшение касается только среднего случая, где усреднение ведется по всевозможным расположениям идентификаторов вдоль кольца.
Теорема 7.6 Алгоритм Чанга-Робертса в среднем случае, когда все процессы являются инициаторами, требует только O(N logN) пересылок сообщений.
Доказательство. (Это доказательство основано на предложении Friedemann
Mattern.)
Предположив, что все процессы являются инициаторами, вычислим среднее количество пересылок маркера по всем круговым расположениям N различных идентификаторов. Рассмотрим фиксированное множество из N идентификаторов, и пусть s будет наименьшим идентификатором. Существует (N-1)! различных круговых расположений идентификаторов; в данном круговом расположении пусть pi - идентификатор, находящийся за i шагов до s; см. Рис. 7.5.
[pic]
Рис.7.5 Расположение идентификаторов на кольце.
Чтобы вычислить суммарное количество пересылок маркера по всем расположениям, вычислим сначала суммарное количество пересылок маркера по всем расположениям, а потом просуммируем по i. Маркер при любом расположении передается N раз, следовательно, он пересылается всего N(N-1)! раз. Маркер передается не более i раз, так как он будет удален из кольца, если достигнет s. Пусть Ai,k - количество циклических расположений, при которых передается ровно k раз.
Тогда суммарное число пересылок равно [pic].
Маркер передается ровно i раз, если pi является наименьшим из идентификаторов от p1 до pi, что имеет место в (1/i)*(N-1)! расположениях; итак
[pic]
Маркер передается не менее k раз (здесь k ? i), если за процессом pi следует k-1 процесс с идентификаторами, большими pi. Количество расположений, в которых pi - наименьший из k идентификаторов pi-k+1, ..., pi, составляет 1/k часть всех расположений, т.е. (1/k)*(N-1)!. Теперь, для k1) активными процессами, и все процессы имеют различные ci, то в круге остаются не меньше 1 и не больше k/2 процессов. В конце круга снова все текущие идентификаторы активных процессов различны и включают наименьший идентификатор.
Доказательство. Путем обмена сообщениями , которые пропускаются пассивными процессами, каждый активный процесс получает текущий идентификатор своего активного соседа против часовой стрелки, который всегда отличается от его собственного идентификатора. Далее, каждый активный процесс продолжает обход круга, передавая сообщения , благодаря которым каждый активный процесс получает текущий идентификатор своего второго активного соседа против часовой стрелки. Теперь все активные процессы имеют различные значения acn, откуда следует, что в конце круга все оставшиеся в круге идентификаторы различны. По крайней мере, остается идентификатор, который был наименьшим в начале круга, т.е. остается хотя бы один процесс. Идентификатор рядом с локальным минимумом не является локальным минимумом, откуда следует, что количество оставшихся в круге не превышает k/2.
Из Утверждения 7.8 следует, что существует круг с номером ???logN?+1, который начинается ровно с одним активным идентификатором, а именно, с наименьшим среди идентификаторов инициаторов.
Утверждение 7.9 Если круг начинается ровно с одним активным процессом p с текущим идентификатором cip, то алгоритм завершается после этого круга с winq = cip для всех q.
Доказательство. Сообщение пропускается всеми процессами и, в конце концов, его получает p. Процесс p обнаруживает, что acnp = cip и посылает по кольцу сообщение , вследствие чего все процессы выходят из основного цикла с winp = acnp.
Алгоритм завершается в каждом процессе и все процессы согласовывают идентификатор лидера (в переменной winp); этот процесс находится в состоянии лидер, а остальные - в состоянии проигравший.
Всего происходит не более ?logN?+1 обходов круга, в каждом из которых передается ровно 2N сообщений, что доказывает, что сложность сообщений ограничена 2N logN + O(N). Теорема 7.7 доказана.
Dolev и др. удалось улучшить свой алгоритм до 1.5N logN, после чего
Petersen получил алгоритм, использующий только 1.44N logN сообщений. Этот алгоритм снова был улучшен Dolev и др. до 1.356N logN. Верхняя граница в
1.356N logN считалась наилучшей для выбора на кольцах более 10 лет, но была улучшена до 1.271N logN Higham и Przytycka [HP93].

7.2.3 Вывод нижней границы
В этом подразделе будет доказана нижняя граница сложности выбора на однонаправленных кольцах. Т.к. выбор можно провести за одно выполнение децентрализованного волнового алгоритма, нижняя граница сложности децентрализованных волновых алгоритмов для колец будет получена как заключение.
Результат получен Pachl, Korach и Rotem [PKR84] при следующих предположениях.
Граница доказывается для алгоритмов, вычисляющих наименьший идентификатор.
Если существует лидер, наименьший идентификатор может быть вычислен с помощью N сообщений, а если наименьший идентификатор известен хотя бы одному процессу, процесс с этим идентификатором может быть выбран опять же за N сообщений. Следовательно, сложность задач выбора и вычисления наименьшего идентификатора различаются не более чем на N сообщений.
Кольцо является однонаправленным.
Процессам не известен размер кольца.
Предполагается, что каналы FIFO. Это предположение не ослабляет результат, потому что сложность не-FIFO алгоритмов не лучше сложности FIFO алгоритмов.
Предполагается, что все процессы являются инициаторами. Это предположение не ослабляет результат, потому что оно описывает ситуацию, возможную для каждого децентрализованного алгоритма.
Предполагается, что алгоритмы управляются сообщениями; т.е. после отправления сообщений при инициализации алгоритма, процесс посылает сообщения в дальнейшем только после получения очередного сообщения. Т.к. рассматриваются асинхронные системы, общие алгоритмы не достигают лучшей сложности, чем алгоритмы, управляемые сообщениями. Действительно, если A - асинхронный алгоритм, то управляемый сообщениями алгоритм B может быть построен следующим образом. После инициализации и после получения любого сообщения B посылает максимальное количество сообщений, которое можно послать в A, не получая при этом сообщений, и только затем получает следующее сообщение. Алгоритм B не только управляется сообщениями, но кроме того, каждое вычисление B является возможным вычислением A (возможно, при довольно пессимистическом распределении задержек передачи сообщений).
Три последних предположения устраняют недетерминизм системы. При этих предположениях каждое вычисление, начинающееся с данной начальной конфигурации, содержит одно и то же множество событий.
В этом разделе через s = (s1, ..., sN), t и т.п. обозначаются последовательности различных идентификаторов процессов. Множество всех таких последовательностей обозначено через D, т.е. D = {(s1, ..., sk): si ?
P и i ? j ? si ? sj}. Длина последовательности s обозначается через len(s), а конкатенация последовательностей s и t обозначается st.
Циклическим сдвигом s называется последовательность s's'', где s = s''s' ; она имеет вид si, ..., sN, s1, ..., si-1. Через CS(s) (cyclic shift - циклический сдвиг) обозначено множество циклических сдвигов s, и естественно |CS(s)| = len(s).
Говорят, что кольцо помечено последовательностью (s1, ..., sN), если идентификаторы процессов с s1 по sN расположены на кольце (размера N) в таком порядке. Кольцо, помеченное s также называют s-кольцом. Если t - циклический сдвиг s, то t-кольцо совпадает с s-кольцом.
С каждым сообщением, посылаемым в алгоритме, свяжем последовательность идентификаторов процессов, называемую следом (trace) сообщения. Если сообщение m было послано процессом p до того, как p получил какое-либо сообщение, след m равен (p). Если m было послано процессом p после того, как он получил сообщение со следом s = (s1, ..., sk), тогда след m равен
(s1, ..., sk, p). Сообщение со следом s называется s-сообщением. Нижняя граница будет выведена из свойств множества всех следов сообщений, которые могут быть посланы алгоритмом.
Пусть E - подмножество D. Множество E полно (exhaustive), если
E префиксно замкнуто, т.е. tu ? E ? t ? E ; и
E циклически покрывает D, т.е. ? s ? D: CS(s) ? E ? ?.
Далее будет показано, что множество всех следов алгоритма полно. Для того, чтобы вывести из этого факта нижнюю границу сложности алгоритма, определены две меры множества E. Последовательность t является последовательной цепочкой идентификаторов в s-кольце, если t - префикс какого-либо r (
CS(s). Обозначим через M(s,E) количество последовательностей в E, которые удовлетворяют этому условию в s-кольце, а через Mk(s,E) - количество таких цепочек длины k;
M(s,E) = |{ t ? E : t - префикс некоторого r ? CS(s) }| и
Mk(s,E) = |{ t ? E : t - префикс некоторого r ? CS(s) и len(t) = k}|.
В дальнейшем, допустим, что A - алгоритм, который вычисляет наименьший идентификатор, а EA - множество последовательностей s таких, что s- сообщение посылается, когда алгоритм A выполняется на s-кольце.
Лемма 7.10 Если последовательности t и u содержат подстроку s и s- сообщение посылается, когда алгоритм A выполняется на t-кольце, то s- сообщение также посылается, когда A выполняется на u-кольце.
Доказательство. Посылка процессом sk s-сообщения, где s = (s1, ..., sk), каузально зависит только от процессов с s1 по sk. Их начальное состояние в u-кольце совпадает с состоянием в t-кольце (напоминаем, что размер кольца неизвестен), и следовательно совокупность событий, предшествующих посылке сообщения, также выполнима и в u-кольце.
Лемма 7.11 EA - полное множество.
Доказательство. Чтобы показать, что EA циклически замкнуто, заметим, что если A посылает s-сообщение при выполнении на s-кольце, тогда для любого префикса t последовательности s A сначала посылает t-сообщение на s- кольце. По Лемме 7.10 A посылает t-сообщение на t-кольце, следовательно t ?
EA.
Чтобы показать, что EA циклически покрывает D, рассмотрим вычисление A на s- кольце. Хотя бы один процесс выбирает наименьший идентификатор, откуда следует (аналогично доказательству Теоремы 6.11), что этот процесс получил сообщение со следом длины len(s). Этот след является циклическим сдвигом s и принадлежит E.
Лемма 7.12 В вычислении на s-кольце алгоритм A посылает не менее M(s,EA) сообщений.
Доказательство. Пусть t ? EA - префикс циклического сдвига r последовательности s. Из определения EA, A посылает t-сообщение в вычислении на t-кольце, а следовательно также и на r-кольце, которое совпадает с s-кольцом. Отсюда, для каждого t из {t ? E: t - префикс некоторого r ? CS(s)} в вычислении на s-кольце посылается хотя бы одно t- сообщение, что доказывает, что количество сообщений в таком вычислении составляет не менее M(s,E).
Для конечного множества I идентификаторов процессов обозначим через Per(I) множество всех перестановок I. Обозначим через aveA(I) среднее количество сообщений, используемых A во всех кольцах, помеченных идентификаторами из
I, а через worA(I) - количество сообщений в наихудшем случае. Из предыдущей леммы следует, что если I содержит N элементов, то
[pic]; и
[pic].
Теперь нижнюю границу можно вывести путем анализа произвольных полных множеств.
Теорема 7.13 Средняя сложность однонаправленного алгоритма поиска наименьшего идентификатора составляет не менее N*?N.
Доказательство. Усредняя по всем начальным конфигурациям, помеченным множеством I, мы находим
[pic]
Зафиксируем k и отметим, что для любого s ( Per(I) существует N префиксов циклических сдвигов s длины k. N! перестановок в Per(I) увеличивают количество таких префиксов до N*N!. Их можно сгруппировать в N*N!/k групп, каждая из которых содержит по k циклических сдвигов одной последовательности. Т.к. EA циклически покрывает D, EA пересекает каждую группу, следовательно [pic].
Отсюда следует[pic][pic].
Этот результат означает, что алгоритм Чанга-Робертса оптимален, когда рассматривается средний случай. Сложность в наихудшем случае больше или равна сложности в среднем случае, откуда следует, что наилучшая достижимая сложность для наихудшего случая находится между N*?N ? 0.69N logN и ?
0.356N logN.
Доказательство, данное в этом разделе, в значительной степени полагается на предположения о том, что кольцо однонаправленное и его размер неизвестен.
Нижняя граница, равная 0.5N*?N была доказана Bodlaender [Bod88] для средней сложности алгоритмов выбора на двунаправленных кольцах, где размер кольца неизвестен. Чтобы устранить недетерминизм из двунаправленного кольца, рассматриваются вычисления, в которых каждый процесс начинается в одно и то же время и все сообщения имеют одинаковую задержку передачи. Для случая, когда размер кольца известен, Bodlaender [Bod91a] вывел нижнюю границу, равную 0.5N logN для однонаправленных колец и (1/4-?)N*?N для двунаправленных колец (обе границы для среднего случая).
В итоге оказывается, что сложность выбора на кольце не чувствительна практически ко всем предположениям. Независимо от того, известен или нет размер кольца, однонаправленное оно или двунаправленное, рассматривается ли средний или наихудший случай, - в любом случае сложность составляет
?(N logN). Существенно важно, что кольцо асинхронно; для сетей, где доступно глобальное время, сложность сообщений ниже, как будет показано в
Главе 11.
Т.к. лидер может быть выбран за одно выполнение децентрализованного волнового алгоритма, из нижней границы для выбора следует нижняя граница для волновых алгоритмов.
Заключение 7.14 Любой децентрализованный волновой алгоритм для кольцевых сетей передает не менее ?(N logN) сообщений, как в среднем, так и в наихудшем случае.

[pic]
Рис.7.8

7.3 Произвольные Сети
Теперь изучим проблему выбора для сетей произвольной, неизвестной топологии без знания о соседях. Нижняя граница ?(N logN+(E() сообщений будет показана ниже. Доказательство объединяет идею Теоремы 6.6 и результаты предыдущего подраздела. В Подразделе 7.3.1 будет представлен простой алгоритм, который имеет низкую сложность по времени, но высокую сложность по сообщениям в худшем случае. В Подразделе 7.3.2 будет представлен оптимальный алгоритм для худшего случая.

Теорема 7.15 Любой сравнительный алгоритма выбора для произвольных сетей имеет (в худшем и среднем случае) сложность по сообщения по крайней мере
?(Nlog N + (E().

Рисунок 7.8 вычисление с двумя ЛИДЕРАМИ.

Доказательство. Граница ?(N log N + (E() является нижней, потому что произвольные сети включают кольца, для которых нижняя граница ?(N logN).
Чтобы видеть, что (E( сообщений является нижней границей, даже в лучшем из всех вычислений, предположим что, алгоритм выбора имеет вычисление С на сети G, в котором обменивается менее чем (E( сообщений ; см. Рисунок 7.8.
Построим сеть G ', соединяя две копии G одним ребром между узлами, связанными ребром , которое не используется в C. Тождественные части сети имеют тот же самый относительный порядок как и в G. Вычисление С может моделироваться одновременно в обеих частях G ', выдавая вычисление, в котором два процесса станут избранными. (

Заключение 7.16 Децентрализованный волновой алгоритм для произвольных сетей без знания о соседях имеет сложность по сообщения по крайней мере ?(NlogN +
(E().

7.3.1 Вырождение и Быстрый Алгоритм
Алгоритм для выбора лидера может быть получен из произвольного централизованного волнового алгоритма применением преобразования называемого вырождением. В полученном алгоритме выбора каждый инициатор начинает отдельную волну; все сообщения волны, начатой процессом p должны быть помечены идентификатором p, чтобы отличить их от сообщений различных волн. Алгоритм гарантирует, что, независимо от того, сколько волн начато, только одна волна будет бежать к решению, а именно, волна самого маленького инициатора. Все другие волны будут прерваны прежде, чем решение может иметь место.
Для волнового алгоритма A, алгоритм выбора Ex(A) следующий. В каждый момент времени каждый процесс активен не более чем в одной волне ; эта волна - текущая активная волна, обозначенная caw , с начальным значением udef.
Инициаторы выбора действуют, как будто они начинают волну и присваивают caw их собственный идентификатор . Если сообщение некоторой волны, скажем волны, которую начал q, достигает p, p обрабатывает сообщение следующим образом.

var cawp : P init udef ; (* текущая активная волна *) recp : integer init 0 ; (* число полученных (tok, cawp (
*) fatherp : P init udef ; (* отец в волне cawp *) lrecp : integer init 0 ; (* число полученных (ldr, . ( *) winp : P init udef; (* идентификатор лидера*) begin if p is initiator then begin cawp := p; forall q ( Neighp do send ( tok, p( to q end; while lrecp < #Neighp do begin receive msg from q ; if msg = ( ldr, r ( then begin if lrecp = 0 then forall q (. Neighp do send ( ldr, r ( to q ; lrecp := lrecp + 1 ; winp := r end else (*—9Y(=ЈS?У'ѕ?Ў.??Ѕ2~>3K cawp, сообщение просто игнорируется, эффективно приводя волну q к неудаче. Если с q = cawp, с сообщением поступают в соответствии с волновым алгоритмом. Если q < cawp или cawp = udef, p присоединяется к выполнению волны q, повторно присваивая переменным их начальные значения и присваивая cawp значение q. Когда волна, начатая q выполняет событие решения (в большинстве волновых алгоритмов, это решение всегда имеет место в q), q будет избран. Если волновой алгоритм такой, что решающий узел не обязательно равен инициатору, то решающий узел информирует инициатора через дерево охватов(остовное дерево) как определено в Lemma 6.3. При этом требуется не более N - 1 сообщений; мы игнорируем их в следующей теореме.

Теорема 7.17. Если А - централизованный волновой алгоритм, использующий М сообщений на одну волну, алгоритм Ex(A), выбирает лидера использую не более
NM сообщений.

Доказательство. Пусть p0 самый маленький инициатор. К волне, начатой p0 немедленно присоединяются все процессы, которые получают сообщение этой волны, и каждый процесс заканчивает эту волну, потому что нет волны с меньшим идентификатором, для которой процесс прервал бы выполнение волны p0. Следовательно, волна p0 бежит к завершению, решение будет иметь место, и p0 становится лидером.
Если p не инициатор, никакая волна с идентификатором p не начнется, следовательно p не станет лидером. Если p ( p0 - инициатор, волна с идентификатором p будет начата, но решению в этой волне будет предшествовать событие посылки от p0 (для этой волны) , или имееть место в p0 (Lemma 6.4). Так как p0 никогда не выполняет событие посылки или внутреннее событие волны с идентификатором p, такое решение не имеет место, и p не избран.
Не более N волн начаты, и каждая волна использует по крайней мере М сообщений, что приводит к полной сложности к NM. (

Более тонким вопросом является оценка сложности по времени алгоритма Ex(A).
Во многих случаях это будет величина того же порядока , что и сложность по времени алгоритма A, но в некоторых неудачных случаях, может случиться, что инициатор с самым маленьким идентификатором начинает волну очень поздно. В общем случае можно показать сложность по времени O (Nt) (где t - сложность по времени волнового алгоритма ), потому что в пределах t единиц времени после того, как инициатор p начинает волну, волна p приходит к решению или начинается другая волна.
Если вырождение применяется к кольцевому алгоритму, получаем алгоритм Chang-
Poberts; см. Упражнение 7.9. Алгоритм 7.9 является алгоритмом выбора полученным из алгоритма эха. Чтобы упростить описание, принимается что udef > q для всех q( P. При исследовании кода, читатель должен обратить внимание, что после получения сообщения (tok, r( с r < cawpp, оператор If с условием r = cawp также выполняется, вследствие более раннего присваивания cawp. Когда выбирается процесс p (получает (tok, p( от каждого соседа), p посылает сообщение (ldr, p( всем процессам, сообщая им, что p - лидер и заставляя их закончить алгоритм.

7.3.2 Алгоритм Gallager-Humblet-Spira
Проблема выбора в произвольных сетях тесно связана с проблемой вычисления дерева охватов с децентрализованным алгоритмом, как выдно из следующего рассуждения. Пусть CE сложность по сообщениям проблемы выбора и CТ сложность вычисления дерева охватов. Теорема 7.2 подразумевает, что
CE(CT+O(N), и если лидер доступен, дерево охватов, может быть вычислено используя 2((( сообщений в алгоритме эха, который подразумевает что CT ( CE
+ 2(((. Нижняя граница CE (теорема 7.15) подразумевает, что две проблемы имеют одинаковый порядок сдожности, а именно, что они требуют по крайней мере ?(N log N + E) сообщений.
Этот подраздел представляет Gallager-Humblet-Spira (GHS), алгоритм для вычисления (минимального) дерева охватов, используя 2((( + 5N log N сообщений. Это показывает, что CE и CТ величины порядка ( (N log N + E).
Этот алгоритм был опубликован в [GHS83]. Алгоритм может быть легко изменен
(как будет показано в конце этого подраздела) чтобы выбрать лидера в ходе вычисления, так, чтобы отдельный выбор как показано в выше не был необходим.
GHS алгоритм полагается на следующие предположения.
(1) Каждое ребро e имеет уникальный вес w (e). Предположим здесь, что w (e)
- реальное число, но целые числа также возможны как веса ребер.
Если уникальные веса ребер не доступны априоре, каждому краю можно давать вес, который сформирован из меньшего из двух первых идентификаторов узлов, связанных с ребром. Вычисление веса края таким образом требует, чтобы узел знал идентификаторы соседей, что требует дополнительно 2((( сообщений при инициализации алгоритма.
(2) Все узлы первоначально находятся в спящем состоянии и просыпаются прежде, чем они начинают выполнение алгоритма. Некоторые узлы просыпаются спонтанно (если выполнение алгоритма вызвано обстоятельствами, встречающимися в этих узлах), другие могут получать сообщение алгоритма, в то время как они все еще спят. В последнем случае узел получающий сообщение сначала выполняет локалбную процедуру инициализации, а затем обрабатывает сообщение.

Минимальное дерево охватов. Пусть G = (V, E) взвешенный граф, где w {e) обозначает вес ребра e. Вес дерева охватов T графа G равняется сумме весов
N-1 ребер, содержащихся в T, и T называется минимальным деревом охватов, или MST, (иногда минимальным по весу охватывающим деревом) если никакое дерево не имеет меньший вес чем T. В этом подразделе предполагаем, что каждое ребро имеет уникальный вес, то есть, различные ребра имеют различные веса, и это - известный факт что в этом случае имеется уникальное минимальное дерево охватов.

Рекомендуем скачать другие рефераты по теме: педагогические рефераты, реферат машини.



Предыдущая страница реферата | 25  26  27  28  29  30  31  32  33  34  35 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки