4817
правок
Рандомизированная широковещательная передача в радиосетях: различия между версиями
Перейти к навигации
Перейти к поиску
м
Рандомизированная широковещательная передача в радиосетях (посмотреть исходный код)
Версия от 13:48, 3 июля 2025
, 3 июль→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
'''Рандомизированные протоколы''' | '''Рандомизированные протоколы''' | ||
'''Процедура Decay''' | '''Процедура Decay''' | ||
| Строка 55: | Строка 54: | ||
'''Протокол широковещательной передачи (Broadcast)''' | '''Протокол широковещательной передачи (Broadcast)''' | ||
Протокол широковещательной передачи выполняет несколько вызовов процедуры Decay(k, m). Согласно теореме 1 (2), чтобы вероятность получения сообщения процессором y была не ниже 1/2, параметр k должен быть не меньше 2 log d (где d – число соседей, посылающих сообщение процессору y). Поскольку d неизвестно, параметр был выбран равным | Протокол широковещательной передачи выполняет несколько вызовов процедуры ''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>. | ||
procedure Broadcast; | '''procedure''' Broadcast; | ||
t = | <math>k = 2 \lceil log \; \Delta \rceil</math>; | ||
<math>t = 2 \lceil log(N / \epsilon \rceil</math>; | |||
дождаться получения сообщения, скажем m; | дождаться получения сообщения, скажем m; | ||
выполнить t раз { | '''выполнить''' t раз { | ||
дождаться (Time mod k) = 0; | |||
Decay(k, m); } | Decay(k, m); } | ||
Считается, что сеть выполняет схему широковещательной передачи Broadcast_scheme, если некоторый процессор, обозначаемый s, передает начальное сообщение, и каждый процессор выполняет описанную выше процедуру Broadcast. | Считается, что сеть выполняет схему широковещательной передачи Broadcast_scheme, если некоторый процессор, обозначаемый s, передает начальное сообщение, и каждый процессор выполняет описанную выше процедуру ''Broadcast''. | ||
'''Теорема 2. Пусть | '''Теорема 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)~\).''' | ||