A Leader-free Byzantine Consensus Algorithm

The paper considers the consensus problem in a partially synchronous system with Byzantine faults. All deterministic algorithms that solve consensus in this context are leader-based. However, in the context of Byzantine faults, leader-based algorithms are more vulnerable to performance degradation than leader-free (non-leader-based) algorithms. This is because a Byzantine leader can cause the system to make progress at an extremely slow rate. This raises the following fundamental question: is it possible to design a deterministic Byzantine consensus algorithm for a partially synchronous system that is not leader-based? The paper gives a positive answer to this question, and presents an algorithm that is resilient-optimal and signature-free.