Срез, согласованный срез — различия между версиями
Yeputons (обсуждение | вклад) |
Yeputons (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
Пусть $E$ — множество событий с полным порядком ($<$) в рамках каждого процесса. | Пусть $E$ — множество событий с полным порядком ($<$) в рамках каждого процесса. | ||
| − | |||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
'''Срез''' $F$ — подмножество $E$ такое, что если $e < f \in F$, то $e \in F. | '''Срез''' $F$ — подмножество $E$ такое, что если $e < f \in F$, то $e \in F. | ||
| − | }} | + | }} |
| − | |||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
'''Согласованный срез''' $G$ — подмножество $E такое, что <tex>\forall f \in E, \forall g \in G : f \rightarrow g \Rightarrow f \in G</tex>. | '''Согласованный срез''' $G$ — подмножество $E такое, что <tex>\forall f \in E, \forall g \in G : f \rightarrow g \Rightarrow f \in G</tex>. | ||
}} | }} | ||
| − | |||
Это означает, что не существует сообщения переданного "через срез" в обратную сторону, т.е не бывает такого, что событие отправки сообщения не вошло в согласованный срез, а принятия вошло (см. рисунок <tex>m_1</tex> - несогласованный срез, <tex>m_2</tex> - согласованный срез). Можем говорить о том, что согласованный срез показывает некий глобальный снимок нашей системы. | Это означает, что не существует сообщения переданного "через срез" в обратную сторону, т.е не бывает такого, что событие отправки сообщения не вошло в согласованный срез, а принятия вошло (см. рисунок <tex>m_1</tex> - несогласованный срез, <tex>m_2</tex> - согласованный срез). Можем говорить о том, что согласованный срез показывает некий глобальный снимок нашей системы. | ||
Версия 20:42, 2 июня 2019
Мотивация: если у распределенной системы нет «глобального состояния», то как запомнить её состояние на диске, чтобы можно было продолжить работу после восстановления с диска?
Пусть $E$ — множество событий с полным порядком ($<$) в рамках каждого процесса.
| Определение: |
| Срез $F$ — подмножество $E$ такое, что если $e < f \in F$, то $e \in F. |
| Определение: |
| Согласованный срез $G$ — подмножество $E такое, что . |
Это означает, что не существует сообщения переданного "через срез" в обратную сторону, т.е не бывает такого, что событие отправки сообщения не вошло в согласованный срез, а принятия вошло (см. рисунок - несогласованный срез, - согласованный срез). Можем говорить о том, что согласованный срез показывает некий глобальный снимок нашей системы.
Эквивалентное определение: не существует $f \in G, e \in E \setminus G$ таких, что $e \to f$.
