Constant space and non-constant time in distributed computing

DOI10.4230/LIPICS.OPODIS.2017.30MaRDI QIDQ3300833zbMATH OpenOpenAlexFDO

Authors Tuomo Lempiäinen, Jukka Suomela

Publication date 30 July 2020

Full work available at URL https://arxiv.org/abs/1705.03876

zbMATH Keywords

distributed computingspace complexityThue-Morse sequenceweak modelsconstant-space algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)

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.

Recommendations

• On real-time and non real-time distributed computing
• New classes of distributed time complexity
• Time-message trade-offs in distributed algorithms
• scientific article; zbMATH DE number 4050992
• Efficient distributed algorithms by using the archimedean time assumption
• Time and Space Lower Bounds for Nonblocking Implementations
• Space- and time-adaptive nonblocking algorithms
• scientific article; zbMATH DE number 3940742
• Transience bounds for distributed algorithms

Cites work

• scientific article; zbMATH DE number 1818513 (Why is no real title available?)
• A lower bound for the distributed Lovász local lemma
• Asynchronous distributed automata: a characterization of the modal \(\mu\)-fragment
• Deploying wireless networks with beeps
• Distributed graph automata
• Emptiness problems for distributed automata
• Exploring an infinite space with finite memory scouts
• Infinite networks, halting and local algorithms
• LCL problems on grids
• Local computation: lower and upper bounds
• Locality in Distributed Graph Algorithms
• On the complexity of local distributed graph problems
• Solving the ANTS problem with asynchronous finite state machines
• Stone age distributed computing
• Weak models of distributed computing, with connections to modal logic
• What Can be Computed Locally?

This page was built for publication: Constant space and non-constant time in distributed computing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3300833)