Bully algorithm

stm5872449

Наткнулся тут на поросшее мхом тестовое задание: http://www.echorussia.ru/jobs/serverside-june-2013.html
Стало любопытно - правильно ли я понимаю, что для работоспособности этого алгоритма требуется мгновенная доставка сообщений? Например, я не вижу в описании никакого механизма защиты от двух нод, одновременно начинающих broadcast IMTHEKING, что в условиях сетевых задержек приведет к тому, что другие ноды получат эти сообщения в разном порядке и договоренность не будет достигнута.
Какой вообще алгоритм (семейство алгоритмов) считается лучшим для решения данной задачи?

Dasar

одновременно начинающих broadcast IMTHEKING

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

stm5872449

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

Пусть нода [N] временно вышла из строя. [N-1] спрашивает ее о состоянии, не получает ответ за T времени и начинает броадкаст. В этот момент [N] пришла в себя и как самая старшая сразу же тоже начала броадкаст. М?

evgen5555

узел N должен анонсировать победу раньше, чем дело бы дошло до опроса узлом N-1
если же очередь опроса у N-1, то узел N лежит серьезно, и вероятность его оживления (в момент T) практически равна нулю
там же есть пинг с ожиданием в 4T

rosali

Я просто худею, когда при обсуждении консистентности алгоритмов синхронизации используют слово "вероятность". А если этот кластер управляет ядерным реактором?..
PS. В алгоритм не вчитывался, но думаю с ним всё в порядке, без всяких вероятностей. Echo серьезные ребята, это вам не mongodb какое-нибудь.

stm5872449

вероятность его оживления (в момент T) практически равна нулю

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

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

Ну это же тестовое задание, а не продакшн код.

evgen5555

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

Так она уже есть: таймаут в условии подобран как 4T. Можешь спросить у "серьезных ребят", откуда они взяли это значение

Dasar

Пусть нода [N] временно вышла из строя

Данный алгоритм расчитан на то, что нода может умереть навсегда, но не рассматривает случай временного выхода ноды из строя.
Это имеет смысл, например, для процессов/потоков внутри одного компьютера. Процесс может умереть, но не может не ответить (можно обеспечить, что временно подвисший процесс считает себя мертвым после отвисания)