Motiverade av applikationer till sensor, peer-to-peer, och adhoc nätverk, studerar vi problemet med datorfunktioner av värden vid noderna i ett nätverk på ett helt distribuerat sätt. I synnerhet anser vi att separata funktioner, som kan skrivas som linjära kombinationer av funktioner av enskilda variabler. Kända iterativa algoritmer för medelvärden kan användas för att beräkna normaliserade värden för sådana funktioner, men dessa algoritmer sträcker sig i allmänhet inte till beräkningen av de faktiska värdena för separata funktioner. Det viktigaste bidraget i detta dokument är utformningen av en distribuerad randomiserad algoritm för beräkning av separerbara funktioner baserat på egenskaper hos exponentiella slumpvariabler. Vi band drifttiden för vår algoritm i termer av drifttiden för en informationsspridning algoritm som används som en subrutin av algoritmen. Eftersom vi är intresserade av helt distribuerade algoritmer, anser vi att en randomiserad skvallermekanism för informationsspridning är subrutinen. Att kombinera dessa algoritmer ger en komplett och enkel distribuerad algoritm för att beräkna separerbara funktioner. Det andra bidraget i detta dokument är en analys av den information som sprider tiden för skvalleralgoritmen. Denna analys ger en övre gräns för informationsspridningstiden, och därmed en motsvarande övre gräns för algoritmens körtid för att beräkna separerade funktioner, när det gäller ledning av en lämplig stokastisk matris. Dessa gränser innebär att, för en klass av grafer med små spektralgap (såsom rutnätsdiagram), den tid som används av vår algoritm för att beräkna medelvärden är av en mindre ordning än den tid som krävs för beräkning av medelvärden av ett känt iterativt skvaller schema [5].
Merparten av litteraturen i skvaller algoritm inställning beräknar funktioner som genomsnitt, summa eller separerbara funktioner REF.
Computing separable functions via gossip
{'venue': "PODC '06", 'journal': None, 'mag_field_of_study': ['Computer Science']}