The Locality of Distributed Symmetry Breaking

zurück zur Übersicht


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).


Beitrag in Konferenztagungsband


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.



  • Institut für Wirtschaftsinformatik
  • Hilti Lehrstuhl für Business Process Management