Contention-Aware Cooperation

Timothé Albouy, Davide Frey, Mathieu Gestin, Michel Raynal, François

Taïani

► To cite this version:

Timothé Albouy, Davide Frey, Mathieu Gestin, Michel Raynal, François Taïani. Contention-Aware Cooperation. OPODIS 2025 - 29th International Conference On Principles Of Distributed Systems, Dec 2025, Iasi, Romania. pp.9:1-9:20, 10.4230/LIPIcs.OPODIS.2025.9 . hal-05456351

HAL Id: hal-05456351

https://inria.hal.science/hal-05456351v1

Submitted on 13 Jan 2026

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Contention-Aware Cooperation

Timothé Albouy ☐

<figure><img src="image_2.png" /></figure>

IMDEA Software Institute, Madrid, Spain

Davide Frey ☐

<figure><img src="image_3.png" /></figure>

Univ Rennes, Inria, CNRS, IRISA, 35042 Rennes-cedex, France

Mathieu Gestin ☐

<figure><img src="image_4.png" /></figure>

CEA, Saclay, France

Michel Raynal ☐

<figure><img src="image_5.png" /></figure>

Univ Rennes, Inria, CNRS, IRISA, 35042 Rennes-cedex, France

François Taïani ☐

<figure><img src="image_6.png" /></figure>

Univ Rennes, Inria, CNRS, IRISA, 35042 Rennes-cedex, France

## Abstract

As shown by Reliable Broadcast and Consensus, cooperation among a set of independent computing entities (sequential processes) is crucial in fault-tolerant distributed computing. Considering *n*-process asynchronous message-passing systems where some processes may be Byzantine, this paper introduces a novel cooperation abstraction, Contention-Aware Cooperation (CAC). While Reliable Broadcast is a one-to-*n* cooperation abstraction and Consensus is an *n*-to-*n* cooperation abstraction, CAC is a *d*-to-*n* cooperation abstraction where *d* ($1 \le d \le n$) varies with each run and remains unknown to the processes. Correct processes accept the same set of *ℓ* pairs $\langle v, i \rangle$ (*v* is the value proposed by $p_i$) from the *d* proposer processes, where $1 \le \ell \le d$ and (as *d*) *ℓ* remains unknown to the processes (except in specific cases). Those *ℓ* values are accepted one at a time, potentially in different orders at each process. In addition, CAC provides each process with an imperfect oracle that provides insights into the values that they may accept in the future. Interestingly, the CAC abstraction is particularly efficient in favorable circumstances, when the oracle becomes accurate, which processes can detect. To illustrate its practical utility, the paper details two applications leveraging CAC: a fast consensus implementation optimized for low contention (named Cascading Consensus), and a novel naming problem that can be solved under full asynchrony. All algorithms presented require signatures.

**2012 ACM Subject Classification** Theory of computation → Distributed algorithms

**Keywords and phrases** Agreement, Asynchronous message-passing system, Byzantine processes, Conflict detection, Consensus, Cooperation abstraction, Distributed computing, Fault tolerance, Optimistically terminating consensus, Short-naming.

**Digital Object Identifier** 10.4230/LIPIcs.OPODIS.2025.9

**Related Version** The full version of this work appears in: arXiv:2311.08776 [2]

**Acknowledgements** This work was partially supported by the French ANR projects ByBloS (ANR-20-CE25-0002-01) and PriCLeSS (ANR-10-LABX-07-81), and by the SOTERIA project. SOTERIA has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 101018342. This content reflects only the author's view. The European Agency is not responsible for any use that may be made of the information it contains.

## 1 Introduction

Distributed computing is the science of algorithm-based cooperation. It consists in defining (using precise specifications) and implementing distributed abstractions (distributed objects) that allow a set of computing entities (denoted processes, nodes, peers, actors, etc.) to cooperate to reach a common goal. In the following, we use the term *process* to denote a

<figure><img src="image_7.png" /></figure>

© Timothé Albouy, Davide Frey, Mathieu Gestin, Michel Raynal, and François Taïani; licensed under Creative Commons License CC-BY 4.0

29th International Conference on Principles of Distributed Systems (OPODIS 2025).

Editors: Andrei Arusoaie, Emanuel Onica, Michael Spear, and Sara Tucci-Piergiovanni; Article No. 9; pp. 9:1–9:20

Leibniz International Proceedings in Informatics

<figure><img src="image_8.png" /></figure>

LIPICS

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
9:2 Contention-Aware Cooperation

sequential computing entity. Considering asynchronous *n*-process message-passing systems, this paper focuses on cooperation abstractions that have to cope with Byzantine processes (i.e., processes that may behave arbitrarily, as defined in [39, 47]).

The gold standard of cooperation abstractions is consensus. It allows a set of processes to propose values, and to eventually agree on one of those values. This abstraction makes it possible to implement a deterministic state machine, i.e., it makes it possible for the processes to run any deterministic algorithm. However, consensus algorithms cannot be deterministically implemented in an asynchronous distributed system in the presence of faulty processes [23]. A way to circumvent this impossibility consists in weakening one of its assumptions: weakening the full asynchrony assumption [8, 17, 19], assuming scheduling constraints, e.g., [9, 12, 38], weakening determinism by allowing the processes to use random numbers, e.g., [6, 18, 41], providing the processes with as-weak-as-possible information on failures [13], or using an appropriate combination of some of the previous weakenings. An issue with these solutions lies in their high cost in terms of latency and in the number of messages exchanged. A survey of these approaches can be found in [51]. Another interesting approach consists in the design of optimistic algorithms that terminate quickly in predefined favorable circumstances (fast-path) and pay a degrading additional price (layered fast-paths) in the other cases, e.g., [10, 35, 52, 53]. Interestingly, the fast-path part of those algorithms usually does not rely on synchrony assumptions. However, the optimistically terminating consensus algorithms do not separate the fast-path from the rest of their consensus algorithm. It is incorporated in the algorithm without considerations for its specificities. In this paper, we propose to isolate the essence of fast-path mechanisms in a standalone abstraction: the Contention-Aware Cooperation.

## 1.1 Content of the paper

This paper focuses on optimistic termination under limited contention, i.e., the ability to exploit a fast-path strategy when no or little disagreement exists in the system. This occurs for instance when only a few actions may conflict, or only a few participants are active at any given time. To address such cases, the paper introduces a harmoniously degrading ladder of fast-paths and integrates them into a novel standalone communication abstraction called Contention-Aware Cooperation (CAC). This abstraction provides many-to-many communication with weak agreement capabilities that informally work as follows.

- Within a CAC instance, some arbitrary number, $d$ (where $1 \le d \le n$), of processes propose values.

- During the subsequent CAC execution, each process accepts pairs, $\langle v, i \rangle$ (where $v$ is the value proposed by $p_i$), so that, eventually, all processes accept the same set of $\ell$ pairs, where $1 \le \ell \le d$. A process accepts pairs one after the other in some arbitrary order, which may vary from one process to another.

