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

'''Теорема 2. Пусть T = 2D + 5maxfpD y/log(n/e)} ■ y/log(n/e). Предположим, что Broadcast_scheme запускается в момент времени Time = 0. Тогда с вероятностью > 1 - 2e к моменту времени 2 dlog A] ■ T все узлы получат сообщение. Более того, с вероятностью > 1 - 2e, все узлы завершат работу к моменту времени 2 dlog A\ ■ (T + \log(N/e)~\).'''

Дополнительные свойства протокола широковещательной передачи:

• Идентификаторы процессоров: протокол не использует идентификаторы процессоров и, следовательно, не требует, чтобы процессоры имели различные идентификаторы (или чтобы они знали идентификаторы своих соседей). Более того, процессор даже не обязан знать количество своих соседей. Это свойство делает протокол адаптивным к изменениям топологии, происходящим на протяжении выполнения, и устойчивым к незлонамеренным сбоям.

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