2026-10-13T05:27:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17624 2024-03-06T10:00:09Z ddc:004 open_access

Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers Johnen, Colette Khattabi, Adnane Milani, Alessia Distributed computing distributed algorithms FIFO queue shared memory fault tolerance concurrent data structures relaxed specifications complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Colette Johnen and Adnane Khattabi and Alessia Milani 2023 Is Part Of LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2022.4 urn:nbn:de:0030-drops-176240 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.4 eng https://creativecommons.org/licenses/by/4.0/legalcode