Contention-Aware Cooperation

As stated in [37] (which introduces the fast Paxos algorithm), the notion of fast consensus algorithm in crash-prone message-passing asynchronous system was introduced in [10]. This algorithm was then extended to Byzantine asynchronous systems in [53]. Many efficiency-oriented Byzantine consensus algorithms have since been designed (e.g., [33, 35, 40, 43, 48] to cite a few).

The algorithms just discussed are specific to a single problem. In [4], Attiya and Welch go one step further and introduce a new problem termed Multivalued Connected Consensus, which unifies a range of weak agreement problems such as crusader agreement [16], graded broadcast [21] and adopt-commit agreement [26]. Differently from consensus, these agreement problems can be solved without requiring additional computational power such as synchrony constraints [8], randomization [6], or failure detectors [13].

Interestingly, the decision space of these weak agreement problems can be represented as a spider graph. Such a graph has a central clique (which can be a single vertex) and a set of $|V|$ paths (where $V$ is a finite set of totally ordered values) of length $R$. Two asynchronous message-passing algorithms that solve Multivalued Connected Consensus are described in [4]. Let $n$ be the number of processes and $t$ the maximal number of processes that can fail. The first algorithm considers crash failures and assumes , and the second considers Byzantine failures and assumes . For both of them, the instance with $R=1$ solves crusader agreement, and the instance $R=2$ solves graded broadcast and adopt-commit.

Albeit bearing some resemblance to our CAC abstraction, these agreements are one-shot agreements with only one output, generally, either a value is decided, or the processes are informed that other processes may have decided a value, then they terminate. No two different values can be decided by a single process. Whereas the CAC abstraction makes it possible to decide multiple values, and the oracle informs the processes about the values they may accept in the future.

Given a correct process $p_i$ and its associated ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$ and ${\mathrm{𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑}}_i$ sets, the following properties define an instance of CAC abstraction.⁶⁶6It can easily be extended to a multi-shot version using execution identifiers such as sequence numbers.

