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

Алгоритм выбора лидера — это процесс в системе распределённых вычислений, который назначает один процесс организатором некоторой задачи, распределённой на несколько компьютеров (узлов). До начала выполнения задачи все узлы сети либо не осведомлены, какой узел будет вести себя как «лидер» (или координатор) задачи, либо не в состоянии общаться с текущим координатором. После того, как алгоритм выбора лидера отработает, каждый узел сети знает об определённом единственном узле, выступающем в качестве лидера.

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

Постановку задачи часто приписывается ЛеЛанну, который формализовал её как метод создания нового маркера в потерявшей маркер сети Token ring.

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

Было предложено много разных алгоритмов для различных топологий сетей — графов, таких как неориентированные кольца, ненаправленных колец, полных графов, решёток, ориентированных эйлеровых графов и других. Основной метод, который отвязывает проблему семейства графов от разработки алгоритма выбора лидера, был предложен Корачем, Куттеном и Мораном.

Определение

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

1. Состояния процессоров делятся на выбранный и не выбранный. Будучи выбранным, процессор остаётся выбранным (аналогично, не выбранным).
2. При любом выполнении алгоритма в точности один процессор становится выбранным, а остальные решают, что они не выбраны.

Правильный алгоритм выбора лидера должен удовлетворять следующим условиям:

1. Завершение: алгоритм должен завершиться за конечное время выбором лидера. В рандомизированных подходах это условие иногда ослабляется (например, требованием завершения с вероятностью 1).
2. Единственность: имеется в точности один процесс, который считает себя лидером.
3. Согласие: все остальные процессы знают, кто есть лидер.

Алгоритм выбора лидера может варьироваться в следующих аспектах:

• Механизм обмена сообщениями: процессоры либо синхронны, кода процессы синхронизируются сигналом часов, либо асинхронны, когда процессы протекают с произвольными скоростями.
• Имена процессов: имеют ли процессы уникальные идентификаторы или неразличимы (анонимны).
• Сетевая топология: например, кольцо, ациклический граф или полный граф.
• Размер сети: алгоритм может или не может использовать знание числа процессов в системе.

Алгоритмы

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

Топология кольцевой сети

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

Анонимные кольца

Говорят, что кольцо анонимно, если любой процессор неотличим. Более формально, система представляет собой тот же самый конечный автомат (то есть автомат, имеющий конечное число внутренних состояний) для любого процессора. Не существует детерминистского алгоритма для выбора лидера в анонимных кольцах, если даже размер сети известен процессам. Это потому, что нет возможности разрушить симметрию в анонимном кольце, если все процессы работают с одинаковой скоростью. Состояние процессоров после некоторых шагов зависит только от начального состояния соседних узлов. Таким образом, поскольку их состояния идентичны и выполняются те же процедуры, в каждом раунде каждый процессор посылает те же самые сообщения. Поэтому состояние каждого процессора меняется также одинаково и если один процессор выбирает себя в качестве лидера, то же самое сделают все остальные процессоры.

Для простоты, докажем это для анонимных синхронных колец. Докажем от противного. Рассмотрим анонимное кольцо R размера n>1. Пусть существует алгоритм «A» решения задачи выбора лидера в анонимном кольце R.

Лемма: После раунда $k$ выполнения алгоритма A в кольце R все процессы имеют одно и то же состояние.

Доказательство: Докажем по индукции по $k$.

База индукции: $k=0$: все процессы в начальном состоянии, так что все процессы идентичны.

Гипотеза индукции: Предположим, что лемма верна для первых $k-1$ раундов.

Шаг индукции: В раунде $k$ любой процесс посылает одно и то же сообщение $m_{r}$ направо и одно и то же сообщение $m_{l}$ налево. Поскольку все процессы имеют одно и то же состояние в раунде $k-1$, в раунде k каждый процесс получит сообщение $m_{r}$ слева и сообщение $m_{l}$ справа. Поскольку все процессы получат одинаковые сообщения в раунде $k$, они перейдут в одно и то же состояние после раунда $k$.

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

Случайные выборы лидера

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

Асинхронное кольцо

Алгоритм $O(n\log n)$ для асинхронного кольца

Поскольку нет алгоритма для анонимных колец (как доказано выше), асинхронные кольца будем считать неанонимными. В неанонимных кольцах каждый процесс имеет уникальный идентификатор $id$ и процесс не знает о размере кольца. Выбор лидера в асинхронных кольцах может быть осуществлён алгоритмом с посылкой $O(n^{2})$ или $O(n\log n)$ сообщений.