Both $d$ (the number of actual proposers) and $\ell$ (the number of eventually accepted values) depend on the run of the CAC instance (e.g., the (unknown) number of proposers, asynchrony, and the behavior of Byzantine processes) and are unknown to participating processes. In particular, a process cannot generally conclude it has accepted the $\ell$ pairs composing the final set of accepted pairs (except in some specific favorable cases that will be discussed later).

To help reach agreement in favorable cases, the CAC abstraction endows each process with an imperfect oracle that offers information about the set of pairs that might get accepted in the future. This oracle is imperfect in the sense that it may produce false positives (it
<table><caption>**Table 1** Comparison of CAC with existing fast paths of optimistic cooperation algorithms</caption><thead><tr><th>Implementation</th><th>Optimistic condition</th><th>Best latency<sup>1</sup></th><th>Byzantine resilience</th></tr></thead><tbody><tr><td>Zyzzyva [34]</td><td>Synchronous period and correct leader</td><td>3</td><td><b>3t + 1</b></td></tr><tr><td>Thunderella [46]</td><td>Synchronous period and correct leader</td><td>3</td><td><b>4t + 1</b></td></tr><tr><td>Parsimonious BFT [49]</td><td>Synchronous period and correct leader</td><td>3</td><td><b>3t + 1</b></td></tr><tr><td>Fast Byzantine consensus [40]</td><td>Synchronous period and correct leader</td><td><b>2</b></td><td><b>5t + 1</b></td></tr><tr><td>Optimal Fast Byzantine Consensus [35]</td><td>Synchronous period and correct leader</td><td><b>2</b></td><td><b>5t - 1</b></td></tr><tr><td>PBFT [12]</td><td>Synchronous period and unanimity</td><td>3</td><td><b>3t + 1</b></td></tr><tr><td>Algorand [28]</td><td>Synchronous period and unanimity</td><td>3</td><td><b>3t + 1</b></td></tr><tr><td>Optimistic Byzantine agreement [60]</td><td>No Byzantine behaviour and synchronous period</td><td>3</td><td><b>3t + 1</b></td></tr><tr><td>Fault scalable BFT services [1]</td><td>Failure-free and unanimity</td><td>3</td><td><b>5t + 1</b></td></tr><tr><td>HQ Replication [15]</td><td>Unanimity</td><td>4</td><td><b>3t + 1</b></td></tr><tr><td>Bosco [53]</td><td>Unanimity</td><td><b>2</b></td><td><b>5t + 1</b></td></tr><tr><td>Consensus on demand [52]</td><td>Unanimity</td><td><b>2</b></td><td><b>5t + 1</b></td></tr><tr><td>Optimistically terminating consensus [60]</td><td>Correct leader and unanimity</td><td><b>2</b></td><td><b>5t + 1</b></td></tr><tr><td>CAC</td><td>Unanimity</td><td><b>2</b></td><td><b>5t + 1</b></td></tr><tr><td>CAC</td><td>Unanimity</td><td>3</td><td><b>3t + 1</b></td></tr></tbody></table>

might return pairs that never get accepted). The oracle cannot, however, produce false negatives: any pair excluded by the oracle will never be accepted by any correct process.

In favorable cases, the oracle's predictions allow processes to detect they have converged to the final set of accepted pairs, and that they will not accept any other pair. As a result, CAC provides a weak form of agreement, and falls into an intermediate class of cooperation abstractions that are less powerful than consensus (and thus feasible even in fully asynchronous environments), but that can achieve fast-path agreement under propitious conditions [4, 16, 20, 59]. Specifically, CAC can dynamically adjust to the number of proposers and the conflicts between proposed values, thereby expanding the design space of existing weak-agreement abstractions.

## 1.2 The CAC abstraction to address low contention problems

The CAC abstraction is designed to solve distributed problems efficiently under low contention. This is particularly useful when implementing objects whose state is determined by the sequence of executed operations, but only a subset of these operations conflict with one-another.

When the probability of contention is low, processes can leverage CAC's imperfect oracle to detect contention and identify competing processes. In the absence of contention or competitors, processes can terminate prematurely (fast path), and fall back on more advanced (and more costly) strategies in the remaining cases. This hybrid strategy is typical of fast/adaptive cooperation distributed algorithms, and ensures safety in all cases, while delivering high performance in favorable ones. In the case of consensus, CAC's focus on contention makes it possible to realize a consensus algorithm that can terminate optimistically even when multiple (different) values are proposed (Section 5.2). This ability contrasts with existing optimistically terminating consensus algorithms [33, 43, 52, 53, 61], which typically either require unanimity and/or synchrony to activate their fast-path mechanism. To illustrate this point, Table 1 compares the fast-path conditions of existing optimistically terminating consensus to those of CAC. The numbers indicated for CAC are those of the optimized algorithm we present in the full version of this paper, which can terminate in

<footnote n="1">¹ Latency is measured in terms of consecutive asynchronous rounds for all algorithms.</footnote>
9:4 Contention-Aware Cooperation

three asynchronous rounds when $n > 3t$ and finishes in two asynchronous rounds in the best cases if $n > 5t$ using signatures. Although CAC does not implement consensus, its fast-path conditions directly transfer to the consensus algorithm based on CAC that we present in the full version of this paper, which motivates this comparison. In Table 1, unanimity means that there is no contention on the proposed values. In other words, all proposing processes propose the same value.

The main results of this comparison are that our CAC implementation is equivalent to the best existing fast paths of optimistically terminating consensus in favorable conditions, i.e., an agreement can be reached in 2 asynchronous rounds when $n \ge 5t + 1$ and there is a unanimity of proposed values. The capabilities of our CAC implementation go, however, beyond this optimal best case. In particular, it can also be used to improve the latency of intermediate cases, i.e., when some contention exists but remains limited. For instance, the CAC-based consensus algorithm we introduce in the full version of this paper (dubbed Cascading Consensus) can still reach an agreement if less than *k* processes endorsed the messages that do not have the majority of endorsements.<fnref n="2" /> As a result, it exhibits a ladder of escalating reconciliation strategies, with intermediate cases limiting reconciliation to the subset of conflicting processes, a capability that is of direct practical relevance when these processes happen to be geographically close to one another [7]. This contention management strategy is made possible thanks to the imperfect oracle of the CAC abstraction.

Note that CAC's interest extends beyond consensus, in particular when there exists a deterministic back-off strategy that can be implemented under full asynchrony. In that case, the CAC abstraction can be used to construct fully asynchronous agreement algorithms, whereas other solutions would have required consensus. To illustrate this strategy, Section 5.1 introduces the short-naming problem, a novel coordination task in which processes seek to adopt unique names with the lowest possible information-theoretic entropy. Using CAC, we present a Byzantine-tolerant algorithm that solves that problem in a fully asynchronous network.

1.3 Benefits of the CAC abstraction

To summarize the benefits of CAC, this novel abstraction along with our proposed imple-
mentations make it possible:

- to implement algorithms with expanded “graceful conditions,” enhancing the efficiency of fast-paths in optimistically terminating consensus algorithms;

