Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Reports, Documentation, and Standards
  4. Leaderless Consensus
 
report

Leaderless Consensus

Antoniadis, Karolos  
•
Desjardins, Antoine
•
Gramoli, Vincent  
Show more
January 8, 2021

Classical synchronous consensus algorithms are leaderless: processes exchange their proposals, pick the max 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).

  • Files
  • Details
  • Metrics
Type
report
Author(s)
Antoniadis, Karolos  
Desjardins, Antoine
Gramoli, Vincent  
Guerraoui, Rachid  
Zablotchi, Mihail Igor  
Date Issued

2021-01-08

Total of pages

33

Subjects

Leaderless termination

•

Byzantine

•

synchronous-k

•

synchronizer

•

fast-path

Editorial or Peer reviewed

NON-REVIEWED

Written at

EPFL

EPFL units
DCL  
Available on Infoscience
January 8, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/174524
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés