Причинно-следственное упорядочение, логические часы, репликация конечного автомата: различия между версиями

Прежде всего, понятие причинно-следственной связи в распределенных системах (либо его отсутствие) приводит к известной проблеме, когда пользователь потенциально может увидеть ответ до того, как увидит соответствующий вопрос. Независимая от времени характеризация причинно-следственной связи Лэмпорта способствует разработке эффективных решений для организации причинно-следственного упорядочения в коммуникациях. В более поздней работе [ ] Лэпморт предлагает более общее определение отношения «произошло ранее», благодаря чему система может быть характеризована на различных уровнях абстракции.

Спустя десять лет после разработки Лэмпортом идеи логических часов Фидж Fidge [2] и Мэттерн [6] разработали понятие векторных часов, преимуществом которого является полная характеризация причинно-следственного упорядочения. И в самом деле, условие, которое является обязательным для логических часов Лэмпорта, является только односторонней импликацией (см. определение 3). Напротив, векторные часы расширяют понятие логических часов Лэмпорта за счет того, что гарантируют, что для любых событий a и b в случае Chai < Chbi верно a ! b. Это может оказаться полезным, например, при выборе множества контрольных точек после восстановления распределенной системы, для распределенной отладки или обнаружения взаимоблокировок. Другие предлагавшиеся расширения идеи логических часов рассмотрели в своем обзоре Рейналь и Сингал [7].

Алгоритм взаимного исключения, предложенный Лэмпортом в [ ] и описанный в данной статье, является одним из первых известных решений задачи атомарной широковещательной передачи. Вкратце, для системы с несколькими процессами, одновременно отправляющими широковещательные сообщения, эта задача требует, чтобы все процессы доставляли (и обрабатывали) все сообщения в одном и том же порядке. На сегодня существует уже несколько подходов к решению этой задачи. Изучив множество алгоритмов, Дефаго и др. [я] классифицировали алгоритм Лэмпорта как алгоритмы истории коммуникаций в силу способа генерации упорядочения.