1 Search Results for "Wade, Dempsey"

Document
DOI: 10.4230/LIPIcs.OPODIS.2020.14
Fast and Space-Efficient Queues via Relaxation

Authors: Dempsey Wade and Edward Talmage

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{wade_et_al:LIPIcs.OPODIS.2020.14,
  author =	{Wade, Dempsey and Talmage, Edward},
  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 =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.14},
  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}
}
  • Refine by Author
  • 1 Talmage, Edward
  • 1 Wade, Dempsey

  • Refine by Classification
  • 1 Computing methodologies → Distributed algorithms

  • Refine by Keyword
  • 1 Message Passing
  • 1 Relaxed Data Types
  • 1 Shared Data Structures
  • 1 Space Complexity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact