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

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

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

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

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

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

Источник: Википедия