On the specification of fault-tolerant broadcast

Two types of fault-tolerant broadcasts, reliable broadcast and atomic broadcast, are discussed. The Byzantine Generals (BG) problem is the most studied formulation of reliable broadcast (L. Lamport et al., 1982). The authors propose the following additional requirement (uniformity) to the usual specification of the BG problem: if any processor, correct or faulty, accepts a message, then all correct processors must accept the same message. The usual specification of the atomic broadcast problem requires that all correct processors agree on the messages broadcast and process them in the same order. The authors propose an additional requirement, called purity, to the usual specification of atomic broadcast. This requirement prevents faulty processors from contaminating the system by broadcasts