Wait-free implementations in message-passing systems

DOI10.1016/S0304-3975(98)00242-4zbMath0916.68065OpenAlexW2172260702MaRDI QIDQ1292433

Mark R. Tuttle, Soma Chaudhuri, Maurice P. 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

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

Related Items

Tight Bounds for Asynchronous Renaming, Renaming in synchronous message passing systems with Byzantine failures, 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

Cites Work

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