4817
правок
Атомарная широковещательная рассылка: различия между версиями
Материал из WEGA
Атомарная широковещательная рассылка (посмотреть исходный код)
Версия от 04:37, 21 ноября 2024
, 21 ноября 2024→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 107: | Строка 107: | ||
'''Атомарная широковещательная рассылка при сбоях типа «ошибка синхронизации»''' | '''Атомарная широковещательная рассылка при сбоях типа «ошибка синхронизации»''' | ||
Второй протокол расширяет первый, добавляя к сообщениям счетчик переходов (т. е. счетчик, увеличивающийся на 1 при каждой передаче сообщения). С помощью этой информации каждый передающий процессор может определить, | Второй протокол расширяет первый, добавляя к сообщениям счетчик переходов (т. е. счетчик, увеличивающийся на 1 при каждой передаче сообщения). С помощью этой информации каждый передающий процессор может определить, является ли сообщение своевременным: если сообщение с временной меткой T и счетчиком переходов h получено в момент времени U, то должно выполняться следующее условие: | ||
(2) <math> T - h \varepsilon < U < T + h(\delta + \varepsilon)</math>. | (2) <math> T - h \varepsilon < U < T + h(\delta + \varepsilon)</math>. | ||
| Строка 123: | Строка 123: | ||
Пусть имеется некоторый текст. Предполагается, что каждый процессор может сгенерировать для него подпись, которую не смогут подделать другие процессоры. Кроме того, каждый процессор знает имя каждого другого процессора в сети и имеет возможность проверить подлинность его подписи. | Пусть имеется некоторый текст. Предполагается, что каждый процессор может сгенерировать для него подпись, которую не смогут подделать другие процессоры. Кроме того, каждый процессор знает имя каждого другого процессора в сети и имеет возможность проверить подлинность его подписи. | ||
Исходя из вышеуказанных предположений, третий протокол трансляции расширяет второй, добавляя к сообщениям подписи. Чтобы процессор (или канал связи) при использовании «византийского» протокола не мог подделать счетчик переходов, сообщение подписывается каждым процессором, который его передает. Например, сообщение, подписанное | |||
Исходя из вышеуказанных предположений, третий протокол трансляции расширяет второй, добавляя к сообщениям подписи. Чтобы процессор (или канал связи) при использовании «византийского» протокола не мог подделать счетчик переходов, сообщение подписывается каждым процессором, который его передает. Например, сообщение, подписанное k процессорами <math>p_1, ..., p_k</math>, выглядит следующим образом: | |||
<math>(relayed,... (relayed, (first, T, \sigma, p_1, s_1), p_2, s_2), ..., p_k, s_k)</math>. | <math>(relayed,... (relayed, (first, T, \sigma, p_1, s_1), p_2, s_2), ..., p_k, s_k)</math>. | ||
Здесь <math>\sigma</math> – обновление, T – временная метка, <math>p_1</math> – источник сообщения, а <math>s_i</math> – подпись, сгенерированная процессором <math>p_i</math>. Любое сообщение, для которого одна из подписей не может быть аутентифицирована, просто отбрасывается. Кроме того, если несколько обновлений, инициированных одним и тем же процессором p, имеют одинаковую временную метку, это означает, что данный процессор неисправен, и соответствующие обновления отбрасываются. Оставшаяся часть протокола аналогична второму случаю, | Здесь <math>\sigma</math> – обновление, T – временная метка, <math>p_1</math> – источник сообщения, а <math>s_i</math> – подпись, сгенерированная процессором <math>p_i</math>. Любое сообщение, для которого одна из подписей не может быть аутентифицирована, просто отбрасывается. Кроме того, если несколько обновлений, инициированных одним и тем же процессором p, имеют одинаковую временную метку, это означает, что данный процессор неисправен, и соответствующие обновления отбрасываются. Оставшаяся часть протокола аналогична второму случаю, считая, что количество переходов определяется количеством подписей. Время завершения <math>\Delta_b</math> также вычисляется следующим образом: | ||
(4) <math>\Delta_b = \pi (\delta + \varepsilon) + d \delta + \varepsilon</math>. | (4) <math>\Delta_b = \pi (\delta + \varepsilon) + d \delta + \varepsilon</math>. | ||
