A New Technique For Distributed Symmetry Breaking

back to overview


Schneider, J., & Wattenhofer, R. (2010). A New Technique For Distributed Symmetry Breaking. Paper presented at the Principles of Distributed Computing (PODC).

Publication type

Paper in Conference Proceedings


We introduce Multi-Trials, a new technique for symmetry breaking for distributed algorithms and apply it to various problems in general graphs. For instance, we present three randomized algorithms for distributed (vertex or edge) coloring improving on previous algorithms and showing a time/color trade-off. To get a Delta + 1 coloring takes time O(log Delta + sqrt(log n)). To obtain an O(Delta + log1+1/ log* n n) coloring takes time O(log* n). This is more than an expo- nential improvement in time for graphs of polylogarithmic degree. Our fastest algorithm works in constant time using O(Delta log(c) n + log1+1/c n) colors, where c denotes an arbi- trary constant and log(c) n denotes the c times (recursively) applied logarithm to n. We also use the Multi-Trials technique to compute net- work decompositions and to compute maximal independent set (MIS), obtaining new results for several graph classes


Organizational Units

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