Antoniadis, KarolosDesjardins, AntoineGramoli, VincentGuerraoui, RachidZablotchi, Igor2022-01-012022-01-012022-01-012021-01-0110.1109/ICDCS51616.2021.00045https://infoscience.epfl.ch/handle/20.500.14299/184143WOS:000728379200036Classical synchronous consensus algorithms are leaderless: processes exchange their proposals, retain the maximum value and decide when they see the same choice across a couple of rounds. Indulgent consensus algorithms are more robust in that they only require eventual synchrony, but are however typically leader-based. Intuitively, this is a weakness for a slow leader can delay any decision.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 (with and without authentication).Computer Science, Hardware & ArchitectureComputer Science, Information SystemsComputer Science, Software EngineeringComputer Science, Theory & MethodsComputer Scienceleaderless terminationbyzantinesynchronous-ksynchronizerfast-pathtimetext::conference output::conference proceedings::conference paper