Browse Prior Art Database

Eventual Byzantine Agreement to Handle a Number of Faults That Is Small With Respect to the Number of Processors

IP.com Disclosure Number: IPCOM000043286D
Original Publication Date: 1984-Aug-01
Included in the Prior Art Database: 2005-Feb-04
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Dolev, D: AUTHOR [+3]

Abstract

In the prior art there is described a method for achieving a Byzantine Agreement, Unanimity and Interactive Consistency. 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 set 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 40% of the total text.

Page 1 of 2

Eventual Byzantine Agreement to Handle a Number of Faults That Is Small With Respect to the Number of Processors

In the prior art there is described a method for achieving a Byzantine Agreement, Unanimity and Interactive Consistency. 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 set by the originator or on the conclusion that the originator is faulty. The current method shows that Byzantine Agreement can be achieved for n processors handling at most t faults within min (t+1, F+2) phases for f actual faults using at most 0(n(f+1)T2+ft6) messages, provided that n>2t2+3t+4 and that t>1. The improvement lies in eliminating the authentication requirement and in the number of phases in case there are faults: if there are actually f>0 faults, the number of phases for 0080 is T+2. Let V denote a set of possible values. For purposes of the current algorithm, messages will have two types: (1) "v" where v is in V, and (2) "p sent v at K" where p is a processor name, v is in V, and k is a phase number. Let MSG denote a set of possible messages including sequences of messages of both types. A history is a finite sequence of phases, each phase being a directed graph with nodes corresponding to a set of processors and edges labeled from MSG. For notational convenience, each history is assumed to begin with a special phase called phase 0 with exactly one labeled inedge to each processor. The remaining phases are numbered with the consecutive positive integers N. At phase k, each processor is said to send the messages on its outedges and to receive the messages on its inedges. At phase 0, each processor is assumed to receive its name, the names of all other processors participating, and the identity of a special processor called the sender . In addition the sender is assumed to receive its value at phase 0. An individual subhistory for processor p is the result of removing from a history all edges except the inedges to p. We denote the individual subhistory for p resulting from history H by pH. Let PR denote a set of n processors, and let ISH denote the set of individual subhistories on PR. We will use Ik (alt.Hk) to denote the initial subsequence or prefix of individual subhistory I (alt. history H) ending with phase k. Our agreement algorithm will be a triple of functions <M,F,T> with M : ISH T MSG, F : ISH T 2V, and T : ISH T N, such that for j<k, TpHj> and if TpHk< then FpHk =1 and M(pHj) equals the empty sequence of messages for j> Function M is called a message generation function, function F is called a decision function, and function T is called a stoppin...