4817
правок
Рандомизированная широковещательная передача в радиосетях: различия между версиями
Перейти к навигации
Перейти к поиску
м
Рандомизированная широковещательная передача в радиосетях (посмотреть исходный код)
Версия от 10:21, 4 июля 2025
, 4 июль→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 61: | Строка 61: | ||
дождаться получения сообщения, скажем m; | дождаться получения сообщения, скажем m; | ||
'''выполнить''' t раз { | '''выполнить''' t раз { | ||
дождаться (Time mod k) = 0; | дождаться (Time '''mod''' k) = 0; | ||
Decay(k, m); } | Decay(k, m); | ||
} | |||
Считается, что сеть выполняет схему широковещательной передачи Broadcast_scheme, если некоторый процессор, обозначаемый s, передает начальное сообщение, и каждый процессор выполняет описанную выше процедуру ''Broadcast''. | Считается, что сеть выполняет схему широковещательной передачи Broadcast_scheme, если некоторый процессор, обозначаемый как <math>s</math>, передает начальное сообщение, и каждый процессор выполняет описанную выше процедуру ''Broadcast''. | ||
'''Теорема 2. Пусть <math>T = 2D + 5 max \{ \sqrt{D}, \sqrt{log(n / \epsilon}) \} \cdot \sqrt{log(n / \epsilon})</math>. Предположим, что Broadcast_scheme запускается в момент времени Time = 0. Тогда с вероятностью | '''Теорема 2. Пусть <math>T = 2D + 5 max \{ \sqrt{D}, \sqrt{log(n / \epsilon}) \} \cdot \sqrt{log(n / \epsilon})</math>. Предположим, что Broadcast_scheme запускается в момент времени Time = 0. Тогда с вероятностью не менее <math>1 - 2 \epsilon</math> к моменту времени <math>2 \lceil log \; \Delta \rceil \cdot T</math> все узлы получат сообщение. Более того, с вероятностью не менее <math>1 - 2 \epsilon</math> все узлы завершат работу к моменту времени <math>2 \lceil log \; \Delta \rceil \cdot (T + \lceil log(N / \epsilon) \rceil )</math>.''' | ||
| Строка 78: | Строка 79: | ||
• '''Идентификаторы процессоров''': протокол не использует идентификаторы процессоров и, следовательно, не требует, чтобы процессоры имели различные идентификаторы (или чтобы они знали идентификаторы своих соседей). Более того, процессор даже не обязан знать количество своих соседей. Это свойство делает протокол адаптивным к изменениям топологии, происходящим на протяжении выполнения, и устойчивым к незлонамеренным сбоям. | • '''Идентификаторы процессоров''': протокол не использует идентификаторы процессоров и, следовательно, не требует, чтобы процессоры имели различные идентификаторы (или чтобы они знали идентификаторы своих соседей). Более того, процессор даже не обязан знать количество своих соседей. Это свойство делает протокол адаптивным к изменениям топологии, происходящим на протяжении выполнения, и устойчивым к незлонамеренным сбоям. | ||
• '''Знание размера сети''': протокол работает почти так же хорошо, если вместо фактического числа процессоров (т. е. <math>n</math>) дать «хорошую» верхнюю границу этого числа (обозначается <math>N</math>). Верхняя граница, полиномиальная от <math>n</math>, дает ту же самую временную сложность с поправкой на константный коэффициент (поскольку сложность логарифмически зависит от <math>N</math>). | • '''Знание размера сети''': протокол работает почти так же хорошо, если вместо фактического числа процессоров (т. е. <math>n</math>) дать ему «хорошую» верхнюю границу этого числа (обозначается <math>N</math>). Верхняя граница, полиномиальная от <math>n</math>, дает ту же самую временную сложность с поправкой на константный коэффициент (поскольку сложность логарифмически зависит от <math>N</math>). | ||
• '''Обнаружение конфликтов''': алгоритм и его сложность остаются действительными, даже если при возникновении конфликта не может быть получено ни одного сообщения. | • '''Обнаружение конфликтов''': алгоритм и его сложность остаются действительными, даже если при возникновении конфликта не может быть получено ни одного сообщения. | ||