- to adjust precisely fast-path parameters to optimally align with algorithmic requirements;

- to isolate the fast-path components of consensus algorithms and implement them in isolation for enhanced modularity;

- to implement new and more efficient contention resolution methods when fast-path conditions are not met;

- to implement new asynchronous solutions to problems weaker than consensus (e.g., such as the short naming problem).

1.4 Related work

The work described in this paper places itself in the context of *fast/adaptive cooperation*
*distributed algorithms where an arbitrary, a priori unknown subset of processes try to modify*

<footnote n="2">² This condition is explained in the full version of this paper, *k* is a parameter of the algorithm.</footnote>
a shared object. These algorithms seek to terminate as rapidly as possible in favorable circumstances (e.g., no or few faults, no or little contention) and with as few as possible actions from non-participating processes while maintaining strong safety guarantees in the general case. Such algorithms have been investigated in earlier works.

Considering shared memory systems, the reader will find more developments of this approach in [50, 54].

**Fast/adaptive consensus in message-passing asynchronous crash-prone/Byzantine systems.** As stated in [36] (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).

**Structuring the space of weak agreement problems.** 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 $t < n/2$, and the second considers Byzantine failures and assumes $t < n/5$. 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.

## 1.5 Roadmap

The article is structured into 6 sections. First, Section 2 introduces the computing model while Section 3 provides a formal definition of the CAC cooperation abstraction. Then, on the feasibility front, Section 4 showcases a first implementation of the CAC primitive that assumes $t < n/4$ but is easy to explain and understand. Next, the CAC algorithm presented in the full version of this paper [2] demonstrates how CAC can be used to solve two synchronization problems of immediate practical relevance: shortnaming (Section 5.1), which provides processes with unique names while minimizing their information-theoretic entropy, and Consensus with optimistic termination (Section 5.2). The consensus implementation we present (termed Cascading Consensus) exploits the CAC abstraction to offer a ladder of harmoniously degrading fast paths that directly arise from the optimistic performance of our optimal CAC implementation to consensus. Finally, Section 6 concludes the article. Due to page limitations, additional developments are provided in the full version of this paper,
including our optimal CAC implementation, which only requires $t < n/3$, and detailed proofs
(including the necessity of this resilience bound for the CAC abstraction) [2].

## 2 Computing Model

**Model.** The system is made up of a set $\Pi$ of $n$ processes, denoted $p_1, \dots, p_n$, that communicate using message-passing over asynchronous channels. “Asynchronous” means that each message can be delayed an arbitrary finitely long time, and that processes can take an arbitrary but finitely long time to process an incoming message. However, channels are reliable, i.e., no message is dropped. Among the processes, at most $t$ are Byzantine. A Byzantine process can arbitrarily deviate from its prescribed algorithm. The other processes (that are at least $n-t$ and at most $n$) are called correct; they follow their prescribed algorithm and do not stop prematurely. We assume an adversary that controls the scheduler and all Byzantine processes. We further assume that cryptographic primitives cannot be forged, namely, we assume an unforgeable signature scheme resistant against chosen message attacks.<fnref n="3" />

In this paper, the word *message* refers to messages sent by the algorithm at the network level to implement an abstraction, they are sent and received. The word *value*, on the other hand, refers to the payloads disseminated at the user level by the abstractions, they are proposed and accepted (or decided in the case of consensus).

Finally, the CAC abstraction uses a best-effort (unreliable as a result of process failures) broadcast abstraction, noted **bekeepr**, as an underlying communication primitive. An invocation of **bekeepr** MSG by a correct process $p_i$ sends the same message MSG to all processes in $\Pi$ if not specified otherwise. We say that messages are “be-broadcast” and “received”.

**Notations.** We denote by $\langle v_1, \dots, v_k \rangle$ the $k$-tuple containing the sequence of $k$ values $v_1$ to $v_k$. The $\star$ symbol is used as the wildcard symbol (any value can be matched).

## 3 Contention-Aware Cooperation: Definition

### 3.1 Definition

The Contention-Aware Cooperation (CAC) object provides each process $p_i$ with (1) an operation denoted **cac\_propose** that allows it to propose a value and (2) two sets denoted **accepted**$_i$ and **candidates**$_i$.<fnref n="4" /> When a process $p_i$ invokes **cac\_propose**($v$), we say that “$p_i$ cac-proposes (in short “proposes”) the value $v$” (for clarity sometimes we also say that “$p_i$ cac-proposes the pair $\langle v, i \rangle$”). When a pair $\langle v, j \rangle$ is added to the set **accepted**$_i$ of a process $p_i$, we say that “$p_i$ cac-accepts (in short “accepts”) $\langle v, j \rangle$”. For the sake of simplicity, when a pair $\langle v, j \rangle$ is cac-accepted, a **CAC\_accept**($v, j$) callback is triggered.

- The set **accepted**$_i$ is initially empty. It then grows monotonically, progressively adding a pair $\langle v, j \rangle$ for each value $v$ that is cac-accepted by $p_i$ from $p_j$. Eventually, **accepted**$_i$ contains all the pairs $\langle v, j \rangle$ accepted by the CAC abstraction (and only them).

- The set **candidates**$_i$ is initialized to $\top$, where $\top$ is defined as a symbolic value representing the identity element of the $\cap$ operation.<fnref n="5" /> Then, **candidates**$_i$ shrinks monotonically, and

<footnote n="3">³ We conjecture that the CAC abstraction cannot be implemented without cryptographic signatures.</footnote>

<footnote n="4">⁴ The *candidates*<sub>*i*</sub> set is the imperfect oracle mentioned in this paper's introduction.</footnote>

<footnote n="5">⁵ That is to say, for any set S, $S \cap \top = \top \cap S = S$, and the statement $S \subseteq \top$ is always true.</footnote>
<figure><img src="image_9.png" /><figcaption>**Figure 1** During an execution, the *accepted*<sub>*i*</sub> and *candidates*<sub>*i*</sub> sets of a correct process *p*<sub>*i*</sub> the same for all correct processes and is contained monotonically grows and shrinks, respectively. **Figure 2** After the execution, the *accepted* set is in the intersection of their *candidates* sets.</figcaption></figure>

contains a dynamic estimation of the pairs ⟨v, j⟩ that have been or will be cac-accepted by process *p*ᵢ. Hence, *accepted*ᵢ ⊆ *candidates*ᵢ always holds. More concretely, *candidates*ᵢ contains all the pairs ⟨v, j⟩ that have been already added to the *accepted*ᵢ set locally by *p*ᵢ along with some pairs ⟨v, k⟩ that may (or may not) be added to the set *accepted*ᵢ later on. Formally, if τ₁ and τ₂ are two arbitrary time points in the execution of *p*ᵢ (in no particular order, i.e., with either τ₁ ≤ τ₂ or τ₁ ≥ τ₂) and *x*ᵢ<sup>τk</sup> represents the value of variable *x*ᵢ at time τₖ, then *candidates*ᵢ satisfies *accepted*ᵢ<sup>τ₂</sup> ⊆ *candidates*ᵢ<sup>τ₁</sup>. As a result, if a pair ⟨v, k⟩ is not in *candidates*ᵢ at some point, *p*ᵢ will never cac-accept this pair. Furthermore, if at some point τ, *p*ᵢ observes *accepted*ᵢ = *candidates*ᵢ, then *p*ᵢ knows it has cac-accepted all values for this CAC instance. Let us notice that this case may never happen (see Section 3.2). The behavior of both types of sets is summarized in Figures 1 and 2.

