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 exclusionobject implementationsspace lower bounds

Mathematics Subject Classification ID

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

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
• scientific article; zbMATH DE number 4047047
• 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

(16)

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

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)