(2021) Leaderless Consensus

2022-08-27 · 1 min read

• Authors: EPFL: Karolos Antoniadis, Antoine Desjardins, Vincent Gramoli, Rachid Guerraoui, Igor Zablotchi
• Paper: https://infoscience.epfl.ch/record/282657/files/LeaderlessConsensusTechRep.pdf
• Video: https://www.youtube.com/watch?v=gPrdhebjTM0

properties #

• leaderless
• alg. v3 provides BFT authenticated and unauthenticated versions
• time: O(n), optimal
• resilience: k < 3f + 1
• bits exchanged: O(n^4), same as PBFT
• messages exchanged: O(n^4), not optimal
• optimistic termination: 2 rounds, optimal

intuition #

Each "round", a process broadcasts his max x and observes everyone else's max x. If there are disagreements, a process "adopts" a new x = max(x_i) for x_i just observed. Otherwise, if everyone agrees, then commit the x.

inputs: [x_1, .., x_n]

while true:
	if contention:
		adopt max(x_1, .., x_n))
	else if x_1 == .. == x_n:
		commit x