부산대학교 도서관

Summary: ``Despite the widespread usage of {\tt FIFO} queues indistributed applications, designing efficient {\tt wait-free}implementations of queues remains a challenge. The majority ofwait-free queue implementations restrict either the number of dequeuers or the number of enqueuers that can operate on the queue, even whenthey use strong synchronization primitives, like the {\it Compare\&Swap}. If we do not limit the number of processes that canperform enqueue and dequeue operations, the best-known upper bound onthe worst case step complexity for a wait-free queue is given byKhanchandani and Wattenhofer [10]. In particular, they present animplementation of a multiple dequeuer multiple enqueuer wait-free queuewhose worst case step complexity is in $O(\sqrt n)$, where $n$ is thenumber of processes. In this work, we investigate whether it ispossible to improve this bound. In particular, we present a wait-freeFIFO queue implementation that supports $n$ enqueuers and $k$ dequeuerswhere the worst case step complexity of an {\it Enqueue} operation isin $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, byallowing concurrent {\it Dequeue} operations to retrieve the sameelement, then we can achieve $O(\log n)$ worst-case step complexity forboth the {\it Enqueue} and {\it Dequeue} operations.''