Document Open Access Logo

Classification of Distributed Binary Labeling Problems

Authors Alkida Balliu , Sebastian Brandt , Yuval Efron , Juho Hirvonen , Yannic Maus , Dennis Olivetti , Jukka Suomela

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.17.pdf
  • Filesize: 0.52 MB
  • 17 pages

Document Identifiers

Author Details

Alkida Balliu
  • Freiburg University, Germany
Sebastian Brandt
  • ETH Zürich, Switzerland
Yuval Efron
  • Technion - Israel Institute of Technology, Haifa, Israel
Juho Hirvonen
  • Aalto University, Finland
Yannic Maus
  • Technion - Israel Institute of Technology, Haifa, Israel
Dennis Olivetti
  • Freiburg University, Germany
Jukka Suomela
  • Aalto University, Finland

Funding

This work was supported in part by the Academy of Finland, Grant 314888 (Juho Hirvonen), and by the European Union’s Horizon 2020 Research And Innovation Programme under grant agreement no. 755839 (Yuval Efron, Yannic Maus).

Acknowledgements

We thank Jan Studený and anonymous reviewers for helpful comments on earlier versions of this work.

Cite As Get BibTex

Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Classification of Distributed Binary Labeling Problems. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.17

Abstract

We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, perfect matching, and the task of coloring edges red and blue such that all nodes are incident to at least one red and at least one blue edge. More generally, we can encode e.g. any cardinality constraints on indegrees and outdegrees.
We study the deterministic time complexity of solving a given binary labeling problem in trees, in the usual LOCAL model of distributed computing. We show that the complexity of any such problem is in one of the following classes: O(1), Θ(log n), Θ(n), or unsolvable. In particular, a problem that can be represented in the binary labeling formalism cannot have time complexity Θ(log^* n), and hence we know that e.g. any encoding of maximal matchings has to use at least three labels (which is tight).
Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it. Hence the distributed time complexity of binary labeling problems is decidable, not only in principle, but also in practice: there is a simple and efficient algorithm that takes the description of a binary labeling problem and outputs its distributed time complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Complexity classes
Keywords
  • LOCAL model
  • graph problems
  • locally checkable labeling problems
  • distributed computational complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. The Distributed Complexity of Locally Checkable Problems on Paths is Decidable. In Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 262-271. ACM Press, 2019. URL: https://doi.org/10.1145/3293611.3331606.
  2. Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Classification of distributed binary labeling problems, 2019. URL: http://arxiv.org/abs/1911.13294.
  3. Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal independent sets. In Proc. 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019), pages 481-497. IEEE, 2019. URL: https://doi.org/10.1109/FOCS.2019.00037.
  4. Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. Distributed Lower Bounds for Ruling Sets. In Proc. 61st IEEE Symposium on Foundations of Computer Science (FOCS 2020). IEEE, 2020. URL: http://arxiv.org/abs/2004.08282.
  5. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. Almost global problems in the LOCAL model. In Proc. 32nd International Symposium on Distributed Computing (DISC 2018), Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1-9:16. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.9.
  6. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. How much does randomness help with locally checkable problems? In Proc. 39th ACM Symposium on Principles of Distributed Computing (PODC 2020). ACM Press, 2020. URL: https://doi.org/10.1145/3382734.3405715.
  7. Alkida Balliu, Juho Hirvonen, Janne H Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela. New classes of distributed time complexity. In Proc. 50th ACM Symposium on Theory of Computing (STOC 2018), pages 1307-1318. ACM Press, 2018. URL: https://doi.org/10.1145/3188745.3188860.
  8. Alkida Balliu, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela. Hardness of Minimal Symmetry Breaking in Distributed Computing. In Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 369-378. ACM Press, 2019. URL: https://doi.org/10.1145/3293611.3331605.
  9. Sebastian Brandt. An Automatic Speedup Theorem for Distributed Problems. In Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 379-388. ACM Press, 2019. URL: https://doi.org/10.1145/3293611.3331611.
  10. Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed Lovász local lemma. In Proc. 48th ACM Symposium on Theory of Computing (STOC 2016), pages 479-488. ACM Press, 2016. URL: https://doi.org/10.1145/2897518.2897570.
  11. Sebastian Brandt, Juho Hirvonen, Janne H Korhonen, Tuomo Lempiäinen, Patric R J Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, and Przemysław Uznański. LCL problems on grids. In Proc. 36th ACM Symposium on Principles of Distributed Computing (PODC 2017), pages 101-110. ACM Press, 2017. URL: https://doi.org/10.1145/3087801.3087833.
  12. Sebastian Brandt, Yannic Maus, and Jara Uitto. A sharp threshold phenomenon for the distributed complexity of the lovász local lemma. In Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 389-398. ACM Press, 2019. URL: https://doi.org/10.1145/3293611.3331636.
  13. Sebastian Brandt and Dennis Olivetti. Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants. In Proc. 39th ACM Symposium on Principles of Distributed Computing (PODC 2020). ACM Press, 2020. URL: https://doi.org/10.1145/3382734.3405745.
  14. Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. The Complexity of Distributed Edge Coloring with Small Palettes. In Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 2633-2652. Society for Industrial and Applied Mathematics, 2018. URL: https://doi.org/10.1137/1.9781611975031.168.
  15. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. In Proc. 57th IEEE Symposium on Foundations of Computer Science (FOCS 2016), pages 615-624. IEEE, 2016. URL: https://doi.org/10.1109/FOCS.2016.72.
  16. Yi-Jun Chang and Seth Pettie. A Time Hierarchy Theorem for the LOCAL Model. SIAM Journal on Computing, 48(1):33-69, 2019. URL: https://doi.org/10.1137/17M1157957.
  17. Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32-53, 1986. URL: https://doi.org/10.1016/S0019-9958(86)80023-7.
  18. Manuela Fischer and Mohsen Ghaffari. Sublogarithmic Distributed Algorithms for Lovász Local Lemma, and the Complexity Hierarchy. In Proc. 31st International Symposium on Distributed Computing (DISC 2017), pages 18:1-18:16, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.18.
  19. Mohsen Ghaffari, David G Harris, and Fabian Kuhn. On Derandomizing Local Distributed Algorithms. In Proc. 59th IEEE Symposium on Foundations of Computer Science (FOCS 2018), pages 662-673, 2018. URL: https://doi.org/10.1109/FOCS.2018.00069.
  20. Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto. Improved distributed degree splitting and edge coloring. In Proc. 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1-19:15. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.19.
  21. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In Proc. 49th ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 784-797. ACM Press, 2017. URL: https://doi.org/10.1145/3055399.3055471.
  22. Mohsen Ghaffari and Hsin-Hao Su. Distributed Degree Splitting, Edge Coloring, and Orientations. In Proc. 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 2505-2523. Society for Industrial and Applied Mathematics, 2017. URL: https://doi.org/10.1137/1.9781611974782.166.
  23. Janne H Korhonen and Jukka Suomela. Towards a complexity theory for the congested clique. In Proc. 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2018), pages 163-172. ACM Press, 2018. URL: https://doi.org/10.1145/3210377.3210391.
  24. Nathan Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. URL: https://doi.org/10.1137/0221015.
  25. Gary L. Miller and John H. Reif. Parallel tree contraction and its application. In Proc. 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), pages 478-489. IEEE, 1985. URL: https://doi.org/10.1109/SFCS.1985.43.
  26. Moni Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM Journal on Discrete Mathematics, 4(3):409-412, 1991. URL: https://doi.org/10.1137/0404036.
  27. Moni Naor and Larry Stockmeyer. What Can be Computed Locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. URL: https://doi.org/10.1137/S0097539793254571.
  28. Dennis Olivetti. Round Eliminator: a tool for automatic speedup simulation, 2020. URL: https://github.com/olidennis/round-eliminator.
  29. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. URL: https://doi.org/10.1137/1.9780898719772.
  30. Will Rosenbaum and Jukka Suomela. Seeing Far vs. Seeing Wide: Volume Complexity of Local Graph Problems. In Proc. 39th ACM Symposium on Principles of Distributed Computing (PODC 2020). ACM Press, 2020. URL: https://doi.org/10.1145/3382734.3405721.
  31. Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization. In Proc. 52nd Annual ACM Symposium on Theory of Computing (STOC 2020), 2020. URL: https://doi.org/10.1145/3357713.3384298.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact