DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2017.30

Constant Space and Non-Constant Time in Distributed Computing

Authors: Tuomo Lempiäinen and Jukka Suomela

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{lempiainen_et_al:LIPIcs.OPODIS.2017.30,
  author =	{Lempi\"{a}inen, Tuomo and Suomela, Jukka},
  title =	{{Constant Space and Non-Constant Time in Distributed Computing}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.30},
  URN =		{urn:nbn:de:0030-drops-86368},
  doi =		{10.4230/LIPIcs.OPODIS.2017.30},
  annote =	{Keywords: distributed computing, space complexity, constant-space algorithms, weak models, Thue-Morse sequence}
}

Search Results

Documents authored by Lempiäinen, Tuomo

Constant Space and Non-Constant Time in Distributed Computing

Abstract

Cite as

Thanks for your feedback!

Could not send message