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

Основным результатом является рандомизированный протокол, который обеспечивает широковещательную передачу за время, оптимальное с точностью до логарифмического множителя. В частности, с вероятностью <math>1 - \epsilon</math> протокол обеспечивает широковещательную передачу за <math>O((D + log \; n / \epsilon) \cdot log \; n)</math> временных интервалов.

Далее следует описание процедуры отправки сообщения m, которая выполняется каждым процессором после получения m:

'''Теорема 1. Пусть <math>y</math> – вершина из <math>G</math>. Пусть <math>d \ge 2</math> соседей <math>y</math> выполняют процедуру ''Decay'' в течение интервала времени [0, k) (предполагается, что все они начинают выполнение в Time = 0). Тогда <math>P(k, d)</math> – вероятность того, что <math>y</math> получит сообщение к моменту Time = k – удовлетворяет следующим свойствам:

Протокол широковещательной передачи выполняет несколько вызовов процедуры ''Decay''(k, m). Согласно теореме 1 (2), чтобы вероятность получения сообщения процессором <math>y</math> была не ниже 1/2, параметр <math>k</math> должен быть не меньше <math>2 \; log \; d</math> (где <math>d</math> – число соседей, посылающих сообщение процессору <math>y</math>). Поскольку <math>d</math> неизвестно, параметр был выбран равным <math>k = 2 \lceil log \; \Delta \rceil</math> (напомним, что параметр <math>\Delta</math> был определен как верхняя граница полустепени захода). Теорема 1 также требует, чтобы все участники начинали выполнять процедуру ''Decay'' в один и тот же временной интервал. Поэтому ''Decay'' запускается только при целочисленных кратных <math>2 \lceil log \; \Delta \rceil</math>.