Skueue: A Scalable and Sequentially Consistent Distributed Queue.

We propose a distributed protocol for a queue, called \textsc{Skueue}, whichspreads its data fairly onto multiple processes, avoiding bottlenecks in highthroughput scenarios. \textsc{Skueue} can be used in highly dynamicenvironments, through the addition of join and leave requests to the standardqueue operations enqueue and dequeue. Furthermore \textsc{Skueue} satisfiessequential consistency in the asynchronous message passing model. Scalabilityis achieved by aggregating multiple requests to a batch, which can then beprocessed in a distributed fashion without hurting the queue semantics.Operations in \textsc{Skueue} need a logarithmic number of rounds w.h.p. untilthey are processed, even under a high rate of incoming requests.