Brief announcement: Randomized shared queues Conference Paper uri icon


  • This paper presents a specification of a randomized shared queue that can lose some elements or return them out of order (not in FIFO), shows that the specification can be implemented over the probabilistic quorum algorithm of [4,3], and analyzes the behavior of this implementation. Distributed algorithms that can tolerate some lost and out-of-order messages are candidates for replacing the message queues with random queues. The modified algorithms will inherit positive attributes concerning load and availability from the underlying queue implementation. The behavior of an application - a class of combinatorial optimization algorithms - when it is implemented using random queues is analyzed.

author list (cited authors)

  • Lee, H., & Welch, J. L.

publication date

  • January 2001