Выборы лидера - Leader election

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

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

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

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

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

Определение

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

Лемма: после раунда ${ displaystyle k}$ допустимого выполнения A в R, все процессы имеют одинаковые состояния.

Доказательство. доказать индукцией по ${ displaystyle k}$ .

Базовый вариант: ${ displaystyle k = 0}$ : все процессы находятся в исходном состоянии, поэтому все процессы идентичны.

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

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

Приведенная выше лемма противоречит тому факту, что после некоторого конечного числа раундов при выполнении A один процесс вошел в выбранное состояние, а другие процессы вошли в невыборное состояние.

Рандомизированные (вероятностные) выборы лидера

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

Асинхронное кольцо^[3]

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

Поскольку не существует алгоритма для анонимных колец (доказанного выше), асинхронные кольца будут рассматриваться как асинхронные неанонимные кольца. В неанонимных кольцах каждый процесс имеет уникальный ${ displaystyle id}$ , и они не знают размер кольца. Выбор лидера в асинхронных кольцах решается некоторым алгоритмом с использованием ${ Displaystyle О (п ^ {2})}$ сообщения или ${ Displaystyle О (п журнал п)}$ Сообщения.

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

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

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

В книге Аттии и Уэлча о распределенных вычислениях^[3] они описали неоднородный алгоритм, используя ${ Displaystyle О (п)}$ сообщения в синхронном кольце с известным размером кольца ${ displaystyle n}$ . Алгоритм работает поэтапно, каждая фаза имеет ${ displaystyle n}$ раундов, каждый раунд - одна единица измерения времени. В фазе ${ displaystyle 0}$ , если есть процесс с ${ displaystyle id = 0}$ , затем обработайте ${ displaystyle 0}$ отправляет сообщение о завершении другим процессам (стоимость отправки сообщений о завершении ${ displaystyle n}$ раундов). В противном случае переходите к следующему этапу. Алгоритм проверит, равен ли номер фазы процессу ${ displaystyle id}$ , затем выполняет те же действия, что и phase ${ displaystyle 0}$ . По окончании исполнения минимальный ${ displaystyle id}$ будет избран лидером. Он использовал именно ${ displaystyle n}$ сообщения и ${ displaystyle n (минимум _id + 1)}$ раундов.

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

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

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

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

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

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

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

В сетка - еще одна популярная форма сетевой топологии, особенно в параллельных системах, системах с избыточной памятью и взаимосвязанных сетях.^[16]
В структуре сетки узлы могут быть угловыми (только два соседа), граничными (только три соседа) или внутренними (с четырьмя соседями). Количество ребер в сетке размером a x b равно m = 2ab-a-b.

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

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

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

Сложность сообщения не более 6(а + б) - 16, а если сетка квадратная, O (√п).

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

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

Тор

Структура сети тора.

Частным случаем архитектуры сеток является тор, который представляет собой сетку с «циклическим обтеканием». В этой структуре каждый узел имеет ровно 4 соединительных ребра. Один из подходов к избранию лидера в такой структуре известен как этапы выборов. Подобно процедурам в кольцевых структурах, этот метод на каждом этапе исключает потенциальных кандидатов, пока в конечном итоге не останется один узел-кандидат. Этот узел становится лидером и затем уведомляет все остальные процессы о завершении.^[18] Этот подход можно использовать для достижения сложности O (n). Также представлены более практические подходы к устранению неисправных каналов в сети.^[19]^[20]

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

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

А Гиперкуб ${ displaystyle H_ {k}}$ сеть, состоящая из ${ Displaystyle п = 2 ^ {к}}$ узлов, каждый со степенью ${ displaystyle k}$ и ${ Displaystyle О (п журнал п)}$ края. Аналогичные избирательные этапы, как и раньше, могут быть использованы для решения проблемы избрания лидера. На каждом этапе соревнуются два узла (называемых дуэлянтами), и победитель переходит на следующий этап. Это означает, что на каждом этапе в следующий этап переходит только половина дуэлянтов. Эта процедура продолжается до тех пор, пока не останется только один дуэлянт, и он станет лидером. После выбора он уведомляет все остальные процессы. Этот алгоритм требует ${ Displaystyle О (п)}$ Сообщения. В случае неориентированных гиперкубов можно использовать аналогичный подход, но с более высокой сложностью сообщения ${ Displaystyle О (п журнал журнал п)}$ .^[21]

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

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

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

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

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

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

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

Кричать

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

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

Этот прием по сути аналогичен поиску Минимальное связующее дерево (MST), в которой корень дерева становится лидером. Основная идея этого метода - отдельные узлы сливаются друг с другом, образуя более крупные структуры. Результатом этого алгоритма является дерево (граф без цикла), корень которого является лидером всей системы. Стоимость метода мега-слияния составляет ${ Displaystyle О (т + п журнал п)}$ где m - количество ребер, а n - количество узлов.

Йо Йо

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

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

Эй-

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

-Эй

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

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

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

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

Приложения

Радиосети

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

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

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

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

Выборы лидера - Leader election

Содержание

Определение