The locality of distributed symmetry breaking Academic Article uri icon


  • Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry- breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes the following:—An MIS algorithm running in O (log 2 &Delta+ 2 o (√ log log n)) time, where Δ is the maximum degree. This is the first MIS algorithm to improve on the 1986 algorithms of Luby and Alon, Babai, and Itai, when log n ≪ Δ ≪ 2√ log n, and comes close to the Ω (&frac; log Δ log log Δ lower bound of Kuhn, Moscibroda, and Wattenhofer.

publication date

  • September 1, 2016