Quit-Resistant Reliable Broadcast and Efficient Terminating Gather

Byzantine reliable broadcast (BRB) is a fundamental asynchronous communication primitive. Traditionally, a BRB protocol is run by $n$ parties $P_1,P_2,\mathrm{\dots },P_n$, where up to $t$ of the parties may deviate arbitrarily from the protocol while the rest remain honest. Given a fixed sender party $P^{\ast }$ who eventually acquires an input $v^{\ast }$, a BRB protocol ensures the following:

• $\mathrm{■}$

  Validity: If $P^{\ast }$ is honest, and an honest $P_i$ outputs $y_i$, then $P^{\ast }$ has acquired $v^{\ast }=y_i$.

• $\mathrm{■}$

  Consistency: If honest parties $P_i$ and $P_j$ output $y_i$ and $y_j$, then $y_i=y_j$.

• $\mathrm{■}$

  Local Termination: If $P^{\ast }$ is honest, then some honest party terminates.

• $\mathrm{■}$

  Global Termination: If some honest party terminates, then all honest parties terminate.

Notice that we split the output correctness properties from the termination properties. Since we focus on termination in this work, the breakdown above will be useful.

When we say that a protocol terminates, what do we mean? In their seminal work on asynchronous byzantine agreement [12], Canetti and Rabin say that a protocol terminates if all the honest parties “complete the protocol (i.e. terminate locally).” The way we understand this is that they do not let parties keep sending messages after they locally terminate, and thus define termination as we will. In [4], Abraham et al. define termination as Canetti and Rabin do, but they also separately define “termination of output” to be the property that every honest party eventually outputs.

Following the definitions in [9], we distinguish between liveness and termination. A live protocol guarantees that if the honest parties all eventually acquire inputs and run forever, then they all output. Liveness is the property called “termination of output” in [4]. Termination is stronger. A terminating protocol guarantees that if the honest parties all eventually acquire inputs and run until they terminate, then they all terminate. A party can terminate once it has output, and after terminating it can no longer accept or send messages.

Termination as opposed to liveness is useful in that it allows the parties to go offline and forget about a protocol once they terminate. When the parties run an asynchronous protocol that is live but not terminating, they must forever remain alert for further messages, even if the network happens to be fast and they decide on their outputs almost instantly. In contrast, if the parties run a terminating asynchronous protocol, then they can go offline once they terminate. Even in networks where the parties are always active, termination lets a party free the resources it has allocated for a protocol, while liveness does not.

It is common in distributed computing to compose $n$ (or more) instances of BRB to implement all-to-all broadcast. In all-to-all broadcast, each party $P_i$ has an input $v_i$ which it broadcasts to the other parties, and each party $P_i$ outputs a set $X_i$ of value-sender pairs $(m,P)$ with at most one value per sender. Typically, one requires at least the following:

• $\mathrm{■}$

  For some constant $z\le n-t$, the honest output sets contain at least $z$ value-sender pairs.

• $\mathrm{■}$

  If there exists some $(m_j,P_j)\in X_i$ for any honest $P_i$ and $P_j$, then $m_j=v_j$.

• $\mathrm{■}$

  If there exist some $(m,P)\in X_i$ and $(m^{\prime },P)\in X_j$ for any honest $P_i$ and $P_j$, then $m=m^{\prime }$.

One simple all-to-all broadcast protocol which we name ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ achieves precisely the guarantees above, with $z$ maximally set to $n-t$. It consists of $n$ parallel BRB instances, one for each party to broadcast its input. The idea is that since there exist $n-t$ honest parties, every honest party eventually terminates $n-t$ instances of BRB and thus terminates ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$. In the wild, ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ and its variants are commonly used in agreement protocols. For instance, Canetti and Rabin [12] use ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ (with $z=2t+1$) for secret sharing/reconstruction in their seminal work on byzantine agreement [12], and Abraham, Amit and Dolev use a strengthened variant of ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ as a core primitive in their seminal work on approximate agreement [2].

The problem the literature sometimes overlooks is that ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ achieves liveness, but not termination. Observe that if a party $P_i$ terminates ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ upon terminating $n-t$ instances of BRB and obtaining $|X_i|=n-t$, then it stops running the $t$ instances of BRB it has not yet terminated. However, unless the BRB protocol lets honest parties quit before they terminate, honest parties quitting BRB instances early leads to ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ losing its liveness. We show this in Section 3 with an attack when ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ uses Bracha’s reliable broadcast protocol ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ [10].

