A Recursive Early-Stopping Phase King Protocol

Early-stopping consensus protocols guarantee termination within a number of rounds that depends only on the actual number ???? of faulty nodes in a run, not the maximum number of faults that can be tolerated. We consider early-stopping deterministic synchro- nous consensus with Byzantine faults in a fully connected message passing system of ???? nodes. Many such protocols are known, but so far none combine early-stopping in ????(???? + 1) rounds with optimal resilience and a bit complexity of ????(????2(???? + 1)). We provide two solutions to the above problem. The first is a low- hanging fruit that almost matches the above requirements, but has worst-case message and bit complexities of Θ(????2 log(???? + 2)). The second reduces the bit complexity further to ????(????2) at the expense of increasing the constant factor in the running time bound. It does so by calling itself recursively at most twice on Θ(????)-sized subsets. This presents a substantial technical hurdle, since it is not known when the recursive call will terminate, and relying on a worst-case bound would lose the property of stopping early. We overcome this obstacle by introducing a (re-)synchronization barrier in the calling routine that forces all correct nodes to proceed in its execution within one round of each other, complemented by a simple mechanism to simulate synchronous execution in this almost synchronized setting. The result is the first protocol that is simultenously optimally resilient, asymptotically optimally early- stopping, and asymptotically bit- and message-optimal.