В алгоритме $O(n^{2})$ любой процесс посылает сообщение с его $id$ налево, затем ждёт сообщения справа. Если $id$ в полученном сообщении больше его собственного $id$, сообщение передаётся налево, если же меньше, сообщение игнорируется и действий никаких не производится. Если $id$ в сообщении равен собственному $id$, налево посылается сообщение о признании себя выбранным лидером. Остальные процессы передают объявление лидера налево и переводят своё состояние в невыбранные. Ясно, что верхняя граница числа сообщений для этого алгоритма равна $O(n^{2})$.

Алгоритм $O(n\log n)$ работает в несколько фаз. На фазе $k$ процесс определяет, не является ли он победителем среди левых $2^{k}$ соседей и $2^{k}$ правых соседей. Если он является победителем, он может перейти в следующую фазу. На фазе $0$ для каждого процесса $P$ необходимо определиться, является ли он победителем, путём посылки сообщения с $id$ левому и правому соседям (соседи не передают сообщения дальше). Сосед отвечает сообщением $ACK$, только если $id$ в сообщении больше его собственного $id$, в противном случает он отвечает сообщением $ACK_{fault}$. Если $P$ получает два сообщения $ACK$, слева и справа, процесс $P$ является победителем на фазе $0$. На фазе $k$ победитель фазы $k-1$ должен послать сообщение с его $id$ $2^{k}$ левым и $2^{k}$ правым соседям. Если соседи на пути следования получают в сообщении $id$ больший их собственного $id$, они пересылают сообщение следующему соседу, в противном случае отвечают сообщением $ACK_{fault}$. Если $2^{k}$-й сосед получает $id$, больший его собственного $id$, он посылает назад $ACK$, в противном случае посылает $ACK_{fault}$. Если процесс получает два сообщения $ACK$, он является победителем в фазе $k$. В последней фазе победитель получает свой собственный $id$ в сообщении, обрывает передачу сообщения далее и посылает сообщение о завершении другим процессам. В худшем случае в каждой фазе имеется ${\frac {n}{2^{k}+1}}$ победителей, где $k$ является номером фазы. Всего будет $\lceil \log(n-1)\rceil$ фаз. Каждый победитель посылает порядка $2^{k}$ сообщений в каждой фазе. Таким образом, сложность по числу сообщений равна $O(n\log n)$.

Синхронное кольцо

В книге Атья и Уэдча «Распределённые вычисления» (англ. Distributed Computing) они описывают неоднородный алгоритм, использующий $O(n)$ сообщений в синхронном кольце с известным размером $n$ кольца. Алгоритм разбивается на фазы, каждая фаза имеет $n$ раундов, каждый проход занимает одну единицу времени. На фазе $0$, если имеется процесс с $id=0$, этот процесс посылает прерывающее сообщение (англ. termination message) другим процессам (посылка прерывающих сообщений стоит $n$ раундов). В противном случае переходим к следующей фазе. Алгоритм проверяет, имеется ли фаза с номером, равным $id$ процесса, затем делает те же шаги, что и для фазы $0$. В конце выполнения алгоритма минимальное $id$ будет выбрано в качестве лидера. Алгоритм использует ровно $n$ сообщений и $n(minimum\_id+1)$ раундов.

Итаи и Родэ предложили алгоритм для ненаправленного кольца с синхронными процессами. Они предполагают, что размер кольца (число узлов) процессам известно. Для кольца с размером n активны $a\leqslant n$ процессоров. Каждый процессор решает с вероятностью $a^{-1}$ стать кандидатом. В конце каждой фазы каждый процесс вычисляет число кандидатов, и если это число равно 1, объявляет себя лидером. Для определения числа c кандидатов каждый кандидат посылает токен (маркер) в начале фазы, который проходит через кольцо, возвратившись ровно через n единиц времени пославшему токен узлу. Каждый процессор определяет значение c путём подсчёта числа токенов, прошедших через узел. Этот алгоритм осуществляет выбор лидера с ожидаемой сложностью $O(n\log n)$. Аналогичный подход используется также, когда используется механизм тайм-аута для определения взаимных блокировок в системе. Существуют алгоритмы для колец специального размера, таких как кольца с простым числом узлов и нечётным числом узлов.

Однородный алгоритм

