Browse Prior Art Database

Byzantine Agreement Method Without Authentication

IP.com Disclosure Number: IPCOM000047738D
Original Publication Date: 1983-Dec-01
Included in the Prior Art Database: 2005-Feb-08
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Related People

Reischuk, RK: AUTHOR

Abstract

This invention relates to a method for achieving Byzantine Agreement without authentication among n 100 communicating processors using event counting and thresholding rather than message exchanges and evaluations. The counting permits simplified probability models of fault behavior among the processes. The model for this problem is a network of n processors that conduct several synchronized phases of information exchange, after which they all must agree on some value that at the beginning was set by one of them. Byzantine Agreement results when, in the presence of undetected faulty processors, all correct processors agree either on the value sent by the originator, or on the conclusion that the originator is faulty and this is actually true.

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

Page 1 of 3

Byzantine Agreement Method Without Authentication

This invention relates to a method for achieving Byzantine Agreement without authentication among n 100 communicating processors using event counting and thresholding rather than message exchanges and evaluations. The counting permits simplified probability models of fault behavior among the processes. The model for this problem is a network of n processors that conduct several synchronized phases of information exchange, after which they all must agree on some value that at the beginning was set by one of them. Byzantine Agreement results when, in the presence of undetected faulty processors, all correct processors agree either on the value sent by the originator, or on the conclusion that the originator is faulty and this is actually true. The method described does not use authentication, and improves previous results in several respects. First, it works correctly for a broader class of histories. This is achieved by distinguishing between different kinds of processor failures and reintegrating processors that were only temporarily faulty.

Secondly, not every processor can prevent the other correct processors from reaching agreement fast, as it is possible in the previous algorithms by sending enough inconsistent messages.

Instead, to each phase there is assigned one special processor, and it essentially depends on the correctness of this processor whether the rest reach agreement within the next phases or not. The algorithm also overcomes communication link failures. The Model for Agreement Algorithms Let PR = p1,...,pn be the set of n processors. p1 is a distinguished processor called transmitter. Let STp be a set of states for pePR, V be the set of values the transmitter may possibly hold, and let MSG denote a set of messages the processors may send to each other. We think of MSG as the powerset of some set of atomic messages. An agreement algorithm for PR is defined by a set of functions

(Image Omitted)

The algorithm consists of running synchronous phases of message sending, message receiving and internal computation (state transition). Such a sequence of phases is called a history. According to the message-sending function Mp which depends on its current state processor, p is supposed to send messages to other processors at the beginning of a phase. At the end of a phase, p will receive the messages sent to it by other processors during that phase, and, depending on this information and its current state, change into a new state as specified by the state transition function Fp . This state will also be the state of p at the beginning of the next phase. For receiving as for sending messages, the i-th element of a sequence from MSGn when applied to Fp, respectively produced by Mp, denotes the information transfer between p and processor pi . (We make the technical assumption that each processor also sends a message to itself.) For the transmitter STp includes states sv for veV...