Constant space and non-constant time in distributed computing

Tuomo Lempiäinen, Jukka Suomela

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

27 Lataukset (Pure)


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.
Otsikko21st International Conference on Principles of Distributed Systems (OPODIS 2017)
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (elektroninen)9783959770613
DOI - pysyväislinkit
TilaJulkaistu - maalisk. 2018
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Conference on Principles of Distributed Systems - Lisbon, Portugali
Kesto: 18 jouluk. 201720 jouluk. 2017
Konferenssinumero: 21


NimiLeibniz International Proceedings in Informatics
KustantajaSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
ISSN (elektroninen)1868-8969


ConferenceInternational Conference on Principles of Distributed Systems


Sukella tutkimusaiheisiin 'Constant space and non-constant time in distributed computing'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä