Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Improved Bit Optimal Early Stopping Consensus Protocol

IP.com Disclosure Number: IPCOM000109979D
Original Publication Date: 1992-Oct-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 2 page(s) / 88K

Publishing Venue

IBM

Related People

Berman, P: AUTHOR [+3]

Abstract

There are many situations in the management of distributed systems with one common characteristic: a collection of processors must coordinate a decision. This problem becomes non-trivial when some of the processors are faulty and cannot be relied upon to faithfully obey a protocol. It is reasonable to at least demand that, regardless of the behavior of the faulty processors, correct processors can reach an agreement consistent with the initial value of a correct processor. The problem of reaching consensus in the presence of faulty processors is called the Distributed Consensus Problem (1).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Improved Bit Optimal Early Stopping Consensus Protocol

       There are many situations in the management of
distributed systems with one common characteristic: a collection of
processors must coordinate a decision.  This problem becomes
non-trivial when some of the processors are faulty and cannot be
relied upon to faithfully obey a protocol.  It is reasonable to at
least demand that, regardless of the behavior of the faulty
processors, correct processors can reach an agreement consistent with
the initial value of a correct processor.  The problem of reaching
consensus in the presence of faulty processors is called the
Distributed Consensus Problem (1).

      In a Distributed Consensus protocol, n processors, of which at
most t may be faulty, begin with initial binary values; after
exchanging messages all correct processors must agree on one of them.
We present a protocol for the Distributed Consensus problem that
tolerates arbitrary processor faults and is early-stopping.
Early-stopping means that the time that the protocol requires is
proportional to the number of failures that actually occur during its
execution.  Note that faulty processors may act in a completely
unrestricted "Byzantine" manner (versus simply crashing), even to the
point of appearing to collude with one another in order to prevent
consensus.

      The formal specification of a protocol for Distributed
Consensus is as follows.  We are given a set of n processors numbered
1 through n.  Some a priori unknown subset of processors may become
faulty and exhibit arbitrary (Byzantine) behavior. However, it is
assumed that no more than t processors may become faulty.  Every
processor is given an initial value, 0 or 1.  After the execution of
the protocol, the final values of the correct (i.e., the non-faulty)
processors have to satisfy the following two conditions, regardless
of the behavior of the faulty processors:
Agreement:     they are all equal.
Validity:      t...