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

В настоящее время авторы работ часто предпочитают определения задач атомарной широковещательной рассылки, не содержащие явных ссылок на физическое время. Множество вариантов определений без времени рассмотрено в работах Хадзилакоса и Туэга [10], а также Дефаго и др. [8]. Одно из таких альтернативных определений представлено ниже, а терминология адаптирована к контексту данной статьи.

1. '''Допустимость''': если исправный процессор рассылает сообщение m, то он в конечном итоге доставляет m.

4. '''Равномерный полный порядок без пробелов''': если некоторый процессор доставляет сообщение m0 после сообщения m, то он доставляет m0 только после того, как он доставил m.

Все три протокола основаны на классическом алгоритме затопления, или рассеяния информации [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, в порядке возрастания имени отправляющего процессора. Наконец, он удаляет все копии сообщений из своих журналов.

Второй протокол расширяет первый, добавляя к сообщениям счетчик переходов (т. е. счетчик, увеличивающийся на 1 при каждой передаче сообщения). С помощью этой информации каждый передающий процессор может определить, когда сообщение является своевременным, то есть если сообщение с временной меткой T и счетчиком переходов h получено в момент времени U, то должно выполняться следующее условие:

Исходя из вышеуказанных предположений, третий протокол трансляции расширяет второй, добавляя к сообщениям подписи. Чтобы процессор (или канал связи) при использовании «византийского» протокола не мог подделать счетчик переходов, сообщение подписывается каждым процессором, который его передает. Например, сообщение, подписанное к процессорами <math>p_1, ..., p_k</math> выглядит следующим образом:

Здесь <math>\sigma</math> – обновление, T – временная метка, <math>p_1</math> – источник сообщения, а <math>s_i</math> – подпись, сгенерированная процессором <math>p_i</math>. Любое сообщение, для которого одна из подписей не может быть аутентифицирована, просто отбрасывается. Кроме того, если несколько обновлений, инициированных одним и тем же процессором p, имеют одинаковую временную метку, это означает, что данный процессор неисправен, и соответствующие обновления отбрасываются. Оставшаяся часть протокола аналогична второму случаю, где количество переходов определяется количеством подписей. Время завершения <math>\Delta_b</math> также вычисляется следующим образом:

'''Теорема 1. Если коммуникационная сеть G требует <math>x</math> шагов, то любой протокол атомарной широковещательной рассылки, способный перенести до <math>\pi</math> отказов процессоров и <math>\lambda</math> отказов каналов связи, имеет время завершения не менее <math>x \delta + \varepsilon</math>.'''

'''Теорема 2. Любой протокол атомарной широковещательной рассылки для гамильтоновой сети с n процессорами, допускающий n - 2 аутентифицируемых византийских ошибок процессоров, не может иметь время завершения меньше <math>(n - 1)(\delta + \varepsilon)</math>.'''

* [[Детекторы отказов]]