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
Loading...
Thumbnail Image
Name

LeaderlessConsensusTechRep.pdf

Type

N/a

Access type

openaccess

License Condition

CC BY

Size

506.95 KB

Format

Adobe PDF

Checksum (MD5)

0fb4dcab5030b53f3c23d87835c4624e

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