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

Probabilistic Agreement in the Presence of Omission Faults

IP.com Disclosure Number: IPCOM000122339D
Original Publication Date: 1991-Nov-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 1 page(s) / 34K

Publishing Venue

IBM

Related People

Dolev, D: AUTHOR [+2]

Abstract

Described is a method for reaching an agreement in the presence of general omission faults. The method produces an algorithm that stops within a constant expected number of rounds, independent of the behavior of the faulty processors.

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

Probabilistic Agreement in the Presence of Omission Faults

      Described is a method for reaching an agreement in the presence
of general omission faults.  The method produces an algorithm that
stops within a constant expected number of rounds, independent of the
behavior of the faulty processors.

      At the beginning, the sender sends its value and every
processor adopts that value, if it is received.  At every other
phase, every processor sends its current adopted value.  A different
value is adopted if it is received from enough processors.  If the
value adopted and sent equals the random coin, a processor decides on
it.  If not enough processors support a value, the coin becomes the
new adopted value.

      In the above method, there exists a probability of 1/2 of
stopping after every phase; thus, a small probability of running too
many phases.  The probability is independent of the actual faulty
behavior (as long as it remains an omission fault).

      The above method handles binary values and describes a method
to generalize it to arbitrary values.

      Disclosed anonymously.