Time and Space Lower Bounds for Nonblocking Implementations

DOI10.1137/S0097539797317299MaRDI QIDQ4507358zbMATH OpenOpenAlexFDO

Authors Prasad Jayanti, King Tan, Sam Toueg

Publication date 18 October 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539797317299

zbMATH Keywords

lower boundssynchronizationnonblockingspace complexitytime complexitywait-freeasynchronous shared memory algorithmsrandomized shared object implementations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Recommendations

• Distributed Computing
• Lower bounds for restricted-use objects
• On the inherent sequentiality of concurrent objects
• On the inherent weakness of conditional primitives
• Time lower bounds for implementations of multi-writer snapshots

Cited in

(21)

• Distributed Computing
• A complexity-based classification for multiprocessor synchronization
• Limited-use atomic snapshots with polylogarithmic step complexity
• Allocate-on-use space complexity of shared-memory algorithms
• Constant space and non-constant time in distributed computing
• Hundreds of impossibility results for distributed computing
• Computing in totally anonymous asynchronous shared memory systems
• On the space complexity of randomized synchronization
• Proving that non-blocking algorithms don't block
• On the inherent sequentiality of concurrent objects
• On the inherent weakness of conditional primitives
• Lower bounds for restricted-use objects
• Linear space bootstrap communication schemes
• Tight bounds for asynchronous renaming
• The space complexity of unbounded timestamps
• The F-Snapshot Problem
• Lower and upper bounds for single-scanner snapshot implementations
• On the time and space complexity of ABA prevention and detection
• Efficient adaptive collect using randomization
• Long-lived counters with polylogarithmic amortized step complexity
• The complexity of updating snapshot objects

This page was built for publication: Time and Space Lower Bounds for Nonblocking Implementations

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