Browse Prior Art Database

Processor and Bit Optimal Early Stopping Consensus Protocol

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

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). (Image Omitted)

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

Processor and 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).

                            (Image Omitted)

      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 that solves 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 novelty of the presented protocol is that it uses
messages of constant size.  No previously existing early-stopping
consensus protocol that is processor optimal has used messages of
constant size.

      The formal specification of a protocol for Distributed
Consensus is as fo...