A Recursive Early-Stopping Phase King Protocol

We provide two solutions to the above problem. The first is a low-hanging fruit that almost matches the above requirements but has a 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 their 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 simultaneously optimally resilient, asymptotically optimally early-stopping, and asymptotically bit- and message-optimal.