Byzantine Agreement Among Network Processors With a Reduced Number of Messages
Original Publication Date: 1983-Jun-01
Included in the Prior Art Database: 2005-Feb-07
This invention relates to a method for achieving Byzantine agreement among n processors with up to t faults, requiring at most O(n+t2) messages at the expense of extra phases. That is, the number of messages required to reach agreement is reduced from O(nt) to O(n+t2). The method steps comprise (a) partitioning the processors into two sets; (b) during phase l, broadcasting an authenticated (signed) first value message by each processor in turn to every other processor; (c) in the interval between phase 2 phase t+2, broadcasting an authenticated first value message to all processors in the second set by each processor in the first set responsive to receipt of a first value message and vis- a-vis; and (d) signifying agreement by each processor to a first value if by phase t+2 an authenticated first value message was received.