Activities per year
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-Zentrum für Informatik |
Pages | 1-16 |
ISBN (Electronic) | 9783959770613 |
DOIs | |
Publication status | Published - Mar 2018 |
MoE publication type | A4 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
Fingerprint
Dive into the research topics of 'Constant space and non-constant time in distributed computing'. Together they form a unique fingerprint.Activities
- 1 Conference presentation
-
Conference presentation at OPODIS 2017 (Lisbon, Portugal)
Lempiäinen, T. (Speaker)
18 Dec 2017 → 20 Dec 2017Activity: Talk or presentation types › Conference presentation