Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site utcsri.UUCP
Path: utzoo!utcsri!arvind
From: arvind@utcsri.UUCP (Arvind Gupta)
Newsgroups: ut.theory
Subject: Byzantine News
Message-ID: <4350@utcsri.UUCP>
Date: Thu, 12-Mar-87 17:03:17 EST
Article-I.D.: utcsri.4350
Posted: Thu Mar 12 17:03:17 1987
Date-Received: Fri, 13-Mar-87 04:20:09 EST
Distribution: ut
Organization: CSRI, University of Toronto
Lines: 22

From: Silvio Micali <silvio@theory.lcs.mit.edu>
Subject: Byzantine News

Interested in Byzantine Agreement?
     
There exists a constructive, cryptographic algorithm for reaching Byzantine
Agreement in constant expected time.
     
The algorithm requires only polynomial local computation
from each processor.
     
The algorithm does not require any pre-processing.
(At the start, the processors only know everyone's identity.)
     
The algorithm works in the most adversarial cryptographic scenario. (It
tolerates up to n/3 polynomial-time faulty processors, dynamically
chosen, capable of arbitrary
Byzantine behaviour, rushing, eavesdropping, undetected
cooperation, etc.)
     
Paul Feldman and Silvio Micali