부산대학교 도서관

Summary: ``Despite the widespread usage of {\tt FIFO} queues in distributed applications, designing efficient {\tt 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 {\it 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 [10]. In particular, they present an implementation of a multiple dequeuer multiple enqueuer wait-free queue whose worst case step complexity is in $O(\sqrt 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 {\it Enqueue} operation is in $O(\log n)$ and of a {\it Dequeue} operation is in $O(k \log n)$. \par ``Then, we show that if the semantics of the queue can be relaxed, by allowing concurrent {\it Dequeue} operations to retrieve the same element, then we can achieve $O(\log n)$ worst-case step complexity for both the {\it Enqueue} and {\it Dequeue} operations.''