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

• '''Знание размера сети''': протокол работает почти так же хорошо, если вместо фактического числа процессоров (т. е. n) дать «хорошую» верхнюю границу этого числа (обозначается N). Верхняя граница, полиномиальная от n, дает ту же самую временную сложность с поправкой на константный коэффициент (поскольку сложность логарифмически зависит от N).

• Обнаружение конфликтов: алгоритм и его сложность остаются действительными, даже если при возникновении конфликта не может быть получено ни одного сообщения.

• Простота и быстрота локальных вычислений: в каждый временной интервал каждый процессор выполняет постоянный объем локальных вычислений.

• Сложность по числу сообщений: каждый процессор активен в течение [log(We)] последовательных фаз, а среднее число передач за фазу составляет не более 2. Таким образом, ожидаемое число передач всей сети ограничено 2n - flog(We)].

• Адаптивность к изменению топологии и отказоустойчивость: протокол устойчив к некоторым изменениям в топологии сети. Например, ребра могут быть добавляться или удаляться в любое время, при условии, что сеть неизменных ребер остается связной. Это соответствует отказам или остановке работы ребер, так что система демонстрирует устойчивость к некоторым незлонамеренным сбоям.

• Ориентированные сети: протокол не использует подтверждения. Таким образом, он может применяться даже тогда, когда каналы связи не симметричны; иначе говоря, тот факт, что процессор v может передать сообщение процессору u, не означает, что и может передать сообщение v. (Соответствующей моделью сети, таким образом, является ориентированный граф). В реальной жизни такая ситуация возникает, например, когда v имеет более мощный передатчик, чем u.

Для детерминированных алгоритмов можно продемонстрировать нижнюю границу: для любого n существует семейство n-узловых сетей, такое, что каждая детерминированная широковещательная схема требует O(n) времени. Для любого непустого подмножества S С {1, 2...n g рассмотрим следующую сеть GS (рис. 1).

Узел 0 является источником, а узел n + 1 – стоком. Источник инициирует сообщение, и задача широковещательной передачи в GS заключается в том, чтобы достичь стока. Сложность проистекает из того факта, что разбиение среднего уровня (т. е. S) не известно заранее. Следующая теорема может быть доказана путем ряда сокращений до определенной «игры на попадание»:

'''Теорема 3. Каждый детерминированный протокол широковещательной передачи, корректный для всех n-узловых сетей, требует O(n) времени.'''

В работе [2] была допущена некоторая путаница в отношении модели широковещательной передачи. В ней ошибочно утверждалось, что нижняя граница справедлива и тогда, когда коллизия неотличима от отсутствия передачи. Ковальски и Пелц [5] опровергли это утверждение, показав, как можно вести широковещательную передачу за логарифмическое время во всех сетях типа GS.