2023/04/19 by Maxime Flin, Flin, Maxime, Mohsen Ghaffari +7
Computer Science · Decision Sciences · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2304.09844
openalex publication_date 2023/04/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present an O(log3log n)-round distributed algorithm for the (Δ+1)-coloring problem, where each node broadcasts only one O(log n)-bit message per round to its neighbors. Previously, the best such broadcast-based algorithm required O(log n) rounds. If Δ∈ Ω(log3 n), our algorithm runs in O(log^* n) rounds. Our algorithm's round complexity matches state-of-the-art in the much more powerful CONGEST model [Halldórsson et al., STOC'21 & PODC'22], where each node sends one different message to each of its neighbors, thus sending up to Θ(nlog n) bits per round. This is the best complexity known, even if message sizes are unbounded. Our algorithm is simple enough to be implemented in even weaker models: we can achieve the same O(log3log n) round complexity if each node reads its received messages in a streaming fashion, using only O(log3 n)-bit memory. Therefore, we hope that our algorithm opens the road for adopting the recent exciting progress on sublogarithmic-time distributed (Δ+1)-coloring algorithms in a wider range of (theoretical or practical) settings.