One consequence of this issue is that the byzantine agreement protocol in [12] by Canetti and Rabin, whose termination mechanism is an ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ variant which a party terminates after terminating $t+1$ broadcasts with identical outputs, does not achieve termination. The protocol does achieve liveness, but it would also do so if one were to remove its termination mechanism entirely. The approximate agreement protocol against corruptions in [2] by Abraham et al. is similarly impacted. Contrary to how their protocol is written, a party can never halt. More recent approximate agreement protocols such as [15, 20, 21, 24, 27] based on the witness technique of [2] are impacted as well.

The question we thus ask is if we can redefine reliable broadcast to ensure the termination of protocols like ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ where a party has to quit reliable broadcast instances to terminate. We answer this affirmatively in Section 4 with quit-resistant reliable broadcast (QBRB), our new BRB variant where the parties can quit (and inform the other parties of their quitting) before they terminate, with precisely the guarantees to prevent attacks of the sort against ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$. A QBRB protocol retains validity and consistency no matter when any honest party quits, and retains global termination as long as no honest party quits before some honest party terminates. It turns out that one can easily modify ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ into a QBRB protocol resilient against corruptions. This is fortunate, as the aforementioned protocols which do not terminate due to BRB not supporting quits become terminating if one replaces the standard BRB invocations in them with QBRB invocations.

Note that a party informing the others when it quits (or wishes to quit) a protocol and this playing a role in termination is an idea that has appeared in the literature before. In [5], the authors design a protocol for byzantine agreement in partial synchrony where upon running a view (i.e. a tagged protocol instance) for too long, a party sends everyone an abort message, and these abort messages play a role in the parties switching to the next view.

We would also be remiss not to mention some of the techniques the literature uses to terminate live agreement protocols. One can upgrade a live byzantine agreement protocol into a terminating one with reliable consensus [13], a constant-round termination procedure based on Bracha’s protocol with $𝒪(n^2)$ messages carrying protocol outputs. More generally, one can upgrade a live agreement protocol where the parties obtain at most $\omega$ distinct outputs (e.g. for approximate agreement in a graph [24]) into a terminating one with the constant-round termination procedure in [22] that builds on reliable consensus, if .

However, for approximate agreement in ${ℝ}^d$, we do not know of any prior termination procedure. So, we offer two approaches to terminate approximate agreement in ${ℝ}^d$. One of them is QBRB, our general solution which by itself suffices to upgrade the protocols in [21, 27] into terminating ones. Our second solution that allows the efficient bundling of many approximate agreement instances (as in [18]) is a terminating Gather protocol. Gather is an ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ variant which requires $|{\bigcap }_{P_i\text{ is honest}}{X}_i|\ge n-t$. It is especially useful for approximate agreement¹¹1For approximate agreement, the typical requirement is that $|X_i\cap X_j|\ge n-t$ for all honest $P_i$ and $P_j$, which is implied by the stronger $|{\bigcap }_{P_i\text{ is honest}}{X}_i|\ge n-t$. [2, 15, 19, 20, 21, 24, 27], though its variants (with additional properties such as binding and verifiability, which we will discuss later) have been used for distributed key generation [4], common coin tossing [14, 18] and asynchronous core set agreement [3, 16].

In Section 5, we design ${\mathrm{\Pi }}_{\mathrm{𝖦𝗍𝗁𝗋}}$, an error-free deterministic Gather protocol optimally secure against corruptions, usable as a termination procedure for any approximate agreement protocol based on Gather iterations since it guarantees that if some honest party terminates, then all of them do. As far as we are aware, no other error-free²²2We call a protocol error-free if it achieves the properties required of it in every possible execution. deterministic³³3Gather is weakening of asynchronous core set agreement (ACS) [8], which requires $X_i=X_j$ for any honest $P_i$ and $P_j$. Though there exist terminating ACS protocols [8], ACS implies byzantine agreement, and error-free deterministic asynchronous byzantine agreement is impossible against one crash fault [17]. Gather protocol in the literature achieves termination. The communication complexity of ${\mathrm{\Pi }}_{\mathrm{𝖦𝗍𝗁𝗋}}$ for $\mathrm{\ell }$-bit inputs is $𝒪(\mathrm{\ell }{n}^2+n^3\log n)$ bits. This is the complexity of the most efficient live Gather protocol (${\mathrm{\Pi }}_{\mathrm{𝖦𝗍𝗁𝗋}}^{\mathrm{𝖫𝗂𝗏𝖾}}$) we are aware of [15], when it is instantiated with a state-of-the-art standard BRB protocol with the complexity $𝒪(\mathrm{\ell }n+n^2\log n)$ [6]. Our ${\mathrm{\Pi }}_{\mathrm{𝖦𝗍𝗁𝗋}}$ protocol additionaly lets one extract a core set of $n-t$ parties whose values are obtained by every honest party from the view of any honest party who outputs; hence, it is binding. Binding Gather was developed in [4], and there are cases involving secret shares which require the binding property [18].

