IEEE Transactions on Signal Processing · 2009 · 491 citations · 33 references
ComputingComputer ScienceComputer SystemsAlgorithmsComputer NetworksDistributed SystemsConsensus AlgorithmsConsensus ProtocolsDistributed AlgorithmsDistributed ComputingDistributed ConsensusWireless Sensor NetworksAd Hoc NetworksBroadcastBroadcast AlgorithmsBroadcastingConvergenceDistributed Broadcast AlgorithmsGossip AlgorithmsGossip-based Consensus
Motivated by applications to wireless sensor, peer-to-peer, and ad hoc networks, we study distributed broadcasting algorithms for exchanging information and computing in an arbitrarily connected network of nodes. Specifically, we study a broadcasting-based gossiping algorithm to compute the (possibly weighted) average of the initial measurements of the nodes at every node in the network. We show that the <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">broadcast</i> <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">gossip</i> <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">algorithm</i> converges almost surely to a consensus. We prove that the random consensus value is, in expectation, the average of initial node measurements and that it can be made arbitrarily close to this value in mean squared error sense, under a balanced connectivity model and by trading off convergence speed with accuracy of the computation. We provide theoretical and numerical results on the mean square error performance, on the convergence rate and study the effect of the ldquomixing parameterrdquo on the convergence rate of the broadcast gossip algorithm. The results indicate that the mean squared error strictly decreases through iterations until the consensus is achieved. Finally, we assess and compare the communication cost of the broadcast gossip algorithm to achieve a given distance to consensus through theoretical and numerical results.
33
Novel Type of Phase Transition in a System of Self-Driven Particles
Tamás Vicsek, András Czirók, Eshel Ben‐Jacob et al. · Physical Review Letters · 1995 · 7.4K citations · Full text
Fast linear iterations for distributed averaging
Lin Xiao, Stephen Boyd · Systems & Control Letters · 2004 · 2.8K citations