• $\mathrm{■}$

  CAC-Validity. If $p_i$ and $p_j$ are correct, ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i\ne \top$, and $⟨v,j⟩\in {\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$,

  then $p_j$ cac-proposed value $v$.

• $\mathrm{■}$

  CAC-Prediction. For any correct process $p_i$ and for any process identity $k$, if, at some point of $p_i$’s execution, $⟨v,k⟩\notin {\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$, then $p_i$ never cac-accepts $⟨v,k⟩$ (i.e., $⟨v,k⟩\notin {\mathrm{𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑}}_i$ holds forever).

• $\mathrm{■}$

  CAC-Non-triviality. For any correct process $p_i$, ${\mathrm{𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑}}_i\ne \mathrm{\varnothing }$ implies ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i\ne \top$.

• $\mathrm{■}$

  CAC-Local-termination. If a correct process $p_i$ invokes $\mathrm{𝖼𝖺𝖼}\mathrm{\_}\mathrm{𝗉𝗋𝗈𝗉𝗈𝗌𝖾}(v)$, its set ${\mathrm{𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑}}_i$ eventually contains a pair $⟨v^{\prime },\star ⟩$ (note that $v^{\prime }$ is not necessarily $v$).

• $\mathrm{■}$

  CAC-Global-termination. If $p_i$ is a correct process and $⟨v,j⟩\in {\mathrm{𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑}}_i$, eventually $⟨v,j⟩\in {\mathrm{𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑}}_k$ at every correct process $p_k$.

The CAC-Validity property states that a correct process $p_i$ may include, in its ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$ set, and possibly cac-accept, a pair $⟨v,j⟩$ from a correct process $p_j$, only if $p_j$ cac-proposed value $v$, i.e., only if there is no identity theft for correct processes. The CAC-Prediction property states that, if, at some point of $p_i$’s execution, some pair $⟨v^{\prime },k⟩$ is no longer in ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$, then $p_i$ will never accept $⟨v^{\prime },k⟩$. In other words, ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$ provides information about which pairs might be accepted by $p_i$ in the future. In particular, if a correct process $p_i$ cac-accepts a pair $⟨v,j⟩$, then $⟨v,j⟩$ was present in ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$ from the start of $p_i$’s execution. (However, the converse is generally not true; the prediction provided by ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$ is, as such, imperfect.) This property is at the core of the cooperation provided by a CAC object. The CAC-Non-triviality property ensures that a trivial implementation that never updates ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$ is excluded. As soon as some process $p_i$ has accepted some pair $⟨v,k⟩$, its ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$ set must contain some explicit information about the pairs that might get accepted in the future.⁷⁷7Ignoring the symbolic value $\top$, ${\mathrm{𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑}}_i$ and ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$ remain finite sets throughout $p_i$’s execution.

The CAC-Local-termination property states that if a correct process cac-proposes a value $v$, its ${\mathrm{𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑}}_i$ set will not remain empty. Notice that this does not mean that the pair $⟨v,i⟩$ will ever be added to ${\mathrm{𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑}}_i$. Finally, the CAC-Global-termination property states that eventually, the $\mathrm{𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑}$ sets of all correct processes are equal. Let us notice that, in general, no process $p_i$ can know when no more pairs will be added to its set ${\mathrm{𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑}}_i$.

Existing systems follow either of two approaches, which, however, do not solve exactly the $\mathrm{𝗌𝗁𝗈𝗋𝗍𝗇𝖺𝗆𝗂𝗇𝗀}$ problem.

• $\mathrm{■}$

  The first approach ignores the input public keys and relies on consensus. Each process chooses its name, independently of its public key, and submits it to the consensus algorithm. In case of contention, the consensus algorithm decides which process wins in a first-come, first-served manner. The problem with this method is that it leverages consensus – hence requiring additional computability power (e.g., partial synchrony or randomization), even if the probability of contention is low. Examples of this solution are NameCoin [32], Ethereum Name Service [31], and DNSSec [30].

• $\mathrm{■}$

  The second method directly uses the input public keys as the name and does not require consensus. If the underlying cryptography is perfectly secure and secret keys are only known to their legitimate users, then the associated public keys are assumed unique, and no conflict can occur because no two processes can claim the same name. The problem with this method is that it does not satisfy the SN-Short-names property as public keys consist of long chains of random characters, which are hard for humans to remember. Some systems circumvent the problem by using functions to map a random string to something that humans can remember: petname systems [22], tripphrases [57], or Proquint IDs [58]. However, these techniques do not reduce the entropy of the identifier, and they are mainly used to prevent identity theft (e.g., phishing).

Assuming perfect public/private keys, the CAC primitive makes it possible to satisfy the SN-Short-names property of $\mathrm{𝗌𝗁𝗈𝗋𝗍𝗇𝖺𝗆𝗂𝗇𝗀}$ without requiring consensus. The idea is to let processes claim sub-strings of their public keys. For example, let a process $p$ have a public key . It will first claim the name using one instance of the CAC primitive. If there is no conflict, i.e., if the size of the $\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}$ set is $1$ after the first acceptance, then the name belongs to $p$ and is associated with its public key. On the other hand, if there is a conflict, i.e., another process claimed the name and the size of the candidate set is strictly greater than $1$ after the first acceptance, then $p$ claims the name . This procedure ensures that a process can always obtain a name. Indeed, because we assume perfect cryptographic primitives, only one process knows the secret key associated with its public key. Therefore, if $p$ conflicts with all its claims on the subsets of its public key, it will eventually claim the name . No other process can claim the same name and prove it knows the associated secret key. We formally describe this algorithm and prove that it solves the $\mathrm{𝗌𝗁𝗈𝗋𝗍𝗇𝖺𝗆𝗂𝗇𝗀}$ problem in the full version of this paper.

Consensus is a cooperation abstraction that allows a set of processes to agree on one of the values proposed by one of them. Consensus offers one operation propose and one callback decide and is defined by the following four properties.

• $\mathrm{■}$

  C-Validity. If all processes are correct and a process decides a value $v$, then $v$ was proposed by some process.

• $\mathrm{■}$

  C-Agreement. No two correct processes decide different values.

• $\mathrm{■}$

  C-Integrity. A correct process decides at most one value.

• $\mathrm{■}$

  C-Termination. If a correct process proposes a value $v$, then all correct processes eventually decide some value (not necessarily $v$).

Note that this definition differs slightly from the usual theoretical definition of consensus in that not all processes need to participate in all executions. This reflects what happens in practical consensus-based systems [18], including cryptocurrencies [41], denylists [25], or auditable registers [3]. In particular, the C-Termination property only guarantees termination when some correct process proposes a value.

Building upon the CAC abstraction, we present a new consensus algorithm, called Cascading Consensus (CC), that adopts an optimistic contention-aware strategy to offer several fast paths for a varying set of favorable circumstances, including non-unanimous settings. This contrasts with existing optimistic consensus algorithms, which can typically only exploit one (usually unanimity). Specifically, if $n\ge 5t+1$ and there is unanimity, CC decides in 2 rounds without synchrony – as one cac instance suffices – thus matching the best existing algorithms for this case [52, 53, 60] (Table 1). If $n\ge 3t+1$ and there is unanimity, CC decides in 3 rounds without synchrony, surpassing existing optimistic algorithms that either terminate in more than 3 rounds [15, 34] and/or require synchrony to exploit their fast path [12, 28, 34, 38, 49, 60] (Table 1). When there is no unanimity, CC further offers a progressive degradation of its fast-path, in contrast with existing unanimity-based algorithms [1, 12, 15, 28, 38, 52, 53, 60], which fall back to a “slow-path” as soon as several conflicting values are proposed. Specifically, CC leverages the fact that not all processes need to propose a value to restrict conflict resolution to the set of processes that actually issued proposals. This yields two advantages. (i) These few processes are more likely to experience synchronous network phases [7] (which are required to guarantee that a deterministic consensus algorithm terminates [8, 17, 19]), and (ii) these “restricted” synchronous phases tend to exhibit shorter network delays, leading to overall heightened efficiency. This local approach is more efficient than full-scale consensus as validated by a recent experimental study [7].

In a nutshell, CC disseminates messages over the entire system using the CAC implementation presented in the full version of this paper extended with proofs of acceptance (cf. Section 3.3). When the first CAC dissemination fails to deliver a (fast) decision, CC exploits a Restrained Consensus algorithm (solving a relaxed consensus variant defined in the full version of this paper). This algorithm makes it possible for a subset ${\mathrm{\Pi }}^{\prime }$ of processes to agree on a set of values, and to prove to the rest of the system that all the processes in ${\mathrm{\Pi }}^{\prime }$ did agree on this value. Hence, it makes it possible to solve the consensus problem locally, and to inform other processes about the result of this consensus. Both the CAC and Cascading Consensus algorithms are fully asynchronous, i.e., they do not require any (partial) synchrony assumptions.

Restrained Consensus, on the other hand, may fail to terminate if there are Byzantine processes or if the network behaves asynchronously (exhibiting long delays). For this reason, Cascading Consensus combines Restrained Consensus with timers as a first fallback strategy to resolve conflicts rapidly among a small subset of processes during favorable synchronous phases. When circumstances are unfavorable (e.g. when network delays exceed timeouts, or under Byzantine failures), the timer expires, and CC falls back to a slow-path mode, which guarantees safety properties in all cases, and terminates (albeit more slowly). Note that the use of timers does not prevent CC from working under asynchrony. Timers are local, and when they expire, CC can fall back to a probabilistic asynchronous or to a partially synchronous algorithm.

CC leverages four sub-algorithms (two CAC instances, an instance of Restrained Consensus, and an instance of a standard consensus, which is used as fallback). It works in four steps, each step being associated with a termination condition that is more likely to be met than the previous one (as shown experimentally in [7]).

In the first step, processes propose values using the first CAC instance. Let $p_i$ be a process that proposed a value. If there is no contention (contention-awareness) i.e., the ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$ set of the first CAC instance has size $1$, $p_i$ can terminate: the value proposed by $p_i$ becomes the decided value. Otherwise, if the size of the ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$ set is greater than $1$ after cac-accepting the value proposed by $p_i$, $p_i$ must resolve the conflict with the other processes that proposed a value, whose pairs are in ${\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}}_i$ (contention-awareness). In this case, conflicting processes proceed to a second step, which involves an instance of the Restrained Consensus (RC) algorithm presented in the full version of this paper. If the conflicting processes are correct and benefit from stable network delays, the RC algorithm is guaranteed to succeed. In this case, the concerned processes disseminate the result of this step to the whole system using the second CAC instance (third step). If, on the other hand, some of the processes participating in the RC algorithm are Byzantine, or if messages from correct processes are delayed too much, the RC algorithm fails. This failure is detected by the second CAC instance (third step), which, in this case, returns $\mathrm{𝑐𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑠}$ sets with more than $1$ pair (contention-awareness). In this case, the Cascading Consensus algorithm proceeds to its final fourth step, handing the final decision to a Global Consensus (GC), i.e., any consensus algorithm based on additional assumptions such as partial synchrony [8, 17, 19], randomization [6, 42], or information on failures [13]. The implementation of GC can be chosen without any constraint. For example, if an asynchronous probabilistic consensus algorithm is chosen to instantiate GC, then CC implements consensus under fully asynchronous assumptions.

