Locality and checkability in wait-free computing

DOI10.1007/978-3-642-24100-0_34MaRDI QIDQ3095336zbMATH OpenOpenAlexFDO

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

decision taskdistributed verificationlocal computingwait-free computing

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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

(11)

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

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)