This paper presents greedy gossip with eavesdropping (GGE), a novel randomized gossip algorithm for distributed computation of the average consensus problem. In gossip algorithms, nodes in the network randomly communicate with their neighbors and exchange information iteratively. The algorithms are simple and decentralized, making them attractive for wireless network applications. In general, gossip algorithms are robust to unreliable wireless conditions and time varying network topologies. In this paper, we introduce GGE and demonstrate that greedy updates lead to rapid convergence. We do not require nodes to have any location information. Instead, greedy updates are made possible by exploiting the broadcast nature of wireless communications. During the operation of GGE, when a node decides to gossip, instead of choosing one of its neighbors at random, it makes a greedy selection, choosing the node which has the value most different from its own. In order to make this selection, nodes need to know their neighbors' values. Therefore, we assume that all transmissions are wireless broadcasts and nodes keep track of their neighbors' values by eavesdropping on their communications. We show that the convergence of GGE is guaranteed for connected network topologies. We also study the rates of convergence and illustrate, through theoretical bounds and numerical simulations, that GGE consistently outperforms randomized gossip and performs comparably to geographic gossip on moderate-sized random geometric graph topologies.
The convergence rate of randomized gossip is characterized by relating the algorithm to a Markov chain @cite_19 . The mixing time of this Markov chain is closely related to the averaging time of the gossip algorithm, and therefore defines the rate of convergence. For certain types of graph topologies, the mixing times are small and convergence of the gossip algorithm is fast. For example, in the case of a complete graph, the algorithm requires @math iterations to converge. However topologies such as random geometric graphs @cite_2 or grids are more realistic for wireless applications. @cite_19 prove that for random geometric graphs, randomized gossip requires @math transmissions to approximate the average consensus well Throughout this paper, when we refer to randomized gossip we specifically mean the natural random walk version of the algorithm, where the node @math is chosen uniformly from the set of neighbors of @math at each iteration. For random geometric graph topologies, which are of most interest to us, @cite_19 prove that the performance of the natural random walk algorithm scales order-wise identically to that of the optimal choice of transition probabilities, so there is no loss of generality. .
@cite_19 @cite_2
2132612558 2171115412 2105333851 2101517602
In this paper, we study two related iterative randomized algorithms for distributed computation of averages. The first algorithm is the Broadcast Gossip Algorithm, in which at each iteration one randomly selected node broadcasts its own state to its neighbors. The second algorithm is a novel variation of the former, in which at each iteration every node is allowed to broadcast: hence, this algorithm, which we call Collision Broadcast Gossip Algorithm (CBGA), is affected by interference among messages. The performance of both algorithms is evaluated in terms of rate of convergence and asymptotical error: focusing on large Abelian Cayley networks, we highlight the role of topology and of design parameters. We show that on fully connected graphs the rate of convergence is bounded away from one, whereas the asymptotical error is bounded away from zero. On the contrary, on sparse graphs the rate of convergence goes to one and the asymptotical error goes to zero, as the size of the network grows larger. Our results also show that the performance of the CBGA is close to the performance of the BGA: this indicates the robustness of broadcast gossip algorithms to interferences. We study the distributed averaging problem on an arbitrary network with a gossip constraint, which means that no node communicates with more than one neighbour in every time slot. We consider algorithms which are linear iterations, where each iteration is described by a random matrix picked i.i.d. from some distribution. We derive conditions that this distribution must satisfy so that the sequence of iterations converges to the vector of averages in different senses. We then analyze a simple asynchronous randomized gossip algorithm for averaging, and show that the problem of optimizing the parameters of this algorithm for fastest convergence is a semi-definite program. Finally we study the relation between Markov chains and the averaging problem, and relate the averaging time of the algorithm to the mixing time of a related Markov chain on the graph. Gossiping is a distributed process whose purpose is to enable the members of a group of n>1 autonomous agents to asymptotically determine in a decentralized manner, the average of the initial values of their scalar gossip variables. This paper analyzes the accelerated gossip algorithms, first proposed in Cao, Spielman, and Yeh (2006), in which local memory is exploited by installing shift-registers at each agent. For the two-register case, the existence of the desired convergence is established under a symmetry assumption by separately studying the convergence in expectation and in mean square. In particular, the optimal rate of convergence in expectation is derived which is faster than that of the standard gossip algorithm, and a sufficient condition on the adjustable parameter for the convergence in mean square is provided. These theoretical results are validated for some classes of networks by comparison with existing empirical data. More general multi-register cases are also discussed. Motivated by applications to sensor, peer-to-peer and ad hoc networks, we study distributed asynchronous algorithms, also known as gossip algorithms, for computation and information exchange in an arbitrarily connected network of nodes. Nodes in such networks operate under limited computational, communication and energy resources. These constraints naturally give rise to "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for arbitrary network, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Using recent results of Boyd, Diaconis and Xiao (2003), we show that minimizing this quantity to design the fastest averaging algorithm on the network is a semi-definite program (SDP). In general, SDPs cannot be solved distributedly; however, exploiting problem structure, we propose a subgradient method that distributedly solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities that are derived from the gossip algorithm. We use this connection to study the performance of gossip algorithm on two popular networks: wireless sensor networks, which are modeled as geometric random graphs, and the Internet graph under the so-called preferential connectivity model.