Randomized wait-free concurrent objects (extended abstract)

DOI10.1145/112600.112602MaRDI QIDQ5255802zbMATHOpenAlexFDO

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)

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

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)