LIPIcs.OPODIS.2019.18.pdf
- Filesize: 0.63 MB
- 15 pages
Document
An Efficient Universal Construction for Large Objects
Authors
-
Part of:
Volume:
23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
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: 2020-02-11
Cite As Get BibTex
Panagiota Fatourou, Nikolaos D. Kallimanis, and Eleni Kanellou. An Efficient Universal Construction for Large Objects. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.18
Abstract
This paper presents L-UC, a universal construction that efficiently implements dynamic objects of large state in a wait-free manner. The step complexity of L-UC is O(n+kw), where n is the number of processes, k is the interval contention (i.e., the maximum number of active processes during the execution interval of an operation), and w is the worst-case time complexity to perform an operation on the sequential implementation of the simulated object. L-UC efficiently implements objects whose size can change dynamically. It improves upon previous universal constructions either by efficiently handling objects whose state is large and can change dynamically, or by achieving better step complexity.
Subject Classification
ACM Subject Classification
- Computing methodologies → Concurrent computing methodologies
- Theory of computation → Concurrent algorithms
- Computing methodologies → Concurrent algorithms
- Computing methodologies → Shared memory algorithms
- Theory of computation → Shared memory algorithms
Keywords
- universal construction
- concurrent object
- shared memory
- simulation
- wait-freedom
- large object
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Yehuda Afek, Dalia Dauber, and Dan Touitou. Wait-free made fast. In Proceedings of the 27th ACM Symposium on Theory of Computing, pages 538-547, 1995.
-
James H. Anderson and Mark Moir. Universal constructions for multi-object operations. In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing, pages 184-193, 1995.
-
James H. Anderson and Mark Moir. Universal Constructions for Large Objects. IEEE Transactions on Parallel and Distributed Systems, 10(12):1317-1332, December 1999.
-
Greg Barnes. A method for implementing lock-free shared data structures. In Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures, pages 261-270, 1993.
-
Phong Chuong, Faith Ellen, and Vijaya Ramachandran. A universal construction for wait-free transaction friendly data structures. In Proceedings of the 22nd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 335-344, 2010.
- Andreia Correia, Pedro Ramalhete, and Pascal Felber. A Wait-Free Universal Construct for Large Objects, 2019. URL: http://arxiv.org/abs/1911.01676.
-
Panagiota Fatourou and Nikolaos D. Kallimanis. The RedBlue Adaptive Universal Constructions. In Proceedings of the 23rd International Symposium on Distributed Computing, pages 127-141, 2009.
-
Panagiota Fatourou and Nikolaos D. Kallimanis. A Highly-Efficient Wait-Free Universal Construction. In Proceedings of the 23nd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 325-334, 2011.
-
Panagiota Fatourou and Nikolaos D. Kallimanis. Revisiting the combining synchronization technique. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 257-266. ACM, 2012.
-
Panagiota Fatourou and Nikolaos D Kallimanis. Highly-Efficient Wait-Free Synchronization. Theory of Computing Systems, pages 1-46, 2013.
-
Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13:124-149, January 1991.
-
Maurice Herlihy. A methodology for implementing highly concurrent data objects. ACM Transactions on Programming Languages and Systems (TOPLAS), 15(5):745-770, November 1993.