Long-lived counters with polylogarithmic amortized step complexity

DOI10.1007/s00446-022-00439-5OpenAlexW4310988981MaRDI QIDQ2689836

Mirza Ahad Baig, Danny Hendler, Alessia Milani, Corentin Travers

Publication date: 14 March 2023

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-022-00439-5

zbMATH Keywords

amortized complexityshared memorywait-freedomconcurrent objectscounter

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Cites Work

• Concurrent counting
• The CB tree: a practical concurrent self-adjusting search tree
• Composite registers
• Adaptive and Efficient Algorithms for Lattice Agreement and Renaming
• A time complexity lower bound for randomized implementations of some shared objects
• Approximate shared-memory counting despite a strong adversary
• Fast randomized consensus using shared memory
• Atomic snapshots of shared memory
• Counting networks
• A Lower Bound on Wait-Free Counting
• Time and Space Lower Bounds for Nonblocking Implementations
• Linearizable counting networks
• Brief Announcement
• Polylogarithmic concurrent data structures from monotone circuits
• Mutual Exclusion with O(log^2 Log n) Amortized Work

This page was built for publication: Long-lived counters with polylogarithmic amortized step complexity