Рандомизированная широковещательная передача в радиосетях: различия между версиями

Модель состоит из произвольной (неориентированной) сети, процессоры которой общаются в синхронных временных интервалах, подчиняясь следующим правилам. В каждом временном интервале каждый процессор выступает либо в роли передатчика, либо в роли приемника. Мы говорим, что процессор, выступающий в роли приемника, получает сообщение во временном интервале t, если ровно один из его соседей ведет передачу в этом временном интервале. Полученное сообщение соответствует переданному. Если в данном временном интервале несколько соседей ведут передачу, возникает конфликт. В этом случае приемник может либо получить сообщение от одного из передающих соседей, либо не получить никакого сообщения. Предполагается, что конфликты (или «коллизии») необнаружимы, поэтому процессор не может отличить случай, когда ни один сосед не ведет передачу, от случая, когда два или более его соседей передают в этом временном интервале. Процессоры не обязаны иметь идентификаторы и не знают своих соседей; в частности, процессорам неизвестна топология сети.

Единственными входными данными, необходимыми протоколу, являются количество процессоров в сети – n, A – априорно известная верхняя граница максимальной степени сети и граница ошибки – e. (Все границы априорно известны алгоритму).

Широковещательная передача – это задача, инициируемая одним процессором, называемым источником, который передает одно сообщение. Цель состоит в том, чтобы сообщение достигло всех процессоров в сети.