The Locality of Distributed Symmetry Breaking

Journal of the ACM - Tập 63 Số 3 - Trang 1-45 - 2016
Leonid Barenboim1, Michael Elkin2, Seth Pettie3, Johannes Schneider4
1Ben-Gurion University
2Ben-Gurion University, Beer-Sheva, Israel
3University of Michigan, MI, USA
4ETH, Zürich

Tóm tắt

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 (log 2 Δ + 2 o (√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, and Wattenhofer.

—A maximal matching algorithm running in 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 O (log Δ + 2 o (√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 n and an O (log  2/3 n )-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 symmetry-breaking task to a corresponding deterministic one on a poly(log  n )-size graph.

Từ khóa


Tài liệu tham khảo

10.1002/rsa.3240020403

10.1016/0196-6774(86)90019-2

A. Amir O. Kapah T. Kopelowitz M. Naor and E. Porat. 2014. The family holiday gathering problem or fair and periodic scheduling of independent sets. CoRR abs/1408.2279 (2014). A. Amir O. Kapah T. Kopelowitz M. Naor and E. Porat. 2014. The family holiday gathering problem or fair and periodic scheduling of independent sets. CoRR abs/1408.2279 (2014).

10.1109/SFCS.1989.63504

R. Bar-Yehuda K. Censor-Hillel and G. Schwartzman. 2016. A distributed (2 + ε)-approximation for vertex cover in O(log Δ/εlog log Δ) rounds. CoRR abs/1602.03713 (2016). R. Bar-Yehuda K. Censor-Hillel and G. Schwartzman. 2016. A distributed (2 + ε)-approximation for vertex cover in O(log Δ/εlog log Δ) rounds. CoRR abs/1602.03713 (2016).

10.1145/2767386.2767410

10.1007/s00446-009-0088-2

10.1145/2027216.2027221

L. Barenboim and M. Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers San Francisco CA. L. Barenboim and M. Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers San Francisco CA.

10.1137/12088848X

10.1002/rsa.3240020402

10.1145/2611462.2611512

10.1145/2611462.2611465

10.1016/S0019-9958(86)80023-7

D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press Cambridge. D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press Cambridge.

10.1002/(SICI)1098-2418(199809)13:2%3C99::AID-RSA1%3E3.0.CO;2-M

M. Elkin , S. Pettie , and H. H. Su . 2015. (2Δ − 1)-edge coloring is much easier than maximal matching in the distributed setting . In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 355--370 . M. Elkin, S. Pettie, and H. H. Su. 2015. (2Δ − 1)-edge coloring is much easier than maximal matching in the distributed setting. In Proceedings 26th ACM-SIAM Symposium on Discrete Algorithms (SODA). 355--370.

10.1145/1281100.1281111

10.5555/2884435.2884455

10.1137/S0895480100373121

10.1145/2897518.2897533

10.1016/0020-0190(86)90144-4

10.1016/S0020-0190(99)00064-2

10.1007/s00446-012-0174-8

10.1145/1993806.1993812

K. Kothapalli and S. V. Pemmaraju . 2012. Super-fast 3-ruling sets . In Proceedings IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LIPIcs , Vol. 18 . Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 136--147. K. Kothapalli and S. V. Pemmaraju. 2012. Super-fast 3-ruling sets. In Proceedings IARCS Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LIPIcs, Vol. 18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 136--147.

K. Kothapalli , C. Scheideler , M. Onus , and C. Schindelhauer . 2006. Distributed coloring in O˜(√log n) bit rounds . In Proceedings 20th International Parallel and Distributed Processing Symposium (IPDPS). K. Kothapalli, C. Scheideler, M. Onus, and C. Schindelhauer. 2006. Distributed coloring in O˜(√log n) bit rounds. In Proceedings 20th International Parallel and Distributed Processing Symposium (IPDPS).

10.1145/1011767.1011811

F. Kuhn T. Moscibroda and R. Wattenhofer. 2010. Local computation: Lower and upper bounds. CoRR abs/1011.5470 (2010). F. Kuhn T. Moscibroda and R. Wattenhofer. 2010. Local computation: Lower and upper bounds. CoRR abs/1011.5470 (2010).

10.1145/1146381.1146387

10.1145/1993806.1993813

10.1137/0221015

10.1007/BF01303516

10.1137/0215074

10.1145/1667053.1667060

C. St . J. A. Nash-Williams . 1964 . Decomposition of finite graphs into forests . J. London Math. Soc. 39 (1964), 12 . C. St. J. A. Nash-Williams. 1964. Decomposition of finite graphs into forests. J. London Math. Soc. 39 (1964), 12.

10.1007/PL00008932

10.1006/jagm.1996.0017

D. Peleg . 2000. Distributed Computing: A Locality-Sensitive Approach . SIAM , Philadelphia, PA . D. Peleg. 2000. Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA.

10.1016/j.ic.2014.12.018

R. Rubinfeld , G. Tamir , S. Vardi , and N. Xie . 2011. Fast local computation algorithms . In Proceedings of the 1st Symposium on Innovations in Computer Science (ICS). 223--238 . See also CoRR abs/1104.1377. R. Rubinfeld, G. Tamir, S. Vardi, and N. Xie. 2011. Fast local computation algorithms. In Proceedings of the 1st Symposium on Innovations in Computer Science (ICS). 223--238. See also CoRR abs/1104.1377.

10.1016/j.tcs.2012.09.004

10.1145/1835698.1835760

10.1007/s00446-010-0097-1

10.1145/167088.167156

Thông tin
Thông tin xuất bản

Journal of the ACM

Tập 63 Số 3

1-45

Thông tin tác giả