Computing separable functions via gossip

ABSTRACT

Motivated by applications to sensor, peer-to-peer, and ad-hoc networks, we study the problem of computing functions of values at the nodes in a network in a totally distributed manner. In particular, we consider separable functions, which can be written as linear combinations of functions of individual variables. Known iterative algorithms for averaging can be used to compute the normalized values of such functions, but these algorithms do not extend in general to the computation of the actual values of separable functions.The main contribution of this paper is the design of a distributed randomized algorithm for computing separable functions based on properties of exponential random variables. We bound the running time of our algorithm in terms of the running time of an information spreading algorithm used as a subroutine by the algorithm. Since we are interested in totally distributed algorithms, we consider a randomized gossip mechanism for information spreading as the subroutine. Combining these algorithms yields a complete and simple distributed algorithm for computing separable functions.The second contribution of this paper is an analysis of the information spreading time of the gossip algorithm. This analysis yields an upper bound on the information spreading time, and therefore a corresponding upper bound on the running time of the algorithm for computing separable functions, in terms of the conductance of an appropriate stochastic matrix. These bounds imply that, for a class of graphs with small spectral gap (such as grid graphs), the time used by our algorithm to compute averages is of a smaller order than the time required for the computation of averages by a known iterative gossip scheme [5].

REFERENCES

• 1: M. C. Azizoğlu and Õ. Eğecioğlu. The isoperimetric number of d-dimensional k-ary arrays. International Journal of Foundations of Computer Science, 10(3):289--300, 1999.
• 2: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar , Luca Trevisan, Counting Distinct Elements in a Data Stream, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.1-10, September 13-15, 2002
• 3: Noam Berger , Christian Borgs , Jennifer T. Chayes , Amin Saberi, On the spread of viruses on the internet, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 4: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 5: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip algorithms: Design, analysis and applications. In Proceedings of IEEE INFOCOM 2005, pages 1653--1664, 2005.
• 6: Jeffrey Considine , Feifei Li , George Kollios , John Byers, Approximate Aggregation Techniques for Sensor Databases, Proceedings of the 20th International Conference on Data Engineering, p.449, March 30-April 02, 2004
• 7: A. Dembo and O. Zeitouni. Large Deviations Techniques and Applications. Springer, second edition, 1998.
• 8: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 9: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 10: A. M. Frieze and G. R. Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics, 10:57--77, 1985.
• 11: A. Ganesh, L. Massoulié, and D. Towsley. The effect of network topology on the spread of epidemics. In Proceedings of IEEE INFOCOM 2005, pages 1455--1466, 2005.
• 12: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 13: David Kempe , Jon M. Kleinberg, Protocols and Impossibility Results for Gossip-Based Communication Mechanisms, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.471-480, November 16-19, 2002
• 14: David Kempe , Jon Kleinberg , Alan Demers, Spatial gossip and resource location protocols, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.163-172, July 2001, Hersonissos, Greece [doi>10.1145/380752.380796]
• 15: David Kempe , Frank McSherry, A decentralized algorithm for spectral analysis, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007438]
• 16: E. Modiano, D. Shah, and G. Zussman. Maximizing throughput in wireless networks via gossip. Submitted, 2005.
• 17: Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031525]
• 18: Boris Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, v.47 n.1, p.213-223, Feb. 1987 [doi>10.1137/0147013]
• 19: R. Ravi. Rapid rumor ramification: Approximating the minimum broadcast time. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, pages 202--213, 1994.
• 20: O. Reingold , S. Vadhan , A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.3, November 12-14, 2000
• 21: Alistair Sinclair, Algorithms for random generation and counting: a Markov chain approach, Birkhauser Verlag, Basel, Switzerland, 1993
• 22: J. N. Tsitsiklis. Problems in Decentralized Decision Making and Computation. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1984.
• 23: J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Transactions on Automatic Control, 31(9):803--812, 1986.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
data aggregation, gossip, randomized algorithms