In section 6, we return to QBRB, and design a QBRB variant ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ which retains local and global termination even if any honest party quits whenever it wishes. The standard output guarantees of reliable broadcast cannot be achieved with such lax participation, and for this reason we introduce the extra outputs $\perp$ and $\top$. If at most $q$ honest parties quit before some honest party terminates, then ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ is just a QBRB protocol, albeit one with an extra output $\top$ to indicate that the sender quit before it acquired an input. If more than $q$ honest parties quit before some honest party terminates, then we give each party the individual option to output $\perp$. The protocol ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ optimally requires for this.

From a practical view, ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ is of interest in that it lets parties quit after they recover from transient crashes to help the remaining parties terminate. For example, a party can quit when it reconnects after a network disconnection, or when it restarts after a power loss. This ensures that as long as the honest parties that transiently crash (no matter how many) eventually come back online, all parties terminate ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$. We remark that reliable broadcast with recoverable transient crashes has been studied before. In [7], one can find a live BRB protocol against a polynomially bounded adversary for when and at most $f$ honest parties suffer transient crashes for a polynomially bounded number of times.

We consider an asynchronous network of $n$ message-sending parties $𝒫=\{P_1,\mathrm{\dots },P_n\}$ who are connected pairwise via reliable authenticated channels. The party set $𝒫$ is publicly known. The parties do not have access to synchronized clocks.

Our basic adversary, which we name the $t$-adversary, corrupts up to $t$ parties. The corrupt parties are byzantine; they deviate arbitrarily from the protocol. The rest of the parties are honest. The adversary schedules messages as it wishes, and it is only required to eventually deliver all messages from honest senders. The adversary can also adaptively corrupt parties during the execution of a protocol depending on the sent messages and the parties’ internal states, and drop messages from parties by corrupting them. So, we call a party honest if it is never corrupted. Unless stated otherwise, our protocols are designed against the $t$-adversary.

By default, a party must run a protocol until it is instructed to terminate. However, a QBRB protocol lets each party quit whenever it wishes by invoking the procedure $\mathrm{𝖰𝗎𝗂𝗍}()$, in which the party might send some final messages to help the remaining parties terminate. The adversary can influence if and when a party invokes $\mathrm{𝖰𝗎𝗂𝗍}()$. The invocation of $\mathrm{𝖰𝗎𝗂𝗍}()$ is an event which a party handles like any other. A QBRB protocol keeps validity and consistency no matter when any honest party invokes $\mathrm{𝖰𝗎𝗂𝗍}()$, but potentially loses global termination if an honest party invokes $\mathrm{𝖰𝗎𝗂𝗍}()$ before some honest party terminates.

In Section 6, we design the broadcast protocol ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ against an adversary which can cause a single transient crash for any honest party. This adversary can arbitrarily choose when any crash occurs and how long it lasts. At the end of a crash, the recovering party immediately invokes $\mathrm{𝖰𝗎𝗂𝗍}()$, having retained the information that $\mathrm{𝖰𝗎𝗂𝗍}()$ needs (the kinds of messages the party has sent in ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$). We define the $(t,\mathrm{𝖼𝗋𝖺𝗌𝗁})$-adversary to be the $t$-adversary with the power to cause transient crashes as described above. Against the $(t,\mathrm{𝖼𝗋𝖺𝗌𝗁})$-adversary, ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ achieves local and global termination no matter when any honest party quits, though with weaker output guarantees if more than $q$ honest parties quit before some honest termination.

