Leaderless Byzantine Paxos

Distributed Computing: 25th International Symposium: DISC 2011, David Peleg, editor. | , pp. 141-142

This two-page note describes a simple idea that I had in 2005. I have found the Castro-Liskov algorithm and other “Byzantine Paxos” algorithms unsatisfactory because they use a leader and, for progress, they require detecting and removing a malicious leader. My idea was to eliminate the leader by using a synchronous Byzantine agreement algorithm to implement a virtual leader. The note is too short to discuss the practical details, but they seem to be straightforward.