Abstract-Motiverad av applikationer till sensor, peer-to-peer, och ad hoc-nätverk, studerar vi distribuerade algoritmer, även känd som skvaller algoritmer, för utbyte av information och för beräkning i ett godtyckligt ansluten nätverk av noder. Topologin för sådana nätverk ändras kontinuerligt när nya noder ansluter sig och gamla noder lämnar nätverket. Algoritmer för sådana nätverk måste vara robusta mot förändringar i topologin. Dessutom fungerar noder i sensornätverk under begränsade beräknings-, kommunikations- och energiresurser. Dessa begränsningar har motiverat utformningen av "gossip"-algoritmer: system som fördelar beräkningsbördan och där en nod kommunicerar med en slumpmässigt vald granne. Vi analyserar genomsnittsproblemet under skvallerrestriktionen för en godtycklig nätverksgraf, och finner att medeltiden för en skvalleralgoritm beror på det näst största eigenvärdet av en dubbelt stokastisk matris som karakteriserar algoritmen. Att utforma den snabbaste skvalleralgoritmen motsvarar att minimera detta eigenvärde, som är ett semidefinit program (SDP). I allmänhet kan SDP inte lösas på ett distribuerat sätt; men, utnyttja problemstrukturen, föreslår vi en distribuerad subgradient metod som löser optimeringsproblem över nätverket. Förhållandet mellan medeltiden och det näst största eigenvärdet relaterar naturligt till blandningstiden för en slumpmässig vandring med övergångssannolikheter som härrör från skvalleralgoritmen. Vi använder denna anslutning för att studera prestanda och skalning av skvalleralgoritmer på två populära nätverk: Wireless Sensor Networks, som är modellerade som Geometric Random Graphs, och Internet graf under den så kallade Preferential Connectivity (PC) modellen.
I annat fall beror deras konvergensgrad på nätgrafens eigengap.
Randomized gossip algorithms
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science']}