When a party “multicasts” a message $m$, it sends $m$ to all parties. To keep things simple, we assume that the honest parties do not transiently crash while multicasting, though note that we could remove this assumption by requiring any party that crashes while multicasting any $m$ to remember $m$ so that it can multicast $m$ again when it recovers from the crash.

For composability, the parties do not begin protocols “having” inputs. Instead, they “acquire” inputs while they are running. This matters since we consider protocols where some parties might quit before they acquire inputs, or terminate despite never acquiring inputs.

Below, we present the classical BRB protocol ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ [10]. Note that a party $P_i$ only accepts a single ECHO message and a single READY message from any party $P_j$. We do not require a party to multicast $⟨\text{ECHO},v⟩$ upon receiving $t+1$ $⟨\text{READY},v⟩$ messages; this rule is absent in modern renditions of the protocol [1, 11]. The protocol ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ is proven secure in [1, 10, 11].

And now, we present a version of ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ which fails to terminate because it uses ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$.

Let us informally argue that ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ terminates against the $t$-adversary when . Since there exist at least $n-t$ honest parties and since ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ guarantees termination for all honest parties when the sender is honest, eventually, some first honest $P_i$ terminates $n-t$ instances of ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ and thus terminates ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$. Then, since ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ guarantees termination for all honest parties when some honest party terminates, every honest party can eventually terminate ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ by terminating the $n-t$ instances of ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ terminated by $P_i$.

As Theorem 1 below indicates, this argument fails. The intuitive reason why is that an honest party must stop participating in every ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ instance to terminate ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$, which means that the party must prematurely quit $t$ instances of ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ before terminating them. Though some honest party eventually terminates $n-t$ ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ instances, these instances lose global termination if other honest parties quit them before terminating them.

One could thwart the attack with a termination procedure based on reliable consensus [13] by exploiting the fact that if an honest party terminates a ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ instance, then every party learns the instance’s output by receiving $n-2t$ READY messages on the output. However, it is hard to come up with a termination procedure that works with any BRB protocol instead of just ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$, and our view is not that ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ is lacking a termination procedure but that the termination properties of standard BRB are lacking for protocols like ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ where a party must quit remaining BRB instances to terminate. Hence, we define quit-resistant BRB (QBRB). A QBRB protocol lets any party quit by invoking $\mathrm{𝖰𝗎𝗂𝗍}()$. Given a fixed sender party $P^{\ast }$ who might (or might not) eventually acquire an input $v^{\ast }$, a QBRB protocol ensures the following:

• $\mathrm{■}$

  Validity: If $P^{\ast }$ is honest, and an honest $P_i$ outputs $y_i$, then $P^{\ast }$ has acquired $v^{\ast }=y_i$.

• $\mathrm{■}$

  Consistency: If honest parties $P_i$ and $P_j$ output $y_i$ and $y_j$, then $y_i=y_j$.

• $\mathrm{■}$

  Local Termination: If $P^{\ast }$ is honest, and it acquires an input, then either some honest party terminates, or some honest party quits.

• $\mathrm{■}$

  Global Termination: If some honest party terminates before any honest party quits, then every honest party either terminates or quits.

We keep the definitions of validity and consistency from standard BRB. However, while a standard BRB protocol requires the parties to run until instructed to terminate, a QBRB protocol lets each party quit whenever it wishes by invoking $\mathrm{𝖰𝗎𝗂𝗍}()$, and retains a meaningful global termination guarantee if no honest party quits before some honest party terminates.

QBRB is what ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ needs to terminate. If in ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ one replaces ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ with any QBRB protocol, then the QBRB instances terminated by the first honest party who terminates ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ retain global termination, and thus ${\mathrm{\Pi }}_{\mathrm{𝖠𝗅𝗅}}$ terminates.

Below, we modify ${\mathrm{\Pi }}_{\mathrm{𝖡𝗋𝖺𝖼𝗁𝖺}}$ into a QBRB protocol ${\mathrm{\Pi }}_{\mathrm{𝖰𝗎𝗂𝗍}}$, optimally secure when . We do so with the QUIT message which a party multicasts when it invokes $\mathrm{𝖰𝗎𝗂𝗍}()$, making it easier for the remaining parties to terminate. The QUIT messages do not compromise the safety guarantees since $t+1$ READY messages are required to obtain output, and global termination relies on the fact that if the honest parties do not multicast QUIT before some honest party terminates, then the first honest termination occurs after $t+1$ honest parties multicast $⟨\text{READY},v⟩$ for some $v$, which means that every honest party will multicast $⟨\text{READY},v⟩$ or QUIT.

