Gossip-Based Computation of Aggregate Information Export

@inproceedings{citeulike:1189172, abstract = {Over the last decade, we have seen a revolution in connectivity between computers, and a resulting paradigm shift from centralized to highly distributed systems. With massive scale also comes massive instability, as node and link failures become the norm rather than the exception. For such highly volatile systems, decentralized gossip-based protocols are emerging as an approach to maintaining simplicity and scalability while achieving fault-tolerant information dissemination.In this paper, we study the problem of computing aggregates with gossip-style protocols. Our first contribution is an analysis of simple gossip-based protocols for the computations of sums, averages, random samples, quantiles, and other aggregate functions, and we show that our protocols converge exponentially fast to the true answer when using uniform gossip.Our second contribution is the definition of a precise notion of the speed with which a node's data diffuses through the network. We show that this diffusion speed is at the heart of the approximation guarantees for all of the above problems. We analyze the diffusion speed of uniform gossip in the presence of node and link failures, as well as for flooding-based mechanisms. The latter expose interesting connections to random walks on graphs.}, address = {Washington, DC, USA}, author = {Kempe, David and Dobra, Alin and Gehrke, Johannes}, booktitle = {FOCS '03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science}, citeulike-article-id = {1189172}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=946317}, isbn = {0-7695-2040-5}, keywords = {computation, distributed, gossip, work}, pages = {482+}, posted-at = {2007-08-23 01:51:42}, priority = {2}, publisher = {IEEE Computer Society}, title = {Gossip-Based Computation of Aggregate Information}, url = {http://portal.acm.org/citation.cfm?id=946317}, year = {2003} }

TY - CONF ID - citeulike:1189172 L3 - citeulike-article-id:1189172 N2 - Over the last decade, we have seen a revolution in connectivity between computers, and a resulting paradigm shift from centralized to highly distributed systems. With massive scale also comes massive instability, as node and link failures become the norm rather than the exception. For such highly volatile systems, decentralized gossip-based protocols are emerging as an approach to maintaining simplicity and scalability while achieving fault-tolerant information dissemination.In this paper, we study the problem of computing aggregates with gossip-style protocols. Our first contribution is an analysis of simple gossip-based protocols for the computations of sums, averages, random samples, quantiles, and other aggregate functions, and we show that our protocols converge exponentially fast to the true answer when using uniform gossip.Our second contribution is the definition of a precise notion of the speed with which a node's data diffuses through the network. We show that this diffusion speed is at the heart of the approximation guarantees for all of the above problems. We analyze the diffusion speed of uniform gossip in the presence of node and link failures, as well as for flooding-based mechanisms. The latter expose interesting connections to random walks on graphs. SN - 0-7695-2040-5 AD - Washington, DC, USA TI - Gossip-Based Computation of Aggregate Information PB - IEEE Computer Society T2 - FOCS '03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science SP - 482 KW - computation KW - distributed KW - gossip KW - work AU - Kempe, David AU - Dobra, Alin AU - Gehrke, Johannes PY - 2003/// UR - http://portal.acm.org/citation.cfm?id=946317 ER -