Алгоритм выбора лидера — процесс в системе распределённых вычислений, который назначает один процесс организатором некоторой задачи, распределённой на несколько компьютеров (узлов). До начала выполнения задачи все узлы сети либо не осведомлены, какой узел будет вести себя как «лидер» (или координатор) задачи, либо не в состоянии общаться с текущим координатором. После того, как алгоритм выбора лидера отработает, каждый узел сети знает об определённом единственном узле, выступающем в качестве лидера.
Узлы сети общаются друг с другом с целью решить, который из них возьмёт на себя роль «лидера». Для этого им нужен некоторый метод, чтобы разрушить симметрию узлов. Например, если каждый узел имеет уникальные и отличительные черты, которые можно сравнить, то узлы могут сравнивать эти черты и решать, какой узел с лучшей характеристикой является лидером.
Постановку задачи часто приписывается ЛеЛанну, который формализовал её как метод создания нового маркера в потерявшей маркер сети Token ring.
Алгоритмы выбора лидера разрабатываются экономичными в терминах передачи общего числа байтов и времени. Алгоритм, предложенный Галлагером, Хамблетом и Спира для общих неориентированных графов, имеет сильное влияние на разработку распределённых алгоритмов вообще и выиграл премию Дейкстры как авторитетная статья в области распределённых вычислений.
Было предложено много разных алгоритмов для различных топологий сетей — графов, таких как неориентированные кольца, ненаправленных колец, полных графов, решёток, ориентированных эйлеровых графов и других. Основной метод, который отвязывает проблему семейства графов от разработки алгоритма выбора лидера, был предложен Корачем, Куттеном и Мораном.
Определение Задача выбора лидера предназначена для решения каждым процессором, будет он лидером или нет, с ограничением, что в точности один процессор решает, что он будет лидером. Алгоритм решает задачу выбора лидера, если Состояния процессоров делятся на выбранный и не выбранный. Будучи выбранным, процессор остаётся выбранным (аналогично, не выбранным). При любом выполнении алгоритма в точности один процессор становится выбранным, а остальные решают, что они не выбраны.
Правильный алгоритм выбора лидера должен удовлетворять следующим условиям: Завершение: алгоритм должен завершиться за конечное время выбором лидера. В рандомизированных подходах это условие иногда ослабляется (например, требованием завершения с вероятностью 1). Единственность: имеется в точности один процесс, который считает себя лидером. Согласие: все остальные процессы знают, кто есть лидер.
Алгоритм выбора лидера может варьироваться в следующих аспектах: Механизм обмена сообщениями: процессоры либо синхронны, кода процессы синхронизируются сигналом часов, либо , когда процессы протекают с произвольными скоростями. Имена процессов: имеют ли процессы уникальные идентификаторы или неразличимы (анонимны). Сетевая топология: например, кольцо, ациклический граф или полный граф. Размер сети: алгоритм может или не может использовать знание числа процессов в системе.
Алгоритмы
Выборы лидера в кольцах
Кольцо является топологией связанного графа, в которой каждый узел связан в точности с двумя другими узлами, то есть в графе с n узлами имеется в точности n рёбер, соединяющих узлы. Кольцо может быть однонаправленным, что означает, что процессоры могут общаться только в одном направлении (узел может посылать сообщения только налево или только направо), или двунаправленным, что означает, что процессоры могут пересылать и получать сообщения в обоих направлениях (узел может посылать сообщения как налево, так и направо).
Анонимные кольца Говорят, что кольцо анонимно, если любой процессор неотличим. Более формально, система представляет собой тот же самый конечный автомат (то есть автомат, имеющий конечное число внутренних состояний) для любого процессора. Не существует детерминистского алгоритма для выбора лидера в анонимных кольцах, если даже размер сети известен процессам. Это потому, что нет возможности разрушить симметрию в анонимном кольце, если все процессы работают с одинаковой скоростью. Состояние процессоров после некоторых шагов зависит только от начального состояния соседних узлов. Таким образом, поскольку их состояния идентичны и выполняются те же процедуры, в каждом раунде каждый процессор посылает те же самые сообщения. Поэтому состояние каждого процессора меняется также одинаково и если один процессор выбирает себя в качестве лидера, то же самое сделают все остальные процессоры.
Для простоты, докажем это для анонимных синхронных колец. Докажем от противного. Рассмотрим анонимное кольцо R размера n>1. Пусть существует алгоритм «A» решения задачи выбора лидера в анонимном кольце R.
Лемма: После раунда выполнения алгоритма A в кольце R все процессы имеют одно и то же состояние.
Доказательство: Докажем по индукции по .
База индукции: : все процессы в начальном состоянии, так что все процессы идентичны.
Гипотеза индукции: Предположим, что лемма верна для первых раундов.
Шаг индукции: В раунде любой процесс посылает одно и то же сообщение направо и одно и то же сообщение налево. Поскольку все процессы имеют одно и то же состояние в раунде , в раунде k каждый процесс получит сообщение слева и сообщение справа. Поскольку все процессы получат одинаковые сообщения в раунде , они перейдут в одно и то же состояние после раунда .
Эта лемма противоречит тому, что после некоторого конечного числа раундов выполнения алгоритма A один из процессов окажется в выбранном состоянии, а остальные окажутся в невыбранном.
Случайные выборы лидера Общим подходом решения задачи выбора лидера в анонимных сетях является использование вероятностных алгоритмов. При таком подходе обычно процессоры предполагают некоторого рода идентификацию, основанную на вероятностной функции, и передают его остальной части сети. В конце концов, применяя алгоритм, осуществляется выбор лидера (с высокой вероятностью).
Асинхронное кольцо
Поскольку нет алгоритма для анонимных колец (как доказано выше), асинхронные кольца будем считать неанонимными. В неанонимных кольцах каждый процесс имеет уникальный идентификатор и процесс не знает о размере кольца. Выбор лидера в асинхронных кольцах может быть осуществлён алгоритмом с посылкой или сообщений.
В алгоритме любой процесс посылает сообщение с его налево, затем ждёт сообщения справа. Если в полученном сообщении больше его собственного , сообщение передаётся налево, если же меньше, сообщение игнорируется и действий никаких не производится. Если в сообщении равен собственному , налево посылается сообщение о признании себя выбранным лидером. Остальные процессы передают объявление лидера налево и переводят своё состояние в невыбранные. Ясно, что верхняя граница числа сообщений для этого алгоритма равна .
Алгоритм работает в несколько фаз. На фазе процесс определяет, не является ли он победителем среди левых соседей и правых соседей. Если он является победителем, он может перейти в следующую фазу. На фазе для каждого процесса необходимо определиться, является ли он победителем, путём посылки сообщения с левому и правому соседям (соседи не передают сообщения дальше). Сосед отвечает сообщением , только если в сообщении больше его собственного , в противном случает он отвечает сообщением . Если получает два сообщения , слева и справа, процесс является победителем на фазе . На фазе победитель фазы должен послать сообщение с его левым и правым соседям. Если соседи на пути следования получают в сообщении больший их собственного , они пересылают сообщение следующему соседу, в противном случае отвечают сообщением . Если -й сосед получает , больший его собственного , он посылает назад , в противном случае посылает . Если процесс получает два сообщения , он является победителем в фазе . В последней фазе победитель получает свой собственный в сообщении, обрывает передачу сообщения далее и посылает сообщение о завершении другим процессам. В худшем случае в каждой фазе имеется победителей, где является номером фазы. Всего будет фаз. Каждый победитель посылает порядка сообщений в каждой фазе. Таким образом, сложность по числу сообщений равна .
Синхронное кольцо В книге Атья и Уэдча «Распределённые вычисления» () они описывают неоднородный алгоритм, использующий сообщений в синхронном кольце с известным размером кольца. Алгоритм разбивается на фазы, каждая фаза имеет раундов, каждый проход занимает одну единицу времени. На фазе , если имеется процесс с , этот процесс посылает прерывающее сообщение () другим процессам (посылка прерывающих сообщений стоит раундов). В противном случае переходим к следующей фазе. Алгоритм проверяет, имеется ли фаза с номером, равным процесса, затем делает те же шаги, что и для фазы . В конце выполнения алгоритма минимальное будет выбрано в качестве лидера. Алгоритм использует ровно сообщений и раундов.
Итаи и Родэ предложили алгоритм для ненаправленного кольца с синхронными процессами. Они предполагают, что размер кольца (число узлов) процессам известно. Для кольца с размером n активны процессоров. Каждый процессор решает с вероятностью стать кандидатом. В конце каждой фазы каждый процесс вычисляет число кандидатов, и если это число равно 1, объявляет себя лидером. Для определения числа c кандидатов каждый кандидат посылает токен (маркер) в начале фазы, который проходит через кольцо, возвратившись ровно через n единиц времени пославшему токен узлу. Каждый процессор определяет значение c путём подсчёта числа токенов, прошедших через узел. Этот алгоритм осуществляет выбор лидера с ожидаемой сложностью . Аналогичный подход используется также, когда используется механизм тайм-аута для определения взаимных блокировок в системе. Существуют алгоритмы для колец специального размера, таких как кольца с простым числом узлов и нечётным числом узлов.
Однородный алгоритм В обычных подходах выбора лидера размер кольца предполагается известным процессам. В случае анонимных колец без использования внешней сущности невозможно выбрать лидера. Даже если предположить, что алгоритм существует, лидер не может оценить размер кольца, то есть в любом анонимном кольце существует положительная вероятность, что алгоритм вычислит неверный размер сети. Чтобы преодолеть эту проблему, Фишер и Цзян использовали так называемого оракла (предсказателя) , которого каждый процессор может спросить, имеется ли уникальный лидер. Они показали, что после некоторого промежутка времени оракл гарантированно вернёт один и тот же ответ всем процессам.
Кольца с уникальными ID В одной из ранних работ Чан и Робертс предложили однородный алгоритм, в котором процессор с наибольшим ID выбирается в качестве лидера. Каждый процессор посылает собственный ID в направлении по часовой стрелке. Процесс получает сообщение и сравнивает ID сообщения с собственным ID. Если ID сообщения больше, сообщение посылается дальше, в противном случае оно отбрасывается. Они показали, что алгоритм использует не более сообщений, а в среднем сообщений. улучшили этот алгоритм до сложности по сообщениям, введя двунаправленную схему рассылки сообщений (позволив процессорам посылать сообщения в обоих направлениях.
Выборы лидера в сетке
Решётка является другим популярным видом сетевой топологии, особенно в параллельных системах, системах избыточной памяти () и сетей внутренней коммуникации. В решёточной структуре узлы являются либо углами (только два соседа), границами (три соседа) или внутренними (с четырьмя соседями). Число рёбер в решётке размера равно .
Неориентированная сеть Обычный алгоритм для решения задачи выбора лидера в неориентированной сети заключается в выборе только одного из четырёх угловых узлов в качестве лидера. Поскольку угловые узлы не могут быть осведомлены о состоянии других процессов, алгоритм должен начинаться в угловых узлах. Лидер выбирается следующим образом.