Randomized wait-free concurrent objects (extended abstract)

DOI10.1145/112600.112602MaRDI QIDQ5255802zbMATH OpenOpenAlexFDO

Authors Maurice Herlihy

Publication date 19 June 2015

Published in Proceedings of the tenth annual ACM symposium on Principles of distributed computing - PODC '91 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/112600.112602

Mathematics Subject Classification ID

Randomized algorithms (68W20) Data structures (68P05) Distributed algorithms (68W15) Distributed systems (68M14) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cited in

(48)

• Wait-free implementations in message-passing systems
• Introduction à l'algorithmique des objets partagés
• Anonymous and fault-tolerant shared-memory computing
• Help when needed, but no more: efficient read/write partial snapshot
• Open consensus
• A scalable lock-free stack algorithm
• Sublogarithmic test-and-set against a weak adversary
• A timing assumption and two \(t\)-resilient protocols for Implementing an eventual leader service in asynchronous shared memory systems
• Trace-based derivation of a scalable lock-free stack algorithm
• Adaptive progress: a gracefully-degrading liveness property
• Refined quorum systems
• Implementing sequentially consistent programs on processor consistent platforms
• Lock-free deques and doubly linked lists
• Efficient algorithms for checking the atomicity of a run of read and write operations
• Atomic snapshots using lattice agreement
• Bounded-wait combining: constructing robust and high-throughput shared objects
• scientific article; zbMATH DE number 7561451 (Why is no real title available?)
• Nonblocking \(k\)-compare-single-swap
• Failure detectors as type boosters
• Solo-valency and the cost of coordination
• Inter-process buffers in separation logic with rely-guarantee
• Tight bounds for asynchronous renaming
• NB{\texttt{malloc}}: Allocating memory in a lock-free manner
• Online search with time-varying price bounds
• Tight bounds for shared memory systems accessed by Byzantine processes
• A modular approach to shared-memory consensus, with applications to the probabilistic-write model
• RMR-efficient implementations of comparison primitives using read and write operations
• Renaming and the weakest family of failure detectors
• The space complexity of unbounded timestamps
• A criterion for atomicity
• Active disk Paxos with infinitely many processes
• Efficient adaptive collect using randomization
• Common2 extended to stacks and unbounded concurrency
• Composite registers
• Model checking transactional memories
• Randomized two-process wait-free test-and-set
• On set consensus numbers
• The mailbox problem
• Threshold protocols in survivor set systems
• The complexity of updating snapshot objects
• The weakest failure detectors to boost obstruction-freedom
• Ll/SC and atomic copy: constant time, space efficient implementations using only pointer-width CAS
• Combining shared-coin algorithms
• Transactional memory
• Lock-free dynamic hash tables with open addressing
• The \(k\)-simultaneous consensus problem
• Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler
• Primitives for asynchronous list compression

This page was built for publication: Randomized wait-free concurrent objects (extended abstract)

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