Leaderless consensus

Classic synchronous consensus algorithms are leaderless in that processes exchange proposals, choose the maximum value and decide when they see the same choice across a couple of rounds. Indulgent consensus algorithms are typically leader-based. Although they tolerate unexpected delays and find practical applications in blockchains running over an open network like the Internet, their performance is highly dependent on the activity of a single participant. This paper asks whether, under eventual synchrony, it is possible to deterministically solve consensus without a leader. The fact that the weakest failure detector to solve consensus is one that also eventually elects a leader seems to indicate that the answer to the question is negative. We prove in this paper that the answer is actually positive.We first give a precise definition of the very notion of a leaderless algorithm. Then we present three indulgent leaderless consensus algorithms, each we believe interesting in its own right: (i) for shared memory, (ii) for message passing with omission failures and (iii) for message passing with Byzantine failures.Finally, we implement a Byzantine fault tolerant (BFT) state machine replication (SMR), that is leaderless. Our empirical results demonstrate that it is faster and more robust than HotStuff, the recent BFT SMR algorithm used in the Facebook Libra blockchain when deployed in a wide area network.(c) 2023 Elsevier Inc. All rights reserved.