Long-lived counters with polylogarithmic amortized step complexity

DOI10.4230/LIPICS.DISC.2019.3MaRDI QIDQ6487520zbMATH OpenFDO

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

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2019.3

zbMATH Keywords

shared memoryamortized complexitywait-freedomconcurrent objectscounter

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Polylogarithmic concurrent data structures from monotone circuits
• Concurrent counting
• Concurrent counting (extended abstract)
• Complexity tradeoffs for read and update operations
• Lower bounds on the amortized time complexity of shared objects

Cited in

(5)

• Brief announcement: Fast shared counting using \(O(n)\) compare-and-swap registers
• Polylogarithmic concurrent data structures from monotone circuits
• Concurrent counting (extended abstract)
• Long-lived counters with polylogarithmic amortized step complexity
• Lower bounds on the amortized time complexity of shared objects

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

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