The Locality of Distributed Symmetry Breaking

back to overview


Barenboim, L., Elkin,M, Pettie, S., & Schneider, J. (2012). The Locality of Distributed Symmetry Breaking. Paper presented at the Symposium on Foundations of Computer Science (FOCS).

Publication type

Paper in Conference Proceedings


We present new bounds on the locality of several classical symmetry breaking tasks in distributed networks. We also introduce a new technique for reducing symmetry breaking problems on low arboricity graphs to low degree graphs. Corollaries of this reduction include MM and MIS algorithms for low arboricity graphs (e.g., planar graphs and graphs that exclude any ?xed minor) requiring O(sqrt(log n)) and O(log^{2/3} n) rounds w.h.p., respectively.


Organizational Units

  • Institute of Information Systems
  • Hilti Chair of Business Process Management