1632
правки
Изменения
м
rollbackEdits.php mass rollback
[[Категория: Параллельное программирование]]
В распределённых системах могут быть разные гарантии порядка доставки отправленных сообщений.
Более того: иногда программисты могут неявно предполагать тот или иной порядок и очень удивляться, когда он нарушается.
[[Файл:distributed-order-fifo-wrong.png|400px]]
Очевидно, что FIFO также гарантирует асинхронный порядок.
== Причинно-согласованный порядок ==
Q -------b'---b--
</pre>
Причинно-согласованный порядок также гарантирует и FIFO-порядок, потому что из $a \le b$ следует $a \to b$.
== Синхронный порядок ==
Можно считать, что сообщения доставляются мгновенно.
В сочетании с линейным порядком событий внутри процессов получаем
{{Определение
|definition=
В системе есть '''синхронный порядок''' сообщений, если всем сообщениям можно сопоставить время $T(m)$ (число) так, что верно:
* Для любого сообщения $m$: $T(rcv(m))=T(snd(m))$ (обозначается $T(m)$).
* Для любых двух событий $e \to f$ верно $T(e)<T(f)$ (обратное может быть неверно), т.е. $T$ является [[Логические часы Лампорта|логическими часами]].
}}
Другими словами, можно рисовать стрелочки доставки сообщений строго вертикально.
Пример нарушения (причинно-согласованность не нарушена):
[[Файл:distributed-order-sync-wrong.png|400px]]
Синхронный порядок гарантирует причинно-согласованный порядок: от противного: пусть есть два сообщения $m, n$, причём $snd(m) \to snd(n)$ (тогда $T(m) < T(n)$) и $rcv(n) \to rcv(m)$ (тогда $T(n)<T(m)$), противоречие.
