Constant space and non-constant time in distributed computing

Thumbnail Image

Access rights

openAccess
publishedVersion

URL

Journal Title

Journal ISSN

Volume Title

A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)

Authors

Date

2018-03

Department

Department of Computer Science

Major/Subject

Mcode

Degree programme

Language

en

Pages

Series

21st International Conference on Principles of Distributed Systems (OPODIS 2017), pp. 1-16, Leibniz International Proceedings in Informatics ; Volume 95

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.

Description

Keywords

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

Other note

DOI

10.4230/LIPIcs.OPODIS.2017.30

Citation

Lempiäinen, T & Suomela, J 2018, Constant space and non-constant time in distributed computing. in 21st International Conference on Principles of Distributed Systems (OPODIS 2017)., 30, Leibniz International Proceedings in Informatics, vol. 95, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-16, International Conference on Principles of Distributed Systems, Lisbon, Portugal, 18/12/2017. https://doi.org/10.4230/LIPIcs.OPODIS.2017.30

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-201812106087

Collections

[article-cris] Perustieteiden korkeakoulu / SCI