Локальные вычисления в неструктурированных радиосетях: различия между версиями

'''Теорема 1. Если n неизвестно узлам, то в односкачковых сетях каждый (возможно, рандомизированный) алгоритм требует до <math>\Omega( n / log \; n)</math> временных интервалов, прежде чем хотя бы один узел сможет отправить сообщение.'''

Для односкачковых сетей и случая, когда n известно глобально, в [8] представлен рандомизированный алгоритм, который с высокой вероятностью выбирает уникального лидера за время <math>O(n \; log \; n)</math>. Впоследствии Юрдзински и Стаховяк [9] улучшили этот результат до <math>O(log^2 \; n)</math>. Обобщенная задача пробуждения в многоскачковой радиосети была впервые изучена в работе [4].