Approximate shared-memory counting despite a strong adversary
From MaRDI portal
Publication:2930301
DOI10.1145/1721837.1721841zbMath1300.68018MaRDI QIDQ2930301
James Aspnes, Keren Censor-Hillel
Publication date: 18 November 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1721837.1721841
68Q25: Analysis of algorithms and problem complexity
68P05: Data structures
68W20: Randomized algorithms
68W15: Distributed algorithms
Related Items
A Tight Space Bound for Consensus, Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity, Faster randomized consensus with an oblivious adversary, Combining shared-coin algorithms, A modular approach to shared-memory consensus, with applications to the probabilistic-write model, Communication-efficient randomized consensus, The CB tree: a practical concurrent self-adjusting search tree, Long-lived counters with polylogarithmic amortized step complexity, Lower Bounds for Restricted-Use Objects, Randomized Consensus in Expected O(n 2) Total Work Using Single-Writer Registers