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 messagepassing 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 nontrivial graph problems that are solvable by constantspace algorithms but that require a nonconstant 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  116 
ISBN (Electronic)  9783959770613 
DOIs  
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  LeibnizZentrum fuer Informatik GmbH 
Volume  95 
ISSN (Electronic)  18688969 
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
 constantspace algorithms
 weak models
 Thue–Morse sequence
Fingerprint
Dive into the research topics of 'Constant space and nonconstant time in distributed computing'. Together they form a unique fingerprint.Activities
 1 Conference presentation

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