Теормин, страница 4

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

R3. Всякий раз, когда процесс получает маркер, он возвращает его назад по тому же каналу, если это не противоречит правилам R1 и R2.

Теорема о классическом алгоритме обхода в глубину

Классический алгоритм поиска в глубину строит остовное дерево поиска в глубину, используя при этом 2|E| обменов сообщениями.

Алгоритм Авебаха

Когда маркер впервые достается процессу p (для инициатора — в момент запуска алгоритма), p оповещает каждого соседа r кроме родительской вершины, отправляя ему сообщение (vis).

Маркер не передается, до тех пор, пока p не получит сообщение (ack) от всех своих соседей. Это гарантирует, что каждый сосед r процесса p осведомлен к моменту отправления маркера процессом p о том, что этот маркер уже побывал у p. Когда позднее маркер достигнет r, процесс r уже не будет отправлять маркер процессу p , если только p не является родительской вершиной для r

Теорема об алгоритме Авербаха

Алгоритм Авербаха строит дерево поиска в глубину за 4N — 2 единиц времени, проводя при этом 4|E| обменов сообщениями.

Алгоритм Сидона.

Основная идея:

1. Один инициатор посылает токен в начальный момент времени

2. mrc – это обратный указатель к указателю father, т.е. указатель на потомка.

3. Сообщение vis шлётся всем, при первом получении узлом токена

4. Если какой-то узел получил сообщение vis от другого узла, то это направление запоминается и блокируется, чтобы туда нельзя было больше послать токен (ибо там токен уже побывал, его туда слать незачем)

5. Аналогично алгоритму поиска в глубину – мы пытаемся вернуть токен как можно быстрее тому, от кого последний раз его получили, чтобы в итоге наше дерево получилось деревом поиска в глубину.

6. Если так получится, что токен и vis встретятся в канале друг на встречу другу (такое теоретически может случиться (из-за долгой задержки vis в канале)), то такое отловится первыми «if» в функциях обработки второй и третей. В этом случае токен будет выкинут, а данный vis станет новым токеном и продолжет ходить по графу.

Теорема об алгоритме Сидона

Алгоритм Сидона строит DFS дерево за 2N — 2 единицы времени, используя 4|E| обменов сообщениями

1. Задача избрания лидера. Основные определения и допущения. Волновые алгоритмы избрания лидера. Выборы лидера на дереве. Выборы в кольцах. Алгоритм Ле-Ланна. Алгоритм Ченя - Робертса. Алгоритм Петерсона/Долева-Клейва-Роде. Эффект угасания.

Задача избрания лидера состоит в том, чтобы, из конфигурации, в которой все процессы пребывают в одном и том же состоянии, достичь такой конфигурации, в которой ровно один процесс будет находиться в состоянии leader , а все остальные процессы — в состоянии lost .

Алгоритмом избрания лидера называется алгоритм, который обладает следующими свойствами.

1. Каждый процесс наделен одним и тем же локальным алгоритмом.

2. Алгоритм является децентрализованным, т.е. вычисление может быть инициировано произвольным непустым подмножеством процессов.

3. Алгоритм достигает заключительной конфигурации в каждом вычислении, и в каждой заключительной конфигурации существует ровно один процесс, который находится в состоянии leader а все остальные процессы при этом пребывают в состоянии lost.

Допущения для задачи избрания лидера:

1. Система вполне асинхронна

2. Каждый процесс опознается по уникальному имени, и это имя изначально известно самому процессу.

3. Каждое сообщение может содержать O(w) бит.

Выборы лидера в дереве – сначала идёт процесс побудки, а потом все листья инициируют древесный волновой алгоритм.

Теорема 8.1.

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

Выбор лидера в кольцах:

1. Алгоритм Ле-Ланна – O(N²) обменов за O(N) времени – каждый инициатор вычисляет список отличительных признаков всех инициаторов, после чего лидером избирается инициатор с наименьшим признаком.

2. Алгоритм Ченя-Робертса – O(N*logN) – в среднем и O(N²) – в худшем, если все процессы инициаторы, то в среднем ≈ 0.69*N*log N

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

1. Алгоритм Петерсона/Долева-Клейва-Роде – O(N*logN) – для однонаправленного кольца.

Суть в том, что признаки беруться среди вершины и её соседей, и выбирается тот, чей признак минимален, тем самым сокращение на каждом шаге – туре, происходит в 2 раза (экспоненциальное падение).

