Partial information spreading with application to distributed maximum coverage

ABSTRACT

This paper addresses partial information spreading among n nodes of a network. As opposed to traditional information spreading, where each node has a message that must be received by all nodes, we propose a relaxed requirement, where only n/c nodes need to receive each message, and every node should receive n/c messages, for some c ≥ 1.

As a key tool in our study we introduce the novel concept of weak conductance, a generalization of classic graph conductance which allows to analyze the time required for partial information spreading. We show the power of weak conductance as a measure of how well-knit the components of a graph are, by giving an example of a graph family for which the conductance is O(n-²), while the weak conductance is as large as 1/2. For such graphs, weak conductance can be used to show that partial information spreading requires time complexity of O(\logn).

Finally, we demonstrate the usefulness of partial information spreading in solving the maximum coverage problem, which naturally arises in circuit layout, job scheduling and facility location, as well as in distributed resource allocation with a global budget constraint. Our algorithm yields a constant approximation factor and a constant deviation from the given budget. For graphs with a constant weak conductance, this implies a scalable time complexity for solving a problem with a global constraint.

References

1. N. Alon, C. Avin, M. Koucky, G. Kozma, Z. Lotker, and M. R. Tuttle. Many random walks are faster than one. In SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, pages 119--128, New York, NY, USA, 2008. ACM.
2. D. Amzallag, J. Naor, and D. Raz. Coping with interference: From maximum coverage to planning cellular networks. In WAOA, pages 29--42, 2006.
3. E. Ando, H. Ono, K. Sadakane, and M. Yamashita. The space complexity of the leader election in anonymous networks. In IPDPS, pages 1--8, 2008.
4. D. Angluin. Local and global properties in networks of processors (extended abstract). In STOC '80: Proceedings of the twelfth annual ACM symposium on Theory of computing, pages 82--93, New York, NY, USA, 1980. ACM.
5. C. Avin and C. Brito. Efficient and robust query processing in dynamic environments using random walk techniques. In IPSN '04: Proceedings of the 3rd international symposium on Information processing in sensor networks, pages 277--286, New York, NY, USA, 2004. ACM.
6. C. Avin and G. Ercal. Bounds on the mixing time and partial cover of ad-hoc and sensor networks. In Wireless Sensor Networks, 2005. Proceeedings of the Second European Workshop on, pages 1--12, 2005.
7. M. Borokhovich, C. Avin, and Z. Lotker. Tight bounds for algebraic gossip on graphs. arXiv:1001.3265v1 {cs.IT}, 2010.
8. F. Chierichetti, S. Lattanzi, and A. Panconesi. Almost tight bounds for rumour spreading with conductance. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), to appear, 2010.
9. F. Chierichetti, S. Lattanzi, and A. Panconesi. Rumour spreading and graph conductance. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1657--1663, 2010.
10. M. Conforti and G. Cornuejols. Submodular set functions, matroids and the greedy algorithm: Tight worstcase bounds and some generalizations of the rado-edmonds theorem. Discrete Applied Math, 7:257--274, 1984.
11. A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. In PODC '87: Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, pages 1--12, New York, NY, USA, 1987. ACM.
12. U. Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634--652, 1998.
13. U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. In SIGAL International Symposium on Algorithms, pages 128--137, 1990.
14. P. Fraigniaud, A. Pelc, D. Peleg, and S. Pérennes. Assigning labels in unknown anonymous networks (extended abstract). In PODC '00: Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, pages 101--111, New York, NY, USA, 2000. ACM.
15. M. R. Garey and D. S. Johnson. "strong" NP-completeness results: Motivation, examples, and implications. J. ACM, 25(3):499--508, 1978.
16. C. Georgiou, S. Gilbert, R. Guerraoui, and D. R. Kowalski. On the complexity of asynchronous gossip. In PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, pages 135--144, New York, NY, USA, 2008. ACM.
17. F. Grandoni, J. Könemann, and A. Panconesi. Distributed weighted vertex cover via maximal matchings. ACM Trans. Algorithms, 5(1):1--12, 2008.
18. D. S. Hochbaum. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. In Approximation algorithms for NP-hard problems, pages 94--143, Boston, MA, USA, 1997. PWS Publishing Co.
19. D. S. Hochbaum and A. Pathria. Analysis of the greedy approach in problems of maximum k-coverage. Naval Research Logistics, 45(6):615--627, 1998.
20. R. Kannan, L. Lovász, and R. Montenegro. Blocking conductance and mixing in random walks. Comb. Probab. Comput., 15(4):541--570, 2006.
21. R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. Randomized rumor spreading. In FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, page 565, Washington, DC, USA, 2000. IEEE Computer Society.
22. D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), page 482, Washington, DC, USA, 2003. IEEE Computer Society.
23. S. Khuller, A. Moss, and J. S. Naor. The budgeted maximum coverage problem. Inf. Process. Lett., 70(1):39--45, 1999.
24. C. Koufogiannakis and N. E. Young. Distributed and parallel algorithms for weighted vertex cover and other covering problems. In PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing, pages 171--179, New York, NY, USA, 2009. ACM.
25. F. Kuhn, T. Moscibroda, and R. Wattenhofer. What cannot be computed locally! In PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pages 300--309, New York, NY, USA, 2004. ACM.
26. F. Kuhn, T. Moscibroda, and R. Wattenhofer. The price of being near-sighted. In SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 980--989, New York, NY, USA, 2006. ACM.
27. L. Lovász and R. Kannan. Faster mixing via average conductance. In STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 282--287, New York, NY, USA, 1999. ACM.
28. D. Mosk-Aoyama and D. Shah. Computing separable functions via gossip. In Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing (PODC), pages 113--122, New York, NY, USA, 2006. ACM.
29. D. Mosk-Aoyama and D. Shah. Information dissemination via network coding. In 2006 IEEE International Symposium on Information Theory, pages 1748--1752, July 2006.
30. G. Nemhauser and L. Wolsey. Maximizing submodular set functions: Formulations and studies of algorithms. Studies on Graphs and Discrete Programming, pages 279--301, 1981.
31. R. G. Shlomi Dolev, Seth Gilbert and C. Newport. Gossiping in a multi-channel radio network (an oblivious approach to coping with malicious interference). In Proceedings of the 21st International Symposium on Distributed Computing (DISC), pages 208--222, 2007.
32. A. Sinclair. Algorithms for random generation and counting: a Markov chain approach. Birkhauser Verlag, Basel, Switzerland, Switzerland, 1993.
33. D. Subhadrabandhu, F. Anjum, S. Kannan, and S. Sarkar. Domination and coverage guarantees through distributed computation. In Proceedings of 43d Annual Allerton Conference on Communication, Control and Computing, Allerton, Monticello, Illinois, September 28--30, 2005.
34. K. Suh, Y. Guo, J. Kurose, and D. Towsley. Locating network monitors: Complexity, heuristics, and coverage. Comput. Commun., 29(10):1564--1577, 2006.
35. R. V. Vohra and N. G. Hall. A probabilistic analysis of the maximal covering location problem. Discrete Appl. Math., 43(2):175--183, 1993.
36. M. Yamashita and T. Kameda. Computing on an anonymous network. In PODC '88: Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, pages 117--130, New York, NY, USA, 1988. ACM.

Index Terms

• Mathematics of computing

  • Probability and statistics

    • Probabilistic algorithms

    • Probabilistic reasoning algorithms

      • Markov-chain Monte Carlo methods

      • Sequential Monte Carlo methods

• Networks

  • Network protocols

• Theory of computation

  • Design and analysis of algorithms