Vi presenterar en snabbare distribuerad sändning primitiv för den klassiska radionätsmodellen. Det mest grundläggande distribuerade radionätet som sänder primitiva - kallade Decay - går tillbaka till ett PODC'87 resultat av Bar-Yehuda, Goldreich, och Itai. I alla radionätverk med några informerade källa noder, kör Decay för O(d log n + log 2 n) rundor informerar alla noder som mest d hoppar bort från en källa med hög sannolikhet. Sedan 1987 har detta primitiva varit den viktigaste byggstenen för att genomföra många andra funktioner i radionät. De enda förbättringarna av denna decennier gamla algoritm är små variationer på grund av [Czumaj, Rytter; FOCS'03] och [Kowalski och Pelc, PODC'03] som uppnår samma funktionalitet i O(d log n d + log 2 n) rundor. För att uppnå en hastighetshöjning av detta måste d och därmed även nätverksdiametern vara nära linjär, dvs. större än n 1−. Vår nya distribuerade primitiva sprider meddelanden för d humle i O(d log n log log n log d + log O(1) n) rundor med hög sannolikhet. Detta förbättrar över Decay för alla super-polylogaritmiska d = log en (1) n och uppnår nära-optimal O(d log n) körtid för d = n. Detta gör också framsteg i en öppen fråga om Peleg.
D. Observera att Haeupler och Wajc REF utformade en primitiv radiosändning med komplexitet O(D log n log log n log D + log O(1) n) w.h.p.
A Faster Distributed Radio Broadcast Primitive: Extended Abstract
{'venue': "PODC '16", 'journal': None, 'mag_field_of_study': ['Computer Science']}