Gossip-Based Aggregate Computation with Low Communication Overhead

Konferenz: networks 2006 - 12th International Telecommunications Network Strategy and Planning - Symposium
06.11.2006 - 09.11.2006 in New Delhi, India

Tagungsband: networks 2006

Seiten: 6Sprache: EnglischTyp: PDF

Persönliche VDE-Mitglieder erhalten auf diesen Artikel 10% Rabatt

Kashyap, Srinivas (University of Maryland)
Deb, Supratim; Naidu, K. V. M.; Rastogi, Rajeev; Srinivasan, Anand (Bell Labs Research India, Bangalore)

Recently, there has been a growing interest in gossip-based protocols that employ randomized communication to ensure robust information dissemination. In this paper, we present a novel gossip-based scheme using which all the nodes in an n-node overlay network can compute the common aggregates of MIN, MAX, SUM, AVERAGE, and RANK of their values using O(n log log n) messages within O(log n log log n) rounds of communication. To the best of our knowledge, ours is the first result that shows how to compute these aggregates with high probability using only O(n log log n) messages. In contrast, the best known gossip-based algorithm for computing these aggregates requires O(n log n) messages and O(log n) rounds. Thus, our algorithm allows system designers to trade off a small increase in round complexity with a significant reduction in message complexity. This can lead to dramatically lower network congestion and longer node lifetimes in wireless and sensor networks, where channel bandwidth and battery life are severely constrained.