Constant space and non-constant time in distributed computing

DOI10.4230/LIPIcs.OPODIS.2017.30zbMath1487.68253arXiv1705.03876OpenAlexW2962799384MaRDI QIDQ3300833

Tuomo Lempiäinen, Jukka Suomela

Publication date: 30 July 2020

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

zbMATH Keywords

Thue-Morse sequencedistributed computingspace complexityweak modelsconstant-space algorithms

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Beeping a maximal independent set
• Lower bounds for local approximation
• Local Computation
• Deploying Wireless Networks with Beeps
• Locality in Distributed Graph Algorithms
• Exploring an Infinite Space with Finite Memory Scouts
• Distributed Graph Automata
• What Can be Computed Locally?
• On the complexity of local distributed graph problems
• Solving the ANTS Problem with Asynchronous Finite State Machines
• Stone age distributed computing
• A lower bound for the distributed Lovász local lemma
• LCL Problems on Grids
• Weak models of distributed computing, with connections to modal logic

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