Approximate shared-memory counting despite a strong adversary

DOI10.1145/1721837.1721841zbMath1300.68018OpenAlexW2168550339MaRDI 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

zbMATH Keywords

martingalesdistributed computingconsensusexpandersapproximate counting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

A modular approach to shared-memory consensus, with applications to the probabilistic-write model ⋮ Long-lived counters with polylogarithmic amortized step complexity ⋮ Combining shared-coin algorithms ⋮ The CB tree: a practical concurrent self-adjusting search tree ⋮ Faster randomized consensus with an oblivious adversary ⋮ Lower Bounds for Restricted-Use Objects ⋮ Randomized Consensus in Expected O(n 2) Total Work Using Single-Writer Registers ⋮ Communication-efficient randomized consensus ⋮ A Tight Space Bound for Consensus ⋮ Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity