Evaluating the efficiency of Byzantine Agreement algorithms

The Byzantine Agreement problem arises in systems consisting of n independent cooperating processes, which have to agree on some data upon which their computations depend. These processes communicate through message passing only. In such systems, a maximum of t processes can fall exhibiting unpredictable behaviour. The processes have independent failure modes and are unaware of which other processes are faulty. In this paper, we will compare several algorithms far the Byzantine Agreement, which have been proposed in the literature. The comparisons are quantitative and try to assess the feasibility of these algorithms concerning the following complexity parameters: minimum number of processes and number of phases required to reach the agreement, and number of messages exchanged. These parameters are meaningful to evaluate the redundancy needed in a system that relies on Byzantine Agreement algorithms, the time duration for execution of algorithms and the overhead induced by the heavy message traffic required to reach agreement. The algorithrns considered in this paper are based on the same system model and all exhibit early stopping characteristics. Their performance is compared with the performance obtained by the original OM algorithm introduced by Lamport, Shostak and Pease. The drastic reduction of the number of messages exchanged between processes brings one to the conclusion that Byzantine Agreement algorithms are feasible in a real-world system if combined with frequent fault removal.