Выборы лидера

Не путать с выборами руководства .

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

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

Определение этой проблемы часто приписывают Леланну, который формализовал ее как метод создания нового токена в сети Token Ring , в которой токен был утерян.

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

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

Определение

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

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

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

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

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

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

Алгоритмы

Выборы лидера на рингах

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

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

Анонимные звонки

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

Для простоты приведем доказательство в анонимных синхронных кольцах. Это доказательство от противного. Рассмотрим анонимное кольцо R размера n>1. Предположим, что существует алгоритм «А» для решения проблемы выбора лидера в этом анонимном кольце 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(nlogn) для асинхронного кольца

Поскольку алгоритма для анонимных колец не существует (доказано выше), асинхронные кольца будут рассматриваться как асинхронные неанонимные кольца. В неанонимных кольцах каждый процесс имеет уникальный $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$, else отвечает $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$s, то он является победителем в фазе $k$. На последнем этапе окончательный победитель получит свой собственный $id$ в сообщении, затем завершается и отправляет сообщение о завершении другим процессам. В худшем случае каждая фаза существует не более ${\frac {n}{2^{k}+1}}$ победители, где $k$ это номер фазы. Есть $\lceil \log(n-1)\rceil$ фазы в целом. Каждый победитель отправляет в порядке $2^{k}$ сообщения на каждом этапе. Итак, сложность сообщения $O(n\log n)$.

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

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

Иттай и Роде представил алгоритм однонаправленного кольца с синхронизированными процессами. Они предполагают, что размер кольца (количество узлов) известен процессам. Для кольца размера n активны a≤n процессоров. Каждый процессор с вероятностью a^(-1) решает, стать ли ему кандидатом. В конце каждого этапа каждый процессор подсчитывает количество кандидатов c и, если оно равно 1, становится лидером.Чтобы определить значение c, каждый кандидат отправляет токен (камень) в начале фазы, который передается по кольцу и возвращается ровно через n единиц времени своему отправителю. Каждый процессор определяет c, подсчитывая количество прошедших камешков. Этот алгоритм обеспечивает выбор лидера с ожидаемой сложностью сообщения O(nlogn). Также используется аналогичный подход, в котором используется механизм тайм-аута для обнаружения взаимоблокировок в системе. Существуют также алгоритмы для колец особых размеров, например простого размера. и нестандартный размер.

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

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

Кольца с уникальными идентификаторами

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

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

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

Сетка — еще одна популярная форма топологии сети, особенно в параллельных системах, системах с избыточной памятью и сетях межсоединений.
В ячеистой структуре узлы могут быть угловыми (только два соседа), граничными (только три соседа) или внутренними (с четырьмя соседями). Количество ребер в сетке размера axb равно m=2ab-ab.

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

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

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\log n)$ края. Для решения проблемы выборов лидера можно использовать аналогичные избирательные этапы, что и предыдущие. На каждом этапе соревнуются два узла (называемые дуэлянтами), и победитель переходит в следующий этап. Это означает, что на каждом этапе в следующий этап переходит только половина дуэлянтов. Эта процедура продолжается до тех пор, пока не останется только один дуэлянт, и он станет ведущим. После выбора он уведомляет все остальные процессы. Этот алгоритм требует $O(n)$ сообщения. В случае неориентированных гиперкубов можно использовать аналогичный подход, но с более высокой сложностью сообщения: $O(n\log \log n)$.

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

Полная структура сети.

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

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

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

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

Приведенный выше алгоритм неверен — он требует дальнейшего усовершенствования.

выборов

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

Крик

Shout (протокол) строит связующее дерево на общем графе и выбирает его корень в качестве лидера. Алгоритм имеет общую стоимость, линейную по мощности ребер.

Мега-слияние

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

Йо-йо

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

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

они-

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

- их

1. Приемник отправляет ДА ​​соседям, от которых было получено наименьшее значение, и НЕТ остальным.
2. Внутренний узел отправляет ДА ​​всем соседям, от которых он получил наименьшее значение, и НЕТ остальным. Если он получает только один НЕТ, он отправляет НЕТ всем.
3. Источник ждет, пока не получит все голоса. Если все ДА, он выживет, а если нет, то он больше не является кандидатом.
4. Когда узел x отправляет NO своему соседу y, логическое направление этого ребра меняется на противоположное.
5. Когда узел y получает НЕТ от внешнего соседа, он меняет направление этой ссылки.

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

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

Общая стоимость этого метода составляет O(mlogn) сообщений. Реальная сложность сообщения, включая обрезку, является открытой исследовательской проблемой и неизвестна.

Приложения

Радиосети

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

Модели и время выполнения

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

Известное время работы для однопереходных сетей варьируется от постоянного (ожидаемого с обнаружением коллизий) до O(n log n) раундов (детерминированное и без обнаружения коллизий). В многоскачковых сетях известное время выполнения отличается примерно от O((D+ log n)(log ² log n)) округляет (с высокой вероятностью в модели с звуковым сигналом), O(D log n) (детерминированный в модели с звуковым сигналом), O(n) (детерминированный с обнаружением столкновений) до O(n log ^3/2 n (логарифм n) ^0.5 ) раундов (детерминированный и без обнаружения столкновений).

См. также

• Распределенные вычисления § Выборы
• Алгоритм хулигана
• Алгоритм Чанга и Робертса
• Алгоритм HS
• Система голосования