A Recursive Early-Stopping Phase King Protocol
Christoph Lenzen, Sahar Sheikholeslami · 2022
Early-stopping consensus protocols guarantee termination within a number of rounds that depends only on the actual number f of faulty nodes in a run, not the maximum number of faults that can be tolerated. We consider early-stopping deterministic synchronous consensus with Byzantine faults in a fully connected message passing system of n nodes. Many such protocols are known, but so far none combine early-stopping in O(f+1) rounds with optimal resilience and a bit complexity of o(n2(f+1)).