On the inherent weakness of conditional primitives

DOI10.1007/S00446-005-0136-5MaRDI QIDQ2375295zbMATH OpenOpenAlexFDO

Authors Faith E. Fich, Danny Hendler, Nir Shavit

Publication date 13 June 2013

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00446-005-0136-5

zbMATH Keywords

conditionalsmutual exclusionspace lower boundsobject implementations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Network design and communication in computer systems (68M10)

Recommendations

• On the impossibility of structure-preserving deterministic primitives
• On the impossibility of structure-preserving deterministic primitives
• Some Variants of the Weakest Precondition in Nondeterminism
• Publication:4503969
• The weakest precondition calculus: Recursion and duality
• Weakest Preconditions for High-Level Programs
• On the inherent weakness of conditional synchronization primitives
• Towards a Theory of Consistency Primitives
• Publication:3783508
• The Weakest Libera! Preconditions of Nondeterministic Machines and Robust Programs

Cites work

• A fast, scalable mutual exclusion algorithm
• A time complexity lower bound for randomized implementations of some shared objects
• An improved lower bound for the time complexity of mutual exclusion
• Bounds on shared memory for mutual exclusion
• Contention in shared memory algorithms
• Hundreds of impossibility results for distributed computing
• Shared-memory mutual exclusion: major research trends since 1986
• Time and Space Lower Bounds for Nonblocking Implementations

Cited in

(15)

• Common2 extended to stacks and unbounded concurrency
• Common2 extended to stacks and unbounded concurrency
• Tight bounds for asynchronous renaming
• Distributed Computing
• On the inherent sequentiality of concurrent objects
• Distributed Computing
• Beyond atomic registers: Bounded wait-free implementations of nontrivial objects
• Time and Space Lower Bounds for Nonblocking Implementations
• The power of multiobjects.
• On the time and space complexity of ABA prevention and detection
• Improved implementations of binary universal operations
• RMR-efficient implementations of comparison primitives using read and write operations
• Can an operation both update the state and return a meaningful value in the asynchronous PRAM model?
• On the space complexity of randomized synchronization
• Highly-efficient wait-free synchronization

This page was built for publication: On the inherent weakness of conditional primitives

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