Locality and checkability in wait-free computing

DOI10.1007/978-3-642-24100-0_34MaRDI QIDQ3095336zbMATHOpenAlexFDO

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

zbMATH Keywords

distributed verificationwait-free computingdecision tasklocal computing

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(10)

• Power and limits of distributed computing shared memory models
• Asynchronous Wait-Free Runtime Verification and Enforcement of Linearizability
• scientific article; zbMATH DE number 1479626 (Why is no real title available?)
• Translating submachine locality into locality of reference
• The relative power of composite loop agreement tasks
• Locality and checkability in wait-free computing
• A new approach on locally checkable problems
• scientific article; zbMATH DE number 7228882 (Why is no real title available?)
• A classification of wait-free loop agreement tasks
• Computable obstructions to wait-free computability

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)