In Gather, each party $P_i$ may eventually acquire an $\mathrm{\ell }$-bit input $v_i$ (where $\mathrm{\ell }$ is publicly known), and each party $P_i$ outputs a set of value-sender pairs $X_i$ (with at most one value per sender). Against the $t$-adversary, a Gather protocol must achieve the following correctness properties:

• $\mathrm{■}$

  Common Core: There exists a common core set $𝒞\subseteq 𝒫$ of size at least $n-t$ such that every honest output set $X_i$ contains some $(m_j,P_j)$ for all $P_j\in 𝒞$.

• $\mathrm{■}$

  Validity: If there exists some $(m_j,P_j)\in X_i$ for any honest $P_i$ and $P_j$, then $m_j=v_j$.

• $\mathrm{■}$

  Consistency: If there exist some $(m,P)\in X_i$ and $(m^{\prime },P)\in X_j$ for any honest $P_i$ and $P_j$, then $m=m^{\prime }$.

If the protocol is binding, then the following stronger version of common core must hold:

• $\mathrm{■}$

  Binding Common Core: At the moment when some honest party outputs for the first time, one can extract a common core set $𝒞$ from the views of the honest parties.

Finally, the protocol should have one of the following termination-related properties:

• $\mathrm{■}$

  Liveness: Suppose the honest parties all eventually acquire inputs. If the honest parties all run the protocol forever, then they all obtain outputs from it.

• $\mathrm{■}$

  Termination: Suppose the honest parties all eventually acquire inputs. If the honest parties all run the protocol until they terminate it, then they all terminate the protocol.

• $\mathrm{■}$

  Strong Termination: If all honest parties eventually acquire inputs, then some honest party terminates; and if some honest party terminates, all honest parties terminate.

Strong termination is typically the termination property a termination procedure (e.g. reliable consensus [13]) achieves. To see why it matters, let ${\mathrm{\Pi }}_L$ and ${\mathrm{\Pi }}_T$ be Gather protocols, the former with liveness only. Let the parties run ${\mathrm{\Pi }}_L$ on their inputs, transform their ${\mathrm{\Pi }}_L$ outputs into ${\mathrm{\Pi }}_T$ inputs, obtain final outputs from ${\mathrm{\Pi }}_T$, and terminate when they output. When a party terminates the composed protocol, it necessarily stops running ${\mathrm{\Pi }}_L$. Hence, the remaining parties might not output from ${\mathrm{\Pi }}_L$, and thus not acquire ${\mathrm{\Pi }}_T$ inputs. Now, if ${\mathrm{\Pi }}_T$ strongly terminates, then the composed protocol does so as well since no party quits ${\mathrm{\Pi }}_L$ before some party terminates ${\mathrm{\Pi }}_T$. However, if ${\mathrm{\Pi }}_T$ is just terminating, then the composed protocol might not terminate since some honest parties might never obtain ${\mathrm{\Pi }}_T$ inputs. Approximate agreement protocols often consist of Gather iterations composed like this, and the strong termination of the last iteration suffices for the composed protocol to (strongly) terminate.

With ${\mathrm{\Pi }}_{\mathrm{𝖦𝗍𝗁𝗋}}^{\mathrm{𝖫𝗂𝗏𝖾}}$ we denote the most efficient live Gather protocol we know of [15]. Instantiated with a state-of-the-art standard BRB protocol which requires $𝒪(\mathrm{\ell }n+n^2\log n)$ bits of communication [6], it achieves the bit complexity $𝒪(\mathrm{\ell }{n}^2+n^3\log n)$. The protocol ${\mathrm{\Pi }}_{\mathrm{𝖦𝗍𝗁𝗋}}^{\mathrm{𝖫𝗂𝗏𝖾}}$ is presented in [15], though for completeness we restate it and its security proof in the appendix. Note that ${\mathrm{\Pi }}_{\mathrm{𝖦𝗍𝗁𝗋}}^{\mathrm{𝖫𝗂𝗏𝖾}}$ is not binding, but our strongly terminating Gather protocol ${\mathrm{\Pi }}_{\mathrm{𝖦𝗍𝗁𝗋}}$ will be.

