Randomized shared queues

1 August 2001

conference paper
Published by Association for Computing Machinery (ACM)

p. 311-313
https://doi.org/10.1145/383962.384050

Abstract

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.

Keywords

This publication has 3 references indexed in Scilit:

"Go with the winners" algorithms
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
Probabilistic quorum systems
Published by Association for Computing Machinery (ACM) ,1997
Byzantine quorum systems
Published by Association for Computing Machinery (ACM) ,1997