Browse Prior Art Database

Faster Byzantine Agreement

IP.com Disclosure Number: IPCOM000106121D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 35K

Publishing Venue

IBM

Related People

Cristian, F: AUTHOR [+3]

Abstract

A method is described for ensuring a fast agreement among n completely connected processors, in the presence of arbitrary failures in at most f of the processors, in spite of clocks that are only synchronized to within a given bound e.

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

Faster Byzantine Agreement

      A method is described for ensuring a fast agreement among n
completely connected processors, in the presence of arbitrary
failures in at most f of the processors, in spite of clocks that are
only synchronized to within a given bound e.

      Given a bound d on message transmission and processing time as
measured on the clock of any processor in the system, the invention
requires time k*e+O(d) in the worst case, where 1 < k < f + 1 when 0
< f < n-2.

      The essence of the invention is the addition of new timeliness
tests to a variant of the Sriknath and Toueg protocol for Byzantine
Agreement [*].  These timeliness tests require any transmission to be
verifiably echoed by at least the minimum number of processors that
can be assumed correct.

      The method is practiced as follows.  The parties exchange
authenticated messages.  Each send operation timestamps the message,
authenticates it, and multicasts it to all parties.  Each receive
operation verifies all signatures, and checks that each message
timestamped t is received after t-e and before t+e+d.  It also checks
that any embedded timestamps and signatures conform to the above test
and the message structure.  When a processor adopts a new time, it
adds another layer of signatures to it.

Reference
[*]  T. K. Srikanth and S. Toueg, "Optimal Clock Synchronization,"
   JACM, Vol. 34, No.  3,  625-645 (July 1987).
   ______________________