The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2022.4
URN: urn:nbn:de:0030-drops-176240
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17624/
Go to the corresponding LIPIcs Volume Portal

Johnen, Colette ; Khattabi, Adnane ; Milani, Alessia

Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers

pdf-format:
LIPIcs-OPODIS-2022-4.pdf (0.9 MB)

Abstract

Despite the widespread usage of FIFO queues in distributed applications, designing efficient wait-free implementations of queues remains a challenge. The majority of wait-free queue implementations restrict either the number of dequeuers or the number of enqueuers that can operate on the queue, even when they use strong synchronization primitives, like the Compare&Swap. If we do not limit the number of processes that can perform enqueue and dequeue operations, the best-known upper bound on the worst case step complexity for a wait-free queue is given by [Khanchandani and Wattenhofer, 2018]. In particular, they present an implementation of a multiple dequeuer multiple enqueuer wait-free queue whose worst case step complexity is in O(√n), where n is the number of processes. In this work, we investigate whether it is possible to improve this bound. In particular, we present a wait-free FIFO queue implementation that supports n enqueuers and k dequeuers where the worst case step complexity of an Enqueue operation is in O(log n) and of a Dequeue operation is in O(k log n).
Then, we show that if the semantics of the queue can be relaxed, by allowing concurrent Dequeue operations to retrieve the same element, then we can achieve O(log n) worst-case step complexity for both the Enqueue and Dequeue operations.

BibTeX - Entry

@InProceedings{johnen_et_al:LIPIcs.OPODIS.2022.4,
  author =	{Johnen, Colette and Khattabi, Adnane and Milani, Alessia},
  title =	{{Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17624},
  URN =		{urn:nbn:de:0030-drops-176240},
  doi =		{10.4230/LIPIcs.OPODIS.2022.4},
  annote =	{Keywords: Distributed computing, distributed algorithms, FIFO queue, shared memory, fault tolerance, concurrent data structures, relaxed specifications, complexity}
}

Keywords: Distributed computing, distributed algorithms, FIFO queue, shared memory, fault tolerance, concurrent data structures, relaxed specifications, complexity
Collection: 26th International Conference on Principles of Distributed Systems (OPODIS 2022)
Issue Date: 2023
Date of publication: 15.02.2023

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