Locality and checkability in wait-free computing

DOI10.1007/978-3-642-24100-0_34zbMATH Open1311.68025OpenAlexW2105440249MaRDI QIDQ3095336FDOQ3095336

Authors: Pierre Fraigniaud, Sergio Rajsbaum, Corentin Travers 

Publication date: 28 October 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-24100-0_34

Recommendations

• Locality and checkability in wait-free computing
• Computable obstructions to wait-free computability
• The topological structure of asynchronous computability
• The Combinatorial Structure of Wait-Free Solvable Tasks
• A simple constructive computability theorem for wait-free computation

zbMATH Keywords

distributed verificationwait-free computingdecision tasklocal computing

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14)

Cites Work

• Proof labeling schemes
• Title not available (Why is that?)
• Property testing and its connection to learning and approximation
• Renaming in an asynchronous environment
• Distributed Computing: A Locality-Sensitive Approach
• Communication algorithms with advice
• Self-testing/correcting with applications to numerical problems
• Spot-checkers
• Distributed enumeration
• Locality in Distributed Graph Algorithms
• Distributed verification and hardness of distributed approximation
• Designing programs that check their work
• Impossibility of distributed consensus with one faulty process
• Title not available (Why is that?)
• The topological structure of asynchronous computability
• Title not available (Why is that?)
• On the complexity of distributed graph coloring
• Three-Processor Tasks Are Undecidable
• Title not available (Why is that?)
• Local Distributed Decision
• A classification of wait-free loop agreement tasks
• Toward more localized local algorithms
• Reaching approximate agreement in the presence of faults
• Deterministic distributed vertex coloring in polylogarithmic time
• Locally checkable proofs
• Deterministic coin tossing with applications to optimal parallel list ranking
• What Can be Computed Locally?
• On the power of synchronization between two adjacent processes
• Covering complexes with applications to algebra
• Designing checkers for programs that run in parallel
• Efficient learning of typical finite automata from random walks
• Locality and checkability in wait-free computing
• Title not available (Why is that?)

Cited In (8)

• Power and limits of distributed computing shared memory models
• Title not available (Why is that?)
• A new approach on locally checkable problems
• A classification of wait-free loop agreement tasks
• Locality and checkability in wait-free computing
• Translating submachine locality into locality of reference
• Asynchronous Wait-Free Runtime Verification and Enforcement of Linearizability
• Title not available (Why is that?)

This page was built for publication: Locality and checkability in wait-free computing

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