Gossip algorithms: design, analysis and applications Export

@proceedings{citeulike:1745530, abstract = {Motivated by applications to sensor, peer-to-peer and ad hoc networks, we study distributed asynchronous algorithms, also known as gossip algorithms, for computation and information exchange in an arbitrarily connected network of nodes. Nodes in such networks operate under limited computational, communication and energy resources. These constraints naturally give rise to "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for arbitrary network, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Using recent results of Boyd, Diaconis and Xiao (2003), we show that minimizing this quantity to design the fastest averaging algorithm on the network is a semi-definite program (SDP). In general, SDPs cannot be solved distributedly; however, exploiting problem structure, we propose a subgradient method that distributedly solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities that are derived from the gossip algorithm. We use this connection to study the performance of gossip algorithm on two popular networks: wireless sensor networks, which are modeled as geometric random graphs, and the Internet graph under the so-called preferential connectivity model.}, author = {Boyd, S. and Ghosh, A. and Prabhakar, B. and Shah, D.}, booktitle = {INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE}, citeulike-article-id = {1745530}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/INFCOM.2005.1498447}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1498447}, doi = {10.1109/INFCOM.2005.1498447}, journal = {INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE}, keywords = {averaging, gossip, manet, protocol}, pages = {1653--1664 vol. 3}, posted-at = {2009-01-28 18:16:25}, priority = {2}, title = {Gossip algorithms: design, analysis and applications}, url = {http://dx.doi.org/10.1109/INFCOM.2005.1498447}, volume = {3}, year = {2005} }

TY - CONF ID - citeulike:1745530 L3 - citeulike-article-id:1745530 N2 - Motivated by applications to sensor, peer-to-peer and ad hoc networks, we study distributed asynchronous algorithms, also known as gossip algorithms, for computation and information exchange in an arbitrarily connected network of nodes. Nodes in such networks operate under limited computational, communication and energy resources. These constraints naturally give rise to "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for arbitrary network, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Using recent results of Boyd, Diaconis and Xiao (2003), we show that minimizing this quantity to design the fastest averaging algorithm on the network is a semi-definite program (SDP). In general, SDPs cannot be solved distributedly; however, exploiting problem structure, we propose a subgradient method that distributedly solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities that are derived from the gossip algorithm. We use this connection to study the performance of gossip algorithm on two popular networks: wireless sensor networks, which are modeled as geometric random graphs, and the Internet graph under the so-called preferential connectivity model. JF - INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE EP - 1664 vol. 3 TI - Gossip algorithms: design, analysis and applications VL - 3 T2 - INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE SP - 1653 KW - averaging KW - gossip KW - manet KW - protocol AU - Boyd, S AU - Ghosh, A AU - Prabhakar, B AU - Shah, D PY - 2005/// UR - http://dx.doi.org/10.1109/INFCOM.2005.1498447 ER -