Browse Prior Art Database

Message Optimal Protocols for Byzantine Agreement

IP.com Disclosure Number: IPCOM000122641D
Original Publication Date: 1991-Dec-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 1 page(s) / 37K

IBM

Abstract

Byzantine Agreement is the problem whereby all processes in a system have to agree on the same value, despite the presence of failures. Described are algorithms for Byzantine Agreement that use a provably minimal number of messages in runs where no failures occur, the case which is expected to hold most often in practice.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 88% of the total text.

Message Optimal Protocols for Byzantine Agreement

Byzantine Agreement is the problem whereby all processes
in a system have to agree on the same value, despite the presence of
failures.  Described are algorithms for Byzantine Agreement that use
a provably minimal number of messages in runs where no failures
occur, the case which is expected to hold most often in practice.

The precise number of messages required for Byzantine Agreement
depends on the total number of processes in the system (n), the bound
on the number of failures (t), and the type of failures considered.
Algorithms are provided that have optimal message complexity for each
type of failure considered.  In the case of omission failures (where
a faulty process may omit to send a message),  the method involves
dividing the processes in the system into three groups, R0, R1, and
B, where B consists of t processes.  If the sender's value is i
(where i is 0 or 1), the sender sends its value to the first process
in Ri, which sends it to the second process in Ri, and so on, to
the last process in Ri, which sends the value to all the processes in
B.  If a failure is detected, a standard algorithm for Byzantine
Agreement is invoked (see [*])  If there are no failures, then
processes in R0 receive no messages if the sender's value is 1, while
processes in R1 receive no message if the sender's value is 0.  The
total number of messages sent in the failure-free executions is n + t
- 1, which is p...