LIPIcs.OPODIS.2020.14.pdf
- Filesize: 482 kB
- 16 pages
Document
Fast and Space-Efficient Queues via Relaxation
Authors
-
Part of:
Volume:
24th International Conference on Principles of Distributed Systems (OPODIS 2020)
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: 2021-01-25
File
Document Identifiers
Acknowledgements
We would like to thank Anh Kieu, Shane Staret, and Jimmy Wei for helping find references.
Cite As Get BibTex
Dempsey Wade and Edward Talmage. Fast and Space-Efficient Queues via Relaxation. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.OPODIS.2020.14
Abstract
Efficient message-passing implementations of shared data types are a vital component of practical distributed systems, enabling them to work on shared data in predictable ways, but there is a long history of results showing that many of the most useful types of access to shared data are necessarily slow. A variety of approaches attempt to circumvent these bounds, notably weakening consistency guarantees and relaxing the sequential specification of the provided data type. These trade behavioral guarantees for performance. We focus on relaxing the sequential specification of a first-in, first-out queue type, which has been shown to allow faster linearizable implementations than are possible for traditional FIFO queues without relaxation. The algorithms which showed these improvements in operation time tracked a complete execution history, storing complete object state at all n processes in the system, leading to n copies of every stored data element. In this paper, we consider the question of reducing the space complexity of linearizable implementations of shared data types, which provide intuitive behavior through strong consistency guarantees. We improve the existing algorithm for a relaxed queue, showing that it is possible to store only one copy of each element in a shared queue, while still having a low amortized time cost. This is one of several important steps towards making these data types practical in real world systems.
Subject Classification
ACM Subject Classification
- Computing methodologies → Distributed algorithms
Keywords
- Shared Data Structures
- Message Passing
- Relaxed Data Types
- Space Complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Yehuda Afek, Guy Korland, and Eitan Yanovsky. Quasi-linearizability: Relaxed consistency for improved concurrency. In Chenyang Lu, Toshimitsu Masuzawa, and Mohamed Mosbah, editors, Principles of Distributed Systems - 14th International Conference, OPODIS 2010, Tozeur, Tunisia, December 14-17, 2010. Proceedings, volume 6490 of Lecture Notes in Computer Science, pages 395-410. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-17653-1_29.
- Hagit Attiya and Jennifer L. Welch. Sequential consistency versus linearizability. ACM Transactions on Computer Systems, 12(2):91-122, 1994. URL: https://doi.org/10.1145/176575.176576.
- Iwan Briquemont, Manuel Bravo, Zhongmiao Li, and Peter Van Roy. Conflict-free partially replicated data types. In 7th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2015, Vancouver, BC, Canada, November 30 - December 3, 2015, pages 282-289. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/CloudCom.2015.81.
- Jean-Michel Hélary and Alessia Milani. About the efficiency of partial replication to implement distributed shared memory. In 2006 International Conference on Parallel Processing (ICPP 2006), 14-18 August 2006, Columbus, Ohio, USA, pages 263-270. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/ICPP.2006.15.
- Thomas A. Henzinger, Christoph M. Kirsch, Hannes Payer, Ali Sezgin, and Ana Sokolova. Quantitative relaxation of concurrent data structures. In Roberto Giacobazzi and Radhia Cousot, editors, The 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '13, Rome, Italy - January 23 - 25, 2013, pages 317-328. ACM, 2013. URL: https://doi.org/10.1145/2429069.2429109.
- Martha J. Kosa. Time bounds for strong and hybrid consistency for arbitrary abstract data types. Chicago Journal of Theoretical Computer Science, 1999, 1999. URL: http://cjtcs.cs.uchicago.edu/articles/1999/9/contents.html.
- Jennifer Lundelius and Nancy A. Lynch. An upper and lower bound for clock synchronization. Information and Control, 62(2/3):190-204, 1984. URL: https://doi.org/10.1016/S0019-9958(84)80033-9.
- Marios Mavronicolas and Dan Roth. Linearizable read/write objects. Theoretical Computer Science, 220(1):267-319, 1999. URL: https://doi.org/10.1016/S0304-3975(98)90244-4.
- Edward Talmage and Jennifer L. Welch. Improving average performance by relaxing distributed data structures. In Fabian Kuhn, editor, Distributed Computing - 28th International Symposium, DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceedings, volume 8784 of Lecture Notes in Computer Science, pages 421-438. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-45174-8_29.
- Werner Vogels. Eventually consistent. Communications of the ACM, 52(1):40-44, 2009. URL: https://doi.org/10.1145/1435417.1435432.
- Jiaqi Wang, Edward Talmage, Hyunyoung Lee, and Jennifer L. Welch. Improved time bounds for linearizable implementations of abstract data types. Information and Computation, 263:1-30, 2018. URL: https://doi.org/10.1016/j.ic.2018.08.004.
- Zhuolun Xiang and Nitin H. Vaidya. Partially replicated causally consistent shared memory: Lower bounds and an algorithm. In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 425-434. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331600.