Browse Prior Art Database

Message for Agreement Among Loosely Coupled Processors Without Authentication

IP.com Disclosure Number: IPCOM000051184D
Original Publication Date: 1982-Aug-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Dolev, D: AUTHOR [+2]

Abstract

This invention relates to a method for obtaining message-oriented synchronism, termed 'Byzantine Agreement', among loosely coupled processors absent an authentication procedure' Authentication was used to verify that values were actually sent by the transmitter, and to control the flow of messages. The general context for the Byzantine Agreement is a network of 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). Byzantine Agreement results when, in the presence of undetected faulty processors, all correct processors are able to agree either on the value sent by its 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 55% of the total text.

Page 1 of 2

Message for Agreement Among Loosely Coupled Processors Without Authentication

This invention relates to a method for obtaining message-oriented synchronism, termed 'Byzantine Agreement', among loosely coupled processors absent an authentication procedure' Authentication was used to verify that values were actually sent by the transmitter, and to control the flow of messages. The general context for the Byzantine Agreement is a network of 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). Byzantine Agreement results when, in the presence of undetected faulty processors, all correct processors are able to agree either on the value sent by its originator or on the conclusion that the originator is faulty.

The method of this invention enables us to reach the Byzantine Agreement without using authentication for n processors with at most t faults within 4t+4 phases using at most O(n**5), provided that n>3t.

In order to describe the correctness rule and decision function for the method, there must first be described the messages used. This is executed 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 q, 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, are needed with the following properties: LOW > t,

HIGH > LOW + t - 1, and

n > HIGH + t - 1.

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 is less than 3t. One example of numbers satisfying the requirements is LOW equals t+1 and HIGH equals 2t 1.

Information kept by a processor will be recorded in two categories: known and committed. If an assertion is recorded as committed, it will also be recorded

1

Page 2 of 2

as known. Type c assertions will not be messages and will only be recorded as known....