# Process-commutative distributed objects: From cryptocurrencies to Byzantine-Fault-Tolerant CRDTs

Davide Frey, Lucie Guillou, Michel Raynal, François Taïani

► To cite this version:

Davide Frey, Lucie Guillou, Michel Raynal, François Taïani. Process-commutative distributed objects: From cryptocurrencies to Byzantine-Fault-Tolerant CRDTs. Theoretical Computer Science, 2024, 1017, pp.114794. 10.1016/j.tcs.2024.114794. hal-04889162

HAL Id: hal-04889162

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

Submitted on 15 Jan 2025

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 Attribution 4.0 International License
Process-Commutative Distributed Objects:
From Cryptocurrencies
to Byzantine-Fault-Tolerant CRDTs

Davide Frey, Lucie Guillou, Michel Raynal, François Taïani

September 27, 2024

Abstract

The aim of this work is to characterize a class of distributed objects that can be im-
plemented using simple algorithms where only a First In First Out (FIFO) order on the
object operations from each process (taken individually) is required. To this end, traces
are used to define a language over legal sequences of operations. To illustrate the proposed
approach, instances of this class of objects are presented, namely money transfer, Petri's
nets, multi-set, and concurrent work stealing queues.

# 1 Introduction

Blockchains and Distributed Ledger Technologies (DLT) have brought a fresh and growing in-
terest to Byzantine Fault Tolerance (BFT), a field initiated more than 40 years ago. BFT
algorithms allow most modern Blockchains and DLTs to enforce a total order (TO) on their
operations even in the face of malicious participants. Unfortunately, total ordering requires
solving Byzantine-Tolerant Agreement, a vexing problem that has long been known to be im-
possible to solve deterministically in asynchronous systems [8]. As a result, existing DLTs are
often particularly costly while striking a compromise regarding either termination or their guar-
antees [9]—for instance, by only providing probabilistic correctness guarantees (Bitcoin), or by
employing costly (randomized) synchronization mechanisms [10, 11].

Total ordering and Byzantine Agreement are, however, less central to Blockchains and DLTs
than first assumed. Recent works have shown that cryptocurrency objects, Blockchain's first and
perhaps most emblematic application, do not require a total order and can be implemented using
much weaker primitives, such as atomic registers or FIFO reliable broadcast. This realization
has far-reaching consequences, both practically and theoretically. In practice, it suggests that
trustless money transfer applications can be implemented much more efficiently than initial
implementations based on full-fledged BFT TO mechanisms (whether based on PoW, BFT
consensus, or PoS). From a theoretical viewpoint, it raises the question of characterizing the class
of BFT distributed objects that can be directly implemented using a plain FIFO broadcast, as
reliable (FIFO) broadcast is a much weaker primitive (computationally) than atomic registers<fnref n="1" />

Using weak synchronization for distributed objects is not new. It has been extensively ex-
plored in the context of Conflict-free Replicated Data Types (CRDTs), a broad family of weakly
synchronized distributed data structures. CRDTs eschew the need for advanced synchroniza-
tion through systematic reconciliation. This pragmatic approach makes them highly scalable,

<footnote n="1">¹When faced with crashes, atomic registers require at least a majority of correct processes, while reliable broadcast imposes no such constraint.</footnote>
robust to transient disconnections and crashes, and particularly attractive when implementing large-scale decentralized services.

Over the last few years, several designs for Byzantine-tolerant CRDTs have been proposed that combine the strengths of traditional CRDTs with the robustness of BFT algorithms. Unfortunately, because CRDTs are not designed to block conflicting updates, these approaches cannot prevent duplicitous actions by malicious participants, which violate an application's invariant when combined. Instead, they remediate such attacks by canceling all or some of the incompatible operations when the problem is (eventually) detected. In particular, existing BFT CRDTs cannot prevent double spending, a problematic situation for cryptocurrency applications.

This paper is a step to chart the territory that lies between best effort BFT CRDTs and totally ordered distributed ledgers.

# 2 Background: System Model and the Trace Monoid

## 2.1 Message-passing computation in the presence of Byzantine advsersaries

The distributed system is composed of $n$ asynchronous processes denoted $p_1, ..., p_n$. Asynchronous means that each process proceeds to its own speed, which can vary with time and remains always unknown by the other processes.

Each pair of processes is connected by an asynchronous reliable bi-directional channel. Asynchronous means that the transfer delay of each message, taken individually, is arbitrary but finite, reliable means that there is neither message corruption, creation, nor message losses.

Two types of process failures are considered.

* A process crash failure is a premature and definitive stop of a process while it is executing its algorithm. The notation $CAMP_{n,t}[\emptyset]$ is used to denote the previous asynchronous distributed computing model in which any number of processes are allowed to crash. The notation $CAMP_{n,t}[t < a]$ is used to denote it when the number of processes allowed to crash is restricted to be strictly smaller than $a$.

* A Byzantine process is a process that behaves arbitrarily, i.e., a process does not follow the code it is assumed to execute. The notation $BAMP_{n,t}[\emptyset]$ is used to denote the previous asynchronous distributed computing model in which up to $t < n$ processes are allowed to crash, while $BAMP_{n,t}[t < a]$ is used to denote it when the number of Byzantine processes is restricted to be strictly smaller than $a$.

## 2.2 Mazurkiewicz Traces

A trace monoid [12, 13, 14, 15] (or free partially commutative monoid, also known as Mazurkiewicz Traces) is a generalization of the notion of words (i.e., finite sequences) over an alphabet $\Sigma$ that naturally captures parallelism and conflicts between operations (represented by the letters of the alphabet).

A trace monoid over an alphabet $\Sigma$ is defined by a symmetric independency relation $I \subseteq \Sigma \times \Sigma$ between the letters (or operations) of $\Sigma$. $(a, b) \in I$ means that the operations $a$ and $b$ commute, so that the effect of $ab$ and $ba$ are equivalent. Two (finite) words $u, v \in \Sigma^*$ are said to be equivalent under $I$, noted $u \sim_I v$ iff one can transform $u$ into $v$ (and reciprocally) by exchanging adjacent operations that are independent within $u$.

The relation $\sim_I$ is an equivalence relation over $\Sigma^*$, and a (finite) trace $t$ is simply an equivalence class of $\sim_I$ within $\Sigma^*$. $\sim_I$ is a congruence for the concatenation operator (noted $\oplus$, but
generally omitted), i.e if $x \sim_I y$ and $u \sim_I v$, then $xu \sim_I yv$. As a result, the concatenation over words translates to the set of traces, with $[u]_I[v]_I = [uv]_I$, where $u, v \in \Sigma^*$ are words over $\Sigma$, and $[u]_I$ is the trace represented by $u$ (u's equivalence class under $\sim_I$). The resulting structure $(\Sigma^* / \sim_I, \oplus)$ is the free partially commutative monoid defined by $\Sigma$ and $I$, noted $M(\Sigma, I)$, or $M(\Sigma)$ for short. As for words, a subset of $M(\Sigma, I)$ is called a trace language.

In the following, unless ambiguous, we will usually note a trace using one of its representative elements (i.e. $ab$ instead of $[ab]_I$).

# 3 Process-Commutative Objects

As already indicated, this paper uses traces to characterize the set of distributed objects (or data structures) that can directly be implemented using a FIFO Byzantine-Tolerant Reliable Broadcast.

## 3.1 Operations

A Process-Commutative Object is a distributed data structure that accepts two types of operations, updates and queries, while obeying a small number of rules on the effect and interaction of these operations.

* Updates modify the datastructure. Updates might return a value (which reflects the datastructure's state). If they do not, they are said to be silent. The set of update operations is noted $\Sigma$.

* Queries do not modify the datastructure, but returns a value, that deterministically depends on the datastructure's state. The set of query operations is noted $Q$.

Any process may execute any query, but some updates operations are only allowed to some processes. More specifically, the set of updates $\Sigma$ is made of $n + 1$ subsets, $\Sigma = C \cup \bigcup_{p_i \in \Pi} O_i$, where

* $C$ is the set of common updates, which is accessible to all processes, and commute with any other operations;

* $O_i$ are updates that are exclusive to process $p_i$, and do not commute with each other.

The sets $C$, and $O_i$ induce an independency relation $I$ over $\Sigma$:

$$I = \Sigma \times \Sigma \setminus \bigcup_{p_i \in \Pi} (O_i \times O_i).$$

Given some update operation $up \in \Sigma$, we note $output(up, v)$ the value returned by $up$ when it is applied to the trace $v$:

$$ \text{output: } \Sigma \times M(\Sigma) \rightarrow \mathbb{V}, \\ (up, v) \mapsto output(up, v), $$

where $\mathbb{V}$ is a set of possible output values. When $up$ is silent, $output(up, v)$ should return some pre-determined constant value (e.g. $\perp$) for all $v$.
## 3.2 Sequential Specification

### 3.2.1 PCO specification

A Process-Commutative Object is specified by a tuple $(C, (O_k)_k, L, Q)$ where

i) $C$ and $(O_k)_k$ are the sets of common and process-specific updates introduced just before,

ii) $L$ is a language of finite traces over the free partially commutative monoid $M(\Sigma, I)$ defined over the object's update operations $\Sigma = C \cup \bigcup_{p_i \in \Pi} O_i$ with the independence relation $I \subseteq \Sigma \times \Sigma$ defined earlier,

iii) and $Q = \{q_k\}_k$ is a set of query functions $q_k : L \to V$, where $V$ is a set of application-dependent output values.

$L$ must further fulfill the following three properties:

*   **Initial emptiness:** the empty trace is part of $L$: $[\epsilon]_I \in L$.

*   **$C^*$-Closure:** $L$ is closed by concatenation with traces of common updates: $LC^* \subseteq L$.

*   **I-diamond Closure:** Given $v \in L$, an update $op_i \in O_i$ exclusive to some process $p_i$, and some trace of updates $z \in M(\Sigma \setminus O_i)$ that are independent of $o_i$, if $\{v \oplus op_i, v \oplus z\} \subseteq L$ then $v \oplus z \oplus op_i \in L$.

### 3.2.2 PCO-legal sequential execution

A sequential execution $S$ of a Process-Commutative Object specified by $(C, (O_k)_k, L, Q)$ is a sequence of invocations $S = (e_k)_k$, where each invocation is labeled by an operation $op$ from $\Sigma \cup Q$, a return value $val$ from $V \cup \{?_V\}$ ($?_V \notin V$) represents a masked value which will serve to specify distributed PCO executions; values which are not masked are said to be visible), and the process $p$ that invokes the operation. We note $e_k = (op, val, p)$.<fnref n="2" />

$S$ is Process-Commutative-Object-legal (PCO-legal for short) w.r.t. $(C, (O_k)_k, L, Q)$ if the following holds:

*   **Process Authorization.** Each operation is invoked by a process authorized to execute it: $\forall (op, val, p_i) \in S, op \in C \cup O_i \cup Q$.

*   **Update Legality.** Each prefix of updates of $S$ represents a legal trace:

