Greedy gossip with eavesdropping

Deniz Üstebay, Mark Coates, Michael G. RabbatISWPC 2008 · DOI · OpenReview

TL;DR

This paper introduces "Greedy Gossip with Eavesdropping" (GGE), a novel decentralized algorithm for achieving average consensus in wireless networks. GGE significantly speeds up convergence compared to traditional randomized gossip by having nodes greedily select neighbors with the most different values, leveraging wireless broadcast to eavesdrop on neighbor information.

What Problem Does This Paper Address?

In distributed systems, especially wireless sensor networks, it's crucial for all nodes to agree on a common value, such as the average of their initial readings. This "average consensus" problem is fundamental for many distributed control and signal processing tasks. Traditional methods like distributed averaging can be slow, and randomized gossip, while robust, also suffers from slow convergence, particularly in large or sparsely connected networks. Geographic gossip offers faster convergence but requires nodes to know their precise locations, which can be a significant overhead and is not always feasible (e.g., in mobile or unlocalized networks). The challenge is to achieve fast and reliable average consensus without relying on location information, by efficiently utilizing the broadcast nature of wireless communication.

Methods

The core of the paper is the Greedy Gossip with Eavesdropping (GGE) algorithm. Here's how it works:

  • Broadcast Model: GGE assumes a wireless broadcast model where a transmitting node's message is heard by all nodes within its range.
  • Eavesdropping: Nodes actively listen to their neighbors' transmissions and maintain a local record of their neighbors' current values.
  • Greedy Selection: When a node is activated to gossip, instead of randomly choosing a neighbor (like in standard randomized gossip), it greedily selects the neighbor whose value is most different from its own. This is the key innovation.
  • Update: The activated node and its chosen neighbor then average their values, similar to standard gossip.
  • Initialization: A crucial aspect is the initialization phase. Since nodes don't initially know their neighbors' values, they perform a randomized gossip during initialization until they have heard from all neighbors. This ensures that the greedy selection can be made from the start of the main gossip phase.
  • Theoretical Framework: The authors connect GGE to randomized incremental subgradient optimization, which allows them to prove convergence guarantees and derive bounds on convergence rates.

Datasets

Not discussed in the paper. The paper relies on simulated network topologies (random geometric graphs and grids) and synthetic initial conditions for evaluating the algorithm's performance.

Key Insights and Ideas

  • Greed is Good (for Consensus): The paper demonstrates that a "myopic" greedy strategy—choosing the neighbor with the most different value—significantly accelerates consensus convergence without biasing the final average. This is counter-intuitive, as one might expect such a strategy to lead to oscillations or instability.
  • Leveraging Eavesdropping: The algorithm cleverly uses the inherent eavesdropping capability in wireless broadcasts to gather neighbor information, avoiding the need for explicit requests or acknowledgments for neighbor values, which would add complexity.
  • Topology Matters: The performance improvement of GGE over randomized gossip is highly dependent on the network topology. Dense networks (like random geometric graphs with higher connectivity) benefit much more than sparse networks (like grids). This is because in denser networks, there are more opportunities for the greedy choice to make a significant impact.
  • No Location, No Problem: GGE achieves its speedup without requiring any knowledge of node locations, making it suitable for a wider range of applications than geographic gossip.

Key Results

  • Faster Convergence: GGE consistently outperforms standard randomized gossip in terms of convergence speed (measured by the number of transmissions) across various initial conditions and network topologies.
  • Competitive with Geographic Gossip: For random geometric graphs, GGE's performance is comparable to geographic gossip, especially asymptotically, while being simpler and not requiring location information.
  • Theoretical Bounds: The paper provides theoretical bounds showing that GGE's convergence rate is related to the network topology's properties (like maximum degree) and is generally better than randomized gossip. Specifically, the upper bound on GGE's averaging time is at most a factor of $d_{max}$ worse than that of randomized gossip, where $d_{max}$ is the maximum node degree.
  • Robustness to Stale Information: Simulations show that GGE remains significantly better than randomized gossip even when a substantial portion (up to 50%) of broadcast messages are missed due to link unreliability.

Limitations and Future Work

  • Initialization Overhead: While the proposed initialization is efficient, it still requires some transmissions before the greedy updates can begin.
  • "Receive" Mode: GGE requires nodes to be in "Receive" mode throughout the algorithm's execution, which might lead to higher energy consumption compared to randomized gossip where nodes can enter "Idle" mode. However, the authors note that empirical studies suggest this difference might be negligible for modern wireless sensor network architectures.
  • Mobile Nodes: The current GGE is designed for static networks. The authors suggest future work to investigate GGE's benefits in networks with mobile nodes, where geographic approaches become less applicable.
  • General Functions: They also plan to explore extending GGE to compute more general functions beyond just the average.
  • Multi-hop Extension: The paper introduces a multi-hop GGE to improve performance in low-degree topologies, suggesting further research into optimizing this extension.

Summary updated

Abstract

This paper presents greedy gossip with eavesdropping (GGE), a new average consensus algorithm for wireless sensor network applications. Consensus algorithms have recently received much attention in the sensor network community because of their simplicity and completely decentralized nature which makes them robust to changes in the network topology and unreliable wireless networking environments. In the sensor network, each node has a measurement value and the aim of average consensus is computing the average of these node values in the absence of a central authority. We prove that GGE converges to the average consensus with probability one. We also illustrate the performance of the algorithm via simulations and conclude that GGE provides a significant performance improvement compared to existing average consensus algorithms such as randomized gossip and geographic gossip.
BibTeX
@inproceedings{ustebay2008greedy,
  author = {Deniz Üstebay and Mark Coates and Michael G. Rabbat},
  title = {{Greedy gossip with eavesdropping}},
  booktitle = {ISWPC},
  year = {2008},
  doi = {10.1109/iswpc.2008.4556312},
}
Figure