Complexity tradeoffs for read and update operations

DOI10.1145/2611462.2611472MaRDI QIDQ2943622zbMATH OpenOpenAlexFDO

Authors Danny Hendler, Vitaly Khait

Publication date 3 September 2015

Published in Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2611462.2611472

zbMATH Keywords

counterMAX registerrestricted-use objectssnapshot

Mathematics Subject Classification ID

Distributed systems (68M14) Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• The complexity of updating snapshot objects
• Polylogarithmic concurrent data structures from monotone circuits
• Faster than optimal snapshots (for a while), preliminary version
• Limited-use atomic snapshots with polylogarithmic step complexity
• MAX registers, counters, and monotone circuits

Cited in

(7)

• Long-lived counters with polylogarithmic amortized step complexity
• Lower bounds for restricted-use objects
• Erratum to: ``Limited-use atomic snapshots with polylogarithmic step complexity
• MAX registers, counters, and monotone circuits
• Polylogarithmic concurrent data structures from monotone circuits
• Limited-use atomic snapshots with polylogarithmic step complexity
• Long-lived counters with polylogarithmic amortized step complexity

This page was built for publication: Complexity tradeoffs for read and update operations

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