Срез, согласованный срез

Материал из Викиконспекты
Перейти к: навигация, поиск

Мотивация: если у распределенной системы нет «глобального состояния», то как запомнить её состояние на диске, чтобы можно было продолжить работу после восстановления с диска?

Пусть $E$ — множество событий с полным порядком ($<$) в рамках каждого процесса.

Определение:
Срез $F$ — подмножество $E$ такое, что если $e < f \in F$, то $e \in F.


Определение:
Согласованный срез $G$ — подмножество $E такое, что [math]\forall f \in E, \forall g \in G : f \rightarrow g \Rightarrow f \in G[/math].

Это означает, что не существует сообщения переданного "через срез" в обратную сторону, т.е не бывает такого, что событие отправки сообщения не вошло в согласованный срез, а принятия вошло (см. рисунок [math]m_1[/math] - несогласованный срез, [math]m_2[/math] - согласованный срез). Можем говорить о том, что согласованный срез показывает некий глобальный снимок нашей системы.

Consistent.png

Эквивалентное определение: не существует $f \in G, e \in E \setminus G$ таких, что $e \to f$.