В обычных подходах выбора лидера размер кольца предполагается известным процессам. В случае анонимных колец без использования внешней сущности невозможно выбрать лидера. Даже если предположить, что алгоритм существует, лидер не может оценить размер кольца, т.е. в любом анонимном кольце существует положительная вероятность, что алгоритм вычислит неверный размер сети. Чтобы преодолеть эту проблему, Фишер и Цзян использовали так называемого оракла (предсказателя) $\Omega ?$, которого каждый процессор может спросить, имеется ли уникальный лидер. Они показали, что после некоторого промежутка времени оракл гарантированно вернёт один и тот же ответ всем процессам.

Кольца с уникальными ID

В одной из ранних работ Чан и Робертс предложили однородный алгоритм, в котором процессор с наибольшим ID выбирается в качестве лидера. Каждый процессор посылает собственный ID в направлении по часовой стрелке. Процесс получает сообщение и сравнивает ID сообщения с собственным ID. Если ID сообщения больше, сообщение посылается дальше, в противном случае оно отбрасывается. Они показали, что алгоритм использует не более $O(n^{2})$ сообщений, а в среднем $O(n\log n)$ сообщений.
Хиршберг и Синклер улучшили этот алгоритм до сложности $O(n\log n)$ по сообщениям, введя двунаправленную схему рассылки сообщений (позволив процессорам посылать сообщения в обоих направлениях.

Выборы лидера в сетке

Решёточная топология сети. Красные узлы обозначают углы, синие означают границу, а серые внутреннюю часть сети.

Решётка является другим популярным видом сетевой топологии, особенно в параллельных системах, системах избыточной памяти (англ. redundant memory systems) и сетей внутренней коммуникации. В решёточной структуре узлы являются либо углами (только два соседа), границами (три соседа) или внутренними (с четырьмя соседями).Число рёбер в решётке размера $a\times b$ равно $m=2ab-a-b$.

Неориентированная сеть

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

1. Процесс просыпания: на этой стадии k узлов инициируют выборный процесс. Каждый инициатор посылает сообщение о просыпании всем соседним узлам. Если узел не является инициатором, он просто перенаправляет сообщение другим узлам. На этой стадии будет послано максимум $3n+k$ сообщений.
2. Процесс выборов: выборы во внешнем кольце занимают две стадии с посылкой максимум $6(a+b)-16$ сообщений.
3. Прекращение: лидер посылает сообщение всем узлам, что требует максимум $2n$ сообщений.

Сложность сообщения не превосходит $6(a+b)-16$, а если решётка квадратная, $O({\sqrt {n}})$.

Ориентированная сеть

Ориентированная решётка является специальным случаем, в которой порты помечены как северный, южный, восточный и западный. Выбор лидера в ориентированной решётке тривиален. Нам следует выбрать угол, например «северо-восточный» и удостовериться, что узел знает, что он является лидером.

Тороидальная сетевая структура

Тороидальная сетевая структура.

Специальным случаем решёточной архитектуры является тор, в котором решётка «свёрнута». В этой структуре каждый узел имеет в точности 4 соединяющих ребра. Один из подходов выборов в такой структуре известен как выборные туры. Подобно процедурам в кольцевых структурах этот метод на каждом туре исключает потенциальных кандидатов, пока не останется единственный кандидат. Этот узел и становится лидером и уведомляет остальные процессы о прекращении выборов. Этот подход используется, чтобы получить сложность O(n). Существует также более практичные подходы с наличием в сети разорванных соединений.

Выборы в гиперкубах

Топология сети H_4 гиперкуба.

Гиперкуб $H_{k}$ — это сеть, состоящая из $n=2^{k}$ узлов, каждый со степенью k. Аналогичные описанным выше выборные туры могут быть использованы для решении задачи выбора лидера. В каждом туре соревнуются пары узлов (называемые дуэлянтами) и победитель переходит на следующий тур, это означает, что только половина дуэлянтов переходят на следующий тур. Процедура продолжается, пока не останется один дуэлянт, и он становится лидером. Будучи выбранным, лидер сообщает о выборе всем остальным процессам. Этот алгоритм требует посылки $O(n)$ сообщений. В случае неориентированных гиперкубов используется аналогичный подход, но сложность по сообщениям вырастает до $O(n\log \log n)$.

Выборы в полных сетях

Структура полной сети.

Полные сети — это структуры, в которых все процессы связаны друг с другом, т.е. степень каждого узла равна n-1, где n представляет собой размер сети. Известно оптимальное решение со сложностью $O(n)$ по числу сообщений и памяти. В этом алгоритме процессы имеют следующие состояния

1. Вне игры: узлы не участвуют в алгоритме выбора лидера.
2. Пассивное: начальное состояние процессов до начала выборов.
3. Кандидат: статус узла после просыпания. Предполагается, что кандидаты станут лидерами.

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

Универсальные техники выбора лидера

Как подсказывает название, эти алгоритмы разработаны для использования в любом типе сетей процессов без предварительного знания топологии сети или её свойств, таких как размер.

Протокол Shout

Протокол Shout строит остовное дерево на графе и выбирает корень в качестве лидера. Алгоритм имеет общую стоимость, линейную от числа рёбер.

Mega-Merger

Эта техника по существу подобна поиску минимального остовного дерева, в котором корень дерева становится лидером. Основная идея этого метода заключается в слиянии индивидуальных узлов для формирования более крупных структур. Результатом алгоритма является дерево (граф без циклов), корень которого и становится лидером всей системы. Цена метода mega-merger равна $O(m+n\log n)$, где m — число рёбер, а n — число узлов.

Yo-yo

Пример YO-YO процедуры. a) Сеть, b) Ориентированная сеть после фазы setup, c) YO- фаза, в которой посланы значения id источников, d)-YO фаза посылки ответов от стоков, e) обновлённая структура после -YO фазы.

