cispa_all_3649.pdf (578.44 kB)

A Recursive Early-Stopping Phase King Protocol

Download (578.44 kB)
conference contribution
posted on 2023-11-29, 18:20 authored by Christoph LenzenChristoph Lenzen, Sahar Sheikholeslami
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.


Preferred Citation

Christoph Lenzen and Sahar Sheikholeslami. A Recursive Early-Stopping Phase King Protocol. In: ACM Symposium on Principles of Distributed Computing (PODC). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM Symposium on Principles of Distributed Computing (PODC)

Legacy Posted Date


Open Access Type

  • Unknown


@inproceedings{cispa_all_3649, title = "A Recursive Early-Stopping Phase King Protocol", author = "Lenzen, Christoph and Sheikholeslami, Sahar", booktitle="{ACM Symposium on Principles of Distributed Computing (PODC)}", year="2022", }

Usage metrics


    No categories selected


    Ref. manager