Optimal deterministic distributed algorithms for maximal independent set in geometric graphs.

Finding a maximal independent set (MIS) in a graph is one of the fundamental problems in distributed computing. Researchers in this community are trying to close the time complexity gap of computing a MIS in a graph, way back from Luby's [STOC'85] O (log n) time (randomized) algorithm and Linial's [SICOMP'92] Ω (log ∗ n) lower bound result (n is the number of nodes of the graph). Since then, an extensive research has been done on this problem, however, most of the results are randomized and we are lack of efficient deterministic solution. In fact, no polylogarithmic (in n) time deterministic algorithm is known so far in general graphs — an open question raised by Linial in 1993 [Comb. Probab. Comput.'93]. In this paper, we study the MIS problem in geometric graphs, a class of graphs which has both theoretical and practical importance. We present O (1) -time deterministic algorithms (hence, optimal) for computing MIS in unit interval graphs, unit square graphs and unit disk graphs. The same idea applies to develop optimal MIS algorithm for higher dimensional unit balls and unit hypercubes. We further extend the MIS algorithms to compute approximate maximum independent set (MaxIS) in the above geometric graph classes. The theoretical results are corroborated through extensive experiments to show the effectiveness and efficiency of our algorithms. Our algorithms are fully decentralized, scalable, and robust. In general, nodes exchange only O (log n) bits message through an edge per communication. Moreover, being local, our algorithms are also suitable in failure model, self-stabilizing and appropriate for dynamic environment. • We study the Maximal and Maximal Independent Sets in geometric graphs in distributed computing model. • Our algorithms work in the CONGEST model of distributed computation. • We design constant time (optimal) distributed algorithms in unit interval, square, disk, and higher dimensional graphs. • We perform comprehensive experimental evaluation and highlight the efficiency of the algorithms. • Experimental results guarantee that our algorithms perform better than the theoretical proven bound. [ABSTRACT FROM AUTHOR]