Constant space and non-constant time in distributed computing

Tuomo Lempiäinen, Jukka Suomela

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

11 Downloads (Pure)

Abstract

While the relationship of time and space is an established topic in traditional centralised complexity 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 computing. 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 consider several graph families and show that indeed, there exist non-trivial graph problems that are solvable by constant-space algorithms but that require a non-constant running time. This 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.
Original languageEnglish
Title of host publication21st International Conference on Principles of Distributed Systems (OPODIS 2017)
PublisherSchloss Dagstuhl - Leibniz Center for Informatics
Pages1-16
ISBN (Electronic)9783959770613
DOIs
Publication statusPublished - Mar 2018
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Principles of Distributed Systems - Lisbon, Portugal
Duration: 18 Dec 201720 Dec 2017
Conference number: 21

Publication series

NameLeibniz International Proceedings in Informatics
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
Volume95
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Conference on Principles of Distributed Systems
Abbreviated titleOPODIS
CountryPortugal
CityLisbon
Period18/12/201720/12/2017

Keywords

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

Fingerprint Dive into the research topics of 'Constant space and non-constant time in distributed computing'. Together they form a unique fingerprint.

Cite this