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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

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

О названии[править | править исходный текст]

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

Свойства безопасности и живучести[править | править исходный текст]

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

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

Предусловия[править | править исходный текст]

Вычислители[править | править исходный текст]

Сеть[править | править исходный текст]

Число процессоров[править | править исходный текст]

Роли[править | править исходный текст]

Кворум[править | править исходный текст]

Предложенное число и согласованное значение[править | править исходный текст]

Примеры реализации[править | править исходный текст]

Простой паксос[править | править исходный текст]

Мульти-паксос[править | править исходный текст]

Оптимизации[править | править исходный текст]

Дешёвый паксос[править | править исходный текст]

Сокращённый паксос[править | править исходный текст]

Обобщённый паксос[править | править исходный текст]

Византийский паксос[править | править исходный текст]

Остановимый паксос[править | править исходный текст]

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

Промышленное использование[править | править исходный текст]

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. 1 2 Pease, Marshall; Robert Shostak, Leslie Lamport (April 1980). “Reaching Agreement in the Presence of Faults”. Journal of the Association for Computing Machinery 27 (2). Проверено 2007-02-02.
  2. Lamport, Leslie (July 1978). “Time, Clocks and the Ordering of Events in a Distributed System”. Communications of the ACM 21 (7): 558–565. DOI:10.1145/359545.359563. Проверено 2007-02-02.

Ссылки[править | править исходный текст]