License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2020.14
URN: urn:nbn:de:0030-drops-134994
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13499/
Go to the corresponding LIPIcs Volume Portal

Wade, Dempsey ; Talmage, Edward

Fast and Space-Efficient Queues via Relaxation

pdf-format:
LIPIcs-OPODIS-2020-14.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{wade_et_al:LIPIcs:2021:13499,
  author =	{Dempsey Wade and Edward Talmage},
  title =	{{Fast and Space-Efficient Queues via Relaxation}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Quentin Bramas and Rotem Oshman and Paolo Romano},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13499},
  URN =		{urn:nbn:de:0030-drops-134994},
  doi =		{10.4230/LIPIcs.OPODIS.2020.14},
  annote =	{Keywords: Shared Data Structures, Message Passing, Relaxed Data Types, Space Complexity}
}

Keywords: Shared Data Structures, Message Passing, Relaxed Data Types, Space Complexity
Collection: 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
Issue Date: 2021
Date of publication: 25.01.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI