День 2380. #ЗаметкиНаПолях
Алгоритмы Выбора Главного Узла в Распределённых БД. Продолжение
1. Алгоритм Забияки

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

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

Предположим, 5 узлов объединены в кольцо с идентификаторами: A(3), B(5), C(2), D(1), E(4), и обратно к узлу A (см. диаграмму ниже).

Если C обнаруживает отсутствие лидера, он начинает выборы, отправляя сообщение своему соседу (D). Сообщение содержит идентификатор 2. Вот что может произойти:
- D(1) получает идентификатор 2, сравнивает его со своим идентификатором (1) и пересылает 2 узлу E.
- E(4) видит, что 4>2, поэтому он заменяет содержимое сообщения на 4 и пересылает его (есть вариант алгоритма, в котором идентификатор не заменяется, а добавляется). Таким образом, сообщение может принять вид [2,4], но в данном примере мы будем использовать подход с заменой.
- A(3) видит, что 4>3, поэтому он сохраняет 4 и пересылает сообщение.
- B(5) снова заменяет его на 5 и пересылает сообщение.
- В конце концов, сообщение возвращается к узлу C, отправителю.

В этот момент узел C видит, что его сообщение вернулось с идентификатором 5, который является наивысшим в системе. Следовательно, он делает вывод, что узел B(5) должен быть лидером. Он рассылает сообщение координатора по кольцу, сообщая всем, что узел B теперь является лидером.

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

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

Продолжение следует…

Источник: https://blog.bytebytego.com/p/top-leader-election-algorithms-in