2026-07-23T19:57:51Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22551 2025-10-02T11:05:59Z ddc:004 open_access

Quit-Resistant Reliable Broadcast and Efficient Terminating Gather Mizrahi Erbes, Mose Wattenhofer, Roger Asynchronous networks byzantine fault tolerance protocol termination reliable broadcast all-to-all broadcast gather Termination is a central property in distributed computing. A party terminates a protocol once it stops accepting and sending messages. We discover that byzantine reliable broadcast is sometimes used in a manner which leads to non-terminating protocols. We consider an asynchronous network of n parties up to t of which are byzantine, and show that if each party is to broadcast its value and terminate upon obtaining n - t values, then composing n parallel reliable broadcast instances leads to non-termination. The issue is that a party must quit t broadcast instances early in order to terminate, a behaviour not supported by ordinary reliable broadcast. So, we modify Bracha’s protocol into a quit-resistant reliable broadcast (QBRB) protocol which lets the parties quit early. This protocol retains its termination guarantees as long as no party quits before some party terminates. Then, we turn our attention to Gather, an all-to-all broadcast primitive which guarantees that the parties obtain n - t common values. Existing error-free deterministic Gather protocols either run forever, or fail to terminate since the parties quit reliable broadcast instances. We design an error-free, deterministic, terminating (and binding) Gather protocol for 𝓁-bit inputs with the communication complexity 𝒪(𝓁 n² + n³log n). This matches the state-of-the-art for non-terminating Gather. Finally, inspired by our QBRB protocol, we design a reliable broadcast protocol which retains its termination guarantees no matter when any party quits. To achieve this, we give each party the option to output ⊥ if more than q parties quit before some party terminates. The protocol requires 4t + q < n, which is optimal, and it lets parties quit after they have suffered transient crash failures so that they can help the remaining parties terminate. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mose Mizrahi Erbes and Roger Wattenhofer 2025 Is Part Of LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2024.15 urn:nbn:de:0030-drops-225519 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.15 eng https://creativecommons.org/licenses/by/4.0/legalcode