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

Authors Colette Johnen, Adnane Khattabi, Alessia Milani



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2022.4.pdf
  • Filesize: 0.89 MB
  • 19 pages

Document Identifiers

Author Details

Colette Johnen
  • Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, Talence, France
Adnane Khattabi
  • Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, Talence, France
Alessia Milani
  • Aix Marseille Univ, CNRS, LIS, UMR 7020, Marseille, France

Cite AsGet BibTex

Colette Johnen, Adnane Khattabi, and Alessia Milani. Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.OPODIS.2022.4

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Distributed algorithms
  • Theory of computation → Proof complexity
Keywords
  • Distributed computing
  • distributed algorithms
  • FIFO queue
  • shared memory
  • fault tolerance
  • concurrent data structures
  • relaxed specifications
  • complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. Relaxed queues and stacks from read/write operations. In 24th International Conference on Principles of Distributed Systems, OPODIS 2020,, pages 13:1-13:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2020.13.
  2. Armando Castañeda and Miguel Piña. Fully read/write fence-free work-stealing with multiplicity, 2020. URL: https://doi.org/10.48550/arXiv.2008.04424.
  3. Matei David. A single-enqueuer wait-free queue implementation. In Proceedings of 18th International Conference Distributed Computing, DISC 2004, pages 132-143, Berlin, Heidelberg, 2004. Springer-Verlag. URL: https://doi.org/10.1007/978-3-540-30186-8_10.
  4. David Eisenstat. Two-enqueuer queue in common2, 2008. Google Scholar
  5. Panagiota Fatourou and Nikolaos D. Kallimanis. Highly-efficient wait-free synchronization. Theor. Comp. Sys., 55(3):475-520, October 2014. URL: https://doi.org/10.1007/s00224-013-9491-y.
  6. Thomas A. Henzinger, Christoph M. Kirsch, Hannes Payer, Ali Sezgin, and Ana Sokolova. Quantitative relaxation of concurrent data structures. SIGPLAN Not., 48(1):317-328, January 2013. URL: https://doi.org/10.1145/2480359.2429109.
  7. Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124-149, January 1991. URL: https://doi.org/10.1145/114005.102808.
  8. Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, July 1990. URL: https://doi.org/10.1145/78969.78972.
  9. Prasad Jayanti and Srdjan Petrovic. Logarithmic-time single deleter, multiple inserter wait-free queues and stacks. In Proceedings of the 25th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS '05, pages 408-419, Berlin, Heidelberg, 2005. Springer-Verlag. URL: https://doi.org/10.1007/11590156_33.
  10. Pankaj Khanchandani and Roger Wattenhofer. On the importance of synchronization primitives with low consensus numbers. In Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN '18, pages 18:1-18:10, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3154273.3154306.
  11. Christoph M. Kirsch, Michael Lippautz, and Hannes Payer. Fast and scalable, lock-free k-fifo queues. In Proceedings of 12th International Conferenc Parallel Computing Technologies, PaCT'13, pages 208-223, Berlin, Heidelberg, 2013. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-39958-9_18.
  12. Alex Kogan and Erez Petrank. Wait-free queues with multiple enqueuers and dequeuers. SIGPLAN Not., 46(8):223-234, February 2011. URL: https://doi.org/10.1145/2038037.1941585.
  13. Zongpeng Li. Non-blocking implementations of queues in asynchronous distributed shared-memory systems. Master’s thesis, Univ. of Toronto, January 2001. Google Scholar
  14. Adam Morrison and Yehuda Afek. Fast concurrent queues for x86 processors. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '13, pages 103-112, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2442516.2442527.
  15. Gil Neiger. Set-linearizability. In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '94, page 396, New York, NY, USA, 1994. Association for Computing Machinery. URL: https://doi.org/10.1145/197917.198176.
  16. Chaoran Yang and John Mellor-Crummey. A wait-free queue as fast as fetch-and-add. SIGPLAN Notices, 51(8):1-13, February 2016. URL: https://doi.org/10.1145/3016078.2851168.
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