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

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

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

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

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

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

Определение [ править ]

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

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

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

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

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

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

Алгоритмы [ править ]

Выборы лидера в кольцах [ править ]

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

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

Анонимные звонки [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Синхронное кольцо [ править ]

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

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

Единый алгоритм [ править ]

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

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

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

Выбор лидера в сетке [ править ]

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

Неориентированная сетка [ править ]

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

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

Сложность сообщения составляет не более 6 ( a + b ) - 16 , а если сетка имеет квадратную форму, O ( √ n ).

Ориентированная сетка [ править ]

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

Тор [ править ]

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

Выборы в гиперкубах [ править ]

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

Выборы в полных сетях [ править ]

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

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

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

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

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

Крик [ править ]

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

Мега-слияние [ править ]

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

Йо-йо [ править ]

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

Эй-

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

-Эй

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

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

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

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

Приложения [ править ]

Радиосети [ править ]

В протоколах радиосети выборы лидера часто используются как первый шаг к приближению к более продвинутым примитивам связи, таким как сбор сообщений или широковещательные передачи. ^[25] Сама природа беспроводных сетей порождает коллизии, когда соседние узлы передают одновременно; избрание лидера позволяет лучше координировать этот процесс. В то время как диаметр 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 (log log n) ^0,5 ) раундов (детерминированный и без обнаружения коллизий).

См. Также [ править ]

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

Ссылки [ править ]