optimal algorithms for byzantine agreement
We exhibit randomized Byzantine agreement (BA) algorithms achieving optimal running time and fault tolerance against all types of adversaries ever considered in the literature. Our BA algorithms do not require trusted parties, preprocessing, or non-constructive arguments. Given private communication lines, we show that n processors can reach BA in expected constant time in a syncronous network if any < n /3 faults occur in an asynchronous network if any < n /4 faults occur For both synchronous and asynchronous networks whose lines do not guarantee private communication, we may use cryptography to obtain algorithms optimal both in fault tolerance and running time against computationally bounded adversaries. (Thus, in this setting, we tolerate up to n /3 faults even in an asynchronous network.)
optimality algorithm byzantine agreement randomization timing fault fault tolerance types trust argument communication processor network asynchronicity synchronization use cryptography