A simple characterization of asynchronous computations

DOI10.1016/J.TCS.2014.07.022MaRDI QIDQ477089zbMATH OpenOpenAlexFDO

Authors Yehuda Afek, Eli Gafni

Publication date 2 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.07.022

zbMATH Keywords

distributed algorithmsshared memorywait-freeasynchronous computabilityread writesubdivided simplex

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• A simple constructive computability theorem for wait-free computation
• The topological structure of asynchronous computability
• An asynchronous computability theorem for fair adversaries
• Initial failures in distributed computations
• Synchronous, asynchronous, and causally ordered communication

Cites work

• scientific article; zbMATH DE number 4102053 (Why is no real title available?)
• scientific article; zbMATH DE number 3698053 (Why is no real title available?)
• A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
• A simple characterization of asynchronous computations
• Agreement in synchronous networks with ubiquitous faults
• Bounds on information exchange for Byzantine agreement
• Distributed computation in dynamic networks
• Electing a leader in a synchronous ring
• Immediate atomic snapshots and fast renaming
• Impossibility Results and Lower Bounds for Consensus under Link Failures
• Impossibility of distributed consensus with one faulty process
• Reaching Agreement in the Presence of Faults
• Reaching approximate agreement in the presence of faults
• Round-by-round fault detectors (extended abstract), unifying synchrony and asynchrony
• Sharing memory robustly in message-passing systems
• Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors
• The Heard-Of model: computing in distributed systems with benign faults
• The topological structure of asynchronous computability
• The unified structure of consensus, a layered analysis approach
• Time is not a healer (preliminary version)
• Unifying synchronous and asynchronous message-passing models

Cited in

(6)

• scientific article; zbMATH DE number 1863169 (Why is no real title available?)
• A simple characterization of asynchronous computations
• A hierarchy of equivalences for asynchronous calculi
• Toward a Topological Characterization of Asynchronous Complexity
• Communication Complexity of Wait-Free Computability in Dynamic Networks
• scientific article; zbMATH DE number 4001466 (Why is no real title available?)

This page was built for publication: A simple characterization of asynchronous computations

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