Non-blocking implementations of Queues in asynchronous distributed shared-memory systems

grantor: University of TorontoWe study non-blocking linearizable implementations of objects shared concurrently by multiple asynchronous processes. In a non-blocking implementation, 'some' process is guaranteed to complete its access to the object, regardless of the other processes' speed. A particular case of non-blocking implementations is a wait-free implementation, in which ' every' process is guaranteed to complete its access to the object. In particular, we investigate implementations of Queue objects from a set of commonly supported types, including Test&Set, Fetch&Add and Swap. We exhibit and prove correct a non-blocking implementation that works for any number of processes, where each process can perform both enqueue and dequeue operations; and a wait-free implementation that works when at most two processes can perform dequeue operations concurrently, while an arbitrary number of processes can perform enqueue operations. We conjecture that when more than two processes can perform dequeue operations concurrently, a wait-free and linearizable Queue implementation is not possible.M.Sc