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.
rundor om topologin är känd i REF.
Randomized broadcast in radio networks with collision detection
{'venue': "PODC '13", 'journal': None, 'mag_field_of_study': ['Computer Science']}