Распределенные алгоритмы (стр. 50 из 85)

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/6.17	произвольная	C	нет	4|E|	2N-2
Со знанием соседей	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.

Рис.6.21 Две сети диаметра два и степени три.

Вычисление сумм с помощью алгоритма обхода. Если A - алгоритм обхода, сумма по всем входам может быть вычислена следующим образом. Процесс p содержит переменную j_p, инициализированную значением входа p. Маркер содержит дополнительное поле s. Всякий раз, когда p передает маркер, p выполняет следующее:

s := s + j_p ; j_p := 0

и затем можно показать, что в любое время для каждого ранее пройденного процесса p j_p = 0 и s равно сумме входов всех пройденных процессов. Следовательно, когда алгоритм завершается, s равно сумме по всем входам.

Вычисление суммы с использованием остовного дерева. Некоторые волновые алгоритмы предоставляют для каждого события принятия решения d_p в процессе p остовное дерево с корнем в p, по которому сообщения передаются по направлению к p. Фактически, каждое вычисление любого волнового алгоритма содержит такие остовные деревья. Однако, может возникнуть ситуация, когда процесс q посылает несколько сообщений и не знает, какие из его исходящих ребер принадлежат к такому дереву. Если процессы знают, какое исходящее ребро является их родителем в таком дереве, дерево можно использовать для вычисления сумм. Каждый процесс посылает своему родителю в дереве сумму всех входов его поддерева.

Этот принцип может быть применен для древовидного алгоритма, эхо-алгоритма и фазового алгоритма для клик. Древовидный алгоритм легко может быть изменен так, чтобы включать сумму входов T_pq в сообщение, посылаемое от p к q. Процесс, который принимает решение, вычисляет окончательный результат, складывая величины из двух сообщений, которые встречаются на одном ребре. Фазовый алгоритм изменяется так, чтобы в каждом сообщении от q к p пересылался вход q. Процесс p складывает все полученные величины и свой собственный вход, и результат является правильным ответом, когда p принимает решение. В эхо-алгоритме входы могут суммироваться с использованием остовного дерева T, построенного явным образом во время вычисления; см. Упражнение 6.15.