4488
правок
Причинно-следственное упорядочение, логические часы, репликация конечного автомата: различия между версиями
Перейти к навигации
Перейти к поиску
м
Причинно-следственное упорядочение, логические часы, репликация конечного автомата (посмотреть исходный код)
Версия от 22:49, 25 марта 2017
, 25 марта 2017→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 41: | Строка 41: | ||
Предположим, что имеется некоторое произвольное полное упорядочение | Предположим, что имеется некоторое произвольное полное упорядочение <math>\prec</math> процессов (например, уникальные имена, лексикографически упорядоченные). Лампорт расширяет отношение «произошло ранее» и определяет отношение "<math>\Rightarrow</math>" как полное упорядочение на множестве всех событий в системе. | ||
Определение 4. Отношение полного упорядочения | '''Определение 4'''. Отношение полного упорядочения <math>\Rightarrow</math> определяется следующим образом. Если <math>a \;</math> – событие в процессе <math>p_i \;</math>, а <math>b \;</math> – событие в процессе <math>p_j \;</math>, тогда <math>a \Rightarrow b</math> в том и только том случае, когда удовлетворяется одно из следующих условий: | ||
1. | 1. <math>C_i \langle a \rangle < C_j \langle b \rangle</math> | ||
2. | 2. <math>C_i \langle a \rangle = C_j \langle b \rangle</math> и <math>p_i \prec p_j</math>. | ||
В работе [ ] Лампорт также обсуждает адаптацию этих условий к физическим часам и предлагает простой алгоритм синхронизации часов. Здесь эти вопросы рассматриваться не будут. | В работе [5] Лампорт также обсуждает адаптацию этих условий к физическим часам и предлагает простой алгоритм синхронизации часов. Здесь эти вопросы рассматриваться не будут. | ||
'''Репликация конечного автомата''' | '''Репликация конечного автомата''' | ||
Задача репликации [[Конечный_автомат|конечного автомата]] была изначально предложена Лампортом [4, 5]. В более позднем обзоре задачи Шнайдер [ ] определяет ее следующим образом (формулировка адаптирована к контексту данной статьи). | Задача репликации [[Конечный_автомат|конечного автомата]] была изначально предложена Лампортом [4, 5]. В более позднем обзоре задачи Шнайдер [8] определяет ее следующим образом (формулировка адаптирована к контексту данной статьи). | ||
Задача 1. (Репликация конечного автомата) | '''Задача 1'''. (Репликация конечного автомата) | ||
Дано: Множество одновременных запросов. Требуется: найти последовательность запросов, обрабатываемых каждым процессом, такую, что: | Дано: Множество одновременных запросов. Требуется: найти последовательность запросов, обрабатываемых каждым процессом, такую, что: | ||
| Строка 70: | Строка 70: | ||
В работе [ ], посвященной логическому времени и обсуждаемой в данной статье, Лампорт не учитывает ошибочные состояния. Он рассматривает их в другой работе, посвященной репликации конечного автомата для устойчивости к ошибкам [ ] и опубликованной в том же году. | В работе [5], посвященной логическому времени и обсуждаемой в данной статье, Лампорт не учитывает ошибочные состояния. Он рассматривает их в другой работе, посвященной репликации конечного автомата для устойчивости к ошибкам [4] и опубликованной в том же году. | ||
== Основные результаты == | == Основные результаты == | ||