An Optimal Byzantine Agreement Algorithm with Arbitrary Node and Link Failures

M. Biely (Switzerland)


Distributed Algorithms, Byzantine Agreement, link failures


In a series of recent papers(1), we showed how to avoid the impossibility result of deterministic consensus in presence of link failures [Gray,1978] for well-known Oral and Written Messages Byzantine agreement algorithms. This is done by employing the perception-based fault model [Schmid,2001]. We will, however, use a simplified version of that model in this paper. The Byzantine Agreement protocol presented in this paper is a polynomial time protocol with optimal resilience in respect to the simplified perception-based fault model. The most important feature of the Byzantine Agreement algorithm is, that it uses some of the processes to tolerate process failures as well as to overcome link failures, as we need only n > 2f(a) + max{f(a),f(l,r,a)+f(l,r)+f(l,s,a)+f(l,s)} where f(l,r), f(l,r,a,), f(l,s), f(l,s,a) are ܴ measures of the link failures allowed.

Important Links:

Go Back