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

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

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

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

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

Алгоритм

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

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

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

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

Анализ

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

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

живость

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

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

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

См. также

Ссылки

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

Витчел, Эммет (2005). «Распределенная координация» . Проверено 4 мая 2005 г.
Гектор Гарсиа-Молина, Выборы в распределенной вычислительной системе, Транзакции IEEE на компьютерах, Vol. С-31, № 1, январь (1982) 48–59.
Л. Лэмпорт, Р. Шостак и М. Пиз, «Проблема византийских генералов». Транзакции ACM в языках и системах программирования, Vol. 4, № 3, июль 1982 г.

Внешние ссылки

СМИ, связанные с алгоритмом Bully, на Викискладе?

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

[1]