Browse Prior Art Database

Multi-valued Protocols Resilient to a Wide Class of Failures

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

Publishing Venue

IBM

Related People

Garay, JA: AUTHOR [+2]

Abstract

A common technique for constructing computer systems that are able to tolerate faults is to replicate the computation on several processors. In order to apply this technique, two tools are necessary: a fault-tolerant Broadcast method for broadcasting data to all processors (such data may originate either from one of the processors or as the output of a sensor) and a fault-tolerant Consensus method allowing the processors to reach a consensus on the computation's result, so that they may take a common action (e.g., activating an actuator). These two methods have been studied in the abstract and are known respectively as the Byzantine Generals Problem and the Consensus Problem.

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

Multi-valued Protocols Resilient to a Wide Class of Failures

       A common technique for constructing computer systems that
are able to tolerate faults is to replicate the computation on
several processors.  In order to apply this technique, two tools are
necessary: a fault-tolerant Broadcast method for broadcasting data to
all processors (such data may originate either from one of the
processors or as the output of a sensor) and a fault-tolerant
Consensus method allowing the processors to reach a consensus on the
computation's result, so that they may take a common action (e.g.,
activating an actuator).  These two methods have been studied in the
abstract and are known respectively  as the Byzantine Generals
Problem and the Consensus Problem.

      Fault tolerant methods for Broadcast and Consensus, as well as
a means for combining the methods to implement a fault-tolerant
computing system, have been developed for a variety of failure
models.  The salient features of the model used in this article is
the existence of n processors, of which up to t may fail, either by
crashing or acting arbitrarily, subject to no more than b processors
acting arbitrarily.  Previously disclosed methods for this model were
efficient for Broadcasting or reaching Consensus when the values were
chosen  from an alphabet of size 2 (e.g., 0 or 1).  In this article,
it is shown how these problems may be efficiently solved for
alphabets of arbitrary size.

      The method disclosed here involves the processors exchanging
messages from the alphabet of size N for only 2 rounds.  These 2
rounds serve to reduce the number of possible values from N to 2.
Once this is done, the previously disclosed methods for Broadcast and
Consensus on alphabet size 2 may be used.

      The only alternative to this method for alphabets of size N is
to solve the Broadcast or Consensus problems on a bit at a time
basis.  For example, to broadcast the value 0 < V < N-1, the
Broadcast method could be invoked for alphabet size 2 on each bit of
the binary representation of V.  This blows up the number of messages
that must be sen...