Document Open Access Logo

Constant Space and Non-Constant Time in Distributed Computing

Authors Tuomo Lempiäinen, Jukka Suomela

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2017.30.pdf
  • Filesize: 494 kB
  • 16 pages

Document Identifiers

Author Details

Tuomo Lempiäinen
Jukka Suomela

Cite As Get BibTex

Tuomo Lempiäinen and Jukka Suomela. Constant Space and Non-Constant Time in Distributed Computing. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.OPODIS.2017.30

Abstract

While the relationship of time and space is an established topic in traditional centralised com- plexity theory, this is not the case in distributed computing. We aim to remedy this by studying the time and space complexity of algorithms in a weak message-passing model of distributed com- puting. While a constant number of communication rounds implies a constant number of states visited during the execution, the other direction is not clear at all. We show that indeed, there exist non-trivial graph problems that are solvable by constant-space algorithms but that require a non-constant running time. Somewhat surprisingly, this holds even when restricted to the class of only cycle and path graphs. Our work provides us with a new complexity class for distributed computing and raises interesting questions about the existence of further combinations of time and space complexity.

Subject Classification

Keywords
  • distributed computing
  • space complexity
  • constant-space algorithms
  • weak models
  • Thue-Morse sequence

Metrics

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

References

  1. Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, and Fabian Kuhn. Beeping a maximal independent set. In Proc. 25th International Symposium on Distributed Computing (DISC 2011), volume 6950 of Lecture Notes in Computer Science, pages 32-50. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-24100-0_3.
  2. Dana Angluin. Local and global properties in networks of processors. In Proc. 12th Annual ACM Symposium on Theory of Computing (STOC 1980), pages 82-93. ACM, 1980. URL: http://dx.doi.org/10.1145/800141.804655.
  3. Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, and Jukka Suomela. New classes of distributed time complexity, 2017. URL: http://arxiv.org/abs/1711.01871.
  4. 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 Annual ACM Symposium on Theory of Computing (STOC 2016), pages 479-488. ACM, 2016. http://dx.doi.org/10.1145/2897518.2897570. URL: http://arxiv.org/abs/1511.00900.
  5. 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 Annual ACM Symposium on Principles of Distributed Computing (PODC 2017), pages 101-110. ACM, 2017. http://dx.doi.org/10.1145/3087801.3087833. URL: http://arxiv.org/abs/1702.05456.
  6. Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. In Proc. 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pages 615-624. IEEE, 2016. http://dx.doi.org/10.1109/FOCS.2016.72. URL: http://arxiv.org/abs/1602.08166.
  7. Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model. In Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), pages 156-167. IEEE, 2017. http://dx.doi.org/10.1109/FOCS.2017.23. URL: http://arxiv.org/abs/1704.06297.
  8. Lihi Cohen, Yuval Emek, Oren Louidor, and Jara Uitto. Exploring an infinite space with finite memory scouts. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 207-224. SIAM, 2017. http://dx.doi.org/10.1137/1.9781611974782.14. URL: http://arxiv.org/abs/1704.02380.
  9. Alejandro Cornejo and Fabian Kuhn. Deploying wireless networks with beeps. In Proc. 24th International Symposium on Distributed Computing (DISC 2010), volume 6343 of Lecture Notes in Computer Science, pages 148-162. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15763-9_15.
  10. Yuval Emek, Tobias Langner, Jara Uitto, and Roger Wattenhofer. Solving the ANTS problem with asynchronous finite state machines. In Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), pages 471-482. Springer, 2014. http://dx.doi.org/10.1007/978-3-662-43951-7_40. URL: http://arxiv.org/abs/1311.3062.
  11. Yuval Emek and Roger Wattenhofer. Stone age distributed computing. In Proc. 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC 2013), pages 137-146. ACM, 2013. http://dx.doi.org/10.1145/2484239.2484244. URL: http://arxiv.org/abs/1202.1186.
  12. Martin Gardner. The fantastic combinations of John Conway’s new solitaire game "life". Scientific American, 223(4):120-123, 1970. Google Scholar
  13. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In Proc. 49th Annual ACM Symposium on Theory of Computing (STOC 2017), pages 784-797. ACM, 2017. http://dx.doi.org/10.1145/3055399.3055471. URL: http://arxiv.org/abs/1611.02663.
  14. Mika Göös, Juho Hirvonen, and Jukka Suomela. Lower bounds for local approximation. Journal of the ACM, 60(5):39:1-23, 2013. http://dx.doi.org/10.1145/2528405. URL: http://arxiv.org/abs/1201.6675.
  15. Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Luosto, Jukka Suomela, and Jonni Virtema. Weak models of distributed computing, with connections to modal logic. Distributed Computing, 28(1):31-53, 2015. http://dx.doi.org/10.1007/s00446-013-0202-3. URL: http://arxiv.org/abs/1205.2051.
  16. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: lower and upper bounds. Journal of the ACM, 63(2):17:1-17:44, 2016. http://dx.doi.org/10.1145/2742012. URL: http://arxiv.org/abs/1011.5470.
  17. Antti Kuusisto. Infinite networks, halting and local algorithms. In Proc. 5th International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2014), volume 161 of Electronic Proceedings in Theoretical Computer Science, pages 147-160, 2014. http://dx.doi.org/10.4204/EPTCS.161.14. URL: http://arxiv.org/abs/1408.5963.
  18. Antti Kuusisto and Fabian Reiter. Emptiness problems for distributed automata. In Proc. 8th International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2017), volume 256 of Electronic Proceedings in Theoretical Computer Science, pages 210-222, 2017. http://dx.doi.org/10.4204/EPTCS.256.15. URL: http://arxiv.org/abs/1705.02609.
  19. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. URL: http://dx.doi.org/10.1137/0221015.
  20. Moni Naor and Larry Stockmeyer. What can be computed locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. URL: http://dx.doi.org/10.1137/S0097539793254571.
  21. Fabian Reiter. Distributed graph automata. In Proc. 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015), pages 192-201. IEEE, 2015. http://dx.doi.org/10.1109/LICS.2015.27. URL: http://arxiv.org/abs/1404.6503.
  22. Fabian Reiter. Asynchronous distributed automata: a characterization of the modal mu-fragment. In Proc. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pages 100:1-100:14. Schloss Dagstuhl - Leibniz Center for Informatics, 2017. https://dx.doi.org/10.4230/LIPIcs.ICALP.2017.100. URL: http://arxiv.org/abs/1611.08554.
  23. John von Neumann. Theory of Self-Reproducing Automata. University of Illinois Press, 1966. Google Scholar
  24. Stephen Wolfram. A New Kind of Science. Wolfram Media, 2002. Google Scholar
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