Time and Space Lower Bounds for Nonblocking Implementations
From MaRDI portal
Publication:4507358
DOI10.1137/S0097539797317299zbMath0968.68064OpenAlexW2030205622MaRDI QIDQ4507358
Sam Toueg, Prasad Jayanti, King Tan
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
synchronizationlower boundstime complexitynonblockingspace complexitywait-freeasynchronous shared memory algorithmsrandomized shared object implementations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)
Related Items
On the inherent weakness of conditional primitives, Tight Bounds for Asynchronous Renaming, The space complexity of unbounded timestamps, Lower and upper bounds for single-scanner snapshot implementations, Long-lived counters with polylogarithmic amortized step complexity, Efficient adaptive collect using randomization, Hundreds of impossibility results for distributed computing, Linear space bootstrap communication schemes, The complexity of updating snapshot objects, A complexity-based classification for multiprocessor synchronization, Lower Bounds for Restricted-Use Objects, Allocate-On-Use Space Complexity of Shared-Memory Algorithms, The F-Snapshot Problem, Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity, Computing in totally anonymous asynchronous shared memory systems
