Причинно-следственное упорядочение, логические часы, репликация конечного автомата: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Данная статья охватывает несколько задач, тесно связанных друг с другом. Первая задача заключается в поддержке отношения причинно-следственной связи между событиями в распределенной системе. Это нужно для того, чтобы дать распределенным системам без явного доступа к физическим часам какое-то представление о времени. | Данная статья охватывает несколько задач, тесно связанных друг с другом. Первая задача заключается в поддержке отношения причинно-следственной связи между событиями в распределенной системе. Это нужно для того, чтобы дать распределенным системам без явного доступа к физическим часам какое-то представление о времени. Лэмпорт [5] определяет понятие логических часов, которые могут использоваться для генерации временных меток, согласующихся с отношениями причинно-следственной связи (в консервативном смысле слова). Он приводит в пример логические часы (также называемые часами Лэмпорта) с распределенным алгоритмом взаимного исключения. Этот алгоритм является иллюстрацией репликации конечного автомата. В сущности, он генерирует общее упорядочение событий, согласованное в масштабах всех процессов. Если все процессы начинаются в одном и том же состоянии, они развиваются согласованно, не требуя дальнейшей синхронизации. | ||
Строка 33: | Строка 33: | ||
'''Логические часы''' | '''Логические часы''' | ||
Лэмпорт также дает общее определение часов следующим образом. | |||
Строка 41: | Строка 41: | ||
Предположим, что имеется некоторое произвольное полное упорядочение <math>\prec</math> процессов (например, уникальные имена, лексикографически упорядоченные). | Предположим, что имеется некоторое произвольное полное упорядочение <math>\prec</math> процессов (например, уникальные имена, лексикографически упорядоченные). Лэмпорт расширяет отношение «произошло ранее» и определяет отношение "<math>\Rightarrow</math>" как полное упорядочение на множестве всех событий в системе. | ||
Строка 51: | Строка 51: | ||
В работе [5] | В работе [5] Лэмпорт также обсуждает адаптацию этих условий к физическим часам и предлагает простой алгоритм синхронизации часов. Здесь эти вопросы рассматриваться не будут. | ||
'''Репликация конечного автомата''' | '''Репликация конечного автомата''' | ||
Задача репликации [[Конечный_автомат|конечного автомата]] была изначально предложена | Задача репликации [[Конечный_автомат|конечного автомата]] была изначально предложена Лэмпортом [4, 5]. В более позднем обзоре задачи Шнайдер [8] определяет ее следующим образом (формулировка адаптирована к контексту данной статьи). | ||
Строка 70: | Строка 70: | ||
В работе [5], посвященной логическому времени и обсуждаемой в данной статье, | В работе [5], посвященной логическому времени и обсуждаемой в данной статье, Лэмпорт не учитывает ошибочные состояния. Он рассматривает их в другой работе, посвященной репликации конечного автомата для устойчивости к ошибкам [4] и опубликованной в том же году. | ||
== Основные результаты == | == Основные результаты == |