Алгоритм Yo-Yo является алгоритмом поиска минимума, состоящим из двух фаз: фазы подготовки и серии итераций . На первой фазе (подготовка), каждый узел обменивается своим id со всеми соседями и в зависимости от результата связывающему ребру придаётся направление. Например, если узел x имеет меньший id, чем у узла y, ребро ориентируется от x в y. Если узел имеет меньший id, чем у всех его соседей, он становится источником. Узел же с бо́льшим id, чем у всех соседей, имеет только входящие рёбра и становится стоком. Все другие узлы являются внутренними.
Когда все рёбра получат ориентацию, алгоритм переходит к фазе итераций. Каждая итерация является туром выборов, в котором некоторые кандидаты удаляются. Каждая итерация имеет две фазы — YO- и -YO. В первой (YO-) фазе источники начинают процесс передачи в каждый сток наименьшего значения id источника, подсоединённого к стоку.

Yo-

1. Источник (локальный минимум) передаёт значение своего id всем соседям
2. Внутренний узел ждёт получения значения из всех входящих рёбер, вычисляет минимальное значение и передаёт во все исходящие рёбра.
3. Сток (узел без исходящих рёбер) получает все значения и вычисляет минимальный id.

-Yo

1. Сток посылает YES соседям, из которых получил наименьшее значение, и не посылает остальным
2. Внутренний узел посылает YES по всем входящим рёбрам, из которых получил минимальное значение и не посылает остальным. Если он получил только NO, он посылает NO всем.
3. Источник ждёт, пока не получит все голоса. Если все они YES, он выживает, а если нет, он больше не кандидат.
4. Когда узел x посылает NO всем входящим соседям, логические направления этих рёбер инвертируется.
5. Если узел получает NO по исходящему ребру, он меняет направление ребра.

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

1. Если сток является листом, он бесполезен, а потому удаляется.
2. Если на фазе YO- некоторое значение получено более чем по одному входному ребру, узел просит всех пославших сообщение, кроме одного, удалить связь с собой.

Метод имеет общую стоимость $O(m\log n)$ по сообщениям. Его действительная сложность, включая обрезку, не известна и является открытой проблемой.

Приложения

Радиосети

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

Модели и время работы

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

Известные времена для сетей без ретрансляторов варьируются от константы (для случая обнаружения коллизий) до O(n \log n) раундов (детерминированные сети и сети без обнаружения коллизий). В сетях с ретрансляторами известное время варьируется где-то от $O((D+\log n)(\log ^{2}\log n))$ раундов (с высокой вероятностью в модели beeping), $O(D\log n)$ (детерминированные модели в модели beeping), $O(n)$ (детерминированные модели с обнаружением коллизий) до $O(n\log ^{1,5}n(\log \log n)^{0,5})$ раундов (детерминированные модели и модели без обнаружения коллизий).

См. также

• Алгоритм забияки
• Алгоритм Чана и Робертса
• Алгоритм Хиршберга — Синклера