TY - JOUR

T1 - The locality of distributed symmetry breaking

AU - Barenboim, Leonid

AU - Elkin, Michael

AU - Pettie, Seth

AU - Schneider, Johannes

N1 - Publisher Copyright:
© 2016 ACM.

PY - 2016/6

Y1 - 2016/6

N2 - 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(log2 δ + 2O( √ 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 ω( logδ/log logδ) lower bound of Kuhn, Moscibroda, andWattenhofer. -A maximal matching algorithm running in O(logδ + log4 log n) time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on δ is nearly optimal. -A (δ+1)-coloring algorithm requiring O(logδ+2O( √ log log n)) time, improving on an O(logδ+ √ log n)-time algorithm of Schneider and Wattenhofer. -A method for reducing symmetry-breaking problems in low arboricity/degeneracy graphs to low-degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an O( √log n)-time maximal matching algorithm for graphs with arboricity up to 2√ log nand an O(log2/3n)-time MIS algorithm for graphs with arboricity up to 2(log n)1/3. Each of our algorithms is based on a simple but powerful technique for reducing a randomized symmetrybreaking task to a corresponding deterministic one on a poly(log n)-size graph.

AB - 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(log2 δ + 2O( √ 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 ω( logδ/log logδ) lower bound of Kuhn, Moscibroda, andWattenhofer. -A maximal matching algorithm running in O(logδ + log4 log n) time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on δ is nearly optimal. -A (δ+1)-coloring algorithm requiring O(logδ+2O( √ log log n)) time, improving on an O(logδ+ √ log n)-time algorithm of Schneider and Wattenhofer. -A method for reducing symmetry-breaking problems in low arboricity/degeneracy graphs to low-degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an O( √log n)-time maximal matching algorithm for graphs with arboricity up to 2√ log nand an O(log2/3n)-time MIS algorithm for graphs with arboricity up to 2(log n)1/3. Each of our algorithms is based on a simple but powerful technique for reducing a randomized symmetrybreaking task to a corresponding deterministic one on a poly(log n)-size graph.

KW - Distributed networks

KW - MIS

KW - matching

KW - vertex coloring

UR - http://www.scopus.com/inward/record.url?scp=84976871537&partnerID=8YFLogxK

U2 - 10.1145/2903137

DO - 10.1145/2903137

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:84976871537

SN - 0004-5411

VL - 63

JO - Journal of the ACM

JF - Journal of the ACM

IS - 3

M1 - 20

ER -