A log-star distributed maximal independent set algorithm for growth-bounded graphs

ABSTRACT

We present a novel distributed algorithm for the maximal independent set (MIS) problem. On growth-bounded graphs (GBG) our deterministic algorithm finishes in O(log* n) time, n being the number of nodes. In light of Linial's Ω(log* n) lower bound our algorithm is asymptotically optimal. Our algorithm answers prominent open problems in the ad hoc/sensor network domain. For instance, it solves the connected dominating set problem for unit disk graphs in O(log* n) time, exponentially faster than the state-of-the-art algorithm. With a new extension our algorithm also computes a delta+1 coloring in O(log* n) time, where delta is the maximum degree of the graph.

REFERENCES

• 1: Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
• 2: Khaled Alzoubi , Xiang-Yang Li , Yu Wang , Peng-Jun Wan , Ophir Frieder, Geometric Spanners for Wireless Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems, v.14 n.4, p.408-421, April 2003 [doi>10.1109/TPDS.2003.1195412]
• 3: Arne Andersson , Torben Hagerup , Stefan Nilsson , Rajeev Raman, Sorting in linear time?, Journal of Computer and System Sciences, v.57 n.1, p.74-93, Aug. 1998 [doi>10.1006/jcss.1998.1580]
• 4: B. Awerbuch , M. Luby , A. V. Goldberg , S. A. Plotkin, Network decomposition and locality in distributed computation, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.364-369, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63504]
• 5: Baruch Awerbuch , George Varghese, Distributed program checking: a paradigm for building self-stabilizing distributed protocols (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.258-267, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185377]
• 6: Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
• 7: Beat Gfeller , Elias Vicari, A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281111]
• 8: Andrew V. Goldberg , Serge A. Plotkin , Gregory E. Shannon, Parallel symmetry-breaking in sparse graphs, SIAM Journal on Discrete Mathematics, v.1 n.4, p.434-446, Nov. 1988 [doi>10.1137/0401044]
• 9: Amos Israel , A. Itai, A fast and simple randomized parallel algorithm for maximal matching, Information Processing Letters, v.22 n.2, p.77-80, 1986 [doi>10.1016/0020-0190(86)90144-4]
• 10: F. Kuhn, T. Moscibroda, T. Nieberg, and R. Wattenhofer. Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. In Proc. of the 19th Int. Symposium on Distributed Computing (DISC), 2005.
• 11: Fabian Kuhn , Tim Nieberg , Thomas Moscibroda , Roger Wattenhofer, Local approximation schemes for ad hoc and sensor networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080827]
• 12: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, On the locality of bounded growth, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073826]
• 13: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, What cannot be computed locally!, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011811]
• 14: Christoph Lenzen , Roger Wattenhofer, Leveraging Linial's Locality Limit, Proceedings of the 22nd international symposium on Distributed Computing, September 22-24, 2008, Arcachon, France [doi>10.1007/978-3-540-87779-0_27]
• 15: Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
• 16: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 17: Thomas Moscibroda , Roger Wattenhofer, Maximal independent sets in radio networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073842]
• 18: Alessandro Panconesi , Aravind Srinivasan, Improved distributed algorithms for coloring and network decomposition problems, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.581-592, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129769]
• 19: J. Schneider and R. Wattenhofer. An Asymptotically Optimal Distributed Maximal Independent Set Algorithm for Wireless Networks with Collision Detection. In Submission.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
ad hoc networks, coloring, connected dominating sets, dominating sets, growth bounded graphs, local algorithms, maximal independent sets, parallel algorithms, radio networks, sensor networks, symmetry breaking, unit disk graphs