Nyligen har det funnits ett växande intresse för skvallerbaserade protokoll som använder slumpmässig kommunikation för att säkerställa en robust informationsspridning. I den här artikeln presenterar vi ett nytt skvallerbaserat system med hjälp av vilket alla noder i ett n-node overlay nätverk kan beräkna de gemensamma aggregaten av MIN, MAX, SUM, AVERAGE, och RANK av sina värden med hjälp av O(n logg n) meddelanden inom O(log n log n) rundor av kommunikation. Såvitt vi vet är vårt första resultat som visar hur man beräknar dessa aggregat med hög sannolikhet med endast O(n logg n) meddelanden. Däremot kräver den mest kända skvallerbaserade algoritmen för beräkning av dessa aggregat O(n log n) meddelanden och O(log n) rundor. Därför gör vår algoritm det möjligt för systemdesigners att byta bort en liten ökning av rund komplexitet med en betydande minskning av meddelande komplexitet. Detta kan leda till dramatiskt lägre nätstockningar och längre nodlivslängder i trådlösa nätverk och sensornätverk, där kanalbandbredd och batteritid är starkt begränsade.
I REF, Kashyap et al. studerade en randomiserad (gossip-baserad) schema med hjälp av vilken alla noder i en komplett overlay nätverk kan beräkna de gemensamma aggregaten av min, max, summa, genomsnitt, och rankning av deras värden med hjälp av Oðn log n på meddelanden inom Oðlog n log n på rundor av kommunikation.
Efficient gossip-based aggregate computation
{'venue': "PODS '06", 'journal': None, 'mag_field_of_study': ['Computer Science']}