%0 Conference Paper %1 deb2006efficient %A Kashyap, Srinivas %A Deb, Supratim %A Naidu, K. V. M. %A Rastogi, Rajeev %A Srinivasan, Anand %B PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems %C New York, NY, USA %D 2006 %I ACM Press %K Aggregation Efficient Lifetime PODS WSN %P 308--317 %R http://doi.acm.org/10.1145/1142351.1142395 %T Efficient gossip-based aggregate computation %U http://portal.acm.org/citation.cfm?id=1142395&dl=GUIDE&coll=GUIDE&CFID=15151515&CFTOKEN=6184618 %X 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(nlog 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. %@ 1-59593-318-2

@inproceedings{deb2006efficient, abstract = {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(nlog 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.}, added-at = {2007-05-17T15:42:09.000+0200}, address = {New York, NY, USA}, author = {Kashyap, Srinivas and Deb, Supratim and Naidu, K. V. M. and Rastogi, Rajeev and Srinivasan, Anand}, biburl = {https://www.bibsonomy.org/bibtex/2b8af73de6abda6809d2165a0dd9d3f42/derkling}, booktitle = {PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems}, description = {Efficient gossip-based aggregate computation}, doi = {http://doi.acm.org/10.1145/1142351.1142395}, interhash = {8e72bdfa00826dd7acda0715bc358e12}, intrahash = {b8af73de6abda6809d2165a0dd9d3f42}, isbn = {1-59593-318-2}, keywords = {Aggregation Efficient Lifetime PODS WSN}, location = {Chicago, IL, USA}, pages = {308--317}, publisher = {ACM Press}, timestamp = {2007-05-17T15:42:09.000+0200}, title = {Efficient gossip-based aggregate computation}, url = {http://portal.acm.org/citation.cfm?id=1142395&dl=GUIDE&coll=GUIDE&CFID=15151515&CFTOKEN=6184618}, year = 2006 }