Fast and Space-Efficient Queues via Relaxation

Wade, Dempsey; Talmage, Edward

doi:10.4230/LIPIcs.OPODIS.2020.14

File

LIPIcs.OPODIS.2020.14.pdf

Filesize: 482 kB
16 pages

Document Identifiers

DOI: 10.4230/LIPIcs.OPODIS.2020.14
URN: urn:nbn:de:0030-drops-134994

Author Details

Dempsey Wade

Bucknell University, Lewisburg, PA, USA

Edward Talmage

Computer Science Department, Bucknell University, Lewisburg, PA, USA

Acknowledgements

We would like to thank Anh Kieu, Shane Staret, and Jimmy Wei for helping find references.

Cite AsGet 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)

0

PDF Downloads

0

Metadata Views

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.