Gracefully degradable algorithm for byzantine agreement

An algorithm for Byzantine agreement without authentication in a set of n processes is presented, where n> 3t and t is the maximum allowable number of faulty processes. This algorithm, called POM (Pruned OM), is based on the same idea as that inspiring the algorithm OM described in Lamport et al.(2), but it can exhibit early stopping whenever possible. The particular feature of this algorithm is that its performance improves as the actual number of faulty processes decreases and as their behaviour becomes less malicious. It is shown that POM rapidly converges to agreement if the actual number of faulty processes is less than t/2; if the sender process is not faulty, 3 rounds and 2(n - 2) message exchanges per process are necessary to reach the agreement. The achieved early stopping does not violate the f + 2 lower bound of Dolev et al.(1983)[5]. A comparison with known algorithms based on similar hypotheses is made.