Browse Prior Art Database

Method for Achieving Byzantine Agreement With Early Stopping and Without Authentication

IP.com Disclosure Number: IPCOM000045912D
Original Publication Date: 1983-May-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 3 page(s) / 17K

Publishing Venue

IBM

Related People

Dolev, D: AUTHOR [+2]

Abstract

In the prior art, there is described a method for achieving a kind of agreement called Byzantine Agreement. The general context for Byzantine Agreement is a network of n processors that have a means for conducting several synchronized phases of information exchange, after which they must all agree on some set of information (that we will treat, for example as a single value from a set V of values). Byzantine Agreement results when, in the presence of undetected faulty processors, all correct processors are able to agree either on the value sent by the originator or on the conclusion that the originator is faulty.

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

Page 1 of 3

Method for Achieving Byzantine Agreement With Early Stopping and Without Authentication

In the prior art, there is described a method for achieving a kind of agreement called Byzantine Agreement. The general context for Byzantine Agreement is a network of n processors that have a means for conducting several synchronized phases of information exchange, after which they must all agree on some set of information (that we will treat, for example as a single value from a set V of values). Byzantine Agreement results when, in the presence of undetected faulty processors, all correct processors are able to agree either on the value sent by the originator or on the conclusion that the originator is faulty.

The method of this invention permits Byzantine Agreement without using authentication; however, it allows us to stop early under many usual circumstances, as opposed to the prior art which required 4t+5 phases to handle the possibility of t faults even when fewer than t faults actually occurred. The instant invention shows that Byzantine Agreement can be achieved for n processors with at most t faults within 2t+3 phases using at most O(nt/4/) messages, provided that nJ3t. When no faults are present, 5 phases will suffice. In general, when the method is set to handle t faults and only f actual faults occur, then each processor will complete processing within 2f+5 phases.

Prior-art techniques use the worst-case number of phases for all cases. In contrast, this method allows early stopping in all but the worst cases: fJt-l. Thus, the method can be both efficient in terms of early stopping time when only a few faults occur and reliable in the sense of handling many potential faults.

First, the specific messages to be used are described. This is done in the context of describing units of information to be recorded by a correctly operating processor, some of which will be transmitted as messages. These units will be called ASSERTIONS.THERE ARE THREE types of assertions:

type a - of the form a(v), for v in V, interpreted as "sender s sent

VALUE V AT PHASE 1;" type b - of the form b(v,y,k), for v in V, y a processor, k a phase number, interpreted as "y sent a(v) at phase k;" and type c - of the form c(v,x,y,k), for v in V, x and y processors, k a phase number, interpreted as "x sent b(v,y,k)."

The original messages sent by the sender will be considered to be a special case of type a. All other messages specified by our algorithm will be either type a or type b assertions.

Two threshold numbers, LOW and HIGH, with the following properties are needed: LOW J t,

HIGH J LOW + t - l, and

n J HIGH + t - l.

1

Page 2 of 3

Thus the number of correctly operating processors will be greater than or equal to high, while the number of faulty processors will be less than low. Note that these requirements imply that n J 3t. One example of numbers satisfying the requirements is LOW = t+l and HIGH = 2t+l.

Information kept by a processor will be recorded in two c...