Queue-based broadcast gossip algorithm for consensus

We study broadcast gossip algorithms to compute the average of given initial sensor measurements. In the context of wireless networks, an algorithm was proposed by Scaglione et al. that allows a single node to broadcast at each time with geometrically fast convergence to consensus. To improve the rate of convergence to consensus, we go beyond this single node broadcast approach and propose a queue-based broadcast gossip algorithm, in which simultaneous node broadcasts are allowed. Since packet collisions may happen, we choose time-varying update weights. Using a novel interval-based consensus error analysis to handle the time-dependent update weights, we show that with appropriate choice of parameters, the proposed algorithm converges to consensus in the mean-square sense geometrically fast. We prove that for the class of networks modeled as non-bipartite Ramanujan graphs, the exponent of convergence of the proposed algorithm is independent of the number of nodes, unlike the single node broadcast case which converges slowly in large networks. We also demonstrate through simulations that our proposed algorithm improves the rate of convergence for some other example networks.

• Publication year

  2016

• Venue

  Allerton Conference on Communication, Control, and Computing

• Publication date

  2016-09-01

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1109/ALLERTON.2016.7852379
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Recursive Distributed Detection for Composite Hypothesis Testing: Algorithms and Asymptotics

  2016cited by this paper
• Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks

  2011cited by this paper
• Large deviations analysis of consensus+innovations detection in random networks

  2011cited by this paper
• Gossip Algorithms for Distributed Signal Processing

  2010cited by this paper
• Broadcast Gossip Algorithms for Consensus

  2009cited by this paper
• Distributed Parameter Estimation in Sensor Networks: Nonlinear Observation Models and Imperfect Communication

  2008cited by this paper
• Stability analysis of the consensus-based distributed LMS algorithm

  2008cited by this paper
• Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization

  2008cited by this paper
• Geographic Gossip: Efficient Averaging for Sensor Networks

  2007cited by this paper
• Distributed Consensus Algorithms in Sensor Networks With Imperfect Communication: Link Failures and Channel Noise

  2007cited by this paper
• Randomized gossip algorithms

  2006cited by this paper
• Topology for Distributed Inference on Graphs

  2006cited by this paper
• Fast linear iterations for distributed averaging

  2003cited by this paper
• Consensus protocols for networks of dynamic agents

  2003cited by this paper
• Problems in decentralized decision making and computation

  1984cited by this paper

• No citing papers are available for this paper.