### The Locality of Distributed Symmetry BreakingThe Locality of Distributed Symmetry Breaking

Access Restriction
Subscribed

 Author Barenboim, Leonid ♦ Elkin, Michael ♦ Pettie, Seth ♦ Schneider, Johannes Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2016 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Distributed networks ♦ MIS ♦ Matching ♦ Vertex coloring Abstract 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 $\textit{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\textit{o}(√log$ log $\textit{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 $\textit{n}$ ≪ Δ ≪ 2√log $\textit{n},$ and comes close to the Ω(&frac;log Δ log log Δ lower bound of Kuhn, Moscibroda, and Wattenhofer. —A maximal matching algorithm running in $\textit{O}(log Δ$ + $log ^{4}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 $\textit{O}(log$ Δ + $2\textit{o}(√log$ log $\textit{n})$ time, improving on an $\textit{O}(log$ Δ + √log $\textit{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 $\textit{O}(√log$ $\textit{n})-time$ maximal matching algorithm for graphs with arboricity up to 2√log $\textit{n}$ and an $O(log ^{2/3}n)-time$ MIS algorithm for graphs with arboricity up to 2(log $\textit{n})1/3.$ Each of our algorithms is based on a simple but powerful technique for reducing a $\textit{randomized}$ symmetry-breaking task to a corresponding $\textit{deterministic}$ one on a $poly(log \textit{n})-size$ graph. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2016-06-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 63 Issue Number 3 Page Count 45 Starting Page 1 Ending Page 45

#### Open content in new tab

Source: ACM Digital Library