Алгоритм забияки

Алгоритм забияки — это метод распределённых вычислений для динамического выбора координатора или лидера из группы распределённых вычислительных процессов. Процесс с наивысшим ID среди живущих (не упавших) процессов выбирается в качестве координатора.

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

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

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

Алгоритм

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

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

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

Если P имеет наивысший ID, он посылает сообщение о победе в выборах всем остальным процессам и становится Координатором. В противном случае P объявляет о выборах всем остальным процессам с ID, большим его собственного.
Если P не получает ответа после объявления выборов, он объявляет о победе в выборах всем остальным процессам и становится Координатором.
Если P получает ответ от процесса с бо́льшим ID, он не посылает больше сообщений о выборах и ждёт сообщений о победе в выборах. (Если за некоторый период времени сообщение о победе не поступает, P начинает процесс выборов с начала.)
Если P получает сообщение о начале выборов от другого процесса с более низким ID, он посылает ответ и начинает процесс выборов с начала путём рассылки сообщений о начале выборов процессам с более высокими ID.
Если P получает сообщение о победе, он считает пославший процесс координатором.

Анализ

Надёжность

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

Живучесть

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

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

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

См. также

Примечания

↑ Dollimore, Kindberg, Coulouris, 2003.

Литература

Emmett Witchel. Distributed Coordination. — 2005.

Jean Dollimore, Tim Kindberg, George F. Coulouris. Distributed systems : concepts and design // Distributed systems : concepts and design. — Third Edition. — Addison–Wesley, 2003.
Hector Garcia-Molina. Elections in a Distributed Computing System // IEEE Transactions on Computers. — 1982. — Январь (т. C-31, № 1). — С. 48–59.
Lamport L., Shostak R., Pease M. The Byzantine Generals Problem // ACM Transactions on Programming Languages and Systems. — 1982. — Июль (т. 4, № 3).

[_36bf7492d522bcb0-1] Dollimore, Kindberg, Coulouris, 2003.

[1]