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

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

Лампорт также дает общее определение часов следующим образом.

Предположим, что имеется некоторое произвольное полное упорядочение <math>\prec</math> процессов (например, уникальные имена, лексикографически упорядоченные). Лампорт расширяет отношение «произошло ранее» и определяет отношение "<math>\Rightarrow</math>" как полное упорядочение на множестве всех событий в системе.

В работе [5] Лампорт также обсуждает адаптацию этих условий к физическим часам и предлагает простой алгоритм синхронизации часов. Здесь эти вопросы рассматриваться не будут.

Задача репликации [[Конечный_автомат|конечного автомата]] была изначально предложена Лампортом [4, 5]. В более позднем обзоре задачи Шнайдер [8] определяет ее следующим образом (формулировка адаптирована к контексту данной статьи).

В работе [5], посвященной логическому времени и обсуждаемой в данной статье, Лампорт не учитывает ошибочные состояния. Он рассматривает их в другой работе, посвященной репликации конечного автомата для устойчивости к ошибкам [4] и опубликованной в том же году.