Damien Imbs

Achour Mostéfaoui

Matthieu Perrin

Michel Raynal

Another Look at the Implementation of Read/write Registers in Crash-prone Asynchronous Message-Passing Systems (Extended Version)

Keywords: Asynchronous system, Atomicity, Communication abstraction, Linearizability, Message-passing system, Process crash, Read/write atomic register, Snapshot object

Yet another paper on" the implementation of read/write registers in crash-prone asynchronous messagepassing systems! Yes..., but, differently from its predecessors, this paper looks for a communication abstraction which captures the essence of such an implementation in the same sense that total order broadcast can be associated with consensus, or message causal delivery can be associated with causal read/write registers. To this end, the paper introduces a new communication abstraction, named SCD-broadcast (SCD standing for "Set Constrained Delivery"), which, instead of a single message, delivers to processes sets of messages (whose size can be arbitrary), such that the sequences of message sets delivered to any two processes satisfies some constraints. The paper then shows that: (a) SCD-broadcast allows for a very simple implementation of a snapshot object (and consequently also of atomic read/write registers) in crashprone asynchronous message-passing systems; (b) SCD-broadcast can be built from snapshot objects (hence SCD-broadcast and snapshot objects -or read/write registers-are "computationally equivalent"); (c) SCDbroadcast can be built in message-passing systems where any minority of processes may crash (which is the weakest assumption on the number of possible process crashes needed to implement a read/write register).

Introduction

The "one-shot" terracotta tablets introduced and used at Sumer about 3030 BC [START_REF] Kramer | History Begins at Sumer: Thirty-Nine Firsts in Man's Recorded History[END_REF], and the "multi-shot" palimpsests used in the middle-age, can be considered as ancestors of the read/write register abstraction. Such an object provides its users with a write operation which defines a new value of the register, and a read operation which returns its value. When considering sequential computing, read/write registers are universal in the sense that they are assumed to allow solving any problem that can be solved [START_REF] Turing | On computable numbers with an application to the Entscheidungsproblem[END_REF].

On the variety of read/write registers and their distributed implementation In a shared read/write memory system, the registers are given for free. The situation is different in a message-passing system, where the computing entities (processes) communicate by sending and receiving messages transmitted through a communication network. Hence, in such a distributed context, a register is not given for free, but constitutes a communication abstraction which must be built by a distributed algorithm with the help of the local memories of the processes and the communication network.