**CAC specification.** Given a correct process *p*ᵢ and its associated *candidates*ᵢ and *accepted*ᵢ sets, the following properties define an instance of CAC abstraction.<fnref n="6" />

- CAC-VALIDITY. If *p*ᵢ and *p*ⱼ are correct, *candidates*ᵢ ≠ ∨, and ⟨v, j⟩ ∈ *candidates*ᵢ, then *p*ⱼ cac-proposed value *v*.

- CAC-PREDICTION. For any correct process $p_i$ and for any process identity $k$, if, at some point of $p_i$'s execution, $\langle v, k \rangle \notin \mathit{candidates}_i$, then $p_i$ never cac-accepts $\langle v, k \rangle$ (i.e., $\langle v, k \rangle \notin \mathit{accepted}_i$ holds forever).

- CAC-NON-TRIVIALITY. For any correct process $p_i$, $accepted_i \neq \emptyset$ implies $candidates_i \neq \top$.

- CAC-LOCAL-TERMINATION. If a correct process $p_i$ invokes $cac\_propose(v)$, its set $accepted_i$ eventually contains a pair $\langle v', \star \rangle$ (note that $v'$ is not necessarily $v$).

- CAC-GLOBAL-TERMINATION. If $p_i$ is a correct process and $\langle v, j \rangle \in accepted_i$, eventually $\langle v, j \rangle \in accepted_k$ at every correct process $p_k$.

The CAC-VALIDITY property states that a correct process $p_i$ may include, in its *candidates*<sub>*i*</sub> 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', k⟩ is no longer in *candidates*<sub>*i*</sub>, then $p_i$ will never accept ⟨v', k⟩. In other words, *candidates*<sub>*i*</sub> 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 *candidates*<sub>*i*</sub> from the start of $p_i$'s execution. (However, the converse is generally not true; the prediction provided by *candidates*<sub>*i*</sub> is, as such, imperfect.) This property is at the core of the cooperation provided by a CAC

<footnote n="6">⁶ It can easily be extended to a multi-shot version using execution identifiers such as sequence numbers.</footnote>
9:8 Contention-Aware Cooperation

object. The CAC-NON-TRIVIALITY property ensures that a trivial implementation that never updates candidates$_i$ is excluded. As soon as some process $p_i$ has accepted some pair $\langle v, k \rangle$, its candidates$_i$ set must contain some explicit information about the pairs that might get accepted in the future.<fnref n="7" />

The CAC-LOCAL-TERMINATION property states that if a correct process cac-proposes a value $v$, its accepted$_i$ set will not remain empty. Notice that this does not mean that the pair $\langle v, i \rangle$ will ever be added to accepted$_i$. Finally, the CAC-GLOBAL-TERMINATION property states that eventually, the accepted 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 accepted$_i$.

## 3.2 Termination of the CAC abstraction

It follows from the definition that, for some correct process $p_i$, if candidates$_i$ = accepted$_i$, then $p_i$ will not cac-accept any new pair $\langle v, j \rangle$. Using the notations from Section 1.1, we see that $\ell = |\text{candidates}_i| = |\text{accepted}_i|$. In this specific case, $p_i$ can detect without ambiguity that the CAC execution has terminated (i.e., $p_i$ will not receive any other pair). $p_i$ also knows that all other correct processes will eventually receive exactly the pairs contained in accepted$_i$. We say that $p_i$ knows it terminated.

The most obvious example of “known termination” is when only one process cac-proposes (or is perceived to cac-propose) a value. In this case, by CAC-VALIDITY, $|\text{candidates}_i|$ eventually equals 1.

However, in the general case, there might be runs where $|\text{candidates}_i| > |\text{accepted}_i|$ during the whole execution of the abstraction. In this case, $p_i$ will not be able to know if it has terminated or if new pairs might be added to the accepted$_i$ set. This is an inherent feature of the CAC abstraction, but, as we will see in Section 5, this does not prevent the abstraction from being appropriate to solve complex coordination problems.

Another side effect of the abstraction is that, it is possible for a correct process $p_j$ to know it terminated because candidates$_i$ = accepted$_i$, while some other correct process $p_j$ might never detect its own termination, because $|\text{candidates}_j| > |\text{accepted}_j|$ during the whole run, even though $p_j$ will not cac-accept any additional value.

## 3.3 CAC with proofs of acceptance

The properties of the CAC abstraction imply that processes cac-accept pairs asynchronously and in different orders. In some applications, correct processes must prove to others that they have legitimately cac-accepted some pair $\langle v, j \rangle$. To support such use cases, the CAC definition can be enriched with transferable *proofs of acceptance* that a process can use to convince others that the underlying algorithm has been respected.

When using proofs of acceptance, the elements in the accepted$_i$ sets become triplets $\langle v, j, \pi_v \rangle$, where $\pi_v$ is a cryptographic construct that serves as proof that $\langle v, j \rangle$ was added to accepted$_i$ while following the prescribed algorithm. We say that $\pi_v$ is valid if there exists a function Verify such that, for any value $v$ and any proof of acceptance $\pi_v$ pertaining to $v$, the following property holds:

$$ \text{Verify}(v, \pi_v) = \text{true} \iff \exists p_i \text{ correct such that, eventually, } \langle v, \star, \pi_v \rangle \in \text{accepted}_i. \quad (1) $$

When $\text{Verify}(v, \pi_v) = \text{true}$, we say that $\pi_v$ is valid, and by extension that the triplet $\langle v, j, \pi_v \rangle$ is valid. When using proofs of acceptance, all properties of the CAC abstraction

<footnote n="7">⁷ Ignoring the symbolic value $\top$, accepted$_i$ and candidates$_i$ remain finite sets throughout $p_i$'s execution.</footnote>
**Algorithm 1** One-shot sig-based CAC implementation assuming $n > 4t$ (code for $p_i$)

