2017/05/22 by Pai, Shreyas, Pandurangan, Gopal, Pemmaraju, Sriram V. +2
#C.2.4 #Data Structures and Algorithms (cs.DS) #Distributed #F.1.2 #F.2.2 #FOS: Computer and information sciences #G.2.2 #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.1705.07861
We study local symmetry breaking problems in the CONGEST model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. A β-ruling set is an independent set such that every node in the graph is at most β hops from a node in the independent set. Our work is motivated by the following central question: can we break the Θ(log n) time complexity barrier and the Θ(m) message complexity barrier in the CONGEST model for MIS or closely-related symmetry breaking problems? We present the following results: - Time Complexity: We show that we can break the O(log n) "barrier" for 2- and 3-ruling sets. We compute 3-ruling sets in O((log n)/(log log n)) rounds with high probability (whp). More generally we show that 2-ruling sets can be computed in O(log Δ⋅ (log n)1/2 + ε + (log n)/(loglog n)) rounds for any ε > 0, which is o(log n) for a wide range of Δ values (e.g., Δ= 2^(log n)1/2-ε). These are the first 2- and 3-ruling set algorithms to improve over the O(log n)-round complexity of Luby's algorithm in the CONGEST model. - Message Complexity: We show an Ω(n2) lower bound on the message complexity of computing an MIS (i.e., 1-ruling set) which holds also for randomized algorithms and present a contrast to this by showing a randomized algorithm for 2-ruling sets that, whp, uses only O(n log2 n) messages and runs in O(Δlog n) rounds. This is the first message-efficient algorithm known for ruling sets, which has message complexity nearly linear in n (which is optimal up to a polylogarithmic factor).