(лучше картинка со слайда 35)

1. Теоретическая нижняя оценка ≈ 0.34*N*log N

Теорема 8.6.

Если

• кольцо — однонаправленное,

• процессы не осведомлены о размерах кольца,

• в каналах поддерживается очередность сообщений,

• все процессы являются инициаторами,

то сложность в среднем всякого алгоритма избрания лидера N будет не меньше, чем N•Н_N, где H_N = .

Теорема 8.7.

Всякий алгоритм избрания лидера на основе сравнения для произвольных сетей имеет сложность (и в среднем, и в наихудшем случае) не меньшую, чем Ω(|E| + N*logN)

Следствие.

Всякий децентрализованный волновой алгоритм для произвольных сетей без предварительной осведомленности о соседях имеет сложность по числу обменов сообщениями, не меньшую чем Ω(|E| + N*logN)

Эффект угасания

Алгоритм избрания лидера можно получить из произвольного волнового алгоритма при помощи конструкции, которая носит название “угасание”.

Каждый инициатор запускает отдельную волну. Чтобы отличаться от сообщений других волн, сообщения, движущиеся по волне, запущенной процессом p, должны быть помечены отличительным признаком процесса p.

Данный алгоритм гарантирует, что независимо от количества запущенных волн только одна волна приведет к решению, а именно, та волна, которую запустил инициатор с самым младшим отличительным признаком. Все остальные волны будут прерваны еще до того, как будет принято решение.

Суть в том, что каждый элемент графа пропускает только ту волну через себя, которая наилучшая из тех, что он видел, любую другую он через себя не пропустит, в итоге только та волна закончит своё действие, которую пропустили все элементы графа, т.е. наилучшая, остальные волны никогда не завершатся.

1. Задача избрания лидера. Нижние оценки сложности. Оптимальные выборы. Алгоритм Галладжера-Хамблета-Спиры (GHS). Глобальное описание алгоритма GHS. Подробное описание алгоритма GHS. Алгоритм Корача-Каттена-Морана.

Утверждение

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

Из этой теоремы следует, что C_E < C_T + O(N)

Если в нашем распоряжении есть лидер, то остовное дерево можно построить с использованием 2|E| обменов сообщениями при помощи централизованного алгоритма обхода сети.

Поэтому справедливо неравенство C_T < C_E + 2|E|

Таким образом, для оптимального выбора лидера необходимо и достаточно уметь оптимально строить остовное дерево.

Алгоритм Галладжера-Хамблета-Спиры (GHS)

Допущения:

1. Каждому ребру приписан уникальный вес ш(в) . Все веса ребер линейно упорядочены.

2. Все узлы пребывают первоначально в состоянии оцепенения и пробуждаются перед началом выполнения алгоритма. Некоторые узлы пробуждаются самопроизвольно, другие могут получить сообщение по ходу работы алгоритма, еще пребывая в оцепенении. При этом узел, получивший сообщение, вначале выполняет процедуру локальной инициализации, а затем приступает к обработке этого сообщения.

Вес остовного дерева T в графе G полагается равным сумме весов всех N — 1 ребер, входящих в состав T. При этом T называется минимальным остовным деревом, или сокращенно MST, если ни одно остовное дерево не имеет вес меньший, чем T.

Утверждение 9.1.

Если все веса ребер попарно различны, то существует только одно MST.

Фрагмент - произвольное поддерево MST. Ребро e называется исходящим ребром фрагмента F, если один из концов e принадлежит F, а другой нет.

Утверждение 9.2.

Если F является фрагментом, и e - ребро наименьшего веса, исходящее из F, то F U {е} также является фрагментом.

Глобальное описание алгоритма GHS:

1. Формируется такое семейство фрагментов, что объединение их содержит все узлы сети.

2. Первоначально это семейство состоит из всех узлов сети, каждый из которых рассматривается как граф с одним узлом.

3. Узлы всякого фрагмента вступают во взаимодействие с целью выявления исходящего из фрагмента ребра с наименьшим весом.

4. Как только будет определено исходящее из фрагмента ребро с наименьшим весом, данный фрагмент соединяется с другим фрагментом путем добавления этого исходящего ребра, которое строится в результате взаимодействия этих двух фрагментов.

Для эффективной реализации нужны:

