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

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

Паксос — семейство протоколов для решения задачи консенсуса в сети ненадёжных вычислителей. Консенсус — процесс получения согласованного результата группой участников, основная проблема — наличие помех в среде передачи данных.[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.

Ссылки

  • Leslie Lamport, Dahlia Malkhi, Lidong Zhou Stoppable Paxos  (англ.) (PDF). Microsoft Research (28 April 2008). Архивировано из первоисточника 26 октября 2012. Проверено 26 августа 2012.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "Алгоритм Паксос" в других словарях:


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»