Skueue: A Scalable and Sequentially Consistent Distributed Queue

We propose a distributed protocol for a queue, called SKUEUE, which spreads its data fairly onto multiple processes, avoiding bottlenecks in high throughput scenarios. SKUEUE can be used in highly dynamic environments, through the addition of JOIN() and LEAVE() requests to the standard queue operations ENQUEUE() and DEQUEUE(). Furthermore SKUEUE satisfies sequential consistency in the asynchronous message passing model. Scalability is achieved by aggregating multiple requests to a batch, which can then be processed in a distributed fashion without hurting the queue semantics. Operations in SKUEUE need a logarithmic number of rounds w.h.p. until they are processed, even under a high rate of incoming requests.