Probabilistic Broadcast

Abstract

We present a class of scalable and probabilisticly reliable communication protocols. The protocols are based on a probabilistic system model and thus their properties tend to be probabilistic in nature. The protocols are scalable in two senses. First, the message costs and latencies of the protocols grow slowly with the system size. Second, the reliability of the protocols, expressed in terms of the probability of a failed run of a protocol, approaches 0 exponentially fast as the number of processes is increased. This scalable reliability is achieved through a form of gossip protocol which is strongly self-stabilizing in a sense similar, although not identical to, the notion of self stabilizing systems proposed by Dijkstra.