Реферат: Распределенные алгоритмы
send < tlist, LÈ{p} > to q
end
else if p - инициатор
then decide
else send < tlist, LÈ{p} > to fatherp
end
Алгоритм 6.18 Алгоритм поиска в глубину со знанием соседей.
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.1.5 было показано, что за одну волну можно вычислить инфимум по входам всех процессов. Вычисление инфимума может быть использовано для вычисления коммутативного, ассоциативного и идемпотентного оператора, обобщенного на входы, такого как минимум, максимум, и др. (см. Заключение 6.14). Большое количество функций не вычислимо таким образом, среди них - сумма по всем входам, т.к. оператор суммирования не идемпотентен. Суммирование входов может быть использовано для подсчета процессов с определенным свойством (путем присваивания входу 1, если процесс обладает свойством, и 0 в противном случае), и результаты этого подраздела могут быть распространены на другие операторы, являющиеся коммутативными и ассоциативными, такие как произведение целых чисел или объединение мультимножеств.
Оказывается, не существует общего метода вычисления сумм с использованием волнового алгоритма, но в некоторых случаях вычисление суммы возможно. Например, в случае алгоритма обхода, или когда процессы имеют идентификаторы, или когда алгоритм порождает остовное дерево, которое может быть использовано для вычисления.
Невозможность существования общего метода. Невозможно дать общий метод вычисления сумм с использованием произвольного волнового алгоритма, подобного методу, использованному в Теореме 6.12 для вычисления инфимумов. Это может быть показано следующим образом. Существует волновой алгоритм для класса сетей, включающего все неориентированные анонимные (anonymous) сети диаметра два, а именно, фазовый алгоритм (с параметром D=2). Не существует алгоритма, который может вычислить сумму по всем входам, и который является правильным для всех неориентированных анонимных (anonymous) сетей диаметра два. Этот класс сетей включает две сети, изображенные на Рис.6.21. Если предположить, что каждый процесс имеет вход 1, ответ будет 6 для левой сети и 8 - для правой. Воспользовавшись технологией, представленной в Главе 9, можно показать, что любой алгоритм даст для обеих сетей один и тот же результат, следовательно, будет работать неправильно. Детальное доказательство оставлено читателю в Упражнении 9.7.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
