Редактирование: Иерархия порядков сообщений

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
[[Категория: Параллельное программирование]]
 
 
В распределённых системах могут быть разные гарантии порядка доставки отправленных сообщений.
 
В распределённых системах могут быть разные гарантии порядка доставки отправленных сообщений.
 
Более того: иногда программисты могут неявно предполагать тот или иной порядок и очень удивляться, когда он нарушается.
 
Более того: иногда программисты могут неявно предполагать тот или иной порядок и очень удивляться, когда он нарушается.
Строка 22: Строка 21:
  
 
[[Файл:distributed-order-fifo-wrong.png|400px]]
 
[[Файл:distributed-order-fifo-wrong.png|400px]]
 
Очевидно, что FIFO также гарантирует асинхронный порядок.
 
  
 
== Причинно-согласованный порядок ==
 
== Причинно-согласованный порядок ==
Строка 44: Строка 41:
 
Q -------b'---b--
 
Q -------b'---b--
 
</pre>
 
</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)$), противоречие.
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: