4527
правок
Атомарная широковещательная рассылка: различия между версиями
Перейти к навигации
Перейти к поиску
Атомарная широковещательная рассылка (посмотреть исходный код)
Версия от 12:19, 20 ноября 2024
, 12:19→Границы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 137: | Строка 137: | ||
== Границы == | == Границы == | ||
В дополнение к трем представленным выше протоколам и их корректности, Кристиан и коллеги [ ] доказали следующие две нижних границы на время завершения протоколов атомарной широковещательной рассылки. | В дополнение к трем представленным выше протоколам и их корректности, Кристиан и коллеги [7] доказали следующие две нижних границы на время завершения протоколов атомарной широковещательной рассылки. | ||
'''Теорема 1. Если коммуникационная сеть G требует x шагов, то любой протокол атомарной широковещательной рассылки, способный перенести до | '''Теорема 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>.''' | ||
== Применение == | == Применение == | ||