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

zbMATH Keywords

randomized algorithmscomplexity classeslocal decisionlocal distributed algorithmsdistributed local algorithms

Mathematics Subject Classification ID

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

Tight bounds for distributed minimum-weight spanning tree verification ⋮ Distributed Testing of Distance-k Colorings ⋮ Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Deciding and verifying network properties locally with few output bits ⋮ Randomized proof-labeling schemes ⋮ Unnamed Item ⋮ Introduction to local certification

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