Атомарная широковещательная рассылка: различия между версиями

Все три протокола основаны на классическом алгоритме затопления, или рассеяния информации [14]. Каждое сообщение содержит временную метку T, имя инициирующего процессора s и обновление <math>\sigma</math>. Сообщение однозначно идентифицируется по паре (s, T). Основной протокол прост. Каждый процессор регистрирует каждое полученное сообщение до тех пор, пока оно не будет доставлено. Когда он получает сообщение, которого никогда не встречал раньше, он пересылает его всем соседним процессорам.

Первый протокол атомарной широковещательной рассылки, поддерживающий сбои типа «пропуск», рассматривает время завершения <math>\Delta_0</math> следующим образом.

(1) <math>\Delta_0 = \pi \delta + d \delta + \varepsilon</math>.

Крайний срок доставки <math>T + \Delta_0</math>o – это время, к которому процессор может быть уверен, что он получил копии всех сообщений с временной меткой T (или более ранними), которые могли быть получены некоторым исправным процессом.

Протокол работает следующим образом. Когда процессор инициирует атомарную широковещательную рассылку, он распространяет это сообщение, аналогично описанному выше алгоритму рассеяния. Основным исключением является то, что каждое сообщение, полученное после того, как показания локальных часов превысили крайний срок доставки этого сообщения, отбрасывается. Затем в локальное время <math>T + \Delta_0</math> процессор доставляет все сообщения, помеченные временной меткой T, в порядке возрастания имени отправляющего процессора. Наконец, он удаляет все копии сообщений из своих журналов.