Making Democracy Work: Fixing and Simplifying Egalitarian Paxos
В статье представлена EPaxos* — упрощенная и исправленная версия протокола Egalitarian Paxos для распределенных систем. Классические протоколы вроде Paxos полагаются на выделенного лидера, что создает единую точку отказа и увеличивает задержку для удаленных клиентов. Egalitarian Paxos предлагает альтернативу без лидера, позволяя репликам совместно упорядочивать команды, сохраняя работоспособность при сбое до f из n=2f+1 процессов. Протокол обеспечивает быстрое выполнение команд за 2 задержки сообщений, если не более e=⌈(f+1)/2⌉ процессов выходят из строя.
Авторы отмечают, что оригинальный Egalitarian Paxos, несмотря на влияние на другие протоколы, страдает от сложности, неоднозначной спецификации и серьезных ошибок. EPaxos* решает эти проблемы с помощью более простого алгоритма восстановления после сбоев, строго доказанного корректности. Протокол также обобщает Egalitarian Paxos на весь спектр пороговых значений отказов f и e, где n ≥ max{2e+f-1, 2f+1}, что авторы доказали оптимальным.