1 **init:** $sigs_i \leftarrow \emptyset$; $candidates_i \leftarrow \top$; $accepted_i \leftarrow \emptyset$; $M_i \leftarrow \emptyset$.
2 **operation cacproposed(v)** is
3 &nbsp;&nbsp;**if** there are no signatures by $p_i$ in $sigs_i$ **then**
4 &nbsp;&nbsp;&nbsp;&nbsp;**sigs_i \leftarrow sigs_i \cup \{WITSIG(p_i, \langle v, i \rangle)\};** &nbsp;&nbsp;&nbsp;&nbsp; $\triangleright p_i$ signs $\langle v, i \rangle$ using a WITSIG signature
5 &nbsp;&nbsp;&nbsp;&nbsp;**beBroadcast BUNDLE(sigs_i).**
6 **when** BUNDLE(sigs_i) is received **do**
7 &nbsp;&nbsp;**valid_i \leftarrow \{**all valid signatures in sigs_i**\};**
8 &nbsp;&nbsp;**if** ($\exists p_k, k: WITSIG(\star, \langle v_k, k \rangle) \in valid_i \land WITSIG(p_k, \langle v_k, k \rangle) \notin valid_i$) **then** **return**;
9 &nbsp;&nbsp;**sigs_i \leftarrow sigs_i \cup valid_i;**
10 **if** $\exists p_j: WITSIG(p_j, \langle v, j \rangle) \in sigs_i \land WITSIG(p_i, \langle \star, \star \rangle) \notin sigs_i$ **then**
11 &nbsp;&nbsp;**sigs_i \leftarrow sigs_i \cup \{WITSIG(p_i, choice(\{\langle v', k \rangle | WITSIG(p_k, \langle v', k \rangle) \in sigs_i\})\};** &nbsp;&nbsp;&nbsp;&nbsp; $\triangleright$ choice chooses one of the elements in the set given as argument.
12 &nbsp;&nbsp;**beBroadcast BUNDLE(sigs_i);**
13 **if** $\{j | WITSIG(p_j, \langle \star, \star \rangle) \in sigs_i\} \ge n - t \land READYMSG(p_i, \star) \notin sigs_i$ **then**
14 &nbsp;&nbsp;**M_i \leftarrow \{WITSIG(\star, \langle \star, \star \rangle) \in sigs_i\};**
15 &nbsp;&nbsp;**sigs_i \leftarrow sigs_i \cup \{READYSIG(p_i, M_i)\};** &nbsp;&nbsp;&nbsp;&nbsp; $\triangleright p_i$ signs $M_i$ using a READYSIG signature
16 &nbsp;&nbsp;**beBroadcast BUNDLE(sigs_i);**
17 **if** $\{j | READYSIG(p_j, \star) \in sigs_i\} \ge n - t$ **then**
18 &nbsp;&nbsp;**beBroadcast BUNDLE(sigs_i);**
19 &nbsp;&nbsp;**if** $candidates_i = \top$ **then** &nbsp;&nbsp;&nbsp;&nbsp; $\triangleright$ first time a value is accepted
20 &nbsp;&nbsp;**candidates_i \leftarrow \{\langle v, k \rangle | \exists M: READYSIG(\star, M) \in sigs_i \land WITSIG(\star, \langle v, k \rangle) \in M\};**
21 &nbsp;&nbsp;**accepted_i \leftarrow**
22 &nbsp;&nbsp;&nbsp;&nbsp; $\{\langle v, k \rangle \in candidates_i | 2t + 1 \text{ distinct processes } p_s \text{ have signed READYSIG}(\star, M_s)\}$; &nbsp;&nbsp;&nbsp;&nbsp; in $sigs_i$ such that WITSIG(\star, \langle v, k \rangle) \in M_s$
23 &nbsp;&nbsp;**for** all pairs $\langle v, k \rangle$ that have just been added to $accepted_i$ **do**
24 &nbsp;&nbsp;&nbsp;&nbsp; **cac_accept(v, k).**

For space reasons, the proof of correctness of Algorithm 1 is provided in the full version of this paper [2].

5 CAC in Action: Solving Low Contention Problems

The CAC abstraction can solve cooperation problems by combining the optimistic conflict avoidance of the abstraction with a back-off strategy when conflicts occur. This section thoroughly explores two of these applications. The first one is a solution to a new naming problem, called short naming. The naming problem makes it possible for processes to claim new names and to associate them with a public key. Short naming is a variant of the naming problem where the new names attributed to processes have low entropy. The CAC abstraction naturally lends itself to such a problem, as it allows runs in which a single proposer puts forward a value and directly obtains agreement on it, thus capturing the case where a process
successfully claims a unique short-name for itself.<fnref n="9" />

The second application studied is the well known consensus problem. We explore a CAC-based solution to this problem denoted *Cascading Consensus*, a new optimistically terminating consensus algorithm that ensures an early decision in favorable circumstances. Moreover, this algorithm uses information provided by the CAC abstraction to reduce synchronization and communication complexity in case of contention. More precisely, this algorithm uses the CAC abstraction to disseminate values. If contention occurs, *i.e.*, if termination is not guaranteed, then only the processes that proposed a value participate in the conflict resolution. This behavior is made possible thanks to the information given by the *candidates* set. In that sense, this algorithm goes beyond similar existing solutions [33, 35, 40, 43, 48], and, to the best of our knowledge, the CAC abstraction is the only existing abstraction that makes it possible to implement an algorithm with such a behavior. These examples could be extended to many other distributed applications, *e.g.*, shared account asset-transfer protocols, access control, naming services, *etc*.

The goal of this section is to present new ways of solving distributed problems using the CAC abstraction. We would like to remind the reader that the main contributions of this paper are the definition, the formalisation and the implementation of the CAC abstraction, not its applications. Furthermore, as far as we know, the behavior of this abstraction is fundamentally different from what has been proposed before. Hence, comparisons with existing work would require extended experimental analysis, which is out of the scope of this paper.

## 5.1 The fault-tolerant asynchronous shortnaming problem

Many distributed applications, including cryptocurrency [11, 45, 55], decentralized identity management [24, 27, 44], or distributed storage [56], involve numerous participating devices that are typically identified by their public keys. For practical purposes, however, applications often choose shorter, more human-manageable names for devices. To formalize this, we define shortnaming as the problem of choosing such short human-manageable names. A shortnaming object provides each process $p_i$ with one operation $n_i \leftarrow shortnaming\_Claim(pk, \pi)$ that allows it to claim a name $n_i$, starting from its public key, pk, and its proof of knowledge of the associated secret key, $\pi$. The object also provides $p_i$ with an (initially empty) set *Names*<sub>*i*</sub>, which associates names with public keys. A *Names*<sub>*i*</sub> set is composed of triples ⟨n, pk, $\pi$⟩ where n is the attributed name, pk is the associated public key, and $\pi$ and the proof of knowledge of the corresponding secret key. The object provides the following properties.

- **SN-UNICITY.** Given a correct process $p_i$, $\forall \langle n_j, pk_j, \pi_j \rangle$, $\langle n_k, pk_k, \pi_k \rangle \in \text{Names}_i$, either $n_j \neq n_k$ or $j=k$.

- **SN-SHORT-NAMES.**<fnref n="10" /> If all processes are correct, and given one correct process $p_i$, eventually we have $\forall \langle n_j, pk_j, \star \rangle$, $\langle n_k, pk_k, \star \rangle \in \text{Names}_i$:
  If $|\text{Max\_Common\_Prefix}(pk_j, pk_k)| \ge |\text{Max\_Common\_Prefix}(pk_j, pk_\ell)|$, $\forall \langle \star, pk_\ell, \star \rangle \in \text{Names}_i$ then $|\text{Max\_Common\_Prefix}(pk_j, pk_k)| + 1 \ge |n_j|$.

