Constant space and non-constant time in distributed computing

DOI10.4230/LIPICS.OPODIS.2017.30zbMATH Open1487.68253arXiv1705.03876OpenAlexW2962799384MaRDI QIDQ3300833FDOQ3300833

Authors: Tuomo Lempiäinen, Jukka Suomela 

Publication date: 30 July 2020

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.

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

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

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)

Cites Work

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

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)