A Recursive Early-Stopping Phase King Protocol

Abstract

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)). We provide two solutions to the above problem. The first is fairly simple and almost matches the above goals, but has worst-case message and bit complexities of Θ(n2 log (f+2)). The second reduces the bit complexity further to O(n2) by calling itself recursively at most twice on Θ(n)-sized subsets. The result is the first protocol that is simultenously optimally resilient, asymptotically optimally early-stopping, and asymptotically bit- and message-optimal.