$$ \forall u \in \Sigma^*, \text{ if } \exists v \in \Sigma^* \text{ such that } u \oplus v = \text{proj}_{\Sigma}(S), \text{ then } [u]_I \in L, $$

where $\text{proj}_{\Sigma}(S)$ is the sequence of update operations in $S$;

*   **Output and Query Validity.** Each query reads from the sequence of updates up to its invocation: if $e_k = (q, val, p)$, with $q \in Q$, then $val = q([\text{proj}_{\Sigma}(S_{<k})]_I)$, where $S_{<k} = (e_\ell)_{\ell \in [1..k-1]}$ is the sequence of invocations that precedes $e_k$.

Similarly, each update associated with a visible value (i.e. $val \neq ?_V$) returns the output obtained from the sequence of updates up to the update's invocation: if $e_k = (\text{up}, val, p)$ with $\text{up} \in \Sigma$ and $val \neq ?_V$, then $val = \text{output}(\text{up}, [\text{proj}_{\Sigma}(S_{<k})]_I)$, where $S_{<k}$ is defined as above.

<footnote n="2">²This is equivalent to defining sequential executions as words over the alphabet $(\Sigma \cup Q) \times (V \cup \{?_V\}) \times \Pi$.</footnote>
## 3.3 A few remarks on the difference between a trace and a word language

The kind of specification of Section 3.2 is reminiscent of that used to define sequential objects using word languages (i.e. subsets of $\Sigma^*$). As with words, a trace $u \in L$ can be understood as a labeled order of operations that contains enough information to determine the state of a PCO object $o$. More specifically, $u$ captures enough information to determine the output of any query function, and together with $L$, $u$ determines which subsequent operations are legal (any operation $op$ such that $u \oplus op \in L$).

The use of traces rather than words introduces however some subtle yet important changes. In a word-based specification, the sequence of operations that produces a word $s$ is unique. As a result, if $s$ is legal, any prefix of $s$ will typically be legal as well (otherwise $s$ cannot be reached). This is not the case with traces. Because the order between operations that is encoded in a trace is partial rather than total, the sequence of successive operations that leads to a trace $u$ is not unique, and the fact that $u$ is legal does not imply that all its prefixes necessarily are.

As an illustration, consider a simple token ring object with two processes $p_A$ (for Alice) and $p_B$ (for Bob), and two update operations $t_{AB}$ (the token goes from Alice to B) and $t_{BA}$ (the token goes from Bob to Alice). A token ring in which the token starts with Alice can be encoded by the trace language $L = \{u \in M(\Sigma, I) | 0 \le \mathbf{1}_u(t_{AB}) - \mathbf{1}_u(t_{BA}) \le 1\}$, with $\Sigma = \{t_{AB}, t_{BA}\}$, $t_{AB} \sim_I t_{BA}$, and where $\mathbf{1}_u(\mathbf{op})$ indicates the number of times the operation $\mathbf{op}$ appears in the trace $u$.

The trace $u_5$ represented in Eq. 1 (shown as a Hasse diagram, with smaller elements on the left) is a legal trace of $L$. $u_5$ denotes the state in which the token is with Bob, after five token exchanges, and the only legal action after $u_5$ is $t_{BA}$. By contrast, the trace $v$ shown in Eq. 2 is not legal (does not belong to $L$)—as Bob cannot transfer twice the token to Alice without ever receiving it from her.

$$ u_5 = \left( \begin{array}{c} t_{AB} - t_{AB} - t_{AB} \\ t_{BA} - t_{BA} \end{array} \right), \qquad (1) $$

$$ v = \left( t_{BA} - t_{BA} \right). \qquad (2) $$

This may be surprising as $v$ is a prefix of $u_5$, and seems to lead to an apparent paradox as we do here, but an apparent contradiction arises if we return to the initial “constructionist” definition of traces, as equivalence classes of the relation $\sim_I$ on words. Under this definition, the word $t_{BA}t_{BA}t_{AB}t_{AB}$ belongs to the trace $u$, yet, although the trace $u$ is legal, the word $t_{BA}t_{BA}t_{AB}t_{AB}$ does not represent a legal sequence of operations on the token-ring object, which must alternate $t_{AB}$ and $t_{BA}$, and cannot start with $t_{BA}$. The key point to note here is that the fact that $u \in L$ is legal does not imply that all representative words of $u$ correspond to possible sequential executions of the object encoded by $L$ (only some do typically). The use of traces however helps stress the indistinguishably (in terms of queries and future operations) between those words of $u$ that are possible under $L$ (i.e. the words $w \in u$ such that $\{[v]_I | v$ is a prefix of $w\} \subseteq L$).

## 3.4 Distributed Histories, Perceived Histories

### 3.4.1 Histories

* A local execution (or history) of a process $p_i$, denoted $E_i$, is a sequential execution $(e_k)_k = (\mathbf{op}_k, val_k, p_i)_k$ in which every operation is invoked by $p_i$, and authorized to $p_i$, i.e. $\mathbf{op}_k \in C \cup O_i \cup Q$, and each returned value is known, i.e. $val_k \neq ?_V$. If an invocation $e_{k_1} =$
(op$_{k_1}$, val$_{k_1}$, p$_i$) precedes an invocation e$_{k_2}$ = (op$_{k_2}$, val$_{k_2}$, p$_i$) (i.e. k$_1$ < k$_2$), we write e$_{k_1}$ →$_i$ e$_{k_2}$, or for short op$_{k_1}$ →$_i$ op$_{k_2}$. →$_i$ is the local process order for p$_i$.

* A history $H$ is a set of $n$ local histories, one per process, $H = (E_1, \dots, E_n)$.

* Given a history $H$ and a process $p_i$, we define $p_i$'s perception of $H$ ($p_i$'s perceived history of $H$) as the history $\hat{H}_i$ in which all query operations save those of $p_i$ have been removed. Formally, $\hat{H}_i = (\hat{E}_1, \dots, \hat{E}_n)$ with:

$$- \hat{E}_i = E_i,$$

$$- \hat{E}_j = \text{proj}_{(\Sigma \times \{?_v\} \times \{p_j\})}(E_j),$$

where $\text{proj}_{(\Sigma \times \{?_v\} \times \{p_j\})}(E_j)$ represents the sequence of invocations obtained by removing all queries from $E_j$, and by masking the output values of the remaining updates, i.e. replacing $e_k = (\text{up}_k, \text{val}_k, p_j) \in E_j$ by $e'_k = (\text{up}_k, ?_v, p_j)$.

### 3.4.2 Serialization

* A *serialization* $S$ of a history $H$ is a sequential execution which contains all invocations of $H$ and respects each local process order ($\rightarrow_i$)$_{1 \le i \le n}$.

* Given a history $H$ and a process $p_i$, a *local serialization* $S_i$ is a serialization of the history $\hat{H}_i$.

## 3.5 Distributed Process-Commutative Objects

### 3.5.1 Process-Commutative Objects in CAMP$_{n,t}$[0]

**Definition 1** (Distributed PCO in the crash fault model). In the $CAMP_{n,t}[0]$ model, a distributed objects implements the PCO specification $(C, (O_k)_k, L, Q)$ if it provides each process $p_i$ with the operations $op \in C \cup O_i \cup Q$ and is such that, for each of its executions, represented by the corresponding history $H$, we have:

* All the operations invoked by correct processes terminate.

* There is a crash-corrected history $H' = (E'_1, \dots, E'_n)$ defined as follows:

- $E'_i = E_i$ if $p_i$ is correct,

- $E'_i$ is either equal to $E_i$, or equal to $E_i$ minus its last element if $p_i$ is faulty.<fnref n="3" />

- For any process $p_i$, there is a PCO-legal serialization $S_i$ of $\hat{H}'_i$.

The above definition insures that a correct process $p_i$ eventually sees all updates issued by other processes (correct or not), minus possibly the last update of crashed processes. The returned value of local updates (performed by $p_i$) and local queries must be explainable by the serialization $S_i$. The outputs of updates performed by remote processes $p_j \neq p_i$ are however masked to $p_i$ through the projection $\text{proj}_{(\Sigma \times \{?_v\} \times \{p_j\})}(-)$ (Section 3.4.1), and do not need to agree with $S_i$.

<footnote n="3">³This models the fact that the last update operations invoked by a crashed process might remain invisible to other processes.</footnote>
### 3.5.2 Process-Commutative Objects in BAMP$_{n,t}$ [$t < n/3$]

The notion of local history $E_i$ is no longer meaningful for Byzantine processes because a Byzantine process can not only crash but can also simulate, omit, or otherwise disrupt operations, either invoked by itself or by others. In particular, there is no relation on a Byzantine process $p_b$ between the operations that an application executing on $p_b$ might invoke, and the behavior that $p_b$ exhibits on the network in terms of messages. To circumvent this disconnect, we introduce the notion of *mock local history* for Byzantine processes. A *mock local history* of a Byzantine process $p_b$ is a local history of $p_b$ that $p_b$ could have produced if it were correct, and that *explains* $p_b$'s behavior from the point of view of the system's correct processes. The system's correct processes implement a Process-Commutative Objects if they all behave in a manner consistent with the same set of mock local histories for the Byzantine processes.

More formally, we define a *mock history* associated with an execution $H$ of a Process-Commutative Object as $H' = (E'_1, \dots, E'_n)$ such that:

* $E'_i = E_i$ if $p_i$ is correct,

* $E'_i \subseteq (O_i \cup C)^*$ if $p_i$ is Byzantine (mock local history).

**Definition 2** (Distributed PCO in the Byzantine fault model). A PCO implements the PCO specification $(C, (O_k)_k, L, Q)$ in BAMP$_{n,t}$ [$t < n/3$] if

* All the operations invoked by correct processes terminate.

* For each of its executions represented by the corresponding history $H$, there is a mock history $H'$ such that, and for any correct process $p_i$, there is a PCO-legal serialization $S_i$ of $\hat{H}'_i$.

