(2021) Leaderless Consensus

2022-08-27 ยท 1 min read

    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