Wait-free implementations in message-passing systems

DOI10.1016/S0304-3975(98)00242-4zbMATH Open0916.68065OpenAlexW2172260702MaRDI QIDQ1292433FDOQ1292433

Authors Soma Chaudhuri, Mark Tuttle, Maurice Herlihy

Publication date 21 June 1999

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

Full work available at URL https://doi.org/10.1016/s0304-3975(98)00242-4

zbMATH Keywords

data structuresdistributed algorithmsincrement registermessage-passing modelstrong renamingwait-free algorithms

Mathematics Subject Classification ID

Data structures (68P05) Parallel algorithms in computer science (68W10)

Recommendations

• Efficient and Robust Sharing of Memory in Message-Passing Systems
• The complexity of early deciding set agreement
• Strong order-preserving renaming in the synchronous message passing model
• Are wait-free algorithms fast?
• scientific article; zbMATH DE number 2013834

Cites work

• A lower bound for the time to assure interactive consistency
• Electing a leader in a synchronous ring
• Impossibility of distributed consensus with one faulty process
• Knowledge and common knowledge in a distributed environment
• Modelling knowledge and action in distributed systems
• Programming simultaneous actions using common knowledge
• Randomized wait-free concurrent objects (extended abstract)
• Reaching Agreement in the Presence of Faults
• Renaming in an asynchronous environment
• The Byzantine Generals Problem
• The Weak Byzantine Generals Problem
• The asynchronous computability theorem for t-resilient tasks
• Time, clocks, and the ordering of events in a distributed system

Cited in

(8)

• Renaming in synchronous message passing systems with Byzantine failures
• Efficient and Robust Sharing of Memory in Message-Passing Systems
• Tight bounds for asynchronous renaming
• Hundreds of impossibility results for distributed computing
• Fully-adaptive algorithms for long-lived renaming
• Generating fast indulgent algorithms
• Strong order-preserving renaming in the synchronous message passing model
• Extending the wait-free hierarchy to multi-threaded systems

This page was built for publication: Wait-free implementations in message-passing systems

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