Общий порядок сообщений — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
[[Категория: Параллельное программирование]]
 
[[Категория: Параллельное программирование]]
 
В системах, которые отсылают одно сообщение нескольким процессам, могут обнаружиться неприятные спецэффекты даже если не нарушен синхронный порядок:
 
В системах, которые отсылают одно сообщение нескольким процессам, могут обнаружиться неприятные спецэффекты даже если не нарушен синхронный порядок:
[[Файл:distributed-total-order-wrong.png|400px]
+
 
 +
[[Файл:distributed-total-order-wrong.png|400px]]
  
 
Проблема в том, что в исходной модели нет операции "отправить сообщение нескольким получателям" и на самом деле $P$ и $S$ отправляют два независимых сообщения двум разным процессам.
 
Проблема в том, что в исходной модели нет операции "отправить сообщение нескольким получателям" и на самом деле $P$ и $S$ отправляют два независимых сообщения двум разным процессам.

Версия 10:52, 3 июня 2019

В системах, которые отсылают одно сообщение нескольким процессам, могут обнаружиться неприятные спецэффекты даже если не нарушен синхронный порядок:

Distributed-total-order-wrong.png

Проблема в том, что в исходной модели нет операции "отправить сообщение нескольким получателям" и на самом деле $P$ и $S$ отправляют два независимых сообщения двум разным процессам.

Расширим модель: введём для сообщения вместо обычного события $rcv(m)$ события $rcv_p(m)$ — процесс $p$ получил событие $m$ (определено для всех $p$ для broadcast-сообщений и только для некоторых $p$ в случае multicast/unicast).

Определение:
В системе с broadcast/multicast-сообщениями имеется полный порядок, если не существует двух сообщений $x$, $y$ и двух потоков $P$, $Q$ таких, что сообщения были приняты в этих потоках в разном порядке: $rcv_P(x) < rcv_P(y) \land rcv_Q(y) < rcv_Q(x)$.

Если у нас только unicast-сообщения, то полный порядок тривиально выполняется даже в асинхронном порядке.