Цитата:
|
Сообщение от УчастнеГ
Мне оба, и лучше на примерах, как применяют, и для чего можно применять в принципе.
|
Тогда будет простой Raft.
Группа старых друзей-алкоголиков в пятницу вечером думает не пойти ли им выпить (прийти к консенсусу).
У каждого из них есть своя более-менее голова, но нет телепатических способностей, любое сообщение от одного к другому требует конечного времени (распределенный консенсус).
В группе есть свой лидер - выбранный и признанный остальными участниками, но принципиально от них не отличающийся (его могут и переизбрать, если есть серьезный повод. Новым лидером может стать любой другой собутыльник).
В обычный день лидер каждому сообщает идут они сегодня пьянствовать или нет. Остальные его внимательно слушают и кивают если поняли команду. Как только лидер увидел что больше половины кивков получено, решение принято - есть консенсус. Если больше половины поступят так как лидер сказал - все отлично.
Дальше, в группе могут появляться новые алкоголики, нужно уметь учитывать их число и кивки.
Из группы могут по-одному вываливаться участники (например, потому что печень). Нужно уметь их исключать. Даже если вдруг захотел вывалиться лидер.
Часть участников группы может застрять в лифте, и не участвовать в кивании. Лидеру нужно уметь не обратить на них внимание, организовать пьянку без них.
И самый интересный случай - в лифте может застрять более половины группы. Они должны понять что команд от лидера не поступает, и выбрать себе нового лидера. Старый тоже должен понять что он слишком мало кивков видит - и он уже не лидер, а обычный алкаш и снова вписывается в коллектив.
Собственно Raft - машина с небольшим числом состояний, которая позволят каждому участнику группы знать в каком он статусе (лидер, самовыдвиженец или рядовой алкоголик), объясняет как выбирается новый лидер, так чтобы он оказался единоличным, признанным, и выбирался в короткое время.
Сложности: строго говоря состояний у этой машинки бесконечное количество. Кроме роли участника у него есть еще таймер, порядковый номер лидера и генератор случайных чисел.
Но в целом алгоритм не сложный.
Paxos: цель та же - договориться идем вечером пить пиво или нет, но без явного лидера. И вообще алгоритм сложнее, хотя и старее, с несчетным числом тонкостей (и я его не помню.)
Византийские варианты: в группе есть тайные трезвенники, намеренно пытающиеся сорвать пьянки. Для этого они могут кивать, но не слушать команду. Или нарушать правила голосования, чтобы не получалось выбрать нового лидера. Если трезвенников не очень много можно достигать консенсуса при их кознях.
Византийские варианты алгоритмов сильно сложнее простых.