<footnote n="9">⁹ By contrast, weak agreement primitives such as crusader agreement [4, 16] require all correct processes to propose a value in every execution, leading to a mismatch with the short-naming problem. Using crusader agreement in a short-naming algorithm would, for instance, require a convoluted strategy in which a correct process $p_i$ first advertises its claim to some name $v$, so that other processes can support this claim by proposing the pair $(i, v)$.</footnote>

<footnote n="10">¹⁰The function `Max Common Prefix()` outputs the longest common prefix between two strings, e.g., `Max Common Prefix("abcdefg", "abcfed") = "abc"`.</footnote>
- **SN-AGREEMENT.** Let $p_i$ and $p_j$ be two correct processes. If $\langle n, pk, \pi \rangle \in \text{Names}_i$ and if the process that invoked `shortnaming_Claim(pk, \pi)` is correct, then eventually $\langle n, pk, \pi \rangle \in \text{Names}_j$.

- **SN-TERMINATION.** If a correct process $p_i$ invokes `shortnaming_Claim(pk, \pi)$, then eventually $\langle \star, pk, \star \rangle \in \text{Names}_i$.

The SN-SHORT-NAMES property captures the fact that the names given to the processes are as short as possible, thereby being easy to remember for humans. If there are no Byzantine processes, each name should be the smallest possible when comparing it to other attributed names. The property only considers this difference eventually, i.e., while a process might have successfully claimed a name, it may take a long time for the process it was concurring with to get its own name.

**Existing shortnaming approaches.** Existing systems follow either of two approaches, which, however, do not solve exactly the shortnaming problem.

- 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].

- 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).

**Solving shortnaming with CAC.** Assuming perfect public/private keys, the CAC primitive makes it possible to satisfy the SN-SHORT-NAMES property of shortnaming 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 "abcdefghij". It will first claim the name "a" using one instance of the CAC primitive. If there is no conflict, i.e., if the size of the *candidates* set is 1 after the first acceptance, then the name "a" 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 "a" and the size of the candidate set is strictly greater than 1 after the first acceptance, then $p$ claims the name "ab". 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 "abcdefghij". 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 shortnaming problem in the full version of this paper.
## 5.2 A “synchronize only when needed” CAC-based consensus algorithm: Cascading Consensus

**Consensus definition.** 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.

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

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

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

- 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.

**A novel CAC-based cascading consensus algorithm.** 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 circumstance 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, 37, 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, 37, 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 $\Pi'$ of processes to agree on a set of values, and to prove to the rest of the system that all the processes in $\Pi'$ 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 *candidates*$_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 *candidates*$_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 *candidates*$_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 *candidates* 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 *ℓ* processes that execute RC have to send a message to all other *ℓ*−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
<table><caption>Table 2 Notations for the different abstractions used in this section.</caption><thead><tr><th>Abstraction</th><th>Operations</th><th>Communication</th><th># participants</th></tr></thead><tbody><tr><td>Contention-Aware Cooperation (CAC)</td><td>cacpropose(v)<br>cacaccept(v, i)</td><td>Asynchronous</td><td>n</td></tr><tr><td>Cascading Consensus (CC)</td><td>cconspropose(v)<br>cconsdecide(v)</td><td>Async. for whole system<br>Sync. for RC</td><td>n</td></tr><tr><td>Restrained Consensus (RC)</td><td>rconspropose(v)<br>rcons_select(E, S<sub>e</sub>, S<sub>r</sub>)<br>rcons_no_selection()</td><td>Synchronous</td><td>l<br>(where typically l &lt;&lt; n)</td></tr><tr><td>Global Consensus (GC)</td><td>gconspropose(v)<br>gconsdecide(v)</td><td>Any</td><td>n</td></tr></tbody></table>

<table><caption>Table 3 Summary of the “progressively degrading” conditions of Cascading Consensus (instantiated with the optimal CAC algorithm presented in the full version of this paper, and their associated round complexity.</caption><thead><tr><th>Condition</th><th>Assumpt. needed</th><th>Execution path</th><th>Nb of system-wide rounds</th><th>Nb of RC rounds</th></tr></thead><tbody><tr><td>Unanimity (fast path)</td><td>n > 5t</td><td>CAC<sub>1</sub> (fast path)</td><td>2</td><td>N/A</td></tr><tr><td>Unanimity (slow path)</td><td>n > 3t</td><td>CAC<sub>1</sub> (slow path)</td><td>3</td><td>N/A</td></tr><tr><td>All procs of RC correct and sync.</td><td>n > 5t</td><td>CAC<sub>1</sub>; RC;<br>CAC<sub>2</sub> (fast path)</td><td>4</td><td>1</td></tr><tr><td>All procs of RC correct and sync.</td><td>n > 3t</td><td>CAC<sub>1</sub>; RC;<br>CAC<sub>2</sub> (slow path)</td><td>5</td><td>1</td></tr><tr><td>≥ 1 Byzantine proc. in RC or async. period</td><td>n > 3t</td><td>CAC<sub>1</sub>; RC;<br>CAC<sub>2</sub>; GC</td><td>5 + GC<br>rounds</td><td>1</td></tr></tbody></table>

where in the algorithm a process terminates by listing the sub-algorithm instances (noted CAC₁, RC, CAC₂, 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.<fnref n="11" />

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

# 6 Conclusion

The paper has introduced a new cooperation abstraction denoted “Contention-Aware Cooperation” (CAC). This abstraction allows an arbitrary set of processes to propose values while multiple value acceptances are triggered. Furthermore, each acceptance comes with information about other acceptances that can possibly occur. This paper is the first to formalize such a cooperation abstraction. Two implementations of CAC have been presented. The first one is a simple algorithm that works in asynchronous networks when $n > 4t$. The second is a latency and Byzantine resilient optimal implementation, which uses fine-tuned thresholds to improve efficiency and reduce the probability of contention. This second

<footnote n="11">¹¹ In 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$.</footnote>
implementation works in three asynchronous rounds if $n > 3t$ and in two asynchronous rounds in favorable cases when $n > 5t$.

This new cooperation abstraction can be used in low-contention distributed applications to improve efficiency or remove the need for synchronization. The paper proposed two such examples, where the CAC abstraction can be used to build distributed algorithms. The first is an optimistically terminating consensus algorithm denoted Cascading Consensus. This algorithm (as some other consensus algorithms, e.g., [10, 52]), can optimistically terminate when there is no contention or when the inputs satisfy specific patterns. However, differently from other algorithms that do not use the CAC abstraction, Cascading Consensus is the first to use information about contention to restrain synchronization to the processes that actually proposed a value. Furthermore, unlike other optimistically terminating consensus algorithms, cascading consensus terminates optimistically even if multiple processes propose different values. The second example is a short-naming algorithm, which works deterministically in fully asynchronous networks. It allows processes to claim shorter names based on their public keys. However, contrary to other asynchronous naming algorithms, the claimed name is a sub-string of the public key, thus reducing the size of the name space, making it easier for humans to handle. This paper is the first to introduce this new solution for the naming problem, where the entropy of names can be reduced in fully asynchronous networks, where processes can be faulty.

More generally, the CAC abstraction can be used to optimistically or deterministically solve other distributed cooperation problems where contention is low, e.g., shared account asset-transfer protocols [5, 14, 29], or distributed access control mechanism [25, 27]. These applications will be explored in future work.

Finally, another interesting direction for future work would be to design an algorithm that implements CAC without cryptographic signatures, or to prove that such an algorithm does not exist.

References

[1] Michael Abd-El-Malek, Gregory R. Ganger, Garth R. Goodson, Michael K. Reiter and Jay J. Wylie. Fault-scalable Byzantine fault-tolerant services. *Proc. 20th ACM Symposium on Operating Systems Principles (SOSP'05)*, 39:59–74, 2005.

[2] Timothé Albouy, Davide Frey, Mathieu Gestin, Michel Raynal and François Taïani. Contention aware cooperation. *CoRR*, abs/2311.08776, 2025. DOI: 10.48550/ARXIV.2311.08776. arXiv: 2311.08776. URL: https://doi.org/10.48550/arXiv.2311.08776.

[3] Hagit Attiya, Antonella Del Pozzo, Alessia Milani, Ulysse Pavloff and Alexandre Rapetti. The Synchronization Power of Auditable Registers. In *Alysson Bessani, Xavier Défago, Junya Nakamura, Koichi Wada and Yukiko Yamauchi, editors, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)*, volume 286 of *Leibniz International Proceedings in Informatics (LIPIcs)*, 4:1–4:23, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. ISBN: 978-3-95977-308-9. DOI: 10.4230/LIPIcs.OPODIS.2023.4. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.4.

[4] Hagit Attiya and Jennifer L. Welch. Multi-valued connected consensus: A new perspective on crusader agreement and adopt-commit. In *OPODIS*, volume 286 of *LIPIcs*, 6:1–6:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.
[5] Alex Auvolat, Davide Frey, Michel Raynal and François Taïani. Money transfer made simple: a specification, a generic algorithm, and its proof. *Bulletin of EATCS*, 132:22–43, 2020.

[6] Michael Ben-Or. Another advantage of free choice (extended abstract): completely asynchronous agreement protocols. In *Proc. 2nd ACM Symposium on Principles of Distributed Computing (PODC'83)*, pages 27–30, 1983.

[7] Christian Berger, Lívio Rodrigues, Hans P. Reiser, Vinicius Cogo and Alysson Bessani. Chasing lightspeed consensus: fast wide-area Byzantine replication with mercury. In *Middleware'24*, pages 158–171. Association for Computing Machinery, 2024. DOI: 10.1145/3652892.3700756.

[8] Zohir Bouzid, Achour Mostéfaoui and Michel Raynal. Minimal synchrony for Byzantine consensus. In *Proc. 34th ACM Symposium on Principles of Distributed Computing (PODC'15)*, pages 461–470. ACM, 2015.

[9] Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols. *J. ACM*, 32(4):824–840, 1985.

[10] Francisco Vilar Brasileiro, Fabíola Gréve, Achour Mostéfaoui and Michel Raynal. Consensus in one communication step. In *Proc. 6th International Conf. on Parallel Computing Technologies (PaCT'01)*, LNCS 2127, pages 42–50. Springer, 2001.

[11] Vitalik Buterin. Ethereum: a next-generation smart contract and decentralized application platform. 2014.

[12] Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance and proactive recovery. *ACM Trans. Comput. Syst.*, 20(4):398–461, 2002.

[13] Tushar Deepak Chandra, Vassos Hadzilacos and Sam Toueg. The weakest failure detector for solving consensus. *J. ACM*, 43(4):685–722, 1996.

[14] Daniel Collins, Rachid Guerraoui, Matteo Monti, Athanasios Xygkis, Matej Pavlovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi and Andrei Tonkikh. Online payments by merely broadcasting messages. In *Proc. 50th Int'l Conference on Dependable Systems and Network (DSN20)*, pages 1–13. IEEE, 2020.

[15] James Cowling, Daniel Myers, Barbara Liskov, Rodrigo Rodrigues and Liuba Shrira. HQ replication: a hybrid quorum protocol for Byzantine fault tolerance. In *Proc. 7th Symposium on Operating Systems Design and Implementation (OSDI'06)*, pages 177–190, 2006.

[16] Danny Dolev. The Byzantine generals strike again. *J. Algorithms*, 3(1):14–30, 1982.

[17] Danny Dolev, Cynthia Dwork and Larry J. Stockmeyer. On the minimal synchronism needed for distributed consensus. *J. ACM*, 34(1):77–97, 1987.

[18] Sisi Duan, Michael K. Reiter and Haibin Zhang. BEAT: asynchronous BFT made practical. In *Proc. 25th ACM SIGSAC Conference on Computer and Communications Security (CCS'18)*, pages 2028–2041. ACM, 2018.

[19] Cynthia Dwork, Nancy A. Lynch and Larry J. Stockmeyer. Consensus in the presence of partial synchrony. *J. ACM*, 35(2):288–323, 1988. DOI: 10.1145/42282.42283. URL: https://doi.org/10.1145/42282.42283.

[20] Paul Feldman and Silvio Micali. Optimal algorithms for byzantine agreement. In *STOC*, pages 148–161. ACM, 1988.

[21] Pesech Feldman and Silvio Micali. An optimal probabilistic protocol for synchronous Byzantine agreement. *SIAM J. Comput.*, 26(4):873–933, 1997.

[22] Md. Sadek Ferdous, Audun Jøsang, Kuldeep Singh and Ravishankar Borgaonkar. Security usability of petname systems. In *Identity and Privacy in the Internet Age*, pages 44–59, 2009.
[23] Michael J. Fischer, Nancy A. Lynch and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. *J. ACM*, 32:374–382, 1985.

[24] Sovrin Foundation. Sovrin: A Protocol and Token for Self-Sovereign Identity and Decentralized Trust. Technical report, Sovrin Foundation, 2018.

[25] Davide Frey, Matthieu Gestin and Michel Raynal. The synchronization power (consensus number) of access-control objects: the case of allowlist and denylist. In *Proc. 37th Int'l Symposium on Distributed Computing (DISC'23)*, volume 281 of *LIPICs*, 21:1–21:23, 2023.

[26] Eli Gafni. Round-by-round fault detectors: unifying synchrony and asynchrony (extended abstract). In *Proc. 17th ACM Symposium on Principles of Distributed Computing (PODC'98)*, pages 143–152. ACM, 1998.

[27] Mathieu Gestin. *Privacy Preserving and fully-Distributed Identity Management Systems*. PhD thesis, Université de Rennes, 2024.

[28] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos and Nickolai Zeldovich. Algorand: scaling Byzantine agreements for cryptocurrencies. In *Proc. 26th Symposium on Operating Systems Principles (SOSP'17)*, pages 51–68. ACM, 2017.

[29] Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovič and Dragos-Adrian Seredinschi. The consensus number of a cryptocurrency. *Distributed Computing*, 35:1–15, 2022.

[30] P. Hoffman. Dns security extensions (dnssec), 2023.

[31] N Johnson and V Griffith. Ethereum name service, 2018.

[32] Harry A Kalodner, Miles Carlsten, Paul M Ellenbogen, Joseph Bonneau and Arvind Narayanan. An empirical study of namecoin and lessons for decentralized namespace design. In *WEIS*, volume 1, pages 1–23, 2015.

[33] Lefteris Kokoris-Kogias, Alberto Sonnino and George Danezis. Cuttlefish: expressive fast path blockchains with fastunlock. *CoRR*, abs/2309.12715, 2023. DOI: 10.48550/ARXIV.2309.12715. arXiv: 2309.12715. URL: https://doi.org/10.48550/arXiv.2309.12715.

[34] Ramakrishna Kotla, Lorenzo Alvisi, Michael Dahlin, Allen Clement and Edmund L. Wong. Zyzzyva: speculative Byzantine fault tolerance. *ACM Trans. Comput. Syst.*, 27(4):7:1–7:39, 2009. DOI: 10.1145/1658357.1658358. URL: https://doi.org/10.1145/1658357.1658358.

[35] Petr Kuznetsov, Andrei Tonkin and Yan Zang. Revisiting optimal resilience of fast Byzantine consensus. In *Proc. 40th ACM Symposium on Principles of Distributed Computing (PODC'21)*, pages 343–353, 2021.

[36] Leslie Lamport. Fast Paxos. *Distributed Computing*, 19:79–103, 2006.

[37] Leslie Lamport. Lower bounds for asynchronous consensus. *Distributed Computing*, 19:104–125, 2006.

[38] Leslie Lamport. The part-time parliament. *ACM Trans. Comput. Syst.*, 16(2):133–169, 1998.

[39] Leslie Lamport, Robert E. Shostak and Marshall C. Pease. The Byzantine generals problem. *ACM Trans. Program. Lang. Syst.*, 4(3):382–401, 1982.

[40] Jean-Philippe Martin and Lorenzo Alvisi. Fast Byzantine consensus. *IEEE Trans. Dependable Secur. Comput.*, 3(3):202–215, 2006.

[41] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi and Dawn Song. The honey badger of BFT protocols. In *Proc. 23rd ACM Conference on Computer and Communications Security (CCS'16)*, pages 31–42, 2016.
[42] Achour Mostéfaoui, Hamouma Moumen and Michel Raynal. Signature-free asynchronous binary Byzantine consensus with $t > n/3$, $O(n^2)$ messages, and $O(1)$ expected time. *J. ACM*, 2015.

[43] Achour Mostéfaoui and Michel Raynal. Low cost consensus-based atomic broadcast. In *Proc. 2000 Pacific Rim International Symposium on Dependable Computing (PRDC'00)*, pages 45–52. IEEE Computer Society, 2000.

[44] Alexander Mühle, Andreas Grüner, Tatiana Gayvoronskaya and Christoph Meinel. A survey on essential components of a self-sovereign identity. *Computer Science Review*, 30:80–86, November 2018. doi: 10.1016/j.cosrev.2018.10.002.

[45] Satoshi Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System. Technical report, March 2009. URL: https://bitcoin.org/bitcoin.pdf.

[46] Rafael Pass and Elaine Shi. Thunderella: blockchains with optimistic instant confirmation. In Jesper Buus Nielsen and Vincent Rijmen, editors, *Advances in Cryptology – EUROCRYPT 2018*, pages 3–33, 2018.

[47] Marshall Pease, Robert Shostak and Leslie Lamport. Reaching agreement in the presence of faults. *J. ACM*, 27:228–234, 1980.

[48] Fernando Pedone and André Schiper. Optimistic atomic broadcast: a pragmatic viewpoint. *Theor. Comput. Sci.*, 291(1):79–101, 2003.

[49] HariGovind V. Ramasamy and Christian Cachin. Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast. In *Principles of Distributed Systems*, pages 88–102, 2006.

[50] Michel Raynal. *Concurrent programming: Algorithms, principles and foundations*. Springer, 2013, pages 1–515.

[51] Michel Raynal. *Fault-tolerant message-passing distributed systems: an algorithmic approach*. Springer, 2018, pages 1–459.

[52] Jakub Sliwinski, Yann Vonlanthen and Roger Wattenhofer. Consensus on demand. In *Proc. 24th Int'l Symposium on Stabilization, Safety, and Security of Distributed Systems*, volume 13751 of LNCS, pages 299–313. Springer, 2022.

[53] Yee Jiun Song and Robbert van Renesse. Bosco: one-step Byzantine asynchronous consensus. In *22nd Int'l Symposium on Distributed Computing*, volume 5218 of LNCS, pages 438–450. Springer, 2008.

[54] Gadi Taubenfeld. *Synchronization algorithms and concurrent programming*. Pearson Education/Prentice Hall, 2006.

[55] Andrei Tonkikh, Pavel Ponomarev, Petr Kuznetsov and Yvonne-Anne Pignolet. Crypto-concurrency: (almost) consensusless asset transfer with shared accounts. In *Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security*, CCS '23, pages 1556–1570. Association for Computing Machinery, 2023. doi: 10.1145/3576915.3616587.

[56] Dennis Trautwein, Aravindh Raman, Gareth Tyson, Ignacio Castro, Will Scott, Moritz Schubotz, Bela Gipp and Yiannis Psaras. Design and evaluation of ipfs: a storage layer for the decentralized web. In *Proceedings of the ACM SIGCOMM 2022 Conference, SIGCOMM '22*, pages 739–752. ACM, August 2022. doi: 10.1145/3544216.3544232. URL: http://dx.doi.org/10.1145/3544216.3544232.

[57] Bret Victor. Tripphrases. http://worrydream.com/tripphrase/, 2008. Accessed: 2023-12-11.

[58] Daniel Shawcross Wilkerson. A proposal for Proquints: identifiers that are readable, spellable, and pronounceable. CoRR, abs/0901.4016, 2009. arXiv: 0901.4016. URL: http://arxiv.org/abs/0901.4016.
[59] Jiong Yang, Gil Neiger and Eli Gafni. Structured derivations of consensus algorithms for failure detectors. In *PODC*, pages 297–306. ACM, 1998.

[60] Piotr Zielinski. Optimistically terminating consensus: all asynchronous consensus protocols in one framework. In *Fifth International Symposium on Parallel and Distributed Computing*, pages 24–33, 2006. DOI: 10.1109/ISPDC.2006.37.

[61] Piotr Zielinski. Optimistically terminating consensus: all asynchronous consensus protocols in one framework. In *Proc. 5th Int'l Symposium on Parallel and Distributed Computing (ISPDC'06)*, pages 24–33. IEEE Computer Society, 2006.