The above definition insures that correct processes can collectively explain what they observe (the mock history $H'$ is shared by all correct processes) by assigning some “virtual” behavior to Byzantine processes. The resulting “virtual processes” should be such that every correct process $p_i$ eventually sees all updates issued by virtual processes and by other correct processes. As in the crash-fault version, the returned value of local updates and local queries must be explainable by the serialization $S_i$. The outputs of updates performed by remote processes $p_j \neq p_i$ remain however masked to $p_i$.

## 4 A Generic Process-Commutative-Object Algorithm

Given a PCO specification $(C, (O_k)_k, L, Q)$ we propose a very simple algorithm that implements it in an asynchronous message passing system. This algorithm is generic in two important ways:

* It works with any PCO specification $(C, (O_k)_k, L, Q)$ (thus covering a wide range of relevant objects, including multisets, distributed Petri nets, crytpocurrencies and work-stealing objects, cf. Section 6.)

* It can be instantiated with different reliable broadcasts, from which it directly inherits its fault-tolerance assumptions and properties. If the broadcast is reliable in $CAMP_{n,t}[\emptyset]$, then our algorithm implements a PCO in $CAMP_{n,t}[\emptyset]$, according to the definition of Section 3.5. If used with a Byzantine reliable broadcast in $BAMP_{n,t}[t < n/3]$, then our algorithm implements a PCO in $BAMP_{n,t}[t < n/3]$, again according to the definition in Section 3.5.
From a computability point of view, we thus define and implement a family of objects that
can be realized in $CAMP_{n,t}[\emptyset]$, i.e. are implementable in asynchronous message-passing systems
suffering from an arbitrary number of crashes (up to $n$). These objects are thus computationally
strictly weaker than atomic RW memory registers (which require that at most a minority of
processes may crash $t < \frac{n}{2}$), and yet encompass a number of useful instances, as we shall see in
Sec.

## 4.1 Reliable broadcast

Following [16], our algorithm uses a multi-shot *reliable broadcast* abstraction with explicit sequence numbers, whose concrete implementation depends on the failure model. A reliable broadcast provides two operations denoted `r broadcast()` and `r deliver()`. When a process $p_i$ invokes `r broadcast(sn, m)$, we say "process *i* r-broadcasts the message *m* with sequence number *sn*", and when a process receives the broadcast $\langle sn, m \rangle$ from $p_i$, we say it "r-delivers *m* with sequence number *sn* from process *i*". The exact properties of the broadcast we use depend on the failure model we assume ($CAMP_{n,t}[\emptyset]$ or $BAMP_{n,t}[t < n/3]$), and we return to these properties in detail in Sections 5.2 and 5.3. We list below some of properties shared by these two broadcast abstractions:

* **Validity.** This property states that there is no message creation. To this end, it relates the outputs (r-deliveries) to the inputs (r-broadcasts). Excluding malicious behaviors, a message that is r-delivered has been r-broadcast.

* **Integrity.** This property states that there is no message duplication.

* **Termination-1.** This property states that correct processes r-deliver what they broadcast.

* **Termination-2.** This property relates the sets of messages r-delivered by different processes.

The Termination properties ensure that all the correct processes r-deliver the same set of
messages, and that this set includes at least all the messages that they r-broadcast.

## 4.2 Local data structure

All processes know the alphabet $\Sigma$ (i.e operations) and the specification of the language $L$
which define our Process-Commutative Object. Each process further maintain the following
local variables:

* $sn_i \in \mathbb{N}$: the sequence number of the last broadcasted message by $p_i$ (initialized to 0);

* $del_i[1..n] \in \mathbb{N}^n$: a local array of the sequence numbers of the last broadcast of each process that $p_i$ has so far processed (initialized to $[0, ..., 0]$);

* $seq_i \in \Sigma^*$: the sequence of update operations processed so far by process $p_i$ (initialized to $\epsilon$).
<figure><img src="image_2.png" /><figcaption>**Algorithm 1:** (code for $p_i$)</figcaption></figure>

## 4.3 Algorithm

$q$ and update denote functions such as $q \in Q$, and $update \in O_i \cup C$.

Algorithm 1 provides two apply functions, one for query operations (lines 2-3), and one for updates (lines 4-10). A query operation is purely local, and simply returns the result of the corresponding query function $q$ applied to $p_i$'s current sequence of observed update operations $seq_i$ (line 3).

When $p_i$ invokes apply for an update operation up (for short we will say that $p_i$ invokes up), this operation must be authorized for $p_i$ and legal (line 5). Assuming it is, $p_i$ computes the next sequence number $sn_i$ and r-broadcasts the pair $\langle sn_i, \text{APPLY}(\text{up}) \rangle$. The predicate at line 8 is satisfied when $p_i$ r-delivers its own broadcast at line 14, at which point the function returns.

When $p_i$ r-delivers a pair $\langle sn, \text{APPLY}(\text{up}) \rangle$ from $p_j$, it waits until it has processed each previous message sent by $p_j$ (FIFO order) and until its current sequence of operations $seq_i$ concatenated to the new operation is legal (line 12). Once those two conditions are satisfied, $p_i$ can update its sequence of operations and increase $del_i[j]$.

# 5 Proofs

## 5.1 Notation and definition

* Let $up_j^{sn}$ denote the update operation issued by $p_j$ with sequence number $sn$.

* We say a process $p_i$ processes the update operation $up_j^{sn}$ if, after it r-delivered the associated message $\langle sn, \text{APPLY}(up_j^{sn}) \rangle$, $p_i$ exits the wait statement at line 12 and executes the associated statements at lines 13-14.

* If the message $\langle sn, \text{APPLY}(up_j^{sn}) \rangle$ r-broadcast by $p_j$ (correct or not) is r-delivered by a correct process, we say that the update $up_j^{sn}$ is successful. (Let us notice that a message r-broadcast by a correct process is always successful.)
## 5.2 In the CAMP model

### 5.2.1 Multi-shot reliable broadcast abstraction in the crash failure model

This communication abstraction, named CR-Broadcast, is defined by the two operations `cr_broadcast()` and `cr_deliver()`. Hence, we use the terminology “to cr-broadcast a message”, and “to cr-deliver a message”.

* CRB-Validity: If a process $p_i$ cr-delivers a message with sequence number $sn$ from a process $p_j$, then $p_j$ cr-broadcasts it with sequence number $sn$.

* CRB-Integrity: For each sequence number $sn$ and sender $p_j$ a process $p_i$ cr-delivers at most one message with sequence $sn$ from $p_j$.

* CRB-Termination-1: If a correct process cr-broadcasts a message, it cr-delivers it.

* CRB-Termination-2: If a process cr-delivers a message from a (correct or faulty) process $p_j$, then all correct processes cr-deliver it.

### 5.2.2 Proof

**Lemma 1.** Any invocation of updates operations and query operations issued by a correct process terminates.

**Proof** The fact that the query operations terminates follows immediately from the codeof the operation.

When a process $p_i$ invokes `up`, it cr-broadcasts the message $\langle sn_i, \text{APPLY}(\text{up}) \rangle$. Because of the CRB-Termination-1 property, $p_i$ eventually cr-delivers its own message. By construction of the algorithm, $sn_i$ counts the number of r-broadcasts performed by $p_i$, while $del_i[i]$ counts the number of its own broadcasts that $p_i$ has already processed. The `wait` statement at line 8, implies that when $p_i$ invokes `up` all earlier updates invoked by $p_i$ have been processed, and no new update can be invoked (and hence processed, by CRB-Validity), until $p_i$ has processed `up`, which can occur only once by CRB-Integrity. As a result, the condition $sn = del_i[i] + 1$ is verified at line 12 when $p_i$ cr-delivers the message corresponding to `up`.

Turning to the second part of the predicate, the only updates that $p_i$ can process between the broadcast of `up` and its crb-delivery by $p_i$ are updates by other processes. As a result, if we note $seq_i^{\text{bcast}}$ the value of $seq_i$ when `up` is crb-broadcast at line 7, and $seq_i^{\text{deli}}$ its value when `up` is crb-delivered at line 12, then $seq_i^{\text{deli}} = seq_i^{\text{bcast}} \oplus z$ with $z \in (\Sigma \setminus O_i)^*$. Because of line 5, we have $[seq_i^{\text{bcast}} \oplus \text{up}]_I \in L$, and because of the second part of the condition at line 12, we have $seq_i^{\text{deli}} = seq_i^{\text{bcast}} \oplus z \in L$. Using the I-diamond Closure of $L$, we get that $[seq_i^{\text{bcast}} \oplus z \oplus \text{up}]_I \in L$, and hence that $[seq_i^{\text{deli}} \oplus \text{up}]_I \in L$, which concludes the proof. $\square_{Lemma 1}$

**Lemma 2.** If a process $p_i$ processes $up_i^{sn}$, then any correct process processes $up_i^{sn}$.

**Proof** we note $seq_i^k = m_1 \oplus \cdots \oplus m_{k-1} \oplus m_k$ the prefix of $seq_i$ of size $k$. We show by induction on $k$, that for every correct process $p_j$, and for every integer $k \le |seq_i|^4$, $seq_i^k$ eventually becomes a trace prefix of $seq_j$ (i.e. $[seq_j]_I = [seq_i^k]_I \oplus w$ for some trace $w$), which implies that $p_j$ eventually processes all operations of $seq_i^k$.

* Case $k = 0$, trivial

<footnote n="4">⁴By convention, we assume $|seq_i| = \infty$ when $seq_i$ is infinite, and $\infty - 1 = \infty$ just below.</footnote>
• $0 \le k \le |seq_i| - 1$, we suppose the induction property true for $k$. Let us consider $p_j$ a correct process. We first prove by contradiction that (A) $p_j$ eventually processes $m_{k+1}$, and then show this implies that (B) the property is true for $k + 1$.

**Part A:** Let us assume that $p_j$ never processes $m_{k+1}$. By induction hypothesis, at some point we have $[seq_j]_I = [seq_i^k]_I \oplus w$ for some $w$, and $p_j$ has processed $m_1, \dots, m_k$. Because of the CRB-Termination-2 property, $p_j$ eventually cr-delivers $m_{k+1}$. As $p_j$ never processes $m_{k+1}$, this means the condition at line 12 never becomes true. Let us note $m_{k+1} = \text{up}_l^{sn}$, and consider a time point after $\text{up}_l^{sn}$ has been cr-delivered, and after $[seq_j]_I = [seq_i^k]_I \oplus w$ for some $w$. A that point, we have

- Since messages of one process are processed in FIFO order, the fact that $\text{up}_l^{sn}$ is never processed by $p_j$ implies $\text{del}_j[l] \le sn - 1$. In addition, as $\text{up}_l^{sn}$ has been processed by $p_i$, $\text{up}_l^{sn-1}$ has been processed as well by $p_i$ and therefore $\text{up}_l^{sn-1} \in \{m_1 \cdots m_k\}$. By our induction hypothesis, $\text{up}_l^{sn-1}$ has been processed by $p_j$ and therefore $\text{del}_j[l] \ge sn - 1$. We conclude that $\text{del}_j[l] = sn - 1$.

- At this same instant, we know that

$$[seq_j]_I \in L \qquad (3)$$

(because of the statement at line 12, we only add operations that preserve $seq_j$'s legality.) If $\text{up}_l^{sn} \in C$, as $LC \subseteq L$ (by $C^*$-Closure), we have $[seq_j \oplus \text{up}_l^{sn}]_I \in L$, rendering the condition of line 12 true, and contradicting the fact that $\text{up}_l^{sn}$ is never processed. This implies that $\text{up}_l^{sn} \in O_l$. Because $p_i$ processes $\text{up}_l^{sn}$, we have

$$[seq_i^k]_I \oplus \text{up}_l^{sn} = [seq_i^k \oplus \text{up}_l^{sn}]_I \in L, \qquad (4)$$

due to the condition at line 12 when $p_i$ processed $\text{up}_l^{sn}$. By induction hypothesis, we also have

$$[seq_j]_I = [seq_i^k]_I \oplus w, \qquad (5)$$

for some $w$. Observing that the number of operations from $p_l$ in both $seq_i^k$ and $seq_j$ is exactly $sn - 1$, we infer that $w$ does not contain any operation from $p_l$:

$$w \in \mathbb{M}(\Sigma \setminus O_l). \qquad (6)$$

Combining Equations 3 to 6, we can apply the I-diamond closure property of $L$, and conclude that $[seq_j]_I \oplus \text{up}_l^{sn} = [seq_i^k]_I \oplus w \oplus \text{up}_l^{sn} \in L$, which means the second conditions at line 12 becomes true, that $\text{up}_l^{sn} = m_{k+1}$ is eventually processed by $p_j$, concluding Part A of the proof.

**Part B:** We know that $p_j$ eventually processes $\text{up}_l^{sn} = m_{k+1}$, and by induction hypothesis that eventually $[seq_j]_I = [seq_i^k]_I \oplus w$ for some trace $w$. Let us consider a time point when both statements have become true. As $seq_i^k$ already contains the $sn - 1$ first operations of $p_l$, $\text{up}_l^{sn}$ must appear in $w$, and we therefore have $[seq_j]_I = [seq_i^k]_I \oplus w_1 \oplus \text{up}_l^{sn} \oplus w_2$ for some traces $w_1$ and $w_2$, with $w_1 \in \mathbb{M}(\Sigma \setminus O_l)$. $\text{up}_l^{sn}$ therefore commutes with $w_1$, and we have $[seq_j]_I = [seq_i^k]_I \oplus \text{up}_l^{sn} \oplus w_1 \oplus w_2 = [seq_i^{k+1}]_I \oplus w'$, with $w' = w_1 \oplus w_2$, which proves the property for $k + 1$.

□Lemma 2

**Lemma 3.** If a process $p_i$ issues a successful operation $\text{up}_l^{sn}$, any correct process eventually processes the operation $\text{up}_l^{sn}$.
before processing up₂, the construction of $S_i^{\succ}$, and the fact that $S_i^{\succ}$ appears after $S_i^{\preceq}$ in $S_i$
ensures the order between up₁ and up₂ is respected in $S_i$. In $\hat{E}_i$, if an update operation up
is invoked before a query $q$, line 8 insures line 13 in the order in which they are invoked
at line 4, and that up is processed before $q$ in $S_i$. The reverse (when $q$ is invoked before
up) is also trivially true. As a result the order between queries and updates in $\hat{E}_i$ is also
preserved in $S_i$.

Now that we have proved that $S_i$ is a serialization of $\hat{H}_i$, let us show that $S_i$ is PCO-legal;

* *Process Authorization* is guaranteed by the condition of line 12.

* *Update Legality*. Let us consider a prefix $u_i$ of $\text{proj}_{\Sigma}(S_i)$. If $p_i$ is correct, by construction of $S_i$, there exists a point in the execution of $p_i$ when $u_i = \text{seq}_i$. Because of line 12, $[\text{seq}_i]_I \in L$, and therefore $[u_i]_I \in L$. If $p_i$ is faulty, $u_i$ is such that $u_i = \text{seq}'_i$ at some point of the execution of $p'_i$, where $\text{seq}'_i$ is the sequence of updates constructed by $p'_i$, and $p'_i$ is the virtual correct process corresponding to $p_i$ until its crash, used to construct $S_i$. By the same argument as for correct processes, $[u_i]_I \in L$.

* *Query Validity*. When a query operation is invoked, it returns $q(\text{seq}_i^q)$ where $\text{seq}_i^q$ denotes the sequence of update operations $p_i$ has processed until the query $q$. If we note $e_k = (q, val, p)$, then $val = q(\text{seq}_i^q)$. By construction of $S_i$, $\text{seq}_i^q = S_i^{<k}$, where $S_i^{<k}$ represents all invocations which precede $e_k$ in $S_i$, and therefore $val = q(\text{proj}_{\Sigma}(S_i^{<k}))$.

□*Theorem 1*

## 5.3 In the BAMP model

This section presents first the reliable broadcast abstraction whose operations instantiate the
$r_broadcast()` and `r_deliver()` operations used in the generic algorithm. Then, it proves that the
resulting algorithm correctly implements a PCO in $BAMP_{n,t}[t < n/3]$.

### 5.3.1 Reliable broadcast abstraction in the Byzantine failure model

* BRB-Validity. If a *correct* process $p_i$ br-delivers a message from a *correct* $p_j$ with sequence number *sn*, then $p_j$ br-broadcast it with sequence number *sn*.

* BRB-Integrity. For each sequence number *sn* and sender $p_j$ a *correct* process $p_i$ br-delivers at most one message with sequence number *sn* from sender $p_j$.

* BRB-Termination-1. If a correct process br-broadcasts a message, it br-delivers it.

* BRB-Termination-2. If a *correct* process br-delivers a message from a (*correct* or *faulty*) process $p_j$, then all correct processes br-deliver it.

### 5.3.2 Proof

**Notation** Now, if $p_j$ is Byzantine, $op_j^{sn}$ does not necessarily correspond to the actual operation invocation by $p_j$, but the BRB-Termination-2 property guarantees that all correct processes br-deliver the *same* set of UPDATE messages (with the same sequence numbers), and therefore agree on how $p_j$'s behavior should be interpreted.

Lemmas 1, 2, and 3 are still valid in this model, by considering only *correct* processes. It
gives us the three following lemmas:
**Lemma 4.** Any invocation of updates operations and query operations issued by a correct process terminates.

**Lemma 5.** If a correct process $p_i$ processes $up_i^{sn}$, then any correct process processes $up_i^{sn}$.

**Lemma 6.** If a correct process $p_i$ issues an operation $up_i^{sn}$, any correct process eventually processes the operation $up_i^{sn}$.

The proofs of those three lemmas is analog to proofs of Lemmas 1, 2, and 3, by replacing the use of CRB-* properties by their corresponding BRB-* ones.

**Theorem 2.** Algorithm 1 instantiated with BR-Broadcast implements a Process-Commutative object in the system model $BAMP_{n,t}[t < n/3]$, and ensures that all operations by correct processes terminates.

**Proof** The constraint $t < n/3$ is due to the BR-broadcast. Let us first note that termination is provided by Lemma 4.

We consider an execution of the algorithm, captured as an history $H = (E_1, \dots, E_n)$. We define the mock local history $H' = (E'_1, \dots, E'_n)$ in the following manner:

* If $p_i$ is correct, $E'_i = E_i$.

* If $p_i$ is Byzantine, $E'_i$ is the set of update operations $(up_i^{sn})_{sn}$ br-delivered from $p_i$ and processed by at least one correct process, ordered according to their sequence numbers. Because of Lemma 5, all correct processes process the updates of $E'_i$, and due to the conditions $sn = \text{del}_i[j] + 1$ at line 12, they have all processed these updates in the order in which they appear in $E'_i$.

Let $p_i$ be a correct process. Let $S_i$ be the sequence of invocations (op, val, $p_i$) that contains (i) the query operations $(q, \text{val}, p_i) \in \mathcal{Q} \times \mathbb{V} \times \{p_i\}$ invoked by $p_i$, and (ii) the update operations (up, val, $p_j$) $\in \Sigma \times \{\perp\} \times \Pi$ processed by $p_i$, ordered in the order in which these queries and updates occurred at $p_i$ (i.e. the order in which the lines 3 and 13 were executed).

We first prove that $S_i$ is a serialization of $\widehat{H'_i}$.

* All invocations of $S_i$ appear in $\widehat{H'_i}(= \widehat{E'_1}, \dots, \widehat{E'_n})$: if $(q, \text{val}, p_i) \in S_i$ is a query, $q$ was invoked by $p_i$ and so is part of $E_i = E'_i = \widehat{E'_i}$. If (up, $\perp$, $p_\ell$) $\in S_i$ is an update, we have two cases. Case 1, if $p_\ell$ is correct, then BRB-Validity, up was issued by $p_\ell$, and (up, $\perp$, $p_\ell) \in \widehat{E}'_\ell$. Case 2, if $p_\ell$ is Byzantine, then since $p_i$ (which is correct) processed (up, $\perp$, $p_\ell$), then we have (up, $\perp$, $p_\ell) \in E'_\ell = \widehat{E}'_\ell$.

* All invocations in $\widehat{H'_i}$ appear in $S_i$: first consider a process $p_\ell \neq p_i$. If $p_\ell$ is correct, $\widehat{E}'_\ell$ only contains update operations issued by $p_\ell$. By Lemma 6, $p_i$ will eventually processes these updates, that will therefore appear in $S_i$. If $p_\ell$ is Byzantine, by construction $\widehat{E}'_\ell$ only contains update operations processed by all correct processes, and hence by $p_i$, and these operations will also appear in $S_i$. $\widehat{E}'_i$ contains all the queries invoked by $p_i$ and all updates issued by $p_i$. By definition, all queries invoked by $p_i$ are in $S_i$. The reasoning on the updates of $\widehat{E}'_i$ is the same as for $\widehat{E}'_{\ell \neq i}$.

* The total order of $S_i$ preserves the process orders $(\to_i)_i$ of $\widehat{H'_i}$: For each process $p_j$, if an update $up_1$ appears before $up_2$ in $\widehat{E}'_j$, it means that $sn_1 < sn_2$ ($sn_k$ being the sequence number associated with $up_k$ during the execution), either because $p_j$ is correct, or by construction of $E'_j$ if $p_j$ is Byzantine. The condition on $sn$ at line 12 ensures that $p_i$ does
not process up₂ before up₁. In $\hat{E}_i$, if an update operation up is invoked before a query $q$, line 8 insures $p_i$ are processed at line 13 in the order in which they are invoked at line 4, and that up is processed before $q$ in $S_i$. The reverse (when $q$ is invoked before up) is also trivially true. As a result the order between queries and updates in $\hat{E}_i$ is also preserved in $S_i$.

The reasoning to prove that $S_i$ is PCO-legal is similar to that of Theorem 1. The arguments for *Process Authorization* and *Query Validity* are the same, and that of *Update Legality* is somewhat simpler, as we only need to consider the correct case:

* *Update Legality*. Let us consider a prefix $u_i$ of $\text{proj}_{\Sigma}(S_i)$. Since $p_i$ is correct, by construction of $S_i$, there exists a point in the execution of $p_i$ when $u_i = \text{seq}_i$. Because of line 12, $[\text{seq}_i]_I \in L$, and therefore $[u_i]_I \in L$.

□Theorem 2

# 6 Examples

This section presents several practical examples of PCO objects. For each example, we define *C*, the list of common updates, ($O_i$)$_i$, the list of process-specific updates, the trace language *L* capturing the legal update sequences as well as the object's state, and finally the set of query functions $Q = \{q_k\}_k$ over *L* that the object implements.

In each case, we prove that the proposed language *L* verifies the three properties introduced in Section 3.2 (*Initial emptiness*, *C*\*-Closure, and *I-diamond Closure*) that are required by our algorithm to implement a Distributed Process-Commutative Object (either in the *CAMP*$_{n,t}$ or *BAMP*$_{n,t}$ mode, depending on the reliable broadcast that is used), as defined in Section 3.5.

## 6.1 Money Transfer

### 6.1.1 Definition

A money transfer object [16] [add appropriate references] is a distributed object that associates each process $p_i$ with an account, and two classes of operations:

*transfer* operations transfer some amount to another process' account, and *balance* operations return the balance of a given process. To demonstrate common updates, we also introduce (optional) *mint* operations, that create money and add it to a given account. In practice such an operation would only be available to a limited set of trusted correct processes, but for simplicity in the following we will assume is it available to everyone w.l.o.g. Accounts cannot be negative, and the total amount of money in the system must be equal to the initial amount augmented by the value of each *mint* operation.

### 6.1.2 Notations

* We note $init_i$ the initial amount available in the account of process $p_i$. For all $p_i$, $init_i \ge 0$.

* We note transfer$_{i,j,x}$ the update operation transfer from $p_i$ to $p_j$ of an amount $x \ge 0$.

* We note mint$_{i,x}$ the update operation mint of an amount $x \ge 0$ into $p_i$'s account.
* For a process $p_i$ and a trace of update operations $v$, we define the following three functions:

$$ \text{plus}(i, v) \stackrel{\text{def}}{=} \sum_{\text{transfer}_{i,i,y} \in v} y + \sum_{\text{mint}_{i,y} \in v} y, \qquad (7) $$

$$ \text{minus}(i, v) \stackrel{\text{def}}{=} \sum_{\text{transfer}_{i,-,y} \in v} y, \qquad (8) $$

$$ \text{acc}(i, v) \stackrel{\text{def}}{=} \text{init}_i + \text{plus}(i, v) - \text{minus}(i, v), \qquad (9) $$

where $x \in v$ in the above formulas iterates over the elements of the trace $v$ that fit the pattern $x$.

* We note $\text{balance}_i$ the query operation $\text{balance}$ for a given account of a process $p_i$. If a balance operation is invoked after the operations contained in a trace $v$, we have $\text{balance}_i(v) = \text{acc}(i, v)$.

### 6.1.3 Alphabet and language definitions

Formally, we define the sets of $C$, $(O_i)_i$, and $Q$ of a money transfer object as follows:

* $C \stackrel{\text{def}}{=} \{\text{mint}_{i,x}\}_{1 \le i \le n, x \in \mathbb{R}_{\ge 0}}$,

* $O_i \stackrel{\text{def}}{=} \{\text{transfer}_{i,j,x}\}_{1 \le j \le n, x \in \mathbb{R}_{\ge 0}}$,

* $Q \stackrel{\text{def}}{=} \{\text{balance}_i\}_{1 \le i \le n}$.

We define the trace language $L$ as

$$ L \stackrel{\text{def}}{=} \{v \in \mathbb{M}(\Sigma) \mid \forall p_i \in \Pi : \text{acc}(i, v) \ge 0\}. \qquad (10) $$

**Theorem 3.** ($C$, $(O_k)_k$, $L$, $Q$) as defined above specifies a Process-Commutative Object, as defined in Section 3.2.

**Proof** We need to prove that $L$ verifies the properties of Initial emptiness, $C^*$-Closure, and I-diamond Closure.

* **Initial emptiness:** It is easy to see that for any process $p_i$, $\text{plus}(i, \epsilon) = \text{minus}(i, \epsilon) = 0$, and therefore that $\text{acc}(i, \epsilon) = \text{init}_i$, where $\epsilon$ represents the empty trace. Since by hypothesis $\text{init}_i \ge 0$ (no process start with a negative balance), $\text{acc}(i, \epsilon) \ge 0$, and $\epsilon \in L$, by definition of $L$.

* **$C^*$-Closure:** Consider a trace $v \in L$, and a money-creation operation on process $p_i$, $\text{mint}_{i,x} \in C$. By definition of $v$, we have for all processes $p_j$ that $\text{acc}(j, v) \ge 0$. By definition of plus(), minus() and acc(), we also have $\text{acc}(i, v \oplus \text{mint}_{i,x}) = \text{acc}(i, v) + x$, and $\text{acc}(j, v \oplus \text{mint}_{i,x}) = \text{acc}(j, v)$ for $j \ne i$. Combined with $x \ge 0$ and $\text{acc}(j, v) \ge 0$ for all $p_j$, this implies that $\text{acc}(j, v \oplus \text{mint}_{i,x}) \ge 0$ for all processes $p_j$, and therefore that $v \oplus \text{mint}_{i,x} \in L$.

* **I-diamond Closure:** Consider a trace $v \in L$, a transfer $\text{transfer}_{i,j,x}$, and a trace of updates $z \in \mathbb{M}(\Sigma \setminus O_i)$, so that $\{v \oplus \text{transfer}_{i,j,x}, v \oplus z\} \subseteq L$. We have to consider the cases of $p_i, p_j$, and $p_\ell \notin \{p_i, p_j\}$. Case of $p_i$: By definition, $\text{acc}(i, v \oplus z \oplus \text{transfer}_{i,j,x}) = \text{acc}(i, v \oplus z) - x$, and $\text{acc}(i, v \oplus \text{transfer}_{i,j,x}) = \text{acc}(i, v) - x$. Because $z$ contains no transfer $\text{transfer}_{i,-,-}$
from $p_i$, we have $\text{acc}(i, v \oplus z) \ge \text{acc}(i, v)$, and therefore $\text{acc}(i, v \oplus z \oplus \text{transfer}_{i,j,x}) = \text{acc}(i, v \oplus z) - x \ge \text{acc}(i, v) - x = \text{acc}(i, v \oplus \text{transfer}_{i,j,x})$. Since $v \oplus \text{transfer}_{i,j,x} \in L$, $\text{acc}(i, v \oplus \text{transfer}_{i,j,x}) \ge 0$, which implies that $\text{acc}(i, v \oplus z \oplus \text{transfer}_{i,j,x}) \ge 0$. Case of $p_j$: By definition $\text{acc}(j, v \oplus z \oplus \text{transfer}_{i,j,x}) = \text{acc}(j, v \oplus z) + x$. With $\text{acc}(j, v \oplus z) \ge 0$ (since $v \oplus z \in L$), and $x \ge 0$ (by definition), this yields $\text{acc}(j, v \oplus z \oplus \text{transfer}_{i,j,x}) \ge 0$. Case of $p_l \notin \{p_i, p_j\}$: $\text{acc}(l, v \oplus z \oplus \text{transfer}_{i,j,x}) = \text{acc}(l, v \oplus z)$, which implies $\text{acc}(l, v \oplus z \oplus \text{transfer}_{i,j,x}) \ge 0$ since $v \oplus z \in L$. These three cases show that $\text{acc}(k, v \oplus z \oplus \text{transfer}_{i,j,x}) \ge 0$ for all processes $p_k$, and therefore that $v \oplus z \oplus \text{transfer}_{i,j,x} \in L$.

□Theorem 3

## 6.2 Multi-set with Deletion Rights

### 6.2.1 Definition

A shared multi-set object with deletion rights provides two classes of update operations: **add**<sub>e</sub> adds the element $e \in E$ to the multiset, while **delete**<sub>e</sub> removes one instance of $e$ from the multiset. Elements might appear multiple times in the multiset, and can be added by any process. A given element $e$ can however only be deleted by a specific process, that has the **deletion right** for this element. We note $E_i$ the set of elements that $p_i$ can delete. The sets $(E_i)_{p_i \in \Pi}$ partition $E$, i.e. $E = \cup_{p_i \in \Pi} E_i$, and $E_i \cap E_j = \emptyset$ for $i \ne j$. An element must also be present as least once in the multiset to be deleted.

A shared multi-set object supports a single query operation, **get_set**, which returns a finite map **card** ∈ Z<sup>E</sup> that provides the cardinality **card**(*e*) of each element *e* in the multiset. As we are dealing with finite mutlisets, **card** is non-zero for only a finite number of elements. If **get_set** is invoked after the **add** and **delete** operations contained in a trace *v*, then

$$ \text{get\_set}(v)(e) = |\text{proj}_{\text{add}_e}(v)| - |\text{proj}_{\text{delete}_e}(v)|. \quad (11) $$

### 6.2.2 Alphabet and language definitions

Formally, we define the sets of $C$, $(O_i)_i$, and $Q$ of a shared multi-set with deletion rights are as follows:

* $C \stackrel{\text{def}}{=} \{\text{add}_e\}_{e \in E}$,

* $O_i \stackrel{\text{def}}{=} \{\text{delete}_e\}_{e \in E_i}$,

* $Q \stackrel{\text{def}}{=} \{\text{get\_set}\}$.

The trace language of a shared multi-set object is defined as

$$ L \stackrel{\text{def}}{=} \{v \in \mathbb{M}(\Sigma) \mid \forall e \in E : \text{get\_set}(v)(e) \ge 0\}. \quad (12) $$

**Theorem 4.** ($C$, $(O_k)_k$, $L$, $Q$) as defined above specifies a Process-Commutative Object.

**Proof** We need to prove that $L$ verifies the properties of Initial emptiness, $C^*$-Closure, and I-diamond Closure defined in Section 3.2.

* Initial emptiness: $\text{get\_set}(\epsilon)(e) = |\text{proj}_{\text{add}_e}(\epsilon)| - |\text{proj}_{\text{delete}_e}(\epsilon)| = 0 - 0$, and therefore $\epsilon \in L$.
* C\*-Closure: Consider a trace $v \in L$, and an add operation $add_e \in C$ on an element $e$. Since $v \in L$, for any $e' \in E$, we have $get_set(v)(e') \ge 0$. This observation, and the fact that $get_set(v \oplus add_e)(e) = get_set(v)(e) + 1$ by construction, implies that $get_set(v \oplus add_e)(e) \ge 0$. Considering now an element $e' \ne e$, we have $get_set(v \oplus add_e)(e') = get_set(v \oplus)(e')$, also yielding $get_set(v \oplus add_e)(e') \ge 0$ by the same reasoning.

* I-diamond Closure: Consider a trace $v \in L$, an operation $delete_{e_i}$ with $e_i \in E_i$, and a trace of updates $z \in \mathbb{M}(\Sigma \setminus O_i)$, so that $\{v \oplus delete_{e_i}, v \oplus z\} \subseteq L$. We need to consider the case of $e_i$ and that of $e \ne e_i$. By definition, $get_set(v \oplus z \oplus delete_{e_i})(e_i) = get_set(v \oplus z)(e_i) - 1$. Since $z$ does not contain any operation $delete_{e_i}$, $get_set(v \oplus z)(e_i) \ge get_set(v)(e_i)$. Because $v \oplus delete_{e_i} \in L$ by assumption, we have $get_set(v \oplus delete_{e_i})(e_i) = get_set(v)(e_i) - 1 \ge 0$, which implies with the earlier equality and inequality that $get_set(v \oplus z \oplus delete_{e_i})(e_i) \ge 0$. Considering now $e \ne e_i$, by definition $get_set(v \oplus z \oplus delete_{e_i})(e) = get_set(v \oplus z)(e)$, and since $get_set(v \oplus z)(e) \ge 0$ (as $v \oplus z \in L$ by assumption), we also have $get_set(v \oplus z \oplus delete_{e_i})(e) \ge 0$.

□Theorem 4

## 6.3 Petri net

### 6.3.1 Definition

A Petri net is defined by the 5-tuple $(P, T, F, M_0, W)$ such as:

* $P$ is a set of places

* $T$ is a set of transitions ($P$ and $T$ are disjoints)

* $F \subseteq (P \times T) \cup (T \times P)$ is a set of directed edges from places to transitions or from transitions to places (thus creating a directed bipartite graph).

* $M_0 \in \mathbb{N}^P$ is an initial marking, that defines how many tokens each place initially contains.

* $W \in (\mathbb{N}_{>0})^F$ indicates on each edge how many tokens are either consumed (for edges in $P \times T$) or produced (for edges in $T \times P$).

We note $\diamond$ the conflict relation between two transitions: $t_1 \diamond t_2$ if $t_1$ and $t_2$ share an input place, or more formally if $N^-(t_1) \cap N^-(t_2) \ne \emptyset$, where $N^-$ denotes the direct predecessors of a vertex in the directed bipartite graph ($P \cup T, F$). We note $\diamond^+$ the reflexive and transitive closure of $\diamond$. Since $\diamond$ is symmetric, $\diamond^+$ is an equivalence relation.

### 6.3.2 Shared Petri Net with Transition Rights

A shared Petri net with transition rights is a shared object that provides the update operations fire$_t$, which fire a given transition $t \in T$. To take into account conflicting transitions, the set of transitions is partitioned into a set $(T_i)_{i \in \Pi}$ of process-specific transitions, and a set of common transitions $T_C$, defined as follows:

* Two conflicting transitions belong to the same set $T_i$: for each $t \in T_i$, $[t]_{\diamond+} \subseteq T_i$, where $[t]_{\diamond+}$ is the equivalence class of $t$ for $\diamond^+$.

* $T_C$ only contains transitions with no input places (i.e. transitions $t$ such that $N^-(t) = \emptyset$, and therefore $[t]_{\diamond+} = \{t\}$).
A process $p_i$ can only fire transitions from $T_i \cup T_C$.

A shared Petri net with transition rights supports a single query operation marking that returns the current marking $M \in \mathbb{Z}^P$ of the Petri net. If marking is invoked after the fire operations contained in a trace $v$, then

$$ \mathit{marking}(v)(p) \stackrel{\text{def}}{=} M_0(p) + \sum_{\mathit{fire}_t \in v: \ t \in N^-(p)} W(t,p) - \sum_{\mathit{fire}_t \in v: \ t \in N^+(p)} W(p,t). \quad (13) $$

### 6.3.3 Alphabet and language definitions

Formally, we define the sets $C$, $(O_i)_i$, and $Q$ of a shared Petri net with transition rights are as follows:

* $C \stackrel{\text{def}}{=} \{\mathit{fire}_t\}_{t \in T_C}$,

* $O_i \stackrel{\text{def}}{=} \{\mathit{fire}_t\}_{t \in T_i}$,

* $Q \stackrel{\text{def}}{=} \{\mathit{marking}\}$.

The trace language of a shared Petri net is defined as

$$ L \stackrel{\text{def}}{=} \{v \in \mathbb{M}(\Sigma) \mid \forall p \in P : \mathit{marking}(v)(p) \geq 0\}. \quad (14) $$

**Theorem 5.** ($C$, $(O_k)_k$, $L$, $Q$) as defined above for a shared Petri net with transition rights specifies a Process-Commutative Object.

**Proof**

* Initial emptiness: By construction $\mathit{marking}(\epsilon) = M_0 \in \mathbb{N}^P$, hence $\epsilon \in L$.

* $C^*$-Closure: Consider a trace $v \in L$, and a fire operation $\mathit{fire}_t \in C$, where $t \in T_C$. By $T_C$'s definition, $N^-(t) = \emptyset$, and therefore $\forall p \in P : t \notin N^+(p)$. Injecting this property in Eq. 13, we have

$$ \begin{aligned} \mathit{marking}(v \oplus \mathit{fire}_t)(p) &= \mathit{marking}(v) + \mathbb{1}_{t \in N^-(p)} \times W(t,p) - \mathbb{1}_{t \in N^+(p)} \times W(p,t), \\ &= \mathit{marking}(v) + \mathbb{1}_{t \in N^-(p)} \times W(t,p), \\ &\geq \mathit{marking}(v). \end{aligned} $$

where $\mathbb{1}_P$ represents the indicator function for predicate $P$.

* I-diamond Closure: Consider a trace $v \in L$, an operation $\mathit{fire}_{t_i}$ with $t_i \in T_i$, and a trace of fire operations $z \in \mathbb{M}(\Sigma \setminus O_i)$, so that $\{v \oplus \mathit{fire}_{t_i}, v \oplus z\} \subseteq L$. We have to consider two categories of places, depending whether a place $p$ belongs to $N^-(t_i)$ or not. Case 1: For a place $p \notin N^-(t_i)$, we have $t_i \notin N^+(p)$, which injected in Eq. 13 yields

$$ \begin{aligned} \mathit{marking}(v \oplus z \oplus \mathit{fire}_{t_i})(p) &= \mathit{marking}(v \oplus z)(p) + \mathbb{1}_{t_i \in N^-(p)} \times W(t,p), \\ &\geq \mathit{marking}(v \oplus z)(p), \quad (\text{since } W(t,p) > 0) \\ &\geq 0. \quad (\text{since } v \oplus z \in L) \end{aligned} $$

Case 2: Consider a place $p \in N^-(t_i)$. For any update operations $\mathit{fire}_{t'} \in z$, by definition of $T_i$, we have $\neg(t' \diamond^+ t_i)$, i.e. $t_i$ is not in conflict with any of the transitions $t'$ fired in the
trace fragment z. As a result, $p \in N^-(t_i)$ implies $\forall \mathbf{fire}_{t'} \in z : p \notin N^-(t')$, and equivalently $\forall \mathbf{fire}_{t'} \in z : t' \notin N^+(p)$, and therefore

$$ \mathbf{marking}(v \oplus z)(p) = \mathbf{marking}(v)(p) + \sum_{\substack{\mathbf{fire}_{t'} \in z: \\ t' \in N^-(p)}} W(t', p), \\ \geq \mathbf{marking}(v)(p). \qquad (\text{since } W(t', p) > 0) $$

and therefore

$$ \mathbf{marking}(v \oplus z \oplus \mathbf{fire}_{t_i})(p) = \mathbf{marking}(v \oplus z)(p) + \mathbb{1}_{t_i \in N^-(p)} \times W(t_i, p) - \mathbb{1}_{t_i \in N^+(p)} \times W(p, t_i), \\ \geq \mathbf{marking}(v)(p) + \mathbb{1}_{t_i \in N^-(p)} \times W(t_i, p) - \mathbb{1}_{t_i \in N^+(p)} \times W(p, t_i), \\ \geq \mathbf{marking}(v \oplus \mathbf{fire}_{t_i})(p), \\ \geq 0. \qquad (\text{since } v \oplus \mathbf{fire}_{t_i} \in L) $$

□Theorem 5

## 6.4 Work Stealing Deque

Work stealing is a classical approach to implement load-balancing within a parallel computing infrastructure with irregular workloads (e.g. a massively parallel computer, a computing grid) [17, 18, 19, 20]. far, we shall consider a system in which $n$ processes submit tasks. A process keeps the tasks it has submitted but which haven't been executed yet in a semi-private datastructure called a *work stealing deque* (WSD for short, more on this below), and executes in priority its own tasks (termed local tasks). When a process no longer has any local task to execute (its deque is empty), it steals a pending task from some other process, selected at random.

Since we consider fault-models in which processes might crash or behave in a Byzantine manner, we consider the case of *idempotent work stealing* [19]. In this relaxed version of work stealing, every task submitted by (correct) processes must eventually be executed at least once, but might be executed several times (contrary to exactly once in traditional work-stealing).

### 6.4.1 A Multiple Idempotent Work Stealing Deque

Work stealing deques, or WSDs, lie at the heart of any work stealing algorithm. A WSD typically supports local LIFO push and pop operations [18], and allows remote processes to perform FIFO pop operations when they attempt to “steal” work from other processes. Because some process might fail in our model, the theft of a task from a correct process by a faulty one could lead to the loss of this task. Our implementation therefore slightly changes the default semantic of WSDs and implement the steal operation as a query operation that returns the top task of a deque, but does not modify the deque. Thief processes notify the owner of a task that the task is completed simply by publishing its result, and the removal proper of the task from the local deque is performed by the owning process. To tolerate Byzantine behavior, we assume that correct process are able to check that the result of a task is indeed valid<fnref n="5" />.

A work-stealing algorithm uses as many deques as there are processes. For simplicity we therefore specify the overall behavior of this set of deques, which we call a Multiple Idempotent Work Stealing Deque.

<footnote n="5">⁵This is usually application specific, but can be implemented in a general manner by only accepting a result if it has been returned by enough (e.g. $t+1$) processes, a mechanism commonly used for instance in voluntary computing platforms.</footnote>
Formally, we define a Multiple Idempotent Work Stealing Deque is a distributed object which provides four update operations (`pushBottom`, `popBottom`, `remove`, and `addResult`) and four query operations (`getTop`, `getBottom`, `getPending`, and `getResults`):

* `pushBottom`<sub>*i*,*t*</sub> adds (push) task *t* to the bottom of the deque of processor *p*<sub>*i*</sub>. Only *p*<sub>*i*</sub> might execute this operation.

* `popBottom`<sub>*i*</sub> removes (pops) and returns the task at the bottom of the deque of processor *p*<sub>*i*</sub> in LIFO order. Only *p*<sub>*i*</sub> might execute this operation.

* `remove`<sub>*i*,*t*</sub> removes task *t* from the deque of processor *p*<sub>*i*</sub> (independently of its position). If *t* is not in *p*<sub>*i*</sub>'s deque, has no effect.

* `addResult`<sub>*t*,*r*</sub> records that the result of task *t* is some value *r*. `addResult`<sub>*t*,*r*</sub> is used by thief processes to notify the owner of a task *t* that a (valid) result is available for *t*.

* `getTop`<sub>*i*</sub> returns the task at the top of *p*<sub>*i*</sub>'s deque in FIFO order (but does not modify the content of the deque, i.e. this is a query operation).

* `getBottom`<sub>*i*</sub> returns the task at the bottom of *p*<sub>*i*</sub>'s deque in LIFO order (but does not modify the content of the deque, i.e. this is a query operation).

* `getPending`<sub>*i*</sub> returns the set of pending tasks, i.e. the task currently stored in *p*<sub>*i*</sub>'s deque (but does not modify the content of the deque, i.e. this is a query operation).

* `getResults`<sub>*t*</sub> returns the set of results published for task *t* by thief processes (i.e. by processes different from *t*'s owner) using `addResult`<sub>*t*,--</sub>.

Only *p*<sub>*i*</sub> might execute `pushBottom`<sub>*i*,*t*</sub>, `popBottom`<sub>*i*</sub>, or `remove`<sub>*i*,*t*</sub>. `addResult`<sub>*t*,*r*</sub> can be executed by any process, but in a Byzantine context the validity of the result *r* can be checked by the process that submitted *t*. `getTop`<sub>*i*</sub>, `getBottom`<sub>*i*</sub>, `getPending`<sub>*i*</sub>, and `getResults`<sub>*t*</sub> are query operations available to any process. We assume tasks have unique IDs that can only be used once, and that IDs are partitioned between processes (e.g. by incorporating process IDs) so that a process *p* cannot submit task using `pushBottom`<sub>*i*,--</sub> using an ID allocated to another process.

**Alphabet and Notations** The sets *C*, (*O*<sub>*i*</sub>)<sub>*i*</sub>, and *Q* of a Multiple Idempotent Work Stealing Deque are defined as

* $C \stackrel{\text{def}}{=} \{\text{addResult}_{t,r} \mid r \text{ is a valid result for task } t\}_{(t,r) \in \mathbb{T} \times \mathbb{V}}$,

* $O_i \stackrel{\text{def}}{=} \{\text{pushBottom}_{i,t}, \text{remove}_{i,t}\}_{(p_i,t) \in \Pi \times \mathbb{T}_i} \cup \{\text{popBottom}_i\}_{p_i \in \Pi}$,

* $Q \stackrel{\text{def}}{=} \{\text{getTop}_i, \text{getBottom}_i, \text{getPending}_i\}_{p_i \in \Pi} \cup \{\text{getResults}_i\}_{i \in \mathbb{T}}$,

where $\mathbb{T}$ is the set of all possible tasks, $\mathbb{T}_i$ is the set of tasks that $p_i$ may submit ($\mathbb{T} = \bigcup_i \mathbb{T}_i$), and $\mathbb{V}$ the set of task results.

**The d_state help function** To help with the definition of the trace language *L*, we introduce a helper function, called `d_state` that returns the current content of *p*<sub>*i*</sub>'s deque following the operations recorded in the trace *v*.

$$ \begin{array}{lclcl} \texttt{d\_state:} & [1..n] \times \mathbb{M}(\Sigma) & \rightarrow & \mathbb{T}^* \cup \{\perp\} & \\ & (i, v) & \mapsto & \texttt{d\_state}(i, v). & \end{array} $$
$d\_state(i, v)$ is defined recursively as follows.

$$d\_state(i, \epsilon) \stackrel{\text{def}}{=} \epsilon, \qquad (15)$$

if $d\_state(i, v) \neq \perp$ then

$$d\_state(i, v \oplus \text{pushBottom}_{i,t}) \stackrel{\text{def}}{=} d\_state(i, v) \oplus t, \qquad (16)$$

$$d\_state(i, v \oplus \text{popBottom}_i) \stackrel{\text{def}}{=} d\_state(i, v)[2..|d\_state(i, v)|], \qquad (17)$$

$$d\_state(i, v \oplus \text{remove}_{i,t}) \stackrel{\text{def}}{=} d\_state(i, v) \setminus t, \qquad (18)$$

if $d\_state(i, v) = \perp$ then

$$d\_state(i, v \oplus \text{op}) \stackrel{\text{def}}{=} \perp. \qquad (19)$$

In the above definitions, $s\_t$ is the sequence obtained when removing all occurrences of $t$ in $s$. $s[i..j]$ represents the subsequence of $s$ containing its $i$th to $j$th elements<fnref n="6" />. We define the special case in which $i > j$ as follows:

$$s[i..i-1] = \epsilon, \qquad (20)$$

$$s[i..j] = \perp \quad \text{if } i > j + 1. \qquad (21)$$

where $\epsilon$ is the empty sequence, and $\perp$ is a non-value. As a result, $d\_state(i, v)$ switches to the non-value $\perp$ when a `pushBottom` operation is applied to an empty deque in (17). Once $d\_state(i, v)$ has collapsed to $\perp$, (19) ensures it keeps this value. Other update operations leave $d\_state(i, v)$ unchanged.

**Lemma 7.** $d\_state$ is a well defined function on $M(\Sigma)$.

*Proof.* Because a trace $v$ only imposes a partial order on its operations, the above recursive definitions could be ambiguous. In the case of $d\_state$, however, because the operations of $O_i$ do not commute, a trace $v$ imposes a total order on the operations `pushBottom`$_{i,t}$, `popBottom`$_i$, and `remove`$_{i,t}$, insuring that $d\_state$ is well defined. □

**Language Definition** The trace language of a Multiple Idempotent Work Stealing Deque is defined as

$$L \stackrel{\text{def}}{=} \{v \in M(\Sigma) \mid \forall p_i \in \Pi, t \in T : |\text{proj}_{\text{pushBottom}_{i,t}}(v)| \le 1 \land d\_state(i, v) \ne \perp\},$$

which essentially states that $p_i$ should only submit a task $t$ at most once, and that `pushBottom`$_i$ is forbidden when $p_i$'s deque is empty, due to the recursive definition of (17), and the fact that $d\_state(i, v)[2..0] = \perp$ by definition.

**Defining the Query and Result Functions** Based on $d\_state$, the query functions `getTop`$_i$, `getBottom`$_i$ and `getPending`$_i$ are defined on $L$ as

$$\text{getTop}_i(v) \stackrel{\text{def}}{=} d\_state(i, v)[|d\_state(i, v)|],$$

$$\text{getBottom}_i(v) \stackrel{\text{def}}{=} d\_state(i, v)[1],$$

$$\text{getPending}_i(v) \stackrel{\text{def}}{=} \text{set}(d\_state(i, v)),$$

$$\text{getResults}_t(v) \stackrel{\text{def}}{=} \{r \in V \mid \text{addResult}_{t,r} \text{ appears at least once in } v\},$$

<footnote n="6">⁶Said differently, if $s = (s_k)_k$, $s[i..j] = (s_k)_{i \le k \le j}$.</footnote>
where $s[i]$ is the $i^{th}$ element of sequence $s$. Similarly when $popBottom_i$ is appended to a trace $v$, it returns the value $d_state(i, v)[1]$:

$$ \mathrm{output}(\mathrm{popBottom}_i, v) \stackrel{\mathrm{def}}{=} \mathrm{d\_state}(i, v)[1]. $$

In the above definitions, by convention, we will assume $s[i] = \perp$ when $i \notin [1..|s|]$. As a result, $getTop_i(v)$, $getBottom_i(v)$, and $output(popBottom_i, v)$ returns a non-value ($\perp$) when $p_i$'s deque is empty.

**Lemma 8.** $getTop_i$, $getBottom_i$, $getPending_i$, $getResults_i$ and $output(popBottom_i, -)$ are well-defined over $L$. Furthermore, for all $v \in L$, if $v \oplus popBottom_i \in L$, then $output(popBottom_i, v) \neq \perp$.

*Proof.* Lemma 7 implies that $getTop_i$, $getBottom_i$, $getPending_i$ and $output(popBottom_i, -)$ are well defined. $getResults_i$ is well defined by construction of $M(\Sigma)$.

Consider $v \in L$, such that $v \oplus popBottom_i \in L$. By definition of $L$,

$$ \mathrm{d\_state}(i, v) \neq \perp, \qquad (22) $$

$$ \mathrm{d\_state}(i, v \oplus popBottom_i) \neq \perp. \qquad (23) $$

By definition of $d_state$, (22) implies that $d_state(i, v \oplus popBottom_i)$ was obtained through (17). The only case in which the range operator applied on a sequence might return $\perp$ is defined by (21). As a result, (23) implies that $|d_state(i, v)| \ge 1$, which yields $output(popBottom_i, v) \neq \perp$ by definition of $output(popBottom_i, v)$. $\square$

**Theorem 6.** $(C, (O_k)_k, L, Q)$ as defined above for a Multiple Idempotent Work Stealing Deque specifies a Process-Commutative Object.

*Proof* We need to prove that $L$ verifies the properties of Initial emptiness, $C^*$-Closure, and I-diamond Closure.

* Initial emptiness follows from the definition of $L$ and (15).

* $C^*$-Closure follows from the fact that $addResult_{t,r}$ does not modify the value of $d_state(i, -)$, i.e.

$$ \mathrm{d\_state}(i, v \oplus addResult_{t,r}) = \mathrm{d\_state}(i, v). $$

* I-diamond Closure: Consider $v \in L$, an update $op_i \in O_i = \{\mathrm{pushBottom}_{i,t}, \mathrm{popBottom}_i, \mathrm{remove}_{i,t}\}_{(p_i,t) \in \Pi \times T}$, and some trace of updates $z \in M(\Sigma \setminus O_i)$ that are independent of $O_i$. Assume $\{v \oplus op_i, v \oplus z\} \subseteq L$. As only the operations of $O_i$ modify the value of $d_state(i, -)$, all operations of $z$ leave $d_state(i, v)$ unchanged, we therefore have by definition of $d_state$

$$ \begin{aligned} \mathrm{d\_state}(i, v \oplus z) &= \mathrm{d\_state}(i, v) \\ \mathrm{d\_state}(i, v \oplus z \oplus op_i) &= \mathrm{d\_state}(i, v \oplus op_i). \end{aligned} $$

As $v \oplus op_i \in L$, $d_state(i, v \oplus op_i) \neq \perp$ by definition of $L$, which with the above equality implies

$$ \mathrm{d\_state}(i, v \oplus z \oplus op_i) \neq \perp. \qquad (24) $$

By a similar reasoning, $\mathrm{pushBottom}_{i,t} \notin z$ leads to $|\mathrm{proj}_{\mathrm{pushBottom}_{i,t}}(v)| = |\mathrm{proj}_{\mathrm{pushBottom}_{i,t}}(v \oplus z)|$. This equality and the fact that $v \oplus op_i \in L$ yield in turn

$$ |\mathrm{proj}_{\mathrm{pushBottom}_{i,t}}(v \oplus z \oplus op_i)| = |\mathrm{proj}_{\mathrm{pushBottom}_{i,t}}(v \oplus op_i)| \le 1. \qquad (25) $$

(24) and (25) mean that $v \oplus z \oplus op_i \in L$ by definition of $L$, concluding the proof.

$\square$ Theorem 6
1 function submit_task(t) is
   ▷t ∈ Tᵢ
2   apply.pushBottomᵢ,t)
3 when apply(getBottomᵢ) ≠ ⊥ do
4     t ← apply(popBottomᵢ)
5     r ← execute(t)
6     publish_result(t, r)
7 when apply(getBottomᵢ) = ⊥ ∧ ∃ pⱼ ≠ pᵢ : apply(getTopⱼ) ≠ ⊥ do
8     t ← apply(getTopⱼ)
9     r ← execute(t)
10    apply(addResultᵢ,r)
11 when ∃ t ∈ apply(getPendingᵢ) : apply(getResultsᵢ) ≠ ∅ do
12    apply removetᵢ,t
13    r ← choose some value from apply(getResultsᵢ)
14    publish_result(t, r)

<caption>**Algorithm 2:** A distributed work stealing algorithm using the Multiple Idempotent Work Stealing Deque specified as a Process-Commutative Object in Section 6.4.1. (Code for $p_i$.)</caption>

## 6.4.2 Using a Multiple Idempotent Work Stealing Deque

Algorithm 2 illustrates how the Multiple Idempotent Work Stealing Deque specified in Section 6.4.1 could be used. The algorithm provides the local function `submit_task()`, and use the callback `publish_result()` (lines 6 and 14) to notify the application that a task has been completed. `submit_task(t)` simply pushes the task `t` onto the bottom of $p_i$'s dequeue object (line 2). The rest of the algorithms is implemented through three event-based handlers:

* The event handler at lines 3-6 executes the task found in $p_i$'s deque, i.e. the task submitted locally by $p_i$ using `submit_task`. Once completed, the task's result is passed on to the application using the callback `publish_result`.

* The event handler at lines 7-10 triggers when $p_i$'s deque becomes empty. $p_i$ selects at random another process $p_j$ whose deque still contains some task(s), and steals one of $p_j$'s tasks to execute it.

* The event handler at lines 11-14 reacts to the publication of results by remote processes for pending local tasks (i.e. local tasks that are still in $p_i$'s deque). When a result for such a task is found, the task is removed from $p_i$'s deque, and its results is passed on to the application through the callback `publish_result`.

Algorithm 2 assumes that a correct process $p_i$ only submits tasks with IDs taken from $T_i$, and never submit any task $t \in T_i$ more than once. (If any of these two conditions were not respected, line 2 would block, due to the definition of $\Sigma$, $L$, and the condition at line 5 of Algorithm 1.) Algorithm 2 further assumes that `submit_task()` and each of the event handlers are executed in mutual exclusion (equivalently are placed in the same monitor), using a fair scheduler, in the sense that any of these four blocks of code cannot remain indefinitely activated without being eventually executed. (We discuss below how these concurrency assumptions can be relaxed.)
Under the following assumptions, Algorithm 2 ensures that if a correct process stops submitting tasks, then eventually all tasks submitted by this correct processes are executed, and a valid result is returned to the application exactly once for each of them, as captured by the following theorem.

**Theorem 7.** *Using Algorithm 2 either in the CAMP<sub>n,t</sub> or BAMP<sub>n,t</sub> models, if a correct process *p*<sub>*i*</sub> invokes submit_task(-) a finite number of times, then each task submitted by *p*<sub>*i*</sub> is eventually executed, and a valid result for each task is returned exactly once to the application using the callback publish_result(-, -).*

*Proof.* Consider an execution of Algorithm 2, and $p_i$, a correct process. Let us note $H = (E_1, \dots, E_n)$ the history recording the invocations of operations on the underlying Multiple Idempotent Work Stealing Deque object. Assuming a crash (resp. Byzantine) fault model, let us note $H' = (E_1, \dots, E_n)$ the crash-corrected history (resp. mock history) corresponding to $H$ (Section 3.5). Because $p_i$ is correct we have $E'_i = E_i$. As earlier, let us note $\widehat{H'}_i = (\widehat{E}'_1, \dots, \widehat{E}'_n)$ $p_i$'s perception of $H'$. By definition, $\widehat{E}'_i = E'_i = E_i$.

Because of Theorem 6, we can apply Theorem 1 (resp. Theorem 2), which yields the existence of a PCO-legal serialization $S_i$ of $\widehat{H'}_i$. $S_i$ contains all the update operations of $H'$, but only the queries of $E_i$.

Assume $p_i$ only invokes submit_task(·) a finite number of times. Further assume some task $\tau \in \mathbb{T}_i$ submitted by $p_i$ is never returned by popBottom$_i$ at line 4 or removed by remove$_{i,\tau}$ at line 12 in $S_i$. Using Query Validity (Section 3.2), and the definitions of pushBottom$_i$, popBottom$_i$ and remove$_{i,\tau}$, this means that for any prefix $s$ of $S_i$ that contains the pushBottom$_{i,\tau}$ operation applied at line 2, we have $\tau \in \text{d\_state}(s, i)$. This implies that any getBottom$_i$ query occurring after pushBottom$_{i,\tau}$ cannot return $\perp$. (*) As a result, the event handler at lines 7-10 of Algorithm 2 will remain activated continuously after pushBottom$_{i,\tau}$. By scheduling assumption, this implies that line 4 will be executed arbitrarily often.

Because $p_i$ only invokes submit_task(·) a finite number of times, an arbitrary number of popBottom$_i$ operations must eventually empty d\_state(s, i), leading to getBottom$_i$ returning $\perp$ at some point, thus contradicting (*). We conclude that $\tau$ must be returned by popBottom$_i$ at line 4 or removed by remove$_{i,t}$ at line 12 in $S_i$.

If $\tau$ is returned by popBottom$_i$ at line 4, because $p_i$ is correct it executes the rest of the event handler, and returns a valid result to the application using publish_result. If $\tau$ is removed at line 12, by definition of getResults$_i$ and the construction of the set $C$ (which only allow for valid results to be included in traces of $L$), the result $r$ found at line 13 is also valid, and $p_i$ returns it to the application.

The fact that pushBottom<sub>*i*,τ</sub> can only be included once in $S_i$, and that both popBottom<sub>*i*</sub> when it returns $\tau$ at line 4 or remove<sub>*i*,τ</sub> at line 12 remove $\tau$ from d\_state(s, i) insures that publish\_result can only be invoked at most once for $\tau$ under our concurrency assumption of mutual exclusion of the event handlers. □

**Relaxing the concurrency assumptions** The result of Theorem 7 still holds if one relaxes the concurrency assumptions slightly, by releasing the monitor of Algorithm 2 when calling execute(t) at lines 5 and 9, while maintaining a mutual exclusion between the first (lines 3-6) and the second event handler (lines 7-10). This approach provides more concurrency, by allowing the application to submit tasks, or remote results to be published at line 14 even if some task is already executing locally.
# 7 Conclusion

This paper introduced the notion of *Process-Commutative Objects (PCO)*, a class of distributed data structures that covers a wide range of practical use cases, from money-transfer systems to concurrent work-stealing deques. Computationally, PCOs are weaker than atomic shared registers, and can be implemented using solely a reliable broadcast primitive, both in a Byzantine and Crash fault model.

A formalized PCOs using Mazurkiewicz traces-based formulation of PCOs has been proposed and a simple generic algorithm implement therm has been given. Four practical applications PCOs have been prvided to illustate the interests of PDOs, namely, money transfer, multi-sets with deletion rights, Petri nets, and work-stealing deques. It is worg noticing that the propsoed algorithm is generic in two dimensions: (i) it can implement any PCO data structure (it is thus universal for PCO objects), and (ii) it inherits the fault-tolerance assumptions of its underlying broadcast (it can be made crash- or Byzantine tolerant simply by using a crash- resp. Byzantine tolerant reliable FIFO broadcast).

# References

[1] M. Ben-Or. "Another Advantage of Free Choice (Extended Abstract): Completely Asynchronous Agreement Protocols". In: PODC'83. 1983, pp. 27-30.

[2] A. Castañeda and M. Piña. "Fully Read/Write Fence-Free Work-Stealing with Multiplicity". In: DISC. Vol. 209. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, 16:1-16:20.

[3] D. Frey, L. Guillou, M. Raynal, and F. Taïani. "Consensus-Free Ledgers When Operations of Distinct Processes are Commutative". In: 16th International Conference on Parallel Computing Technologies (PaCT). Sept. 2021, pp. 359-370.

[4] S. Gupta, J. Hellings, and M. Sadoghi. *Fault-Tolerant Distributed Transactions on Blockchain*. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2021.

[5] L. Lamport, R. Shostak, and M. Pease. "The Byzantine Generals Problem". In: ACM *ACM Transactions on Programming Languages and Systems* 4 (1982), pp. 382-401.

[6] C. Li, D. Porto, A. Clement, J. Gehrke, N. Preguiça, and R. Rodrigues. "Making Geo-Replicated Systems Fast as Possible, Consistent when Necessary". In: OSDI. 2012. ISBN: 978-1-931971-96-6.

[7] M. Raynal. *Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach*. Springer, 2018. ISBN: 978-3-319-94140-0.

[8] M. J. Fischer, N. A. Lynch, and M. Paterson. "Impossibility of Distributed Consensus with One Faulty Process". In: J. ACM (1985).

[9] S. Gilbert and N. Lynch. "Perspectives on the CAP Theorem". In: Computer (2012).

[10] A. Mostéfaoui, H. Moumen, and M. Raynal. "Signature-Free Asynchronous Binary Byzantine Consensus with $t < n/3$, O(n2) Messages, and O(1) Expected Time". In: J. ACM (2015).

[11] M. O. Rabin. "Randomized byzantine generals". In: FOCS. 1983.

[12] A. Mazurkiewicz. "Trace Theory". In: Advances in Petri Nets 1986, Part II on Petri Nets: Applications and Relationships to Other Models of Concurrency. Bad Honnef: Springer-Verlag, 1987, pp. 279-324. ISBN: 0387179062.
[13] W. Zielonka. "Safe Executions of Recognizable Trace Languages by Asynchronous Automata". In: *Logic at Botik*. Vol. 363. Lecture Notes in Computer Science. Springer, 1989, pp. 278-289.

[14] V. Diekert and G. Rozenberg, eds. *The Book of Traces*. World Scientific, 1995.

[15] V. Diekert and A. Muscholl. "Trace Theory". In: *Encyclopedia of Parallel Computing*. Springer, 2011, pp. 2071-2079.

[16] A. Auvolat, D. Frey, M. Raynal, and F. Taïani. "Money Transfer Made Simple". In: *Bulletin of Association for Theoretical Computer Science (BEATCS)* 132 (Oct. 2020). ISSN: 0252-9742.

[17] R. D. Blumofe and C. E. Leiserson. "Scheduling Multithreaded Computations by Work Stealing". In: *J. ACM* 46.5 (Sept. 1999), pp. 720-748. ISSN: 0004-5411.

[18] D. Hendler, Y. Lev, and N. Shavit. "Dynamic memory ABP work-stealing". In: *Distributed Computing: 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4-7, 2004. Proceedings 18*. Springer. 2004, pp. 188-200.

[19] M. M. Michael, M. T. Vechev, and V. A. Saraswat. "Idempotent work stealing". In: *Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming*. 2009, pp. 45-54.

[20] J. Dinan, D. B. Larkins, P. Sadayappan, S. Krishnamoorthy, and J. Nieplocha. "Scalable work stealing". In: *SC. ACM*, 2009.