Infoscience

Report

What Good are Probabilistic Specifications and What Probabilistic Specifications are Good?

The number of probabilistic approaches to classic'' distributed systems problems such as reliable broadcast, consensus, or leader election, has further increased recently. Probabilistic algorithms, possibly starting from probabilistic system models, have been motivated by the need for practicable solutions to such problems, circumventing bottlenecks and limitations inherent to distributed computing. While many approaches coming out of this revival of probabilistic approaches are indeed pathbreaking, it is legitimate to question the usefulness of certain efforts, which claim some form of probabilistic reliability, yet fail to provide clear specifications of the proposed algorithms. In this paper, we point out the inherent difficulties related to the specification of the behavior of probabilistic algorithms through various examples.