Linearizable implementations do not suffice for randomized distributed computation

DOI10.1145/1993636.1993687MaRDI QIDQ5419107zbMATH OpenOpenAlexFDO

Authors Wojciech Golab, Lisa Higham, Philipp Woelfel

Publication date 5 June 2014

Published in Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

adversary modelsatomicitylinearizabilityrandomized algorithms

Mathematics Subject Classification ID

Distributed systems (68M14) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• Strongly linearizable implementations, possibilities and impossibilities
• Wait-freedom is harder than lock-freedom under strong linearizability
• Are shared objects composable under an oblivious adversary?
• Randomized consensus with regular registers
• Eventually linearizable shared objects

Cited in

(27)

• Wait-freedom is harder than lock-freedom under strong linearizability
• The correctness proof of Ben-Or's randomized consensus algorithm
• Randomized consensus with regular registers
• On atomic registers and randomized consensus in m\&m systems
• Strongly linearizable implementations, possibilities and impossibilities
• Sublogarithmic test-and-set against a weak adversary
• Tight bounds for asynchronous renaming
• Strongly Linearizable Implementations of Snapshots and Other Types
• Eventually linearizable shared objects
• Are shared objects composable under an oblivious adversary?
• Automata, Languages and Programming
• Brief Announcement: Intermediate Value Linearizability: A Quantitative Correctness Criterion
• Faster randomized consensus with an oblivious adversary
• The limits of helping in non-volatile memory data structures
• Intermediate value linearizability: a quantitative correctness criterion
• Quorum tree abstractions of consensus protocols
• On implementing SWMR registers from SWSR registers in systems with Byzantine failures
• Randomized mutual exclusion with sub-logarithmic RMR-complexity
• A wait-free queue with polylogarithmic step complexity
• Optimal resilience in systems that mix shared memory and message passing
• Preserving hyperproperties of programs using primitives with consensus number 2
• Faithful simulation of randomized BFT protocols on block DAGs
• Faster randomized repeated choice and DCAS
• Strongly linearizable LL/SC from CAS
• Strong linearizability using primitives with consensus number 2
• Fast and fair randomized wait-free locks
• Intermediate value linearizability: a quantitative correctness criterion

This page was built for publication: Linearizable implementations do not suffice for randomized distributed computation

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