1. Имя фрагмента

2. Соединение старшего и младшего фрагментов (ранг результирующего фрагмент равен рангу большего из фрагментов, если фрагменты имели одинаковый ранг, то новый ранг будет на 1 больше)

3. Ранги фрагментов

Утверждение 9.3.

Если соблюдать указанные выше правила соединения фрагментов, то суммарно во всех процессах перемена имени или ранга случится не более N*log N раз.

Подробное описание алгоритма GHS <см. слайды с 41 лекции 10>

Теорема.

Алгоритм GHS вычисляет минимальное остовное дерево, используя при этом не более (5N*log N + 2|E|) обменов сообщениями.

Алгоритм Корача-Каттена-Морана – алгоритм метода угасания, но с оптимизациями.

Чтобы «гасить» обходы, алгоритм оперирует на разных уровнях, подобно тому как алгоритм Петерсона/Долев-Клейва-Роде разбивает свое вычисление на туры.

Если запущены по крайней мере два обхода, то один из маркеров рано или поздно достигнет того процесса, в котором уже успел побывать другой. Тогда обход, который проводится при помощи вновь прибывшего маркера, будет прерван.

Цель работы алгоритма состоит в том, чтобы привести две маркера вместе в один процесс, где они будут подавлены, и после этого может начаться новый обход.

1. Задача обнаружения завершения вычислений. Алгоритм Дейкстры-Шолтена. Алгоритм Шави-Франчеза. Алгоритм Сафры. Алгоритм возвращения кредитов.

Вычисление завершается явно, если все процессы пребывают в заключительном состоянии. Тогда говорят, что произошло завершение работы алгоритма.

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

Упрощения для задачи обнаружения завершения вычислений.

1. Активный процесс становится пассивным только после осуществления внутреннего события.

2. Процесс всегда становится активным после получения сообщения.

3. Внутренние события, приводящие к тому, что процесс p становится пассивным, — это единственно возможные внутренние события в процессе p.

Теорема 1

Будем полагать, что предикат term (Y) обращается в истину на всякой конфигурации y, на которой не может произойти ни одного события в базовом вычислении.

term(Y) <=> (Для любого p принадлежащего P: state_p = passive) && (Для любого pq принадлежащего E: Mpq не содержит сообщения <mes>)

Задача обнаружения вычисления заключается в присоединении к системе контрольного алгоритма, который приведет все процессы в заключительные состояния, после того как базовое вычисление достигнет заключительной конфигурации.

Контрольный алгоритм состоит из алгоритма обнаружения завершения вычисления и алгоритма оповещения о завершении вычисления.

Требования к алгоритму обнаружения завершения вычисления:

1. Невмешательство

2. Живость - если выполняется условие term, то алгоритм оповещения Announce должен быть вызван спустя конечное число шагов.

3. Безопасность - если вызван алгоритм Announce, то конфигурация должна удовлетворять условию term.

Теорема 2.

Для всякого алгоритма обнаружения завершения вычисления существует такое базовое вычисление, осуществляющее M обменов базовыми сообщениями, для обнаружения завершения которого рассматриваемый алгоритм совершает не менее M обменов контрольными сообщениями.

Теорема 3.

Для обнаружения завершения децентрализованного базового вычисления в худшем случае требуется совершить обмен не менее чем W контрольными сообщениями, где W — коммуникационная сложность волнового алгоритма.

Алгоритм Дейкстры-Шолтена

Условия применения:

• базовый алгоритм централизованный;

• топология сети произвольная;

• сеть неориентированная;

• контрольный алгоритм централизованный и инициируется в том же процессе, что и базовый алгоритм.

Алгоритм обнаружения завершения строит и постоянно обновляет дерево вычислений T = (V_T, E_T), которое обладает следующими двумя свойствами.

1. Граф T либо является пустым, либо представляет собой ориентированное дерево, корнем которого является вершина р₀

2. Множество V_T включает все активные процессы и все базовые сообщения, находящиеся на этапе пересылки.

Инициатор р₀ вызывает процедуру Announce, если р₀ yt принадлежит V_T; согласно первому свойству граф T в таком случае является пустым, а согласно второму свойству это означает, что вычисление завершилось.

Когда процесс p отправляет базовое сообщение <mes>, это сообщение добавляется к дереву в качестве вершины <mes>, причем родительской вершиной для нее становится процесс p.