Document Open Access Logo

Long-Lived Counters with Polylogarithmic Amortized Step Complexity

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.DISC.2019.3.pdf
  • Filesize: 0.56 MB
  • 16 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Shared memory algorithms
  • Theory of computation → Concurrent algorithms
Keywords
  • Shared Memory
  • Wait-freedom
  • Counter
  • Amortized Complexity
  • Concurrent Objects

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

A shared-memory counter is a well-studied and widely-used concurrent object. It supports two operations: An Inc operation that increases its value by 1 and a Read operation that returns its current value. Jayanti, Tan and Toueg [Jayanti et al., 2000] proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read and write operations, of a large class of shared objects that includes counters. The lower bound leaves open the question of finding counter implementations with sub-linear amortized step complexity.
In this paper, we address this gap. We present the first wait-free n-process counter, implemented using only read and write operations, whose amortized operation step complexity is O(log^2 n) in all executions. This is the first non-blocking read/write counter algorithm that provides sub-linear amortized step complexity in executions of arbitrary length. Since a logarithmic lower bound on the amortized step complexity of obstruction-free counter implementations exists, our upper bound is optimal up to a logarithmic factor.

Cite As Get BibTex

Mirza Ahad Baig, Danny Hendler, Alessia Milani, and Corentin Travers. Long-Lived Counters with Polylogarithmic Amortized Step Complexity. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.DISC.2019.3

Author Details

Mirza Ahad Baig
  • LaBRI, Bordeaux INP, France
  • CNRS, ReLaX, UMI2000, Siruseri, India
  • Chennai Mathematical Institute, Siruseri, India
Danny Hendler
  • Ben-Gurion University of the Negev, Beer-Sheva, Israel
Alessia Milani
  • LaBRI, Bordeaux INP, France
Corentin Travers
  • LaBRI, Bordeaux INP, France

Funding

Mirza Ahad Baig, Alessia Milani and Corentin Travers are supported by ANR projects Descartes and FREDDA. Mirza Ahad Baig is additionally supported by UMI Relax. Danny Hendler is supported by the Israel Science Foundation (grant 380/18).

Acknowledgements

We thank the anonymous reviewers for their many helpful comments.

References

  1. Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM (JACM), 40(4):873-890, 1993. Google Scholar
  2. Yehuda Afek, Haim Kaplan, Boris Korenfeld, Adam Morrison, and Robert E Tarjan. The CB tree: a practical concurrent self-adjusting search tree. Distributed computing, 27(6):393-417, 2014. Google Scholar
  3. James Anderson. Composite registers. Distributed Computing, 6(3):141-154, 1993. Google Scholar
  4. James Aspnes, Hagit Attiya, and Keren Censor-Hillel. Polylogarithmic concurrent data structures from monotone circuits. J. ACM, 59(1):2:1-2:24, 2012. Google Scholar
  5. James Aspnes and Keren Censor. Approximate shared-memory counting despite a strong adversary. ACM Trans. Algorithms, 6(2):25:1-25:23, 2010. Google Scholar
  6. James Aspnes and Keren Censor-Hillel. Atomic Snapshots in O(log³ n) Steps Using Randomized Helping. In 27th International Symposium on Distributed Computing (DISC), volume 8205 of Lecture Notes in Computer Science, pages 254-268. Springer, 2013. Google Scholar
  7. James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. Journal of algorithms, 11(3):441-461, 1990. Google Scholar
  8. Hagit Attiya and Arie Fouren. Adaptive and efficient algorithms for lattice agreement and renaming. SIAM Journal on Computing, 31(2):642-664, 2001. Google Scholar
  9. Hagit Attiya and Danny Hendler. Time and Space Lower Bounds for Implementations Using k-CAS. IEEE Trans. Parallel Distrib. Syst., 21(2):162-173, 2010. Google Scholar
  10. Michael A. Bender and Seth Gilbert. Mutual Exclusion with O(log² log n) Amortized Work. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 728-737. IEEE, 2011. Google Scholar
  11. Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(1):124-149, 1991. Google Scholar
  12. Maurice Herlihy, Victor Luchangco, and Mark Moir. Obstruction-Free Synchronization: Double-Ended Queues as an Example. In 23rd International Conference on Distributed Computing Systems (ICDCS), pages 522-529. IEEE Computer Society, 2003. Google Scholar
  13. Maurice P Herlihy and Jeannette M Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(3):463-492, 1990. Google Scholar
  14. Michiko Inoue, Toshimitsu Masuzawa, Wei Chen, and Nobuki Tokura. Linear-time snapshot using multi-writer multi-reader registers. In International Workshop on Distributed Algorithms, pages 130-140. Springer, 1994. Google Scholar
  15. Prasad Jayanti. A Time Complexity Lower Bound for Randomized Implementations of Some Shared Objects. In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC '98, pages 201-210, 1998. Google Scholar
  16. Prasad Jayanti, King Tan, and Sam Toueg. Time and Space Lower Bounds for Nonblocking Implementations. SIAM J. Comput., 30(2), 2000. Google Scholar
  17. Shlomo Moran and Gadi Taubenfeld. A lower bound on wait-free counting. J. Algorithms, 24(1):1-19, 1997. Google Scholar
  18. Shlomo Moran, Gadi Taubenfeld, and Irit Yadin. Concurrent Counting. J. Comput. Syst. Sci., 53(1):61-78, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact