Vi studerar skvalleralgoritmer för ryktet sprider problem, som ber varje nod att leverera ett rykte till alla noder i ett okänt nätverk. Gossip algoritmer tillåter noder bara att ringa en granne per runda och har nyligen lockat uppmärksamhet som meddelande effektiva, enkla och robusta lösningar på ryktet sprider problemet. En lång serie av tidningar analyserade utförandet av enhetliga slumpmässig skvaller där noder upprepade gånger kallar en slumpmässig granne att utbyta alla rykten med. Ett huvudresultat av detta arbete var att enhetligt skvaller fullbordas i O( log n 0 ) rundor där 0 är ledning av nätverket. Mer nyligen utformades icke-uniforma slumpmässiga skvallerprogram för att möjliggöra effektiv ryktesspridning i nätverk med flaskhalsar. I synnerhet gav STOC'12] en O(log 3 n)-algoritm för att lösa det 1-lokala sändningsproblemet där varje nod vill utbyta rykten lokalt med sin 1-grannskap. Genom att upprepade gånger tillämpa detta protokoll kan man lösa det globala ryktet som sprids snabbt för alla nätverk med liten diameter, oberoende av ledning. Alla dessa algoritmer är i sig randomiserade i sin design och analys. En parallell forskningsriktning har varit att minska och bestämma mängden slumpmässighet som behövs för effektiv ryktesspridning. Detta har gjorts via lägre gränser för begränsade modeller och genom att utforma skvalleralgoritmer med ett minskat behov av slumpmässighet, t.ex. genom att använda pseudorandomgeneratorer med korta slumpmässiga frön. Den allmänna intuitionen och samförståndet om dessa resultat har varit att randomisering spelar en viktig roll för att effektivt sprida rykten och att åtminstone ett polylogaritmiskt antal slumpmässiga bitar behövs. I detta papper vi förbättrar över denna state of the art på flera sätt genom att presentera en deterministisk skvaller algoritm som löser den k-lokala sändningsproblem i 2 k + log n) log n rundor 1. Förutom att vara den första effektiva deterministiska lösningen på ryktet spridning problem denna algoritm är intressant i många aspekter: Det är enklare, mer naturligt, mer robust, och snabbare än dess randomiserade hänge och garanterar framgång med säkerhet i stället för med hög sannolikhet. Analysen är dessutom enkel, fristående och skiljer sig i grunden från tidigare arbeten. * Konferensversionen av denna uppsats publicerades i ACM-SIAM Symposium for Discrete Algorithms [18] där den vann en bästa studentuppsats. 1 Under hela denna papperslogg x betecknar log 2 x, Det vill säga den rundade upp binära logaritmen.
Senast Haeupler REF föreslog en helt deterministisk algoritm som sprider ett rykte med 2 D + log n) log n rundor (men också kräver obegränsad meddelandestorlek).
Simple, Fast and Deterministic Gossip and Rumor Spreading
{'venue': None, 'journal': 'arXiv: Data Structures and Algorithms', 'mag_field_of_study': ['Computer Science', 'Mathematics']}