йо-йо (алгоритм)

Yo-Yo — распределенный алгоритм, направленный на поиск минимума и выбор лидера в обобщенном связном неориентированном графе . В отличие от Mega-Merger, он имеет тривиальную процедуру завершения и анализа затрат.

Введение

Йо-йо представил Никола Санторо. Это происходит путем последовательного исключения и метода сокращения графа, называемого обрезкой . Алгоритм разделен на фазу предварительной обработки, за которой следует циклическое повторение прямой фазы, называемой «Йо-», и обратной фазы, называемой «-Йо».

Предварительные условия

Йо-Йо строит избирает минимального лидера на следующих условиях:

• Полная надежность: ни одно сообщение не теряется при передаче.
• Начальные уникальные значения (ID): каждый узел имеет уникальный идентификатор.
• Двунаправленные каналы связи: каждое ребро является двунаправленным, связь может передаваться в обоих направлениях.

Никаких дополнительных ограничений не требуется.

Алгоритм

Предварительная обработка

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

• Источники: узлы с исходящими узлами, но без входящих узлов. Это наименьшее количество узлов в каждом районе.
• Промежуточные узлы: узлы как с исходящими, так и с входящими ребрами. Это не наименьшие и не наибольшие узлы в каждом районе.
• Приемники: узлы с входящими ребрами, но без исходящих ребер. Это самые большие узлы в каждом районе.

они-

Йо- фаза, значения источников смещаются вниз к стокам.

Фаза «Йо-» инициируется источниками. Источник отправляет свой идентификатор через входящие ребра и ждет. Промежуточные узлы ждут получения соответствующих идентификаторов от каждого из своих входящих ребер. Как только все ожидаемые значения собраны, выполняется минимальное вычисление, и минимальный идентификатор передается через исходящие ребра. На этом этапе раковины пассивны.

Сообщения отправляются через ориентированные ребра и достигают приемников, что запускает фазу «-Yo».

- Они

Фаза -Йо предполагает положительные/отрицательные ответы.

Приемники инициируют фазу «-Yo», вычисляя минимальный полученный идентификатор и отправляя положительное ДА или отрицательное НЕТ через свои входящие ребра. ДА через отправляется через ребра, несущие минимальный вычисленный идентификатор, НЕТ — оставшиеся ребра. Сообщения поднимаются по структуре к источникам: источники с хотя бы одним входящим НЕТ становятся мертвыми и теряют статус кандидата.

Фаза «-Yo» также включает фазу реструктуризации, на которой источники-промежуточные-поглотители приспосабливаются к источникам, не являющимся кандидатами. Ребра, несущие НЕТ, меняются местами, и кандидаты-проигравшие на текущем этапе становятся либо стоками, либо промежуточными узлами.

Обрезка

Обрезка — это метод оптимизации, применяемый на этапе «-Yo», и его сообщение обычно включается в положительный/отрицательный ответ. Он удаляет ненужные ребра и узлы. Первые представляют собой ребра, которые получают одно и то же значение от $u>1$ входящие ребра: тривиально $u$ бесполезны и обрезаются узлом. Такие ребра становятся мертвыми и игнорируются в следующих итерациях. Последний вместо этого уменьшает количество узлов за счет удаления унарных приемников, то есть приемников с $v=1$ входящий край. Эти ребра будут вынуждены отправить обратно (единственный) полученный минимум с ответом YES , следовательно, они не выполняют никаких вычислений, полезных для нахождения минимума.

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

Расходы

Фаза предварительной обработки состоит из обмена через каждое ребро двух узлов, инцидентных на ребре. Таким образом, мы имеем стоимость $\sum _{v\in V}deg(v)=2m$. Фазы Йо-Йо состоят из сканирования структуры вперед и назад, следовательно, $2m_{i}$ сообщения, где $m_{i}$ — количество текущих активных ребер. Количество итераций определяется количеством итераций, полезных для удаления каждого исходного источника. По гипотезе каждый источник связан как минимум с другим промежуточным узлом: если это не так, то это несвязный компонент графа, но по определению граф связен. В худшем случае промежуточный сценарий $n_{i}$ узлы соединяются попарно и на каждой итерации удаляется не более половины источников. Реструктурируя каждую из уцелевших $n_{i+1}$ источники теперь будут подключаться попарно. Как и в предыдущем случае, выживет максимум половина. Очевидно, что завершение достигается, когда остается только один источник. Сокращение вдвое налагает $log_{2}n$ количество итераций последнего вычисления, т. е. одного между двумя наиболее удаленными сохранившимися источниками, помещенными в $diam(G)$. Общая стоимость составляет $2m\log {n}$.

Прекращение действия

Завершение гарантируется переключением в направлениях, выполняемых при нажатии ДА / НЕТ . Сокращение источников в фазе «-Йо» происходит монотонно: по предыдущему наблюдению каждый источник сравнивается хотя бы с одним другим источником, и по уникальности источников один из них преобладает, а остальные умирают. Поскольку число исходных источников конечно, монотонное сокращение приведет к тому, что останется один источник.