Δ-reliable broadcast: a probabilistic measure of broadcast reliabillity

We introduce a new probabilistic specification of reliable broadcast communication primitives, called Δ - reliable broadcast. This specification captures in a precise way the reliability of practical broadcast algorithms that, on the one hand, were devised with some form of reliability in mind but, on the other hand, are not considered reliable according to "traditional" reliability specifications. We illustrate the use of our specification by precisely measuring and comparing the reliability of two popular broadcast algorithms, namely bimodal multicast and IP multicast. In particular, we quantify how the reliability of each algorithm scales with the size of the system.