Алгоритм Паксос

Паксос — семейство протоколов для решения задачи консенсуса в сети ненадёжных вычислителей. Консенсус — процесс получения согласованного результата группой участников, основная проблема — наличие помех в среде передачи данных.^[1] Данная задача используется, например, для утверждения транзакций в распределённых системах.

Протоколы решения задачи консенсуса — базовый элемент автоматного подхода в распределённых вычислениях, предложенного Лесли Лампортом^[2] и исследованного далее Ф. Шнайдером.^[1]

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

Семейство протоколов Паксос было создано и описано в 1990 г., но не было опубликовано в научной литературе до 1998 г. Однако, исследования на данную тематику начались задолго до реализации протокола. Например, автоматная репликация, подход к программированию на основе модели виртуальной синхронизации, предложенной в 1985 г.

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

О названии

Алгоритм назван в честь вымышленной системы права греческого острова Паксос.

Свойства безопасности и живучести

Алгоритмы данного семейства гарантируют 3 следующих показателя:

• Нетривиальность — решение может быть принято только из заранее заданного множества исходов;
• Консистентность — принятое решение совпадает у всех вычислителей, в нём участвовавших;
• Живучесть(C,L) — Если было предложено решение C, то рано или поздно вычислитель L примет какое-либо решение (при условии наличия достаточного количества работающих вычислителей).

Предусловия

Вычислители

Сеть

Число процессоров

Роли

Кворум

Предложенное число и согласованное значение

Примеры реализации

Простой паксос

Мульти-паксос

Оптимизации

Дешёвый паксос

Сокращённый паксос

Обобщённый паксос

Византийский паксос

Остановимый паксос

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

Промышленное использование

• Данное семейство алгоритмов используется в распределённой службе блокировок Chubby компании Google, используемой, в свою очередь, в BigTable.
• Microsoft использует паксос в своей системе автоматического управления кластерами.

См. также

• Алгоритм консенсуса Чандры-Тоэг
• Виртуальная синхронизация
• Конечный автомат

Примечания

Ссылки

• Leslie Lamport, Dahlia Malkhi, Lidong Zhou Stoppable Paxos  (англ.) (PDF). Microsoft Research (28 April 2008). Проверено 26 августа 2012.