1294
правки
Атомарная широковещательная рассылка: различия между версиями
Материал из WEGA
Атомарная широковещательная рассылка (посмотреть исходный код)
Версия от 03:26, 22 ноября 2024
, 22 ноября 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 4 промежуточные версии 1 участника) | |||
| Строка 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>. | ||
| Строка 140: | Строка 142: | ||
'''Теорема 1. Если коммуникационная сеть G требует <math>x</math> шагов, то любой протокол атомарной широковещательной рассылки, | '''Теорема 1. Если коммуникационная сеть G требует <math>x</math> шагов, то любой протокол атомарной широковещательной рассылки, допускающий до <math>\pi</math> отказов процессоров и <math>\lambda</math> отказов каналов связи, имеет время завершения не менее <math>x \delta + \varepsilon</math>.''' | ||
'''Теорема 2. Любой протокол атомарной широковещательной рассылки для гамильтоновой сети с n процессорами, допускающий n - 2 | '''Теорема 2. Любой протокол атомарной широковещательной рассылки для гамильтоновой сети с n процессорами, допускающий n - 2 выявляемых с помощью аутентификации византийских ошибок процессоров, не может иметь время завершения меньше <math>(n - 1)(\delta + \varepsilon)</math>.''' | ||
== Применение == | == Применение == | ||
| Строка 162: | Строка 164: | ||
* [[Причинно-следственное упорядочение, логические часы, репликация конечного автомата]] | * [[Причинно-следственное упорядочение, логические часы, репликация конечного автомата]] | ||
* [[Синхронизация часов]] | * [[Синхронизация часов]] | ||
* [[Детекторы | * [[Детекторы сбоев]] | ||
== Литература == | == Литература == | ||
| Строка 194: | Строка 196: | ||
15. Wiesmann, M., Schiper, A.: Comparison of database replication techniques based on total order broadcast. IEEE Trans. Knowl. Data Eng. 17, 551-566 (2005) | 15. Wiesmann, M., Schiper, A.: Comparison of database replication techniques based on total order broadcast. IEEE Trans. Knowl. Data Eng. 17, 551-566 (2005) | ||
[[Категория: Совместное определение связанных терминов]] | |||
