Probabilistic Byzantine Agreements
Original Publication Date: 1986-May-01
Included in the Prior Art Database: 2005-Mar-09
This invention relates to a method of achieving Byzantine Agreement in a series of phased broadcast information exchanges using a random message sequence reachable by all correct processors. The random sequence is used in an operational way. Relatedly, the prior art taught the use of random sequence to agree on the thresholds processors have to set up in order to circumvent faults and to reach a decision. The random bit is chosen as the default value, in case there is no clear majority to either of the values, and to decide when the majority value is equal to the random bit. In this invention, a single threshold probabilistic method is obtained. Previous probabilistic agreement methods required at least two thresholds, and therefore a worse ratio of correct to faulty processors. Assumptions 1. An omission fault model.