4528
правок
Атомарная широковещательная рассылка: различия между версиями
Материал из WEGA
Атомарная широковещательная рассылка (посмотреть исходный код)
Версия от 12:13, 20 ноября 2024
, 12:13→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 89: | Строка 89: | ||
Все три протокола основаны на классическом алгоритме затопления, или рассеяния информации [ ]. Каждое сообщение содержит временную метку T, имя инициирующего процессора s и обновление | Все три протокола основаны на классическом алгоритме затопления, или рассеяния информации [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, в порядке возрастания имени отправляющего процессора. Наконец, он удаляет все копии сообщений из своих журналов. | |||
Протокол работает следующим образом. Когда процессор инициирует атомарную широковещательную рассылку, он распространяет это сообщение, аналогично описанному выше алгоритму рассеяния. Основным исключением является то, что каждое сообщение, полученное после того, как показания локальных часов превысили крайний срок доставки этого сообщения, отбрасывается. Затем в локальное время T + | |||
'''Атомарная широковещательная рассылка при сбоях типа «ошибка синхронизации»''' | '''Атомарная широковещательная рассылка при сбоях типа «ошибка синхронизации»''' | ||
Второй протокол расширяет первый, добавляя к сообщениям счетчик переходов (т. е. счетчик, увеличивающийся на 1 при каждой передаче сообщения). С помощью этой информации каждый передающий процессор может определить, когда сообщение является своевременным, то есть если сообщение с временной меткой T и счетчиком переходов h получено в момент времени U, то должно выполняться следующее условие: | Второй протокол расширяет первый, добавляя к сообщениям счетчик переходов (т. е. счетчик, увеличивающийся на 1 при каждой передаче сообщения). С помощью этой информации каждый передающий процессор может определить, когда сообщение является своевременным, то есть если сообщение с временной меткой T и счетчиком переходов h получено в момент времени U, то должно выполняться следующее условие: | ||
(2) | (2) <math> T - h \varepsilon < U < T + h(\delta + \varepsilon)</math>. | ||
Перед передачей сообщения каждый процессор проводит вышеприведенную проверку на приемлемость и отбрасывает сообщение, если оно не удовлетворяет данному условию. Время завершения | Перед передачей сообщения каждый процессор проводит вышеприведенную проверку на приемлемость и отбрасывает сообщение, если оно не удовлетворяет данному условию. Время завершения <math>\Delta_t</math> протокола для случая ошибок синхронизации выглядит следующим образом: | ||
(3) | (3) <math>\Delta_t = \pi (\delta + \varepsilon) + d \delta + \varepsilon</math>. | ||
| Строка 124: | Строка 122: | ||
'''Атомарная широковещательная рассылка при сбоях типа «византийская ошибка»''' | '''Атомарная широковещательная рассылка при сбоях типа «византийская ошибка»''' | ||
Пусть имеется некоторый текст. Предполагается, что каждый процессор может сгенерировать для него подпись, которую не смогут подделать другие процессоры. Кроме того, каждый процессор знает имя каждого другого процессора в сети и имеет возможность проверить подлинность его подписи. | |||
Исходя из вышеуказанных предположений, третий протокол трансляции расширяет второй, добавляя к сообщениям подписи. Чтобы процессор (или канал связи) при использовании «византийского» протокола не мог подделать счетчик переходов, сообщение подписывается каждым процессором, который его передает. Например, сообщение, подписанное к процессорами <math>p_1, ..., p_k</math> выглядит следующим образом: | |||
(relayed,... (relayed, {first, T, </math>\sigma</math>, pi,s\) ,p2,s?) | |||
(relayed,... | |||
