Gossip algoritmer sprida information i distribuerade nätverk av noder upprepade gånger vidarebefordra information till några slumpmässiga kontakter. Till sin natur tenderar skvalleralgoritmer att spridas och vara feltoleranta. Om de görs rätt kan de också vara snabba och budskapseffektiva. En vanlig modell för skvaller kommunikation är den slumpmässiga telefonsamtal modell, där i varje synkron runda varje nod kan PUSH eller PULL information till eller från en slumpmässig annan nod. Till exempel Karp et al. [FOCS 2000] gav algoritmer i den här modellen som sprider ett meddelande till alla noder i  till (log n) rundor medan endast O(log log n) meddelanden per nod i genomsnitt. De visade också att det i den här modellen är nödvändigt med minst  till (log n) rundor och att algoritmer som uppnår denna round-komplexitet måste skicka meddelanden per nod i genomsnitt. Nyligen, Avin och Elässer [DISC 2013], studerade slumpmässiga telefonsamtal modellen med den naturliga och allmänt använda antagandet om direkt adressering. Direkt adress tillåter noder att direkt kontakta noder vars ID (t.ex. IP-adress) lärdes tidigare. De visar att i denna inställning kan man "bryta log n-barriären" och uppnå en skvalleralgoritm som körs i O( ε log n) rundor, om än när man använder O( ε log n) meddelanden per nod. I den här artikeln studerar vi samma modell och ger en enkel skvalleralgoritm som sprider ett budskap i endast O(log log n) rundor. Vi bevisar dessutom en matchande en (log log n) nedre gräns som visar att denna körtid är bäst möjligt. I synnerhet visar vi att någon skvalleralgoritm tar med hög sannolikhet minst 0.99 log log n rundor att avsluta. Slutligen, vår algoritm kan tweaked att skicka endast O(1) meddelanden per nod i genomsnitt med endast O(log n) bitar per meddelande. Vår algoritm uppnår därför samtidigt den optimala rund-, meddelande- och bit-komplexiteten för denna inställning. Som alla tidigare skvalleralgoritmer, vår algoritm är också robust mot misslyckanden. I synnerhet, om i början en glömsk motståndare misslyckas någon F noder vår algoritm fortfarande, med hög sannolikhet, informerar alla utom o(F ) överlevande noder.
Haeupler och Malkhi REF generaliserade arbetet med en skvalleralgoritm som körs i O(ln ln n) rundor och skicka O(1) meddelanden per nod med O(ln n) bitar per meddelande, som alla är optimala.
Optimal gossip with direct addressing
{'venue': "PODC '14", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}