A 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 DM), is based on the same idea as that inspiring the algorithm DM described in [LSP], but it can exhibit early stopping whenever it is possible. The particular feature of this algorithm is that its performance improves as the actual number of faulty processes decreases and theiir behaviour becomes less malicious. It is shown that POM rapidly converges to the 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-1) message exchanges per process are necessary to reach the agreement. The achieved early stopping does not violate the f+2 lower bound of [DRSb]. A comparison with known algorithms based on similar hypotheses is made.