Алгоритм хулигана - Bully algorithm

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

Предположения

Алгоритм предполагает, что:^[1]

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

Алгоритм

В алгоритме используются следующие типы сообщений:

Сообщение о выборах: отправляется для объявления выборов.
Ответное (живое) сообщение: отвечает на сообщение о выборах.
Сообщение координатора (победа): отправляется победителем выборов для объявления победы.

Когда процесс п восстанавливается после сбоя, или детектор отказов указывает, что текущий координатор отказал, п выполняет следующие действия:

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

Анализ

Безопасность

Свойство безопасности, ожидаемое от протоколов о выборах лидера, состоит в том, что каждый исправный процесс либо выбирает процесс Qили вообще не выбирает. Обратите внимание, что все процессы, которые выбирают лидера, должны принимать решение об одном и том же процессе. Q как лидер. Алгоритм Bully удовлетворяет этому свойству (в соответствии с указанной моделью системы), и ни в какой момент времени два процесса в группе не могут иметь противоречивое представление о том, кто является лидером, кроме как во время выборов. Это правда, потому что если бы это было не так, есть два процесса Икс и Y таким образом, что оба отправили группе сообщение Координатора (победа). Это означает Икс и Y должны также послать друг другу сообщения о победе. Но этого не может произойти, так как перед отправкой сообщения о победе между ними будет происходить обмен сообщениями о выборах, и процесс с более низким идентификатором процесса из двух никогда не будет отправлять сообщения о победе. Мы получили противоречие, и, следовательно, наше первоначальное предположение о том, что в системе есть два лидера в любой момент времени, неверно, и это показывает, что алгоритм хулигана безопасен.

Живучесть

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

Использование полосы пропускания сети

Предполагая, что сообщения алгоритма хулигана имеют фиксированный (известный, инвариантный) размер, наибольшее количество сообщений обменивается в группе, когда процесс с наименьшим идентификатором инициирует выборы. Этот процесс отправляет (N-1) сообщений о выборах, следующий более высокий идентификатор отправляет (N-2) сообщений и т. Д., В результате чего ${ displaystyle Theta left (N ^ {2} right)}$ сообщения о выборах. Есть также ${ displaystyle Theta left (N ^ {2} right)}$ Живые сообщения и ${ Displaystyle Theta влево (N вправо)}$ сообщений координатора, тем самым делая общее количество сообщений, которыми обмениваются в худшем случае, ${ displaystyle Theta left (N ^ {2} right)}$ .

Смотрите также

внешняя ссылка

СМИ, связанные с Алгоритм хулигана в Wikimedia Commons

[1] Кулурис, Джордж; Доллимор, Жан; Киндберг, Тим (2000). Распределенные системы: концепции и дизайн (3-е изд.). Эддисон Уэсли. ISBN 978-0201619188.

[1]