Note that, in a single execution, not all processes necessarily perform the same number of steps. For example, some processes may accept a single value after 2 rounds, reaching a decision in the first CAC instance. Other processes may, instead, require additional steps to reach the same decision because their candidate set contains additional values. The CAC-Prediction property guarantees that the latter processes can only accept the value accepted by the former.

Table 3 summarizes the termination conditions of the CC algorithm and their associated round complexity. The table considers two types of rounds: the fourth column counts system-wide rounds – i.e., for one asynchronous round, each process has to send $n$ messages. The final column counts the asynchronous rounds executed by RC– i.e., for RC round, the $\mathrm{\ell }$ processes that execute RC have to send a message to all other $\mathrm{\ell }-1$ involved processes. With fewer processes involved, the asynchronous rounds of RC will typically be faster (measured in wall-clock time) than those of the whole network [7]. The “execution path” column details where in the algorithm a process terminates by listing the sub-algorithm instances (noted $CA{C}_1$, $RC$, $CA{C}_2$, and $GC$) that intervene in a process execution. For instance, the first row describes the most favorable scenario in which a correct process terminates after the first two rounds of the first CAC instance.¹¹¹¹11In the table, Unanimity refers to the unanimity of the proposers (since not all processes are required to propose in our algorithm). We have omitted an even more favorable case, in which all correct processes propose the same value (i.e., there is a pre-agreement between correct processes), and Byzantine processes remain silent. In this limit case, CC saves one further round under the conditions presented in the first two rows: it decides in one round when $n>5t$ and two rounds when $n>3t$.

We detail the workings of the Restrained Consensus algorithm (RC), and the operations of Cascading Consensus in the full version of this paper.