4817
правок
Рандомизированная широковещательная передача в радиосетях: различия между версиями
Материал из WEGA
Рандомизированная широковещательная передача в радиосетях (посмотреть исходный код)
Версия от 10:25, 4 июля 2025
, 4 июль→Литература
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Литература) |
||
| Строка 122: | Строка 122: | ||
Последующие работы продемонстрировали оптимальность рандомизированного алгоритма: | Последующие работы продемонстрировали оптимальность рандомизированного алгоритма: | ||
• Алон и др. [1] доказали существование семейства сетей радиуса 2 с <math>n</math> вершинами, для которых любое расписание широковещательной передачи требует не менее <math>\Omega(log^2 \; n)</math> временных | • Алон и др. [1] доказали существование семейства сетей радиуса 2 с <math>n</math> вершинами, для которых любое расписание широковещательной передачи требует не менее <math>\Omega(log^2 \; n)</math> временных интервалов. | ||
• Кушилевиц и Мансур [7] показали, что для любого рандомизированного широковещательного протокола существует сеть, в которой ожидаемое время передачи сообщения равно <math>\Omega(D \; log(N/D))</math>. | • Кушилевиц и Мансур [7] показали, что для любого рандомизированного широковещательного протокола существует сеть, в которой ожидаемое время передачи сообщения равно <math>\Omega(D \; log(N/D))</math>. | ||
• Бруски и Дель Пинто [3] показали, что для любого детерминированного алгоритма | • Бруски и Дель Пинто [3] показали, что для любого детерминированного распределенного алгоритма шировокещательной передачи, любых <math>n</math> и <math>D \le n/2</math> существует сеть с <math>n</math> узлами диаметром <math>D</math>, такая, что время, необходимое для широковещательной передачи, равно <math>\Omega(D \; log \; n)</math>. | ||
• Ковальски и Пелц [6] обсудили сети, в которых коллизии неотличимы от отсутствия передачи. Они представили нижнюю границу <math>\Omega(n \; log \; n/log(n/D))</math> и верхнюю границу <math>O(n \; log \; n)</math>. Для этой модели они также предложили рандомизированный алгоритм <math>O(D \; log \; n + log^2 \; n)</math>, подтвердив нижнюю границу из [1] и улучшив границу из работы [2] для графов, для которых <math>D = \theta(n/log \;n)</math>. | • Ковальски и Пелц [6] обсудили сети, в которых коллизии неотличимы от отсутствия передачи. Они представили нижнюю границу <math>\Omega(n \; log \; n/log(n/D))</math> и верхнюю границу <math>O(n \; log \; n)</math>. Для этой модели они также предложили рандомизированный алгоритм <math>O(D \; log \; n + log^2 \; n)</math>, подтвердив нижнюю границу из [1] и улучшив границу из работы [2] для графов, для которых <math>D = \theta(n/log \;n)</math>. | ||