The protocol ${\mathrm{\Pi }}_{\mathrm{𝖦𝗍𝗁𝗋}}^{\mathrm{𝖫𝗂𝗏𝖾}}$ involves $n$ standard BRB broadcasts of $\mathrm{\ell }$-bit inputs, $n$ standard BRB broadcasts of $n$-bit inputs and $n$ multicasts of $n$-bit inputs. To make ${\mathrm{\Pi }}_{\mathrm{𝖦𝗍𝗁𝗋}}^{\mathrm{𝖫𝗂𝗏𝖾}}$ (strongly) terminate, it suffices to replace its standard BRB broadcasts and multicasts with QBRB broadcasts. The issue is that against corruptions we do not know of a more efficient error-free QBRB protocol than ${\mathrm{\Pi }}_{\mathrm{𝖰𝗎𝗂𝗍}}$, and replacing all standard BRB broadcasts and multicasts in ${\mathrm{\Pi }}_{\mathrm{𝖦𝗍𝗁𝗋}}^{\mathrm{𝖫𝗂𝗏𝖾}}$ with ${\mathrm{\Pi }}_{\mathrm{𝖰𝗎𝗂𝗍}}$ instances results in the bit complexity $𝒪(\mathrm{\ell }{n}^3+n^4)$. Our ${\mathrm{\Pi }}_{\mathrm{𝖦𝗍𝗁𝗋}}$ protocol instead achieves strong termination while preserving the complexity $𝒪(\mathrm{\ell }{n}^2+n^3\log n)$.

The QBRB protocol ${\mathrm{\Pi }}_{\mathrm{𝖰𝗎𝗂𝗍}}$ in Section 4 loses its termination guarantees if any honest party quits before some honest party terminates. Now, we design an error-free deterministic QBRB variant ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ which keeps its termination guarantees no matter when any honest party quits.

Of course, such lax participation from the honest parties makes the standard output guarantees impossible. Hence, we introduce the extra outputs $\perp$ and $\top$. For some publicly known $q$, if at most $q$ honest parties quit before some honest party terminates, then ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ is just a QBRB protocol, albeit one with an extra output $\top$ to indicate that the sender quit before it acquired an input. If more than $q$ honest parties quit before some honest party terminates, then we relax the output guarantees and give each party the individual option to output $\perp$. The protocol ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ optimally requires for this, which means that if $t\ll n$, then almost every honest party can quit without the output $\perp$ becoming permitted.

Formally, let $ℳ$ be the input domain of ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$, with $ℳ\cap \{\perp ,\top \}=\mathrm{\varnothing }$. The protocol ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ has the output domain $ℳ\cup \{\perp ,\top \}$, and given a fixed sender party $P^{\ast }$ who may eventually acquire an input $v^{\ast }\in ℳ$, it guarantees the following against the $(t,\mathrm{𝖼𝗋𝖺𝗌𝗁})$-adversary:

• $\mathrm{■}$

  Validity: Suppose $P^{\ast }$ is honest. If an honest $P_i$ outputs $y_i\in ℳ$, then $P^{\ast }$ has acquired $v^{\ast }=y_i$, and if an honest $P_i$ outputs $\top$, then $P^{\ast }$ has quit before acquiring an input.

• $\mathrm{■}$

  Consistency: If honest parties $P_i$ and $P_j$ output $y_i\ne \perp$ and $y_j\ne \perp$, then $y_i=y_j$.

• $\mathrm{■}$

  Robustness: If at most $q$ honest parties quit before some honest party terminates, then no honest party outputs $\perp$.

• $\mathrm{■}$

  Local Termination: If $P^{\ast }$ is honest, and it either acquires an input or quits before doing so, then either some honest party terminates, or all honest parties quit.

• $\mathrm{■}$

  Global Termination: If some honest party terminates, then every honest party either terminates or quits.

As per the definition of the $(t,\mathrm{𝖼𝗋𝖺𝗌𝗁})$-adversary in Section 2, the protocol ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ achieves security even if the reason a party quits is that it has suffered a transient crash. This makes ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ of practical interest when the parties are prone to such crashes. For example, a party could get disconnected from the network or run out of battery while running ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$. Then, upon recovering, the party would invoke $\mathrm{𝖰𝗎𝗂𝗍}()$ to help the remaining parties terminate.

In ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$, transient crash tolerance follows from quit tolerance. If a party invokes $\mathrm{𝖰𝗎𝗂𝗍}()$ upon recovering from a crash, then the protocol proceeds almost as if the party never crashed, but just invoked $\mathrm{𝖰𝗎𝗂𝗍}()$ while running normally. From before crashing a party must retain only the information that $\mathrm{𝖰𝗎𝗂𝗍}()$ needs. In ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$, a party must remember the kinds of messages (among INIT, ECHO, READY) that it multicast before crashing.

Due to a lack of space, we formally prove Theorem 4 in the appendix. Note that is optimal (by Theorem 5) even if the honest parties cannot transiently crash.

The main innovation in ${\mathrm{\Pi }}_{\mathrm{𝖠𝗇𝗒}}$ is the flexible ECHO quorum threshold, which allows the honest parties to form ECHO quorums on the INIT value $v^{\ast }$ of an honest sender $P^{\ast }$ (the input of $P^{\ast }$, or $\top$ if $P^{\ast }$ quits before acquiring an input) as long as at most $t+q$ honest parties quit. If $P^{\ast }$ is honest, it multicasts $⟨\text{INIT},v^{\ast }⟩$, and at most $t+q$ honest parties quit, then for some $f\le t+q$ there exist at least $n-t-f$ honest parties who multicast $⟨\text{ECHO},v^{\ast }⟩$ and at least $f$ honest parties who multicast $⟨\text{ECHO},\perp ⟩$. Since $n-t-f>\max (t,\frac{n+t-f}{2})$, this suffices for the honest parties to be able to form quorums on $v^{\ast }$.

As usual, conflicting ECHO quorums do not occur because each honest party multicasts at most one ECHO message. Intuitively, if the adversary can create conflicting quorums on $v$ and $v^{\prime }$ with $⟨\text{ECHO},\perp ⟩$ messages, then it can also do so with just $⟨\text{ECHO},v⟩$ and $⟨\text{ECHO},v^{\prime }⟩$ messages. So, consider the case where the corrupt parties never send $⟨\text{ECHO},\perp ⟩$. If $f\le n$ honest parties multicast $⟨\text{ECHO},\perp ⟩$, then a party must receive $⟨\text{ECHO},v⟩$ from more than $\frac{n+t-f}{2}$ parties to form an ECHO quorum on $v$. Conflicting quorums on $v\ne v^{\prime }$ do not occur since at most $n-f$ parties send either $⟨\text{ECHO},v⟩$ or $⟨\text{ECHO},v^{\prime }⟩$. Lastly, an invalid quorum on $v$ (formed without $P^{\ast }$ sending $⟨\text{INIT},v⟩$) is prevented by a quorum on $v$ requiring at least $t+1$ $⟨\text{ECHO},v⟩$ messages.

If an honest party quits, then it multicasts both QUIT and some READY message. If $t+q+1$ honest parties quit, then the $t+q+1$ QUIT messages they multicast suffice for every honest party to multicast a READY message. Hence, every honest party can receive READY messages from $n-t$ parties and terminate. On the other hand, if at most $t+q$ honest parties quit, then we get local termination by the fact that after the honest sender $P^{\ast }$ multicasts $⟨\text{INIT},v^{\ast }⟩$, every honest party receives sufficiently many ECHO messages to multicast $⟨\text{READY},v^{\ast }⟩$.

If some honest party terminates, then there are at least $n-2t\ge 2t+q+1$ honest parties who multicast READY messages. Since for some $v\ne \perp$ every honest READY message is either $⟨\text{READY},v⟩$ or $⟨\text{READY},\perp ⟩$, either there are at least $t+1$ honest parties who multicast $⟨\text{READY},v⟩$, or there are at least $t+q+1$ honest parties who multicast $⟨\text{READY},\perp ⟩$. Either way, every honest party multicasts a READY message, and so every honest party can terminate.

Finally, if at most $q$ honest parties quit before some honest $P_i$ terminates, then $P_i$ terminates with at most $q$ honest copies of $⟨\text{READY},\perp ⟩$. Hence, $P_i$ terminates with at least $n-2t-q$ honest copies of $⟨\text{READY},v⟩$ for some $v\ne \perp$. The senders of these copies do not send READY messages on any $v^{\prime }\ne v$; so, any honest $P_j$ who terminates (including $P_i$) does so after receiving $n-3t-q\ge t+1$ honest copies of $⟨\text{READY},v⟩$ and setting its output to $v$.