Several types of registers have been proposed. They differ according to (a) their size (from binary registers which contain a single bit, to bounded and unbounded registers); (b) their behavior in the presence of concurrency (safe, regular, atomic [START_REF] Lamport | On interprocess communication, Part I: basic formalism[END_REF]); (c) the number of processes which are allowed to read them (Single-Reader -SR-vs Multi-Reader -MR-register); and (d) the number of processes which are allowed to write them (Single-Writer -SR-vs Multi-Writer -MR-register), which gives four possible combinations from SWSR to MWMR. There are algorithms building MWMR atomic (bounded and unbounded) registers from SWSR binary safe registers [START_REF] Lamport | On interprocess communication, Part I: basic formalism[END_REF] (see [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Lynch | Distributed algorithms[END_REF][START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF] for surveys of such algorithms).

As far as a read/write register is concerned, atomicity means that (a) each read or write operation appears as if it had been executed instantaneously at a single point of the time line, (b) this point appears between its start event and its end event, (c) no two operations appear at the same point of the time line, and (d) a read returns the value written by the closest preceding write operation (or the initial value of the register if there is no preceding write) [START_REF] Lamport | On interprocess communication, Part I: basic formalism[END_REF][START_REF] Misra | Axioms for memory access in asynchronous hardware systems[END_REF]. Linearizability is atomicity extended to any object defined from a sequential specification on total operations [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF]. In the following, we consider the terms atomicity and linearizability as synonyms. Hence, a sequence of read and write operations satisfying atomicity is said to be linearizable, and is called a linearization. The point of the time line at which an operation appears to have been executed is called its linearization point.

Many distributed algorithms have been proposed, which build a read/write register on top of a messagepassing system, be it failure-free or failure-prone. In the failure-prone case, the addressed failure models are the process crash failure model, and the Byzantine process failure model (see textbooks, e.g., [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Lynch | Distributed algorithms[END_REF][START_REF] Raynal | Communication and agreement abstractions for fault-tolerant asynchronous distributed systems[END_REF][START_REF] Raynal | Distributed algorithms for message-passing systems[END_REF]). When considering process crash failures (the one considered in this paper 1 ), the most famous of these algorithms was proposed by H. Attiya, A. Bar-Noy, and D. Dolev in [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF]. This algorithm, usually called ABD according to the names of its authors, considers an n-process asynchronous system in which up to t < n/2 processes may crash. As t < n/2 is an upper bound of the number of process crashes which can be tolerated (see [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF]), this algorithm is t-resilient optimal. Its instances implementing SWMR or MWMR atomic read/write registers rely on (a) quorums [START_REF] Vukolic | Quorum systems, with applications to storage and consensus[END_REF], and (b) a classical broadcast/reply communication pattern. This communication pattern is used twice in a read operation, and once (twice) in a write operation for an SWMR (MWMR) atomic read/write register.

Other algorithms -each with its own properties-implementing atomic read/write registers on top of crashprone asynchronous message-passing systems can be found in the literature ( [START_REF] Attiya | Efficient and robust sharing of memory in message-passing systems[END_REF][START_REF] Dutta | Fast access to distributed atomic memory[END_REF][START_REF] Th | Oh-RAM! One and a half round read/write atomic memory[END_REF][START_REF] Mostéfaoui | Two-bit messages are sufficient to implement atomic read/write registers in crashprone systems[END_REF] to cite a few; see also the analytic presentation given in [START_REF] Ruppert | Implementing shared registers in asynchronous message-passing systems[END_REF]).

From registers to snapshot objects The snapshot object was introduced in [START_REF] Afek | Atomic snapshots of shared memory[END_REF][START_REF] Anderson | Multi-writer composite registers[END_REF]. A snapshot object is an array REG [1..m] of atomic read/write registers which provides the processes with two operations, denoted write() and snapshot(). If the base registers are SWMR the snapshot is called SWMR snapshot (and we have then m = n). In this case, the invocation of write(v) by a process p i assigns v to REG[i], and the invocation of snapshot() by a process p i returns the value of the full array as if the operation had been executed instantaneously. If the base registers are MWMR, the snapshot is called MWMR snapshot. The invocation of write(r, v), where 1 ≤ r ≤ m, by a process p i assigns v to REG[r], and snapshot() is defined as before. Said another way, the operations write() and snapshot() are atomic, i.e., in any execution of an SWMR (or MWMR) snapshot object, its operations write() and snapshot() are linearizable.

Implementations of both SWMR and MWMR snapshot objects on top of read/write atomic registers have been proposed (e.g., [START_REF] Afek | Atomic snapshots of shared memory[END_REF][START_REF] Anderson | Multi-writer composite registers[END_REF][START_REF] Imbs | Help when needed, but no more: efficient read/write partial snapshot[END_REF][START_REF] Inoue | Linear time snapshots using multi-writer multi-reader registers[END_REF]). The "hardness" to build snapshot objects in read/write systems and associated lower bounds are presented in the survey [START_REF]How hard is it to take a snapshot?[END_REF]. The best algorithm known to implement an SWMR snapshot requires O(n log n) read/write on the base SWMR registers for both the write() and snapshot() operations [START_REF] Attiya | snapshots in O(n log n) operations[END_REF]. As far as MWMR snapshot objects are concerned, there are implementations where each operation has an O(n) cost2 .

As far as the construction of an SWMR (or MWMR) snapshot object in crash-prone asynchronous messagepassing systems where t < n/2 is concerned, it is possible to stack two constructions: first an algorithm implementing SWMR (or MWMR) atomic read/write registers (such as ABD), and, on top of it, an algorithm implementing an SWMR (or MWMR) snapshot object. This stacking approach provides objects whose operation cost is O(n 2 log n) messages for SWMR snapshot, and O(n 2 ) messages for MWMR snapshot. An algorithm based on the same communication pattern as ABD, which builds an atomic SWMR snapshot object "directly" (i.e., without stacking algorithms) was recently presented in [START_REF] Delporte-Gallet | Implementing snapshot objects on top of crashprone asynchronous message-passing systems[END_REF] (the aim of this algorithm is to perform better that the stacking approach in concurrency-free executions).

Another look at the implementation of read/write registers and snapshot objects In sequential computing, there are "natural" pairings linking data structures and control structures. The most simple examples are the pair "array and for loop", and the pair "tree and recursion".

When we look at the implementation of a causal read/write register [START_REF] Ahamad | Causal memory: definitions, implementation and programming[END_REF] on top of a (crash-free or crashprone) message-passing system, the causal message delivery broadcast abstraction [START_REF] Birman | Reliable communication in the presence of failures[END_REF][START_REF] Raynal | The causal ordering abstraction and a simple way to implement it[END_REF] is the appropriate communication abstraction. Namely, given this abstraction for free, the algorithms implementing the read and write operations build on top of it, become very simple, need only a few lines, and are easy to understand and to prove correct. Of course, this is due to the fact that the causal broadcast abstraction captures and abstracts the causality relation needed to implement a causal read/write register. Similarly, total order broadcast is the communication abstraction associated with the consensus object [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. This is summarized in Table As already said, all the algorithms we know which implement atomic read/write registers, and (by stacking transitivity or directly) SWMR or MWMR snapshots objects, on top of crash-prone asynchronous messagepassing systems, are based on a broadcast/reply pattern plus the use of intersecting quorums. Hence, the following question naturally arises: Is this approach the "only" way to implement a snapshot object (or an atomic register), or is there a specific communication abstraction which captures the essence and simplifies the implementation of snapshot objects (and atomic read/write registers)?

Content of the paper Informatics in general (and distributed computing in particular) is a science of abstractions, and this paper is distributed programming abstraction-oriented. It strives to address a "desired level of abstraction and generality -one that is broad enough to encompass interesting new situations yet specific enough to address the crucial issues" as expressed in [START_REF] Fischer | Appraising two decades of distributed computing theory research[END_REF]. More precisely, it answers the previous question in a positive way. To this end, it presents a simple broadcast abstraction which matches -and therefore captures the essence of-snapshot objects (and atomic read/write registers). We call it Set-Constrained Delivery Broadcast (in short SCD-broadcast). Given this communication abstraction, it is possible to quorum-free build snapshot objects, and vice versa. Hence, similarly to consensus and total order broadcast, SCD-broadcast and snapshot objects have the same computational power (Table 1).

The SCD-broadcast communication abstraction allows a process to broadcast messages, and to deliver sets of messages (instead of single messages) in such a way that, if a process p i delivers a message set3 ms containing a message m, and later delivers a message set ms ′ containing a message m ′ , then no process p j can deliver first a set containing m ′ and later another set containing m. Let us notice that p j is not prevented from delivering m and m ′ in the same set.

The implementation of an instance of SCD-broadcast costs O(n 2 ) messages. It follows that the cost of a snapshot operation (or a read/write register operation) on top of a message-passing asynchronous system, where any minority of processes may crash, is also O(n 2 ) for both SWMR and MWMR snapshot objects (i.e., better than the stacking approach for SWMR snapshot objects). Additionally, be the snapshot objects that are built SWMR or MWMR, their implementation differ only in the fact that their underling read/write registers are SWMR or MWMR. This provides us with a noteworthy genericity-related design simplicity.

Of course, there is rarely something for free. The algorithms implementing the snapshot and write operations are simple because the SCD-broadcast abstraction hides enough "implementation details" and provides consequently a high level abstraction (much higher than the simple broadcast used in ABD-like algorithms). Its main interest lies in its capture of the high level message communication abstraction that, despite asynchrony and process failures, allows simple message-passing implementations of shared memory objects such as snapshot objects and atomic read/write registers.

Roadmap

The paper is composed of 7 sections. Section 2 presents the two base computation models concerned in this paper, (read/write and message-passing). Section 3 presents the SCD-broadcast communication abstraction. Then, Section 4 presents a simple algorithm which implements a snapshot object on top of an asynchronous system enriched with SCD-broadcast, in which any number of processes may crash. Section 6 addresses the other direction, namely, it presents an algorithm building the SCD-broadcast abstraction on top of an asynchronous system enriched with snapshot objects and where any number of processes may crash. Section 7 concludes the paper. A noteworthy feature of the algorithms that are presented lies in their simplicity, which is a first class property.

Appendix A describes an implementation of SCD-broadcast suited to asynchronous message-passing systems where any minority of processes may crash. Hence, being implementable in the weakest4 messagepassing system model in which a read/write register can be built, SCD-broadcast is not "yet another oracle" which makes things simpler to understand but cannot be implemented. Appendix B presents simplified SCDbased algorithms which build atomic and sequentially consistent read/write registers.

Basic Computation Models

This section presents two basic computation models. In both cases, the process model is the same.

Processes

The computing model is composed of a set of n asynchronous sequential processes, denoted p 1 , ..., p n . "Asynchronous" means that each process proceeds at its own speed, which can be arbitrary and always remains unknown to the other processes.

A process may halt prematurely (crash failure), but it executes its local algorithm correctly until its possible crash. The model parameter t denotes the maximal number of processes that may crash in a run. A process that crashes in a run is said to be faulty. Otherwise, it is non-faulty. Hence a faulty process behaves as a non-faulty process until it crashes.

Basic crash-prone asynchronous shared memory model

Atomic read/write register The notion of an atomic read/write register has been formalized in [START_REF] Lamport | On interprocess communication, Part I: basic formalism[END_REF][START_REF] Misra | Axioms for memory access in asynchronous hardware systems[END_REF]. An MWMR atomic register (say REG) is a concurrent object which provides each process with an operation denoted REG.write(), and an operation denoted REG.read(). When a process invokes REG.write(v) it defines v as being the new value of REG. An MWMR atomic register is defined by the following set of properties.

• Liveness. An invocation of an operation by a non-faulty process terminates.

• Consistency (safety). All the operations invoked by the processes, except possibly -for each faulty process-the last operation it invoked, appear as if they have been executed sequentially and this sequence of operations is such that:

each read returns the value written by the closest write that precedes it (or the initial value of REG if there is no preceding write),

if an operation op1 terminates before an operation op2 starts, then op1 appears before op2 in the sequence.

This set of properties states that, from an external observer point of view, the read/write register appears as if it is accessed sequentially by the processes, and this sequence (a) respects the real-time access order, and (b) belongs to the sequential specification of a register.

Notation The previous computation model is denoted CARW n,t [∅] (Crash Asynchronous Read-Write). This basic read/write model is also called wait-free read/write model. The symbol ∅ means there is no specific constraint on t, which is equivalent to t < n, as it is always assumed that not all processes crash.

Snapshot object

Basic crash-prone asynchronous message-passing model

Communication Each pair of processes communicate by sending and receiving messages through two unidirectional channels, one in each direction. Hence, the communication network is a complete network: any process p i can directly send a message to any process p j (including itself). A process p i invokes the operation "send TYPE(m) to p j " to send to p j the message m, whose type is TYPE. The operation "receive TYPE() from p j " allows p i to receive from p j a message whose type is TYPE.

Each channel is reliable (no loss, corruption, nor creation of messages), not necessarily first-in/first-out, and asynchronous (while the transit time of each message is finite, there is no upper bound on message transit times).

Let us notice that, due to process and message asynchrony, no process can know if another process crashed or is only very slow.

Notation and necessary and sufficient condition This computation model is denoted CAMP n,t [∅] (Crash Asynchronous Message-Passing).

The constraint (t < n/2) is a necessary and sufficient condition to implement an atomic read/write register in CAMP n,t [∅] [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF]. Hence, the model CAMP n,t [∅] whose runs are constrained by t < n/2 is denoted

CAMP n,t [t < n/2].

A Broadcast Abstraction: Set-Constrained Message Delivery

Definition The set-constrained broadcast abstraction (SCD-broadcast) provides the processes with two operations, denoted scd_broadcast() and scd_deliver(). The first operation takes a message to broadcast as input parameter. The second one returns a non-empty set of messages to the process that invoked it. Using a classical terminology, when a process invokes scd_broadcast(m), we say that it "scd-broadcasts a message m". Similarly, when it invokes scd_deliver() and obtains a set of messages ms, we say that it "scd-delivers a set of messages ms". By a slight abuse of language, we also say that a process "scd-delivers a message m" when it delivers a message m ∈ ms.

SCD-broadcast is defined by the following set of properties, where we assume -without loss of generalitythat all the messages that are scd-broadcast are different.

• Validity. If a process scd-delivers a set containing a message m, then m was scd-broadcast by some process.

• Integrity. A message is scd-delivered at most once by each process.

• MS-Ordering. If a process p i scd-delivers first a message m belonging to a set ms i and later a message m ′ belonging to a set ms ′ i = ms i , then no process scd-delivers first the message m ′ in some scddelivered set ms ′ j and later the message m in some scd-delivered set ms j = ms ′ j .

• Termination-1. If a non-faulty process scd-broadcasts a message m, it terminates its scd-broadcast invocation and scd-delivers a message set containing m.

• Termination-2. If a non-faulty process scd-delivers a message m, every non-faulty process scd-delivers a message set containing m.

Termination-1 and Termination-2 are classical liveness properties (found for example in Uniform Reliable Broadcast). The other ones are safety properties. Validity and Integrity are classical communication-related properties. The first states that there is neither message creation nor message corruption, while the second states that there is no message duplication.

The MS-Ordering property is new, and characterizes SCD-broadcast. It states that the contents of the sets of messages scd-delivered at any two processes are not totally independent: the sequence of sets scd-delivered at a process p i and the sequence of sets scd-delivered at a process p j must be mutually consistent in the sense that a process p i cannot scd-deliver first m ∈ ms i and later m ′ ∈ ms ′ i = ms i , while another process p j scd-delivers first m ′ ∈ ms ′ j and later m ∈ ms j = ms ′ j . Let us nevertheless observe that if p i scd-delivers first m ∈ ms i and later m ′ ∈ ms ′ i , p j may scd-deliver m and m ′ in the same set of messages. An example Let m 1 , m 2 , m 3 , m 4 , m 5 , m 6 , m 7 , m 8 , ... be messages that have been scd-broadcast by different processes. The following scd-deliveries of message sets by p 1 , p 2 and p 3 respect the definition of SCD-broadcast:

• at p 1 : {m 1 , m 2 }, {m 3 , m 4 , m 5 }, {m 6 }, {m 7 , m 8 }. • at p 2 : {m 1 }, {m 3 , m 2 }, {m 6 , m 4 , m 5 }, {m 7 }, {m 8 }. • at p 3 : {m 3 , m 1 , m 2 }, {m 6 , m 4 , m 5 }, {m 7 }, {m 8 }.
Differently, due to the scd-deliveries of the sets including m 2 and m 3 , the following scd-deliveries by p 1 and p 2 do not satisfy the MS-broadcast property:

• at p 1 : {m 1 , m 2 }, {m 3 , m 4 , m 5 }, ... • at p 2 : {m 1 , m 3 }, {m 2 }, ...

A containment property Let ms ℓ

i be the ℓ-th message set scd-delivered by p i . Hence, at some time, p i scd-delivered the sequence of message sets

ms 1 i , • • • , ms x i . Let MS x i = ms 1 i ∪ • • • ∪ ms x i .
The following property follows directly from the MS-Ordering and Termination-2 properties:

• Containment. ∀ i, j, x, y: (MS x i ⊆ MS y j ) ∨ (MS y j ⊆ MS x i ).
Remark 1: Weakening SCD-broadcast If the messages in a message set are delivered one at a time, and the MS-Ordering property is suppressed, SCD-broadcast boils down to Reliable Broadcast.

Remark 2: On the partial order created by the message sets The MS-Ordering and Integrity properties establish a partial order on the set of all the messages, defined as follows. Let → i be the local message delivery order at a process p i defined as follows: m → i m ′ if p i scd-delivers the set containing m before the set containing m ′ . As no message is scd-delivered twice, it is easy to see that → i is a partial order (locally know by p i ). The reader can check that there is a total order (which remains unknown to the processes) on the whole set of messages, that complies with the partial order ∪ 1≤i≤n → i . This is where SCD-broadcast can be seen as a weakening of total order broadcast. • done i is a Boolean variable.

• reg i [1.
.m] contains the current value of REG [1..m], as known by p i .

• tsa i [1..m]
= (h1 < h2) ∨ ((h1 = h2) ∧ (i1 < i2)).
Algorithm 1: snapshot operation (Lines 1-4) When p i invokes REG.snapshot(), it first sets done i to false, and invokes scd_broadcast SYNC(i). SYNC() is a synchronization message, whose aim is to entail the refreshment of the value of reg i [1..m] (lines 11-17) which occurs before the setting of done i to true (line 18). When this happens, p i returns the value of its local variable reg i [1..m] and terminates its snapshot invocation. when the message set [START_REF] Delporte-Gallet | Implementing snapshot objects on top of crashprone asynchronous message-passing systems[END_REF] for each r such that WRITE(r, -, -) ∈ scd-delivered message set do [START_REF] Dutta | Fast access to distributed atomic memory[END_REF] let date, writer be the greatest timestamp in the messages WRITE(r, -, -); [START_REF]How hard is it to take a snapshot?[END_REF] if (tsai[r] <ts date, writer ) [START_REF] Ellen | Time lower bounds for implementations of multi-writer snapshots[END_REF] then let v the value in WRITE(r, -, date, writer );

operation snapshot() is (1) donei ← false; (2) scd_broadcast SYNC(i); (3) wait(donei); (4) return(reg i [1..m]).
{ WRITE(rj 1 , vj 1 , datej 1 , j1 ), • • • , WRITE(rj x , vj x , datej x , jx ), SYNC(jx+1), • • • , SYNC(jy) } is scd-delivered do (
(15) regi[r] ← v; tsai[r] ← date, writer (16)
end if (17) end for; [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF]

if ∃ℓ : j ℓ = i then donei ← true end if.
Algorithm 1: Construction of an MWMR snapshot object CAMP n,t [SCD-broadcast] (code for p i ) Algorithm 1: write operation (Lines 5-10) When a process p i wants to assign a value v to REG[r], it invokes REG.write(r, v). This operation is made up of two parts. First p i executes a re-synchronization (lines 5-7, exactly as in the snapshot operation) whose side effect is here to provide p i with an up-to-date value of tsa i [r].date. In the second part, p i associates the timestamp tsa i [r].date + 1, i with v, and invokes scd_broadcast WRITE(r, v, tsa i [r].date + 1, i ) (line 9). In addition to informing the other processes on its write of REG[r], this message WRITE() acts as a re-synchronization message, exactly as a message SYNC(i). When this synchronization terminates (i.e., when the Boolean done i is set to true), p i returns from the write operation (line 10).

Algorithm 1: scd-delivery of a set of messages When p i scd-delivers a message set, namely,

{ WRITE(r j 1 , v j 1 , date j 1 , j 1 ), • • • , WRITE(r jx , v jx , date jx , j x ), SYNC(j x+1 ), • • • , SYNC(j y ) } it first looks if there are messages WRITE().
If it is the case, for each register REG[r] for which there are messages WRITE(r, -, -) (line 11), p i computes the maximal timestamp carried by these messages (line 12), and updates accordingly its local representation of REG[r] (lines 13-15). Finally, if p i is the sender of one of these messages (WRITE() or SYNC()), done i is set to true, which terminates p i 's re-synchronization (line 18).

Message cost An invocation of snapshot() involves one invocation of scd_broadcast(), and an invocation of write() involves two such invocations. It is shown in Appendix A that, in a message-passing system, scd_broadcast() costs O(n 2 ) protocol messages. It follows that, in such systems, the message cost of both operations of a snapshot object is O(n 2 ). (This remains true for SWMR snapshot objects, see Appendix B.)

Proof of Algorithm 1

As they are implicitly used in the proofs that follow, let us recall the properties of the SCD-broadcast abstraction. The non-faulty processes scd-deliver the same messages (exactly one each), and each of them was scd-broadcast. As a faulty process behaves correctly until it crashes, it scd-delivers a subset of the messages scd-delivered by the non-faulty processes.

Without loss of generality, we assume that there is an initial write operation issued by a non-faulty process. Moreover, if a process crashes in a snapshot operation, its snapshot is not considered; if a process crashes in a write operation, its write is considered only if the message WRITE() it sent at line 9 is scd-delivered to at least one non-faulty process (and by the Termination-2 property, at least to all non-faulty processes). Let us notice that a message SYNC() scd-broadcast by a process p i does not modify the local variables of the other processes.

Proof of Lemmas for Theorem 1 Lemma 1 If a non-faulty process invokes an operation, it returns from its invocation.

Proof Let p i be a non-faulty process that invokes a read or write operation. By the Termination-1 property of SCD-broadcast, it eventually receives a message set containing the message SYNC() or WRITE() it sends at line 2, 6 or 9. As all the statements associated with the scd-delivery of a message set (lines 11-18) terminate, it follows that the synchronization Boolean done i is eventually set to true. Consequently, p i returns from the invocation of its operation. .m] at line 18 (end of the processing of a message set by process p i ). Let TSA = ∪ 1≤i≤n TSA i .

Lemma 2

The order ≤ tsa is total on TSA.

Proof Let us first observe that, for any i, all values in TSA i are totally ordered (this comes from ts i [1.

.m] whose entries can only increase, lines 13 and 15). Hence, let tsa1[1..m] be an array value of TSA i , and tsa2[1..m] an array value of TSA j , where i = j. Let us assume, by contradiction, that ¬(tsa1 ≤ tsa tsa2) and ¬(tsa2 ≤ tsa tsa1). As ¬(tsa1 ≤ tsa tsa2), there is a registers r such that tsa2[r] < tsa1[r]. According to lines 13 and 15, there is a message WRITE(r, -, tsa 1[r]) received by p i when tsa i = tsa1 and not received by p j when tsa j = tsa2 (because tsa2[r] < tsa1[r]). Similarly, there is a message WRITE(r ′ , -, tsa2[r ′ ]) received by p j when tsa j = tsa2 and not received by p i when tsa i = tsa1. This situation contradicts the MS-Ordering property, from which we conclude that either tsa1 ≤ tsa tsa2 or tsa2 ≤ tsa tsa1.

2 Lemma 2

Definitions Let us associate a timestamp ts(write(r, v)) with each write operation as follows. Let p i be the invoking process; ts(write(r, v)) is the timestamp of v as defined by p i at line 9, i.e., tsa i [r].date + 1, i . Let op1 and op2 be any two operations. The relation ≺ on the whole set of operations is defined as follows: op1 ≺ op2 if op1 terminated before op2 started. It is easy to see that ≺ is a real-time-compliant partial order on all the operations.

Lemma 3

No two distinct write operations on the same register write1(r, v) and write2(r, w) have the same timestamp, and (write1(r, v) ≺ write2(r, w)) ⇒ (ts(write1) < ts ts(write2)).

Proof Let date1, i and date2, j be the timestamp of write1(r, v) and write2(r, w), respectively. If i = j, write1(r, v) and write2(r, w) have been produced by different processes, and their timestamp differ at least in their process identity.

So, let us consider that the operations have been issued by the same process p i , with write1(r, v) first. As write1(r, v) precedes write2(r, w), p i first invoked scd_broadcast WRITE(r, v, date1, i ) (line 9) and later WRITE(r, w, date2, i ). It follows that these SCD-broadcast invocations are separated by a local reset of the Boolean done i at line 16. Moreover, before the reset of done i due to the scd-delivery of the message {• • • ,WRITE(r, v, date1, i ), • • • }, we have tsa i [r].date i ≥ date1 (lines 12-16). Hence, we have tsa i [r].date ≥ date1 before the reset of done i (line 18). Then, due to the "+1" at line 9, WRITE(r, w, date2, i ) is such that date2 > date1, which concludes the proof of the first part of the lemma.

Let us now consider that write1(r, v) ≺ write2(r, w). If write1(r, v) and write2(r, w) have been produced by the same process we have date1 < date2 from the previous reasoning. So let us assume that they have been produced by different processes p i and p j . Before terminating write1(r, v) (when the Boolean done i is set true at line 18), p i received a message set ms1 i containing the message WRITE(r, v, date1, i ). When p j executes write2(r, w), it first invokes scd_broadcast SYNC(j) at line 6. Because write1(r, v) terminated before write2(r, w) started, this message SYNC(j) cannot belong to ms1 i .

Due to Integrity and Termination-2 of SCD-broadcast, p j eventually scd-delivers exactly one message set ms1 j containing WRITE(r, v, date1, i ). Moreover, it also scd-delivers exactly one message set ms2 j containing its own message SYNC(j). On the the other side, p i scd-delivers exactly one message set ms2 i containing the message SYNC(j). It follows from the MS-Ordering property that, if ms2 j = ms1 j , p j cannot scd-deliver ms2 j before ms1 j . Then, whatever the case (ms1 j = ms2 j or ms1 j is scd-delivered at p j before ms2 j ), it follows from the fact that the messages WRITE() are processed (lines 11-17) before the messages SYNC(j) (line 18), that we have tsa j [r] ≥ date1, i when done j is set to true. It then follows from line 9 that date2 > date1, which concludes the proof of the lemma.

2 Lemma 3

Associating timestamp arrays with operations Let us associate a timestamp array tsa(op) [1..m] with each operation op() as follows.

• Case op() = snapshot(). Let p i be the invoking process; tsa(op) is the value of tsa i [1..m] when p i returns from the snapshot operation (line 4).

• Lemma 4 Let op and op ′ be two distinct operations such that op ≺ op ′ . We have tsa(op) ≤ tsa tsa(op ′ ). Moreover, if op ′ is a write operation, we have tsa(op) < tsa tsa(op ′ ).

Proof Let p i and p j be the processes that performed op and op ′ , respectively. Let SYNC j be the SYNC(j) message sent by p j (at line 2 or 6) during the execution of op ′ . Let term_tsa i be the value of tsa i [1..m] when op terminates (line 4 or 10), and sync_tsa j the value of tsa j [1..m] when done j becomes true for the first time after p j sent SYNC j (line 3 or 7). Let us notice that term_tsa i and sync_tsa j are elements of the set TSA.

According to lines 13 and 15, for all r, tsa i [r] is the largest timestamp carried by a message WRITE(r, v, -) received by p i in a message set before op terminates. Let m be a message such that there is a set sm scddelivered by p i before it terminated op. As p j sent SYNC j after p i terminated, p i did not receive any set containing SYNC j before it terminated op. By the properties Termination-2 and MS-Ordering, p j received message m in the same set as SYNC j or in a message set sm ′ received before the set containing SYNC j . Therefore, we have term_tsa i ≤ tsa sync_tsa j .

If op is a snapshot operation, then tsa(op) = term_tsa i . Otherwise, op() = write(r, v). As p i has to wait until it processes a set of messages including its WRITE() message (and executes line 18), we have ts(op) < ts term_tsa i [r]. Finally, due to the fact that term_tsa i ∈ TSA and Lemma 2, we have tsa(op) ≤ tsa term_tsa i .

If op ′ is a snapshot operation, then sync_tsa j = tsa(op ′ ) (line 4). Otherwise, op() = write(r, v) and thanks to the +1 in line 9, sync_tsa j [r] is strictly smaller than tsa(op ′ )[r] which, due to Lemma 2, implies sync_tsa j < tsa tsa(op ′ ).

It follows that, in all cases, we have tsa(op) ≤ tsa term_tsa i ≤ tsa sync_tsa j ≤ tsa tsa(op ′ ) and if op ′ is a write operation, we have tsa(op) ≤ tsa term_tsa i ≤ tsa sync_tsa j < tsa tsa(op ′ ), which concludes the proof of the lemma.

2 Lemma 4

The previous lemmas allow the operations to be linearized (i.e., totally ordered in an order compliant with both the sequential specification of a register, and their real-time occurrence order) according to a total order extension of the reflexive and transitive closure of the → lin relation defined thereafter. Definition 1 Let op, op ′ be two operations. We define the → lin relation by op → lin op ′ if one of the following properties holds:

• op ≺ op ′ ,
• tsa(op) < tsa tsa(op ′ ),

• tsa(op) = tsa(op ′ ), op is a write operation and op ′ is a snapshot operation,

• tsa(op) = tsa(op ′ ), op and op ′ are two write operations on the same register and ts(op) < ts ts(op ′ ), Lemma 5 The snapshot object built by Algorithm 1 is linearizable.

Proof We recall the definition of the → lin relation: op → lin op ′ if one of the following properties holds:

• op ≺ op ′ ,
• tsa(op) < tsa tsa(op ′ ),

• tsa(op) = tsa(op ′ ), op is a write operation and op ′ is a snapshot operation,

• tsa(op) = tsa(op ′ ), op and op ′ are two write operations on the same register and ts(op) < ts ts(op ′ ),

We define the → ⋆ lin relation as the reflexive and transitive closure of the → lin relation. Let us prove that the → ⋆ lin relation is a partial order on all operations. Transitivity and reflexivity are given by construction. Let us prove antisymmetry. Suppose there are op 0 , op 2 , ..., op m such that op 0 = op m and op i → lin op i+1 for all i < m. By Lemma 4, for all i < m, we have tsa(op i ) ≤ tsa tsa(op i+1 ), and tsa(op m ) = tsa(op 0 ), so the timestamp array of all operations are the same. Moreover, if op i is a snapshot operation, then op i ≺ op (i+1)%m is the only possible case (% stands for "modulo") , and by Lemma 4 again, op (i+1)%m is a snapshot operation. Therefore, only two cases are possible.

• Let us suppose that all the op i are snapshot operations and for all i, op i ≺ op (i+1)%m . As ≺ is a partial order relation, it is antisymmetric, so all the op i are the same operation.

• Otherwise, all the op i are write operations. By Lemma 4, for all op i ≺ op (i+1)%m . The operations op i and op i+1%m are ordered by the fourth point, so they are write operations on the same register and ts(op i ) < ts ts(op i+1%m ). By antisymmetry of the < ts relation, all the op i have the same timestamp, so by Lemma 3, they are the same operation, which proves antisymmetry.

Let ≤ lin be a total order extension of → ⋆ lin . Relation ≤ lin is real-time compliant because → ⋆ lin contains ≺. Let us consider a snapshot operation op and a register r such that tsa(op)[r] = date1, i . According to line 10, it is associated to the value v that is returned by read1() for r, and comes from a WRITE(r, v, date1, i ) message sent by a write operation op r = write(r, v). By definition of tsa(op r ), we have tsa(op r ) ≤ tsa tsa(op) (Lemma 4), and therefore op r ≤ lin op. Moreover, for any different write operation op ′ r on r, by Lemma 3, ts(op ′ r ) = ts(op r ). If ts(op ′ r ) < ts ts(op r ), then op ′ r ≤ lin op r . Otherwise, tsa(op) < tsa tsa(op ′ r ), and (due to the first item of the definition of → lin ) we have op ≤ lin op ′ r . In both cases, the value written by op r is the last value written on r before op, according to ≤ lin .

2 Lemma 5

Theorem 1 Algorithm 1 builds an MWMR snapshot object in the system model CAMP n,t [SCD-broadcast].

Proof The proof follows from Lemmas 1-5.

T heorem 1

6 From SWMR Snapshot to SCD-broadcast This section presents an algorithm which builds the SCD-broadcast abstraction in CARW n,t [snapshot]. This algorithm completes the computational equivalence of snapshot and SCD-broadcast. (SWMR snapshot objects can be easily implemented in CAMP n,t [SCD-broadcast] by instantiating Algorithm 1 with m = n, and only allowing p i to invoke REG.write(r, -).)

Algorithm 2

Shared objects The shared memory is composed of two SWMR snapshot objects (as defined above). Let ǫ denote the empty sequence.

• SENT [1.

.n]: is a snapshot object, initialized to [∅, • • • , ∅], such that SENT [i] contains the messages scd-broadcast by p i .

• SETS _SEQ[1..n]: is a snapshot object, initialized to [ǫ, • • • , ǫ], such that SETS _SEQ[i]
contains the sequence of the sets of messages scd-delivered by p i .

The notation ⊕ is used for the concatenation of a message set at the end of a sequence of message sets.

Local objects Each process p i manages the following local objects.

• sent i is a local copy of the snapshot object SENT .

• sets_seq i is a local copy of the snapshot object SETS _SEQ.

• to_deliver i is an auxiliary variable whose aim is to contain the next message set that p i has to scd-deliver.

The function members(set_seq) returns the set of all the messages contained in set_seq.

Description of Algorithm 2 When a process p i invokes scd_broadcast(m), it adds m to sent i [i] and SENT [i] to inform all the processes on the scd-broadcast of m. It then invokes the internal procedure progress() from which it exits once it has a set containing m (line 1).

A background task T ensures that all messages will be scd-delivered (line 2). This task invokes repeatedly the internal procedure progress(). As, locally, both the application process and the underlying task T can invoke progress(), which accesses the local variables of p i , those variables are protected by a local fair mutual exclusion algorithm providing the operations enter_mutex() and exit_mutex() (lines 3 and 11).

operation scd_broadcast(m) is (1) sent i[i] ← sent i[i] ∪ {m}; SENT .write(sent i[i]); progress().
(2) background task T is repeat forever progress() end repeat. procedure progress() is (3) enter_mutex(); (4) catch_up(); [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF] Proof Let us consider two messages m and m ′ . Due to total order property on the operations on the snapshot object SENT , it is possible to order the write operations of m and m ′ into SENT . Without loss of generality, let us assume that m is added to SENT before m ′ . We show that no process scd-delivers m ′ before m. 5Let us consider a process p i that scd-delivers the message m ′ . There are two cases.

sent i ← SENT .snapshot(); (6) to_deliveri ← (∪ 1≤j≤n sent i[j]) \ members(sets_seq i [i]); (7) if (to_deliveri = ∅) then sets_seq i [i] ← sets_seq i [i] ⊕ to_deliveri ; (8) SETS _SEQ[i] ← sets_seq i [i]; (9
• p i scd-delivers the message m ′ at line 9. Hence, p i obtained m ′ from the snapshot object SENT (lines 5-6). As m was written in SENT before m ′ , we conclude that SENT contains m. It then follows from line 6 that, if p i has not scd-delivered m before (i.e., m is not in sets_seq i [i]), then p i scd-delivers it in the same set as m ′ .

• p i scd-delivers the message m ′ at line 16. Due to the predicate used at line 13 to build a set of message to scd-deliver, this means that there is a process p j that has previously scd-delivered a set of messages containing m ′ . Moreover, let us observe that the first time the message m ′ is copied from SENT to some SETS _SEQ[x] occurs at line 8. As m was written in SENT before m ′ , the corresponding process p x cannot see m ′ and not m. It follows from the previous item that p x has scd-delivered m in the same message set (as the one including m ′ ), or in a previous message set. It then follows from the predicate of line 13 that p i cannot scd-delivers m ′ before m.

To summarize, the scd-deliveries of message sets in the procedure catch_up() cannot violate the MS-Ordering property, which is established at lines 6-10.

Conclusion

This paper has introduced a new communication abstraction (SCD-broadcast) providing processes with an abstraction level between reliable broadcast and total order broadcast (which captures the necessary and sufficient constraint on message deliveries which allows consensus objects to be implemented in asynchronous crash-prone message-passing systems). More precisely, SCD-broadcast captures the abstraction level which is "necessary and sufficient" to implement read/write registers and snapshot objects on top of asynchronous message-passing systems prone to process failures. "Sufficient" means here that no other notion or object 6 is needed to build a register or a snapshot object at the abstraction level provided by SCD-broadcast, while "necessary" means that the objects that are built (registers and snapshot objects) are the weakest from a shared memory computational point of view.

As announced in the Introduction, an algorithm implementing SCD-broadcast in an asynchronous messagepassing system where any minority of processes may crash is described in Appendix A. This algorithm requires O(n 2 ) protocol messages per invocation of scd_broadcast(). It follows that the SCD-broadcast-based MWMR snapshot algorithm presented in the paper requires O(n 2 ) protocol messages per invocation of snapshot() or write() operation. This is the best read/write snapshot algorithm we know in the context of asynchronous message-passing systems.

A An Implementation of SCD-broadcast in Message-Passing Systems

This section shows that the SCD-broadcast communication abstraction is not an oracle-like object which allows us to extend our understanding of computing, but cannot be implemented. It describes an implementation of SCD-broadcast in CAMP n,t [t < n/2], which is the weakest assumption on process failures that allows a read/write register to be built on top of an asynchronous message-passing system [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF] (see footnote 4).

To simplify the presentation, and without loss of generality, we consider that the communication channels are FIFO. The associated communication operations are denoted fifo_broadcast() and fifo_deliver().

A.1 Algorithm 3

Local variables at a process p i Each process p i manages the following local variables.

• buffer i : buffer where are stored the messages not yet scd-delivered in a message set.

• to_deliver i : next set of messages to be scd-delivered.

• sn i : local sequence number (initialized to 0), which measures the local progress of p i .

• clock i [1.
.n]: array of sequence numbers. clock i [j] is the greatest sequence number x such that the application message identified by x, j was in a message set scd-delivered by p i .

Operation scd_broadcast() When p i invokes scd_broadcast(m), where m is an application message, it sends the message FORWARD(m, i, sn i , i, sn i ) to itself (this simplifies the writing of the algorithm), and waits until it has no more message from itself pending in buffer i , which means it has scd-delivered a set containing m.

A protocol message FORWARD() (line 1) is made up of five fields: the associated application message m, and two pairs, each made up of a sequence number and a process identity. The first pair (sd, sn) is the identity of the application message, while the second one (f, sn f ) is the local progress (sn f ) of the forwarder process p f when it forwards this protocol message.

Reception of FORWARD(m, sd, sn sd , f, sn f ) When a process p i receives such a protocol message, it first invokes forward(m, sd, sn sd , f, sn f ) to participate in the reliable broadcast of this message (line 3), and then invokes try_deliver() to see if a message set can be scd-delivered (line 4).

Procedure forward() This procedure can be seen as an enrichment (with the fields f and sn f ) of the reliable broadcast implemented by the messages FORWARD(m, sd, sn sd , -, -). Considering such a message FORWARD(m, sd, sn sd , f, sn f ), m was scd-broadcast by p sd at its local time sn sd , and relayed by the forwarding process p f at its local time sn f . If sn sd ≤ clock i [sd], p i has already scd-delivered a message set containing m (see lines 18 and 20). If sn sd > clock i [sd], there are two cases.

• The message m is not in buffer i . In this case, p i creates a quadruplet msg, and adds it to buffer i (lines 8-10). This quadruplet msg.m, msg.sd, msg.f, msg.cl is such that the field msg.m contains the application message m, the field msg.sd contains the id of the sender of this application message, the field msg.sn contains the local date associated with m by its sender, the field msg.cl is an array of size n, such that msg.cl[x] = sequence number (initially +∞) associated with m by p x when it broadcast FORWARD(msg.m, -, -, -, -). This last field is crucial in the scd-delivery of a message set containing m.

After the quadruplet msg has been built, p i first adds it to buffer i (line 10), and invokes (line 11) fifo_broadcast FORWARD(m, sd, sn sd , i, sn i ) to implement the reliable broadcast of m identified by sd, sn sd . Finally, p i records its progress by increasing sn i (line 12).

• There is a quadruplet msg in buffer i associated with m, i.e., msg = m, sd, -, -∈ buffer i (predicate of line 6). In this case, p i assigns sn f to msg.cl[f ] (line 7), thereby indicating that m was known and forwarded by p f at its local time sn f .

operation scd_broadcast(m) is (1) forward(m, i, sni, i, sni);

(2) wait(∄ msg ∈ bufferi : msg.sd = i).

when the message FORWARD(m, sd, sn sd , f, sn f ) is fifo-delivered do % from p f (3) forward(m, sd, sn sd , f, sn f ); (4) try_deliver().

procedure forward(m, sd, sn sd , f, sn f ) is [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF] Algorithm 3: An implementation of SCD-broadcast in CAMP n,t [t < n/2] (code for p i ) Procedure try_deliver() When it executes try_deliver(), p i first computes the set to_deliver i of the quadruplets msg containing application messages m which have been seen by a majority of processes (line 15). From p i 's point of view, a message has been seen by a process p f if msg.cl[f ] has been set to a finite value (line 7).

If a majority of processes received first a message FORWARD(m ′ , -, -, -, -) and later another message FORWARD(m, -, -, -, -), it might be that some process p j scd-delivered a set containing m ′ before scddelivering a set containing m. Therefore, p i must avoid scd-delivering a set containing m before scd-delivering a set containing m ′ . This is done at line 16, where p i withdraws the quadruplet msg corresponding to m if it has not enough information to deliver m ′ (i.e. the corresponding msg ′ is not in to_deliver i ) or it does not have the proof that the situation cannot happen, i.e. no majority of processes saw the message corresponding to msg before the message corresponding to msg ′ .

If to_deliver i is not empty after it has been purged (lines [START_REF] Fischer | Appraising two decades of distributed computing theory research[END_REF][START_REF] Th | Oh-RAM! One and a half round read/write atomic memory[END_REF], p i computes a message set to scd-deliver. This set ms contains all the application messages in the quadruplets of to_deliver i (line 20). These quadruplets are withdrawn from buffer i (line 18). Moreover, before this scd-delivery, p i needs to updates clock i [x] for all the entries such that x = msg.sd where msg ∈ to_deliver i (line 18). This update is needed to ensure that the future uses of the predicate of line 17 are correct.

A.2 Proof of Algorithm 3

Lemma 12 If a process scd-delivers a set containing m, some process invoked scd_broadcast(m).

Proof If process p i scd-delivers a set containing a message m, it has previously added into buffer i a quadruplet msg such that msg.m = m (line 10), for which it has fifo-received at least n 2 FORWARD(m, -, -, -, -) messages. The first of these messages ever sent was sent after a process invoked scd_broadcast(m). 2 Lemma 12 Lemma 13 No process scd-delivers the same message twice.

Proof After a message m scd-broadcast by p sd with a sequence number sn sd is scd-delivered by p i , clock i [sd] ≥ sn sd thanks to line 18 and there is no msg ∈ buffer i with msg.sd = sd and msg.sn = sn sd , as it was re-

  operation write(r, v) is (5) donei ← false; (6) scd_broadcast SYNC(i);[START_REF] Attiya | Sequential consistency versus linearizability[END_REF] wait(donei); (8) donei ← false; (9) scd_broadcast WRITE(r, v, tsai[r].date + 1, i ); (10) wait(donei).

2 1

 21 Lemma Extension of the relation < ts The relation < ts is extended to a partial order on arrays of timestamps, denoted ≤ tsa , defined as follows: tsa1[1..m] ≤ tsa tsa2[1..m] def = ∀r : (tsa1[r] = tsa2[r]∨tsa1[r] < ts tsa2[r]). Moreover, tsa1[1..m] < tsa tsa2[1..m] def = (tsa1[1..m] ≤ tsa tsa2[1..m]) ∧ (tsa1[1..m] = tsa2[1..m]). Definition Let TSA i be the set of the array values taken by ts i [1.

  Case op() = write(r, v). Let min tsa ({A}), where A is a set of array values, denote the smallest array value of A according to < tsa . Let tsa(op) def = min tsa ({tsa[1..m] ∈ TSA such that ts(op) ≤ ts tsa[r]}). Hence, tsa(op) is the first tsa[1..m] of TSA, that reports the operation op() = write(r, v).

2 11 Theorem 2

 2112 Lemma Algorithm 2 implements the SCD-Broadcast abstraction in the system model CARW n,t [t < n]. Proof The proof follows from Lemma 6 (Validity), Lemma 7 (Integrity), Lemmas 8 and 9 (Termination-1), Lemma 10 (Termination-2), and Lemma 11 (MS-Ordering).2 T heorem 2

  .

	Concurrent object	Communication abstraction
	Causal read/write registers	Causal message delivery [9, 35]
	Consensus	Total order broadcast [10]
	Snapshot object (and R/W register)	SCD-broadcast (This paper)

Table

  This object was defined in the introduction. As we have seen, snapshot objects can be built in CARW n,t [∅]. As we have seen there are two types of snapshot objects. SWMR snapshot objects (whose base registers are SWMR), and MWMR snapshot objects (whose base registers are MWMR). In the following we consider MWMR snapshot objects, but the algorithms can be trivially adapted to work with SWMR snapshot objects.CARW n,t [∅] enriched with snapshot objects is denoted CARW n,t [snapshot]. As a snapshot object can be built in CARW n,t [∅] this model has the same computational power as CARW n,t [∅]. It only offers a higher abstraction level.

  Building an MWMR snapshot object on top of CAMP n,t [SCD-broadcast] Let REG[1..m] denote the MWMR snapshot object that is built. Local representation of REG at a process p i At each register p i , REG[1..m] is represented by three local variables reg i [1..m] (data part), plus tsa i [1..m] and done i (control part).

	4 From SCD-broadcast to an MWMR Snapshot Object

Let CAMP n,t [SCD-broadcast] denote CAMP n,t [∅] enriched with the SCD-broadcast abstraction. Hence, this abstraction is given for free. This section presents and proves correct a simple algorithm building an MWMR snapshot object on top of CAMP n,t [SCD-broadcast]. The same algorithm with very few simple modifications can be used to build SWMR or MWMR atomic registers in CAMP n,t [SCD-broadcast] (see Appendix B).

4.1

  is an array of timestamps associated with the values stored in reg i [1..m]. A timestamp is a pair made of a local clock value and a process identity. Its initial value is 0, -. The fields associated with tsa i [r] are denoted tsa i [r].date, tsa i [r].proc . Timestamp-based order relation We consider the classical lexicographical total order relation on timestamps, denoted < ts . Let ts1 = h1, i1 and ts2 = h2, i2 . We have ts1 < ts ts2

	def

  while (∃j, set : set is the first set in sets_seq i [j] : set ⊆ members(sets_seq i [i]) do Algorithm 2: An implementation of SCD-broadcast in CARW n,t [snapshot] (code for p i ) Lemma 11 Let p i be a process that scd-delivers a set ms i containing a message m and later scd-delivers a set ms ′ i containing a message m ′ . No process p j scd-delivers first a set ms ′ j containing m ′ and later a set ms j containing m.

	)	scd_deliver(to_deliveri )
	(10) end if;
	(11) exit_mutex().
	procedure catch_up() is
	(12) sets_seq i ← SETS _SEQ.snapshot();
	(13) (14)	to_deliveri ← set \ members(sets_seq i [i]);
	(15) sets_seq (16) scd_deliver(to_deliveri )
	(17) end while.

i [i] ← sets_seq i [i] ⊕ to_deliveri ; SETS _SEQ[i] ← sets_seq i [i];

  if (sn sd > clocki[sd])[START_REF] Attiya | snapshots in O(n log n) operations[END_REF] then if (∃ msg ∈ bufferi : msg.sd = sd ∧ msg.sn = sn sd ) (7)then msg.cl[f ] ← sn f (8) else threshold[1..n] ← [∞, . . . , ∞]; threshold[f ] ← sn f ; (9)let msg ← m, sd, sn sd , threshold[1..n] ;[START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF] bufferi ← bufferi ∪ {msg};[START_REF] Delporte-Gallet | Implementing snapshot objects on top of crashprone asynchronous message-passing systems[END_REF] fifo_broadcast FORWARD(m, sd, sn sd , i, sni);let to_deliveri ← {msg ∈ bufferi : |{f : msg.cl[f ] < ∞}| > n 2 }; (16) while (∃msg ∈ to_deliveri , msg ′ ∈ bufferi \ to_deliveri : |{f : msg.cl[f ] < msg ′ .cl[f ]}| ≤ n 2 ) do to_deliveri ← to_deliveri \ {msg} end while; (17) if (to_deliveri = ∅) (18)then for each (msg ∈ to_deliveri such that clocki[msg.sd] < msg.sn) do clocki[msg.sd] ← msg.sn end for; (19) bufferi ← bufferi \ to_deliveri ; (20) ms ← {m : ∃ msg ∈ to_deliveri : msg.m = m}; scd_deliver(ms) (21) end if.

	(12)	sni ← sni + 1
	(13)	end if
	(14) end if;
	procedure try_deliver() is
	(15)

For Byzantine failures, see for example[START_REF] Mostéfaoui | Atomic read/write memory in signature-free Byzantine asynchronous message-passing systems[END_REF].

Snapshot objects built in read/write models enriched with operations such as Compare&Swap, or LL/SC, have also been considered, e.g.,[START_REF] Jayanti | An optimal multiwriter snapshot algorithm[END_REF][START_REF] Imbs | Help when needed, but no more: efficient read/write partial snapshot[END_REF]. Here we are interested in pure read/write models.

[START_REF] Anderson | Multi-writer composite registers[END_REF] In the rest of the paper, the identifiers starting with"ms" denote message sets.

From the point of view of the maximal number of process crashes that can be tolerated, assuming failures are independent.

Let us notice that it is possible that a process scd-delivers them in two different message sets, while another process scd-delivers them in the same set (which does not contradicts the lemma).

The notion of intersecting quorums is neither provided by the abstraction level offered by SCD-broadcast, nor required -in addition to SCD-broadcast-to implement registers or snapshot objects. Actually, it is hidden and majority quorums appear only in the implementation of SCD-broadcast.

Acknowledgments

This work has been partially supported by the Franco-German DFG-ANR Project 40300781 DISCMAT (devoted to connections between mathematics and distributed computing), and the French ANR project DESCARTES (devoted to layered and modular structures in distributed computing). The authors want to thank Faith Ellen for fruitful exchanges on shared memory snapshot.

The procedure progress() first invokes the internal procedure catch_up(), whose aim is to allow p i to scd-deliver sets of messages which have been scd-broadcast and not yet locally scd-delivered.

To this end, catch_up() works as follows (lines [START_REF] Dutta | Fast access to distributed atomic memory[END_REF][START_REF]How hard is it to take a snapshot?[END_REF][START_REF] Ellen | Time lower bounds for implementations of multi-writer snapshots[END_REF][START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF][START_REF] Fischer | Appraising two decades of distributed computing theory research[END_REF][START_REF] Th | Oh-RAM! One and a half round read/write atomic memory[END_REF]. Process p i first obtains a snapshot of SETS _SEQ, and saves it in sets_seq i (line 12). This allows p i to know which message sets have been scd-delivered by all the processes; p i then enters a "while" loop to scd-deliver as many message sets as possible according to what was scd-delivered by the other processes. For each process p j that has scd-delivered a message set set containing messages not yet scd-delivered by p i (predicate of line 13), p i builds a set to_deliver i containing the messages in set that it has not yet scd-delivered (line 14), and locally scd-delivers it (line [START_REF] Fischer | Appraising two decades of distributed computing theory research[END_REF]). This local scd-delivery needs to update accordingly both sets_seq i [i] (local update) and SETS _SEQ[i] (global update).

When it returns from catch_up(), p i strives to scd-deliver messages not yet scd-delivered by the other processes. To this end, it first obtains a snapshot of SENT , which it stores in sent i (line 5). If there are messages that can be scd-delivered (computation of to_deliver i at line 6, and predicate at line 7), p i scddelivers them and updates sets_seq i [i] and SETS _SEQ[i] (lines 7-9) accordingly.

Proof of Algorithm 2

Lemma 6 If a process scd-delivers a set containing a message m, some process invoked scd_broadcast(m).

Proof The proof follows directly from the text of the algorithm, which copies messages from SENT to SETS _SEQ, without creating new messages.

2 Lemma 6

Lemma 7 No process scd-delivers the same message twice.

Proof Let us first observe that, due to lines 7 and 15, all messages that are scd-delivered at a process p i have been added to sets_seq i [i]. The proof then follows directly from (a) this observation, (b) the fact that (due to the local mutual exclusion at each process) sets_seq i [i] is updated consistently, and (c) lines 6 and 14, which state that a message already scd-delivered (i.e., a message belonging to sets_seq i [i]) cannot be added to to_deliver i .

Lemma 8 Any invocation of scd_broadcast() by a non-faulty process p i terminates.

Proof The proof consists in showing that the internal procedure progress() terminates. As the mutex algorithm is assumed to be fair, process p i cannot block forever at line 3. Hence, p i invokes the internal procedure catch_up(). It then issues first a snapshot invocation on SETS _SEQ and stores the value it obtains the value of sets_seq i . There is consequently a finite number of message sets in sets_seq i . Hence, the "while" of lines 13-17 can be executed only a finite number of times, and it follows that any invocation of catch_up() by a non-faulty process terminates. The same reasoning (replacing SETS _SEQ by SENT ) shows that process p i cannot block forever when it executes the lines 5-10 of the procedure progress(). , so the previous case applies. After p j broadcasts its message FORWARD(m, sd, sn sd , j, sn j ) on line 11, there is a msg ∈ buffer j with ts(msg) = sd, sn sd , until it is removed on line 16 and clock j [sd] ≥ sn sd . Therefore, one of the conditions at lines 5 and 6 will stay false for the stamp ts(msg) and p j will never execute line 11 with the same stamp sd, sn sd later.

2 Lemma 14

Lemma 15 Let p i be a process that scd-delivers a set ms i containing a message m and later scd-delivers a set ms ′ i containing a message m ′ . No process p j scd-delivers first a set ms ′ j containing m ′ and later a set ms j containing m.

Proof Let us suppose there are two messages m and m ′ and two processes p i and p j such that p i scd-delivers a set ms i containing m and later scd-delivers a set ms ′ i containing m ′ and p j scd-delivers a set ms ′ j containing m ′ and later scd-delivers a set ms j containing m.

When m is delivered by p i , there is an element msg ∈ buffer i such that msg.m = m and because of line 15, p i has received a message FORWARD(m, -, -, -, -) from more than n 2 processes. • If there is no element msg ′ ∈ buffer i such that msg ′ .m = m ′ , since m ′ has not been delivered by p i yet, p i has not received a message FORWARD(m ′ , -, -, -, -) from any process (lines 10 and 19). Therefore, because the communication channels are FIFO, more than n 2 processes have sent a message FORWARD(m, -, -, -, -) before sending a message FORWARD(m ′ , -, -, -, -).

• Otherwise, msg ′ / ∈ to_deliver i after line 16. As the communication channels are FIFO, more than n 2 processes have sent a message FORWARD(m, -, -, -, -) before a message FORWARD(m ′ , -, -, -, -).

Using the same reasoning, it follows that when m ′ is delivered by p j , more than n 2 processes have sent a message FORWARD(m ′ , -, -, -, -) before sending a message FORWARD(m, -, -, -, -). There exists a process p k in the intersection of the two majorities, that has both sent a message FORWARD(m ′ , -, -, -, -) before sending FORWARD(m, -, -, -, -) and sent a message FORWARD(m ′ , -, -, -, -) before sending FORWARD(m, -, -, -, -). However, by Lemma 14, p k can only send one message FORWARD(m ′ , -, -, -, -) and one message FORWARD(m, -, -, -, -), which leads to a contradiction.

2 Lemma 15

Lemma 16 If a message FORWARD(m, sd, sn sd , i, sn i ) is fifo-broadcast by a non-faulty process p i , this process scd-delivers a set containing m.

Proof Let p i be a non-faulty process. For any pair of messages msg and msg ′ ever inserted in buffer i , let ts = ts(msg) and ts ′ = ts(msg ′ ). Let → i be the dependency relation defined as follows:

2 (i.e. the dependency does not exist if p i knows that a majority of processes have seen the first update -due to msg ′ -before the second -due to msg-). Let → ⋆ i denote the transitive closure of

FORWARD(m, sd, sn sd , -, -)

FORWARD(m l+1 , sd l+1 , sn sd l+1 , -, -)

Figure 1: Message pattern introduced in Lemma 16 Let us suppose (by contradiction) that the timestamp sd, sn sd associated with the message m (carried by the protocol message FORWARD(m, sd, sn sd , i, sn i ) fifo-broadcast by p i ), has an infinity of predecessors according to → ⋆ i . As the number of processes is finite, an infinity of these predecessors have been generated by the same process, let us say p f . Let f, sn f (k) k∈N be the infinite sequence of the timestamps associated with the invocations of the scd_broadcast() issued by p f . The situation is depicted by Figure 1.

As p i is non-faulty, p f eventually receives a message FORWARD(m, sd, sn sd , i, sn i ), which means f broadcast an infinity of messages FORWARD(m(k), f, sn f (k), f, sn f (k)) after FORWARD(m, sd, sn sd , f, sn f ). Let f, sn f (k1) and f, sn f (k2) be the timestamps associated with the next two messages sent by p f , with sn f (k1) < sn f (k2). By hypothesis, we have f, sn f (k2) → ⋆ i sd, sn sd . Moreover, all processes received their first message FORWARD(m, sd, sn sd , -, -) before their first message FORWARD(m(k), f, sn f (k), -, -), so sd,

In the time interval starting when p f sent the message FORWARD(m(k1), f, sn f (k1), f, sn f (k1)) and finishing when it sent the the message FORWARD(m(k2), f, sn f (k2), f, sn f (k2)), the waiting condition of line 2 became true, so p f scd-delivered a set containing the message m(k1), and according to Lemma 12, no set containing the message m(k2). Therefore, there is an index l such that process p f delivered sets containing messages associated with a timestamp sd ′ (l), sn ′ (l) for all l ′ > l but not for l ′ = l. Because the channels are FIFO and thanks to lines 15 and 16, it means that a majority of processes have sent a message FORWARD(-, sd ′ (l + 1), sn ′ (l + 1), -, -) before a message FORWARD(-, sd ′ (l), sn ′ (l), -, -), which contradicts the fact that sd ′ (l), sn ′ (l) → i sd ′ (l + 1), sn ′ (l + 1) .

Let us suppose a non-faulty process p i has fifo-broadcast a message FORWARD(m, sd, sn sd , i, sn i ) (line 10). It inserted a quadruplet msg with timestamp sd, sn sd on line 9 and by what precedes, sd, sn sd has a finite number of predecessors sd 1 , sn 1 , . . . , sd l , sn l according to → ⋆ i . As p i is non-faulty, according to Lemma 14, it eventually receives a message FORWARD(-, sd k , sn k , -, -) for all 1 ≤ k ≤ l and from all non-faulty processes, which are in majority.

Let pred be the set of all quadruplets msg ′ such that msg ′ .sd, msg ′ .sn sd → ⋆ i sd, sn sd . Let us consider the moment when p i receives the last message FORWARD(-, sd k , sn k , f, sn f ) sent by a correct process p f . For all msg ′ ∈ pred , either msg ′ .m has already been delivered or msg ′ is inserted to_deliver i on line 15. Moreover, no msg ′ ∈ pred will be removed from to_deliver i , on line 16, as the removal condition is the same as the definition of → i . In particular for msg ′ = msg, either m has already been scd-delivered or m is present in to_deliver i on line 17 and will be scd-delivered on line 20.

2 The O(n 2 ) message complexity comes from the fact that, due to the predicates of line 5 and 6, each application message m is forwarded at most once by each process (line 11).

2 T heorem 3

The next corollary follows from (i) Theorems 1 and 3, and (ii) the fact that the constraint (t < n/2) is an upper bound on the number of faulty processes to build a read/write register (or snapshot object) [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF].

Corollary 1 Algorithm 3 is resiliency optimal.

B Building an MWMR atomic register on top of CAMP n,t [SCD-broadcast]

This appendix shows the genericity dimension of Algorithm 1. It presents trivial simplifications of it, which build MWMR atomic registers and MWMR sequentially consistent registers.

B.1 The algorithm

Let REG denote the MWMR atomic read/write register that is built. The algorithm that builds it is a trivial simplification of the snapshot Algorithm 1, namely its projection on a single MWMR atomic register.

REG is now locally represented by a local variable reg i and the associated timestamp ts i initialized to 0, -. The message sent at Line 9 is now WRITE(v, ts i .date i + 1, i ), and the predicate of line 11 simplifies to "there are messages WRITE())".

B.2 Proof of the algorithm

The proof is a simplified version of the proof of Theorem 1. For self-completeness, we give here its full proof even if some parts of it are "cut-and-paste" of parts of proofs given in Section 4.2. As in that section, let us associate a timestamp ts(op) with each operation op() as follows (this is the place where the proof is simplified with respect to a snapshot object).

• Case op() = write(v). Let p i be the invoking process; ts(op) is the timestamp of v as defined by p i at line 9, i.e., ts i .date + 1, i .

• Case op() = read(). Let w be the value returned by the read; ts(op) is then the timestamp associated with w at line 15 by its writer.

Let op1 and op2 be any two operations. The relation ≺ on the whole set of operations is defined as follows: op1 ≺ op2 if op1 terminated before op2 started. It is easy to see that ≺ is a real-time-compliant partial order on all the operations.

The reader can easily check that the statement and the proof of Lemma 1 (applied to the termination of read and write operations), and Lemma 3 (applied to the total order on the write operations, compliant with both the sequential specification of a register, and their real-time occurrence order) remain valid for the algorithm suited to an MWMR atomic read/write register. The next lemma addresses the read operations (which are simpler to manage than snapshot operations).

Lemma 19

The read/write register REG is linearizable.

Proof Let us now insert each read operation in the previous (real time compliant) total order as follows.

Let read1() be a read operation whose timestamp is date1, i . This operation is inserted just after the write operation write1() that has the same timestamp (this write wrote the value read by read1()). Let us remark that, as read1() obtained the value timestamped date1, i , it did not terminate before write1() started. vii It follows that the insertion of read1() into the total order cannot violate the real-time order between write1() and read1().

Let us consider the operation write2() that follows write1() in the write total order. If read1() ≺ write2(), the placement of read1() in the total order is real-time-compliant. If ¬(read1() ≺ write2()), due to the timestamp obtained by read1(), we cannot have write2() ≺ read1(). It follows that in this case also, the placement of read1() in the total order is real-time-compliant.

Finally, let us consider two read operations read1() and read2() which have the same timestamp date, i (hence, they read from the same write operation, say write1()). Both are inserted after write1() in the order of their invocations (if read1() and read2() started simultaneously, they are inserted according to the order on the identities of the processes that invoked them). Hence, the read and write operations are linearizable, which concludes the proof of the lemma.

2 Let us remark that, due to the Boolean done k , the writer p k scd-delivers message sets containing at most one message WRITE().

B.4 On sequentially consistency

The case of an MWMR sequentially consistent register As indicated in the Introduction, sequential consistency was introduced in [START_REF] Lamport | How to make a multiprocessor computer that correctly executes multiprocess programs[END_REF]. It is atomicity minus the requirement stating that "if an operation op1 terminates before an operation op2 starts, then op1 must appear before op2 in the sequence of the read and write operations". As noticed in [START_REF] Raynal | Sequential consistency as lazy linearizability[END_REF], sequential consistency can be seen as a weakened form of atomicity, namely lazy linearizability. The composition of sequentially consistent registers is investigated in [START_REF] Perrin | On composition and implementation of sequential consistency[END_REF]. The algorithm for sequential consistency presented in [START_REF] Perrin | On composition and implementation of sequential consistency[END_REF] and Algorithm 3 are based on similar principles. The constraint (t < n/2) is also a necessary and sufficient condition to implement a sequentially consistent read/write register in CAMP n,t [∅].

The reader can check that an algorithm building a a sequentially consistent MWMR read/write register can easily be obtained from Algorithm 1 as simplified in Section B.1. One only needs to suppress the synchronization messages SYNC() which ensure the compliance with respect to real-time. The concerned lines are lines 1-3 (read synchronization), and lines 5-7 (write synchronization). In a simple way, this shows the versatility dimension of Algorithm 1.

From sequential consistency to atomicity Given a sequentially consistent snapshot object, Algorithm 2 builds the SCD-broadcast communication abstration. (As the reader can check, this follows from the fact that, when looking at its proof, this algorithm relies only on the fact that the operations on the snapshot object can be totally ordered.) Hence, using on top of it the SCD-broadcast-based Algorithm 1, we obtain an atomic snapshot object. It follows that, thanks to SCD-broadcast, the algorithms presented in the paper allow a sequentially consistent snapshot object to be transformed into an atomic snapshot object (and it is known that -differently from sequential consistent objects-atomic objects are composable for free [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF]).