Browse Prior Art Database

Probabilistic Byzantine Agreements

IP.com Disclosure Number: IPCOM000060903D
Original Publication Date: 1986-May-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Dolev, D: AUTHOR

Abstract

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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 64% of the total text.

Page 1 of 1

Probabilistic Byzantine Agreements

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. Thus, faulty processors completely obey the algorithm, but some messages they were supposed to send may not have arrived (output fault). 2. A completely synchronous system and completely connected and reliable communication network. 3. The sender is known and also the phase at which it should send its value. 4. The sender may send either 0 or 1. 5. There exists a sequence of random binary values (called coins), and all processors can access that sequence. All processors are synchronized on the sequence. Method Steps 1. At phase 1, the sender sends its value. Every other processor initiates v=0. 2. At the end of pha...