Constant space and non-constant time in distributed computing

Tuomo Lempiäinen; Jukka Suomela

doi:10.4230/LIPIcs.OPODIS.2017.30

Constant space and non-constant time in distributed computing

Tuomo Lempiäinen, Jukka Suomela

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

15 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 language	English
Title of host publication	21st International Conference on Principles of Distributed Systems (OPODIS 2017)
Publisher	Schloss Dagstuhl - Leibniz Center for Informatics
Pages	1-16
ISBN (Electronic)	9783959770613
DOIs	https://doi.org/10.4230/LIPIcs.OPODIS.2017.30
Publication status	Published - Mar 2018
MoE publication type	A4 Article in a conference publication
Event	International Conference on Principles of Distributed Systems - Lisbon, Portugal Duration: 18 Dec 2017 → 20 Dec 2017 Conference number: 21

Publication series

Name	Leibniz International Proceedings in Informatics
Publisher	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
Volume	95
ISSN (Electronic)	1868-8969

Conference

Conference	International Conference on Principles of Distributed Systems
Abbreviated title	OPODIS
Country/Territory	Portugal
City	Lisbon
Period	18/12/2017 → 20/12/2017

Keywords

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

Access to Document

10.4230/LIPIcs.OPODIS.2017.30

LIPIcs-OPODIS-2017-30Final published version, 497 KBLicence: CC BY

1 Conference presentation

Conference presentation at OPODIS 2017 (Lisbon, Portugal)
Tuomo Lempiäinen (Speaker)
18 Dec 2017 → 20 Dec 2017
Activity: Talk or presentation types › Conference presentation

Cite this

@inproceedings{5f7ffbbc0abd49439a6402760f8945a9,

title = "Constant space and non-constant time in distributed computing",

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.",

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

author = "Tuomo Lempi{\"a}inen and Jukka Suomela",

year = "2018",

month = mar,

doi = "10.4230/LIPIcs.OPODIS.2017.30",

language = "English",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz Center for Informatics",

pages = "1--16",

booktitle = "21st International Conference on Principles of Distributed Systems (OPODIS 2017)",

note = "International Conference on Principles of Distributed Systems, OPODIS ; Conference date: 18-12-2017 Through 20-12-2017",

}

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 Center for Informatics, pp. 1-16, International Conference on Principles of Distributed Systems, Lisbon, Portugal, 18/12/2017. https://doi.org/10.4230/LIPIcs.OPODIS.2017.30

Constant space and non-constant time in distributed computing. / Lempiäinen, Tuomo; Suomela, Jukka.

21st International Conference on Principles of Distributed Systems (OPODIS 2017). Schloss Dagstuhl - Leibniz Center for Informatics, 2018. p. 1-16 30 (Leibniz International Proceedings in Informatics; Vol. 95).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Constant space and non-constant time in distributed computing

AU - Lempiäinen, Tuomo

AU - Suomela, Jukka

N1 - Conference code: 21

PY - 2018/3

Y1 - 2018/3

N2 - 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.

AB - 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.

KW - distributed computing

KW - space complexity

KW - constant-space algorithms

KW - weak models

KW - Thue–Morse sequence

U2 - 10.4230/LIPIcs.OPODIS.2017.30

DO - 10.4230/LIPIcs.OPODIS.2017.30

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics

SP - 1

EP - 16

BT - 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

PB - Schloss Dagstuhl - Leibniz Center for Informatics

T2 - International Conference on Principles of Distributed Systems

Y2 - 18 December 2017 through 20 December 2017

ER -

Constant space and non-constant time in distributed computing

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Activities

Conference presentation at OPODIS 2017 (Lisbon, Portugal)

Cite this