Randomized distributed decision
DOI10.1007/s00446-014-0211-xzbMath1320.68223arXiv1207.0252OpenAlexW2570310514MaRDI QIDQ2256969
Pierre Fraigniaud, Mika Göös, David Peleg, Merav Parter, Amos Korman
Publication date: 23 February 2015
Published in: Lecture Notes in Computer Science, Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1207.0252
randomized algorithmscomplexity classeslocal decisionlocal distributed algorithmsdistributed local algorithms
Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Distributed algorithms (68W15)
Related Items
Cites Work
- Tight bounds for distributed minimum-weight spanning tree verification
- Distributed verification of minimum spanning trees
- Proof labeling schemes
- Locality and checkability in wait-free computing
- Decidability Classes for Mobile Agents Computing
- Locally checkable proofs
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- Distributed Computing: A Locality-Sensitive Approach
- What Can be Computed Locally?
- On the Complexity of Distributed Network Decomposition
- Distributed Verification and Hardness of Distributed Approximation
- Distributed (δ+1)-coloring in linear (in δ) time
- A new technique for distributed symmetry breaking
- Towards a complexity theory for local distributed computing