4817
правок
Рандомизированная широковещательная передача в радиосетях: различия между версиями
Перейти к навигации
Перейти к поиску
м
Рандомизированная широковещательная передача в радиосетях (посмотреть исходный код)
Версия от 13:41, 3 июля 2025
, 3 июль→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
== Основные результаты == | == Основные результаты == | ||
Основным результатом является рандомизированный протокол, который обеспечивает широковещательную передачу за время, оптимальное с точностью до логарифмического множителя. В частности, с вероятностью 1- | Основным результатом является рандомизированный протокол, который обеспечивает широковещательную передачу за время, оптимальное с точностью до логарифмического множителя. В частности, с вероятностью <math>1 - \epsilon</math> протокол обеспечивает широковещательную передачу за <math>O((D + log \; n / \epsilon) \cdot log \; n)</math> временных интервалов. | ||
С другой стороны, была доказана линейная нижняя граница временной сложности широковещательной передачи в детерминированном варианте. А именно, любой детерминированный протокол широковещательной передачи требует | С другой стороны, была доказана линейная нижняя граница временной сложности широковещательной передачи в детерминированном варианте. А именно, любой детерминированный протокол широковещательной передачи требует <math>\Omega(n)</math> временных интервалов, даже если сеть имеет диаметр 3, а <math>n</math> известно всем процессорам. Эти два результата демонстрируют экспоненциальный разрыв в сложности между рандомизацией и детерминизмом. | ||
| Строка 31: | Строка 31: | ||
Далее следует описание процедуры отправки сообщения m, которая выполняется каждым процессором после получения m: | Далее следует описание процедуры отправки сообщения m, которая выполняется каждым процессором после получения m: | ||
procedure Decay(k, m); | '''procedure''' Decay(k, m); | ||
'''repeat''' не более k раз (но не менее одного раза!) | |||
отправить m всем соседям; | |||
задать значение броска монеты coin равным 0 или 1 с равной вероятностью, | |||
'''until''' coin = 0. | |||
| Строка 38: | Строка 41: | ||
'''Теорема 1. Пусть y – вершина из G. Пусть d > | '''Теорема 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 – удовлетворяет следующим свойствам: | ||
1. | 1. <math>lim_{k \to \infty} P(k, d) \ge 2/3</math>; | ||
2. для k > | 2. для <math>k \ge 2 \lceil log \; d \rceil</math> верно <math>P(k, d) > 1/2</math>. | ||
(Все логарифмы приведены к основанию 2).''' | (Все логарифмы приведены к основанию 2).''' | ||