arvind@utcsri.UUCP (Arvind Gupta) (03/13/87)
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