LIPIcs.OPODIS.2018.8.pdf
- Filesize: 465 kB
- 17 pages
Document
The Amortized Analysis of a Non-blocking Chromatic Tree
Author
-
Part of:
Volume:
22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Principles of Distributed Systems (OPODIS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-01-15
Cite AsGet BibTex
Jeremy Ko. The Amortized Analysis of a Non-blocking Chromatic Tree. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.OPODIS.2018.8
https://doi.org/10.4230/LIPIcs.OPODIS.2018.8
Abstract
A non-blocking chromatic tree is a type of balanced binary search tree where multiple processes can concurrently perform search and update operations. We prove that a certain implementation has amortized cost O(dot{c} + log n) for each operation, where dot{c} is the maximum number of concurrent operations at any point during the execution and n is the maximum number of keys in the tree during the operation. This amortized analysis presents new challenges compared to existing analyses of other non-blocking data structures.
Subject Classification
ACM Subject Classification
- Theory of computation → Data structures design and analysis
- Theory of computation → Distributed algorithms
Keywords
- amortized analysis
- non-blocking
- lock-free
- balanced binary search trees
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley-Interscience, 2nd edition, 2004.
- Joan Boyar, Rolf Fagerberg, and Kim S. Larsen. Amortization Results for Chromatic Search Trees, with an Application to Priority Queues. In Proceedings of Algorithms and Data Structures, 4th International Workshop (WADS), pages 270-281, 1995. URL: http://dx.doi.org/10.1007/3-540-60220-8_69.
-
Trevor Brown. Techniques for Constructing Efficient Lock-Free Data Structures. PhD thesis, Department of Computer Science, University of Toronto, 2017.
- Trevor Brown, Faith Ellen, and Eric Ruppert. Pragmatic primitives for non-blocking data structures. In Proceedings of the Symposium on Principles of Distributed Computing (PODC), pages 13-22, 2013. URL: http://dx.doi.org/10.1145/2484239.2484273.
- Trevor Brown, Faith Ellen, and Eric Ruppert. A general technique for non-blocking trees. In Proceedings of the Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 329-342, 2014. URL: http://dx.doi.org/10.1145/2555243.2555267.
- Bapi Chatterjee, Nhan Nguyen Dang, and Philippas Tsigas. Efficient lock-free binary search trees. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 322-331, 2014. URL: http://dx.doi.org/10.1145/2611462.2611500.
- Faith Ellen, Panagiota Fatourou, Joanna Helga, and Eric Ruppert. The amortized complexity of non-blocking binary search trees. In Proceedings of the Symposium on Principles of Distributed Computing (PODC), pages 332-340, 2014. URL: http://dx.doi.org/10.1145/2611462.2611486.
- Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. Non-blocking binary search trees. In Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 131-140, 2010. URL: http://dx.doi.org/10.1145/1835698.1835736.
- Mikhail Fomitchev and Eric Ruppert. Lock-free linked lists and skip lists. In Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 50-59, 2004. URL: http://dx.doi.org/10.1145/1011767.1011776.
- Joel Gibson and Vincent Gramoli. Why Non-blocking Operations Should be Selfish. In Proceedings of the Distributed Computing - 29th International Symposium (DISC), pages 200-214, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48653-5_14.
- Timothy L. Harris. A Pragmatic Implementation of Non-blocking Linked-Lists. In Proceedings of the Distributed Computing, 15th International Conference (DISC), pages 300-314, 2001. URL: http://dx.doi.org/10.1007/3-540-45414-4_21.
- Otto Nurmi and Eljas Soisalon-Soininen. Chromatic Binary Search Trees. A Structure for Concurrent Rebalancing. Acta Inf., 33(6):547-557, 1996. URL: http://dx.doi.org/10.1007/BF03036462.
- Niloufar Shafiei. Non-Blocking Doubly-Linked Lists with Good Amortized Complexity. In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS), pages 35:1-35:17, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.OPODIS.2015.35.