Vi presenterar en randomiserad distribuerad algoritm som i radionätverk med kollisionsdetektering sänder ett enda meddelande i O(D + log 6 n) rundor, med hög sannolikhet. Denna tids komplexitet är mest intressant på grund av dess optimala additiva beroende av nätverksdiameter D. Den förbättrar över de för närvarande mest kända O(D log n D + log 2 n) algoritmer, på grund av Czumaj och Rytter [FOCS 2003], och Kowalski och Pelc [PODC 2003]. Dessa algoritmer är konstruerade för modellen utan kollisionsdetektering och är optimala i den modellen. Som Peleg uttryckligen påpekade i sin 2007 års undersökning om radiosändningar i radionät var det dock fortfarande en öppen fråga om huruvida gränsen kan förbättras med kollisionsdetektering. Vi studerar också distribuerade algoritmer för att sända k-meddelanden från en enda källa till alla noder. Detta problem är en naturlig och viktig generalisering av problemet med ett enda meddelande, men är i själva verket betydligt mer utmanande och mindre förståeligt. Vi visar följande resultat: Om nätverkets topologi är känd för alla noder, då kan en k-meddelandesändning utföras i O(D+k log n+log 2 n) rundor, med hög sannolikhet. Om topologin inte är känd, men kollisionsdetektering är tillgänglig, kan en k-meddelandesändning utföras i O(D + k log n + log 6 n) rundor, med hög sannolikhet. Den första bundet är optimal och den andra är optimal modulo tillsatsen O(log 6 n) term.
I modellen med kollisionsdetektering, en O(D + log 6 n)-tid randomiserad algoritm på grund av Ghaffari et al. REF är den första att utnyttja kollisioner och överträffa algoritmer (och lägre gräns) för sändning utan kollisionsdetektering.
Randomized broadcast in radio networks with collision detection
{'venue': "PODC '13", 'journal': None, 'mag_field_of_study': ['Computer Science']}