Achour Mostéfaoui
email: achour.mostefaoui@univ-nantes.frhamouma.moumen@gmail.comraynal@irisa.fr

Hamouma Moumen

Michel Raynal

Modular Randomized Byzantine k-Set Agreement in Asynchronous Message-passing Systems

Keywords: Asynchronous message-passing system, Broadcast abstraction, Byzantine process, Coin, Distributed algorithm, k-Set agreement, Randomized algorithm, Signature-free algorithm

k-Set agreement is a central problem of fault-tolerant distibuted computing. Considering a set of n processes, where up to t may commit failures, let us assume that each process proposes a value. The problem consists in defining an algorithm such that each non-faulty process decides a value, at most k dfferent values are decided, and the decided values satisfy some context-depending validity condition. Synchronous message-passing algorithms solving k-set agreement have been proposed for different failure models (mainly process crashes, and process Byzantine failures). Differently, k-set agreement cannot be solved in failure-prone asynchronous message-passing systems when t ≥ k. To circumvent this impossibility an asynchronous system must be enriched with additional computational power.

Assuming t ≥ k, this paper presents a distributed algorithm that solves k-set agreement in an asynchronous message-passing system wher up to t processes may commit Byzantine failures. To that end, each process is enriched with randomization power. While randomized k-set agreement algorithms exist for the asynchronous process crash failure model where t ≥ k, to our knowledge the proposed algorithm is the first that solves k-set agreement in the presence of up to t ≥ k Byzantine processes. Interestingly, this algorithm is signature-free, and ensures that no value proposed only by Byzantine processes can be decided by a non-faulty process. Its design is based on a modular construction which rests on a "no-duplicity" one-to-all broadcast abstraction, and two all-to-all communication abstractions.

Introduction

Distributed agreement in the presence of process failures The world is distributed and more and more applications are now distributed. Moreover, when considering the core of non-trivial distributed applications, it appears that the computing entities (processes) have to agree in one way or another, for example to take a common decision, execute specific actions, or validate some commitment. Said another way, agreement problems lie at the core of distributed computing.

The most famous distributed agreement problem is the consensus problem. Let us consider a set of processes, where some of them may commit failures. Assuming each process proposes a value, the consensus problem is defined by the following properties: each non-faulty process must decide a value (termination), such that the same value is decided by the non-faulty processes (agreement), and this value satisfies some validity condition, which depends on the proposed values and the considered failure model [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF][START_REF] Pease | Reaching agreement in the presence of faults[END_REF].

The k-set agreement problem is a natural weakening of consensus [START_REF] Chaudhuri | More choices allow more faults: Set consensus problems in totally asynchronous systems[END_REF]. It allows the non-faulty processes to decide different values, as long as no more than k values are decided. Hence, consensus is 1-set agreement. Let us notice that k-set agreement can be easily solved in crash-prone systems where k (the maximal number of different values that can be decided) is greater than t (the maximal number of processes that may be faulty). The k-set agreement problem has applications, e.g., to compute a common subset of wavelengths (each process proposes a wavelength and at most k of them are selected), or to duplicate k state machines where at most one is required to progress forever [9,[START_REF] Raynal | Distributed universality[END_REF].

Byzantine failures

This failure type has first been introduced in the context of synchronous distributed systems [START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Pease | Reaching agreement in the presence of faults[END_REF][START_REF] Raynal | Fault-tolerant agreement in synchronous message-passing systems[END_REF], and then investigated in the context of asynchronous distributed systems [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]. A process has a Byzantine behavior when it arbitrarily deviates from its intended behavior. We then say that it "commits a Byzantine failure" (otherwise we say the process is non-faulty or correct). This bad behavior can be intentional (malicious) or simply the result of a transient fault that altered the local state of a process, thereby modifying its behavior in an unpredictable way. Let us notice that process crashes (unexpected halting) define a strict subset of Byzantine failures.

Let us remind that (as already said) the world is distributed, asynchronous message-passing systems are more and more pervasive, processes have to agree in one way or another, and the assumption "no process has a bad behavior" is no longer sensible. Hence, agreement in asynchronous Byzantine message-passing systems is becoming a more and more important issue of fault-tolerance.

An impossibility result and how to cope with it Let consider a system made up of n processes, where up to t may be faulty. Whatever the value of k (i.e., even if k ≤ t), k-set agreement can always be solved if the system is synchronous [START_REF] Raynal | Fault-tolerant agreement in synchronous message-passing systems[END_REF]. The situation is different in asynchronous systems where k-set agreement is impossible to solve in the process crash failure model when k ≤ t [START_REF] Borowsky | Generalized FLP Impossibility Results for t-Resilient Asynchronous Computations[END_REF][START_REF] Herlihy | The Topological Structure of Asynchronous Computability[END_REF][START_REF] Saks | Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge[END_REF]. As Byzantine failures are more severe than process crash failures, this impossibility remains true in asynchronous Byzantine systems.

It follows from this impossibility that, when k ≤ t, the underlying asynchronous distributed system has to be enriched with additional computational power for k-set agreement to be solved. Such an additional computational power can be provided with minimal synchrony assumptions (e.g., [START_REF] Bouzid | Minimal synchrony for Byzantine consensus[END_REF] which considers k = 1 and Byzantine failures), appropriate failure detectors (e.g., [START_REF] Friedman | Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems[END_REF] which considers k = 1 and Byzantine failures), or randomization (e.g., [START_REF] Rabin | Randomized Byzantine generals[END_REF] which considers k = 1 and Byzantine failures, and [START_REF] Hillel | Multi-sided shared coins and randomized set agreement[END_REF][START_REF] Mostéfaoui | Randomized k-set agreement[END_REF] which consider k ≤ t and crash failures, in read/write shared memory systems and messagepassing systems, respectively).

Intrusion-tolerant agreement with respect to Byzantine processes

The validity property associated with a distributed agreement problem relates its outputs to its inputs. In a system where processes may commit Byzantine failures, there is no way to direct a Byzantine process to decide some specific value, and consequently the k-set agreement validity property can only be on the values decided by the correct processes.

A classical validity property for Byzantine agreement states that, when the non-faulty processes propose the same value, they must decide it. Hence, as soon as two non-faulty processes propose different values, any value can be decided by the correct processes, even a value "proposed" by a Byzantine process. (Let us observe that a Byzantine process can appear as proposing different values to different correct processes.) It follows that, as noticed and deeply investigated in [START_REF] De Prisco | On k-Set consensus problems in asynchronous systems[END_REF], the solvability of Byzantine k-set agreement is sensitive to the particular validity property that is considered.

In this paper we consider the following validity property (introduced in [START_REF] Mostéfaoui | Signature-free broadcast-based intrusion tolerance: never decide a Byzantine value[END_REF] where it is called intrusion-tolerance): no value proposed only by Byzantine processes can be decided by a non-faulty process. One way to be able to design a k-set algorithm providing this property, consists in allowing a non-faulty process to decide a default value ⊥, except (to prevent triviality) when the non-faulty processes propose the same value. (The ⊥ decision at some non-faulty processes can occur for example in the very adversary scenario where the non-faulty processes propose different values, while the Byzantine processes propose the same value). Another way to design a k-set algorithm providing intrusion-tolerance consists in adding a constraint on the total number of different values that can be proposed by the non-faulty processes. Let m be this number. It is shown in [START_REF] Herlihy | Distributed computing through combinatorial topology[END_REF] that, in a system of n processes where up to t processes may commit Byzantine failures, such a constraint is nt > mt (i.e., there is a value proposed by at least (t + 1) non-faulty processes).

Content of the paper

This paper is on Byzantine k-set agreement. It has two main contributions.

• The first is a pair of all-to-all communication abstractions. The first one, called MV-broadcast (where MV stands for "Multivalued Validated"), allows the non-faulty processes to exchange values in such a way that all the non-faulty processes eventually obtain the same set of values, and none of these values is from Byzantine processes only. The second one, called SMV-broadcast (where S stands for "Synchronized") is built on top the first one, and is such that, if a non-faulty process obtains a set with a single value, the set obtained by any other non-faulty process contains this value. The important point is that these communication abstractions allow the processes to exchange values while eliminating the values sent only by Byzantine processes. They generalize to the "multivalue" case the communication abstractions introduced in [START_REF] Mostéfaoui | Signature-free asynchronous binary Byzantine consensus with t < n/3, O(n 2 ) messages, and O(1) expected time[END_REF], where the set of values that the processes exchange is limited to two values. • The second contribution is a modular k-set agreement algorithm for asynchronous messagepassing systems where processes may commit Byzantine failures. This algorithm, which roundbased, relies on the previous SMV-broadcast abstraction, and (as already announced) on the additional computational power supplied by local random coins (with several sides). As far as we know, this is the first randomized k-set agreement algorithm for asynchronous Byzantine messagepassing systems.

The previous Byzantine-tolerant algorithms have two noteworthy features. The first is that they all are signature-free. This means that the "adversary" is not required to be computationally bounded. The second is their conceptual simplicity, which is a first-class property.

Roadmap

The paper is composed of 5 sections. Section 2 presents the computation model and a basic broadcast abstraction (called ND-broadcast, where ND stand for "No Duplicity") introduced in [START_REF] Toueg | Randomized Byzantine agreement[END_REF]. As indicated by its name, this broadcast operation, which requires t < n/3, allow to hide a duplicity behavior which can be produced by Byzantine processes. Then Section 3 presents the MV-broadcast and SMV-broadcast abstractions. SMV-broadcast is based on both MV-broadcast and ND-broadcast. Section 4 presents the modular randomized k-set agreement algorithm, whose construction relies on two instances of SMV-broadcast per round. Finally, Section 5 concludes the paper.

Computation Model and ND-broadcast 2.1 Computation model

Asynchronous processes

The system is made up of a finite set Π of n > 1 asynchronous sequential processes, namely Π = {p 1 , . . . , p n }. "Asynchronous" means that each process proceeds at its own pace, which may vary arbitrarily with time, and remains always unknown to the other processes.

Communication network

The processes communicate by exchanging messages through an asynchronous reliable point-to-point network. "Asynchronous" means that a message is eventually received by its destination process, i.e., there is no bound on message transfer delays. "Reliable" means that the network does not loss, duplicate, modify, or create messages. "Point-to-point" means that there is a bi-directional communication channel between each pair of processes. Hence, when a process receives a message, it can identify its sender.

A process p i sends a message to a process p j by invoking the primitive "send TAG(m) to p j ", where TAG is the type of the message and m its content. To simplify the presentation, it is assumed that a process can send messages to itself. A process receives a message by executing the primitive "receive()".

The operation broadcast TAG(m) is a macro-operation which stands for "for each j ∈ {1, . . . , n} send TAG(m) to p j end for".This operation is usually called unreliable broadcast (if the sender crashes in the middle of the for loop, it is possible that only an arbitrary subset correct processes receives a message).

Failure model Up to t processes may exhibit a Byzantine behavior. A process that exhibits a Byzantine behavior is called faulty. Otherwise, it is correct or non-faulty. A Byzantine process is a process that behaves arbitrarily: it may crash, fail to send or receive messages, send arbitrary messages, start in an arbitrary state, perform arbitrary state transitions, etc. As a simple example, a Byzantine process, which is assumed to send a message m to all the processes, can send a message m 1 to some processes, a different message m 2 to another subset of processes, and no message at all to the other processes. More generally, a Byzantine process has an unlimited computational power, and Byzantine processes can collude to "pollute" the computation. Let us notice that, as each pair of processes is connected by a channel, no Byzantine process can impersonate another process, but Byzantine processes are not prevented from influencing the delivery order of messages sent to correct processes.

Discarding messages from Byzantine processes If, according to its algorithm, a process p j is assumed to send a single message TAG() to a process p i , then p i processes only the first message TAG(v) it receives from p j . This means that, if p j is Byzantine and sends several messages TAG(v), TAG(v ′ ) where v ′ = v, etc., all of them except the first one are discarded by their receivers. (Let us observe that this does not prevent multiple copies of the first message TAG() to be received and processed by their receiver.) Notation This computation model is denoted BAMP n,t [∅] (BAMP stands for "Byzantine Asynchronous Message Passing"). In the following, this model is both restricted with a constraint on t and enriched with an object providing processes with additional computational power. More precisely, BAMP n,t [t < n/α] (where α is a positive integer) denotes the model BAMP n,t [∅] where the maximal number of faulty processes is smaller than n/α, and BAMP n,t [t < n/α, LRC] denotes the model BAMP n,t [t < n/α] where each process is enriched with a local random coin (LRC). Let us notice that, as LRC belongs to the model, it is given for free in BAMP n,t [t < n/α, LRC].

Time complexity

When computing the time complexity we ignore local computation time, and consider the longest sequence of causally relate messages m 1 , m 2 , . . ., m z (i.e., for any x ∈ [2..z], the reception of m x-1 is a requirement for the sending of m x ). The size of such a longest sequence defines the time complexity.

No-duplicity broadcast

Definition of ND-broadcast The ND-broadcast communication abstraction was introduced by S. Toueg in [START_REF] Toueg | Randomized Byzantine agreement[END_REF]. It is defined by two operations denoted ND broadcast() and ND deliver(), which allow the processes to eliminate bad behaviors of Byzantine processes. More precisely, a Byzantine process is prevented from sending different messages to different correct processes, while it is assumed to send the very same message to all of them.

When a process invokes ND broadcast() we say that it "ND-broadcasts" a message, and when it invokes ND deliver() we say that it "ND-delivers" a message 1 . Considering an instance of ND-broadcast where the operation ND broadcast() is invoked by a process p i , this communication abstraction is defined by the following properties.

• ND-Validity. If a non-faulty process ND-delivers a message from p i , then, if it is non-faulty, p i ND-broadcast this message. • ND-No-duplicity. No two non-faulty processes ND-deliver distinct messages from p i .

• ND-Termination. If the sender p i is non-faulty, all the non-faulty processes eventually ND-deliver its message.

Let us observe that, if the sender p i is faulty, it is possible that some non-faulty processes NDdeliver a message from p i while others do not ND-deliver a message from p i . As already indicated, the no-duplicity property prevents non-faulty processes from ND-delivering different messages from a faulty sender.

An algorithm implementing ND-broadcast

It is shown in [START_REF] Toueg | Randomized Byzantine agreement[END_REF] that t < n/3 is a necessary requirement to implement ND-broadcast in a Byzantine asynchronous message-passing system. Algorithm 1 (from [START_REF] Toueg | Randomized Byzantine agreement[END_REF]) implements ND-broadcast in BAMP n,t n,t [t < n/3] as follows.

operation ND broadcast MSG(vi) is (1) broadcast ND INIT(i, vi). when ND INIT(j, v) is delivered do (2) if first reception of ND INIT(j, -) then UB broadcast ND ECHO(j, v) end if. when ND ECHO(j, v) is delivered do (3) if ND ECHO(j, v) received from (n -t) different processes and MSG(j, v) not yet ND delivered (4) then ND deliver MSG(j, v) (5) end if. Algorithm 1: Implementing ND-broadcast in BAMP n,t [t < n/3]
When a process p i wants to ND-broadcast a message whose content is v i , it broadcasts the message ND INIT(i, v i ) (line 1). When a process receives a message ND INIT(j, -) for the first time, it broadcasts a message ND ECHO(j, v) where v is the data content of the ND INIT() message (line 2). If the message ND INIT(j, v) received is not the first message ND INIT(j, -), p j is Byzantine and the message is discarded. Finally, when p i has received the same message ND ECHO(j, v) from (nt) different processes, it locally ND-delivers MSG(j, v) (lines 3-4).

The algorithm considers an instance of ND-broadcast, i.e., a correct process invokes at most once ND-broadcast. Adding a sequence number to each message allows each process to ND-broadcast a sequence of messages.

Theorem 1. Algorithm 1 implements ND-broadcast in the system model BAMP n,t [t < n/3].
Proof To prove the ND-termination property, let us consider a non-faulty process p i that ND-broadcasts the message MSG(v i ). As p i is non-faulty, the message ND INIT(i, v i ) is received by all the non-faulty processes, which are at least (nt), and every non-faulty process broadcasts ND ECHO(i, v i ) (line 2). Hence, each non-faulty process receives the message ND ECHO(i, v i ). from (nt) different processes. It follows that every non-faulty process eventually ND-delivers the message MSG(i, v i ) (lines 3-4).

To prove the ND-no-duplicity property, let us assume by contradiction that two non-faulty processes p i and p j ND-deliver different messages m 1 and m 2 from some process p k (i.e., m 1 = MSG(k, v) and m 2 = MSG(k, w), with v = w). It follows from the predicate of line 3, that p i received ECHO(k, v) from a set of (nt) distinct processes, and p j received ECHO(k, w) from a set of (nt) distinct processes. As n > 3t, it follows that the intersection of these two sets contains a non-faulty process. But, as it is non-faulty, this sent the same message ND ECHO() to p i and p j (line 2). Hence, m 1 = m 2 , which contradicts the initial assumption.

To prove the ND-validity property, we show that, if Byzantine processes forge and broadcast a message ND ECHO(i, w) such that p i is correct and has never invoked ND broadcast MSG(w), then no correct process can ND-deliver MSG(i, w). Let us observe that at most t processes can broadcast the message ND ECHO(i, w). As t < nt, it follows that the predicate of line 3 can never be satisfied at a correct process. Hence, if p i is correct, no correct process can ND-deliver from p i a message that was not been ND-broadcast by p i .

✷ T heorem 1

It is easy to see that this implementation uses two consecutive communication steps and O(n 2 ) underlying messages (n -1 in the first communication step, and n(n -1) in the second one). Moreover, there are two types of protocol messages, and the size of the control information added to a message is log 2 n (sender identity).

Multivalued Validated Broadcast: MV-broadcast and SMV-broadcast

This section presents the all-to-all MV-broadcast and SMV-broadcast communication abstractions. "Allto-all" mean that it is assumed that all the non-faulty processes invoke the corresponding broadcast operation. As indicated in the introduction, these abstractions extend to the "multivalue" case the BVbroadcast and SBV-broadcast communication abstractions introduced in [START_REF] Mostéfaoui | Signature-free asynchronous binary Byzantine consensus with t < n/3, O(n 2 ) messages, and O(1) expected time[END_REF], which consider binary values only.

Multivalued validated all-to-all broadcast

Definition of MV-broadcast This communication abstraction provides the processes with a single operation denoted MV broadcast(). When a process invokes MV broadcast TAG(m), we say that it "MV-broadcasts the message typed TAG and carrying the value m". The invocation of MV broadcast TAG(m) does not block the invoking process. The aim of MV-broadcast is to eliminate the values (if any) that have been broadcast only by Byzantine processes.

In an MV-broadcast instance, each correct process p i MV-broadcasts a value and eventually obtains a set of values. To store these values, MV-broadcast provides each process p i with a read-only local variable denoted mv values i . This set variable, initialized to ∅, increases asynchronously when new values are received.

Definition Each instance of MV-broadcast is defined by the four following properties.

• MV-Termination. The invocation of MV broadcast() by a correct process terminates.

• MV-Justification. If p i is a correct process and v ∈ mv valid i , v has been MV-broadcast by a correct process.

• MV-Uniformity. If p i is a correct process and v ∈ mv valid i , eventually v ∈ mv valid j at every correct process p j . • MV-Obligation. Eventually the set mv valid i of each correct process p i is not empty.

The following properties are immediate consequences of the previous definition.

• MV-Equality. The sets mv valid i of the correct processes are eventually non-empty and equal.

• MV-Integrity. The set mv valid i of a correct process p i never contains a value MV-broadcast only by Byzantine processes.

Feasibility condition in the presence of up to t Byzantine processes Let m be the number of different values MV-broadcast by correct processes. It follows from the previous specification that, even when the (at most) t Byzantine processes propose the same value w, which is not proposed by correct processes, w cannot belong to the set mv valid i of a correct process p i . This can be ensured if and only if there is a value MV-broadcast by at least (t + 1) correct processes. This feasibility condition is captured by the predicate nt > mt (a proof of this feasibility condition can be found in [START_REF] Herlihy | Distributed computing through combinatorial topology[END_REF]). Hence n > (m + 1)t is a feasibility condition for MV-broadcast to cope with up to t Byzantine processes. Let us notice that, as m ≥ 2, n > (m + 1)t implies n > 3t.

An MV-broadcast algorithm Algorithm 2 describes a simple implementation of MV-broadcast, suited to the system model BAMP n,t [t < n/(m + 1)]. This algorithm is based on a simple "echo" mechanism. Differently from previous echo-based algorithms (e.g., [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Srikanth | Simulating authenticated broadcasts to derive simple fault-tolerant algorithms[END_REF]), the echo is used here with respect to each value that has been received (whatever the number of processes that broadcast it), and not with respect to each pair composed of a value plus the identity of the process that broadcast this value. Hence, a value entails at most one echo per process, whatever the number of processes that MV-broadcast this value.

let witness(v) = number of different processes from which MV VAL(v) was received.

operation MV broadcast MSG(vi) is

(1) broadcast MV VAL(vi); return().

when MV VAL(v) is received (2) if (witness(v) ≥ t + 1) ∧ (MV VAL(v) not yet broadcast) (3)
then broadcast MV VAL(v) % a process echoes a value only once % (4) end if; [START_REF] Hillel | Multi-sided shared coins and randomized set agreement[END_REF]

if (witness(v) ≥ n -t) ∧ (v / ∈ mv validi) (6)
then mv validi ← mv validi ∪ {v} % local delivery of a value % (7) end if.

Algorithm 2: Implementing MV-broadcast in BAMP n,t [t < n/(m + 1)] When a process p i invokes MV broadcast MSG(v i ), it broadcasts MV VAL(v i ) to all the processes (line 1). Then, when a process p i receives (from any process) a message MV VAL(v), (if not yet done) it forwards this message to all the processes (line 3) if it has received the same message from at least (t+1) different processes (line 2). Moreover, if p i has received v from at least (2t + 1) different processes, the value v is added to mv valid i (lines 5-6). Let us notice that, except in the case where |mv valid i | = m, no correct process p i can know if its set mv valid i has obtained its final value.

Theorem 2. Algorithm 2 implements MV-broadcast in the system model BAMP

n,t [t < n/(m + 1)].
Proof The proof of the MV-Termination property is trivial. If a correct process invokes MV broadcast(), it eventually sends a message to each process, and terminates.

Proof of the MV-Justification property. To show this property, we prove that a value MV-broadcast only by faulty processes cannot be added to the set mv valid i of a correct process p i . Hence, let us assume that only faulty processes MV-broadcast v. It follows that a correct process can receive the message MV VAL(v) from at most t different processes. Consequently the predicate of line 2 cannot be satisfied at a correct process. Moreover, as nt > t, the predicate of line 5 cannot be satisfied either at a correct process, and the property follows.

Proof of the MV-Uniformity property. If a value v is added to the set mv valid i of a correct process p i (local delivery), this process received MV VAL(v) from at least (n-t) different processes (line 5), i.e., from at least (n -2t) different correct processes. As each of these correct processes sent this message to all the processes, it follows that the predicate of line 2 is eventually satisfied at each correct process, which consequently broadcasts MV VAL(v) to all. As there are at least (nt) correct processes, the predicate of line 5 is then eventually satisfied at each correct process, and the MV-Uniformity property follows.

Proof of the MV-Obligation property. It follows from he feasibility condition n > (m+1)t, that there is a value v MV-broadcast by at least (t + 1) correct processes. It then follows that these processes issue MV broadcast MSG(v), and consequently all correct processes first deliver the message MV VAL(v) and then broadcast at line 3 (if not previously done). Hence, each correct process p i eventually delivers this message from (n-t) processes and and adds v to its set mv valid i (line 5-6), which proves the property.

✷ T heorem 2

Cost of the algorithm As at most m values are MV-broadcast by the correct processes, it follows from the text of the algorithm that each correct process broadcasts each of these values at most once (at line 1 or line 3). Hence, if there are c ∈ [nt.

.n] correct processes, their broadcasts entail the sending of at most m c n messages MV VAL(). Finally, whatever the number of values that are MV-broadcast, the algorithm requires at most two communication steps.

Synchronized multivalued validated all-to-all broadcast

Definition of SMV-broadcast This all-to-all communication abstraction provides the processes with a single operation denoted SMV broadcast(). As indicated by its name, its aim is to synchronize processes so that, if a single value v is delivered to a correct process, then v is delivered to all the correct processes.

In an SMV-broadcast instance, each correct process invokes SMV broadcast TAG(m), where TAG is the type of the message and m value it wants to broadcast. Such an invocation returns to the invoking process p i a set denoted view i and called a local view. We say that a process contributes to a set view i if the value it SMV-broadcasts belongs to view i . SMV-broadcast is defined by the following properties.

• SMV-Termination. The invocation of SMV broadcast TAG() by a correct process terminates.

• SMV-Obligation. The set view i returned by a correct process p i is not empty.

• SMV-Justification. If p i is correct and v ∈ view i , then a correct process SMV-broadcast v.

• SMV-Inclusion. If p i and p j are correct processes and view i = {v}, then v ∈ view j .

• SMV-Contribution. If p i is correct, at least (nt) processes contribute to its set view i .

• SMV-No-duplicity. Let VIEW be the union of the sets view i of the correct processes. A process contributes to at most one value of VIEW .

The following property is an immediate consequence of the previous definition. property.

• SMV-Singleton. If p i and p j are correct,

[(view i = {v}) ∧ (view i = {w})] ⇒ (v = w).
Let v ∈ VIEW , p i a correct process, and p j a Byzantine process. It is possible that, while the value v was SMV-broadcast by p i (hence p i contributed to VIEW ), p j also appears as contributing to VIEW with the same value v. The SMV-No-duplicity property states the following: no value w ∈ VIEW \ {v} appears as a contribution of p j .

An SMV-broadcast algorithm Algorithm 3 implements SMV-broadcast in BAMP n,t [t < n/(m + 1)]. A process p i first MV-broadcasts a message MSG (v i ) and waits until the associated set mv values i is not empty (lines 1-2). Let us remind that, when p i stops waiting, mv values i has not necessarily obtained its final value. Then, p i extracts a value w from mv values i and ND-broadcasts it to all (line 3). Let us notice that, due to the ND-no-duplicity property, no two correct processes can NDdeliver different values from the same Byzantine process.

operation SMV broadcast MSG (vi) is (1)
MV broadcast MSG(esti); [START_REF] Borowsky | Generalized FLP Impossibility Results for t-Resilient Asynchronous Computations[END_REF] wait (mv valuesi = ∅); % mv valuesi has not necessarily its final value when the wait statement terminates % (3)

ND broadcast ND AUX(w) where w ∈ mv valuesi; (4) wait (∃ a set viewi such that its values (i) belong to mv valuesi, and (ii) come from messages ND AUX() from (nt) distinct processes); [START_REF] Hillel | Multi-sided shared coins and randomized set agreement[END_REF] return (viewi).

Algorithm 3: Implementing SMV-broadcast in BAMP n,t [t < n/(m + 1)]

Finally, p i waits until the predicate of line 4 is satisfied. This predicate has two aims. The first is to discard from view i (the set returned by p i ) a value broadcast only by Byzantine processes. Hence the predicate view i ⊆ mv values i . The second aim is to ensure that, if the view view i of a correct process p i contains a single value, then this value eventually belongs to the view view j of any correct process p j . To this end, (nt) different processes (hence, at least (n -2t) correct processes) must contribute to view i .

Multiset version of SMV-broadcast

While a value belongs or does not belong to a set, a multiset (also called a bag) is a set in which the same value can appear several times. As an example, while {a, b, c} and {a, b, b, c, c, c} are the same set, they are different multisets.

It is easy to see that the "set" version of the SMV-broadcast (where view i is a set) and Algorithm 3 can be easily converted into a "multiset" version where view i is a multiset. Both versions will be used in the randomized k-set agreement presented in Section 4. Proof Proof of the SMV-Termination property. Let us first observe that, due to the MV-Termination property and the MV-Obligation property of the underlying MV-broadcast, no correct process blocks forever at line 2. As there are at least (nt) correct processes, and none of them blocks forever a line 2, it follows from the ND-Termination property that each correct process return from the ND-broadcast at line 3, and eventually ND-delivers values from at least the (nt) correct processes. Moreover, due to the MV-Justification property, these values have been SMV-broadcast by correct processes, and, due to the MV-Uniformity property, the sets mv valid i of all correct processes are eventually equal. It then follows that the predicate of line 4 becomes eventually satisfied at any correct process p i , and consequently the invocations of SMV broadcast() of the correct processes terminate.

Proof of the SMV-Obligation property. Any correct process p i eventually ND-delivers (nt) messages ND AUX() sent by correct processes. As (a) these messages carry values taken from the set mv values x of correct processes, and (b) these sets (b.1) are eventually equal at all correct processes, and (b.2) contain all values ND-broadcast at line 3 by the correct processes, it follows (from the predicate of line 4) that the set view i returned by a correct process is not empty.

Proof of the SMV-Justification property. This property follows directly from the fact that the predicate of line 4 discards the values ND-broadcast only by Byzantine processes, and from the MV-Justification property, namely, the set mv values i of a correct process contains only values MV-broadcast by correct processes.

Proof of the SMV-Inclusion property. Let us consider a correct process p i and assume view i = {v}. It follows from the predicate of line 4 that p i has ND-delivered the same message ND AUX(v) from at least (nt) different processes. As at most t of them are Byzantine, it follows that p i ND-delivered this message from at least (n -2t) different correct processes, i.e., as n -2t ≥ t + 1, from at least (t + 1) correct processes.

Let us consider any correct process p j . This process ND-delivered messages ND AUX() from at least (nt) different processes. As (nt) + (t + 1) > n, it follows that there is a correct process p x that ND-broadcast the same message ND AUX(v) to p i and p j . It follows that v ∈ view j , which concludes the proof of the lemma.

Proof of the SMV-Contribution property. This property follows trivially from the part (ii) of the waiting predicate of line 4.

Proof of the SMV-No-duplicity property. This property is an immediate consequence of the ND-Noduplicity property of the ND-broadcast issued at line 3.

✷ T heorem 3

Randomized Byzantine k-Set Agreement

This section presents and proves correct a Byzantine k-set agreement algorithm, which is modularly built on top of the SMV-broadcast communication abstraction and the additional computational power supplied to each process by a local random coin (LRC).

Intrusion-tolerant Byzantine k-set agreement

The intrusion-tolerant Byzantine (ITB) k-set agreement was informally presented in the introduction.

It is assumed that each non-faulty process invokes an operation called propose k (). This operation has an input parameter v, which is the value proposed by the invoking process. It returns a value, which is called the "value decided" by the invoking process. ITB k-set agreement is formally defined in terms of properties that any solution must to satisfy. When considering deterministic k-set agreement algorithms, these properties are the following ones.

• KS-D-Termination. If a correct process invokes propose k (), it decides a value.

• KS-Validity. If a correct process decides v, then v was proposed by a correct process.

• KS-Agreement. The set of values decided by the correct processes contains at most k values.

As we are interested in a randomized algorithm to solve k-set agreement, the termination property has to be weakened as follows: any correct process decides with probability 1. In the context of roundbased randomized algorithms, this property can restated as follows.

• KS-RR-Termination. lim r→+∞ Probability [p i decides by round r] = 1.

Enriching the basic Byzantine asynchronous model with a random coin

As announced, the additional computational power used to solve ITB k-set agreement despite Byzantine processes is supplied by a multi-sided random coin denoted LRC. The random abstraction LRC provides each process with a local coin that provides it with a single operation denoted random(). Each invocation takes a finite set X as input parameter, and returns a value of X such that each value of X as the probability 1/|X| to be returned. As seen in the introduction, we assume k ≤ t. Moreover, we have also seen that, in order a correct process decides neither a value proposed only by Byzantine processes, nor a predefined default value, it is assumed that, whatever the domain of the values that can be proposed by the correct processes, in any ). This random value is obtained from the set (denoted mv valid i [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF] in the algorithm) locally output by the first MV-broadcast instance invoked by p i . The use of these sets allows the algorithm to benefit from the fact that these sets are eventually equal at all correct processes (MV-Equality property). The KS-Termination relies on this property.

As shown in the proof, an important behavioral property of the algorithm lies in the fact that, at any round r, it is impossible for two correct processes p i and p j to be such that (⊥ / ∈ view i [r, 2]) ∧ (view i [r, 2] = {⊥}). These two predicates are mutually exclusive.

On the value of W The value W is used at line 5 for a safety reason, namely, no more than k non-⊥ values can belong to the set AUX [r]. As we have seen, this is captured by the constraint W (k + 1) > n. It appears that W has also to be constrained for a liveness reason, namely, when the correct processes start a new round r with at most k different estimates values, none of them must adopt the value ⊥ at line 5 (otherwise, instead of deciding at line 7, they could loop forever).

This liveness constraint is as follows. Let us consider the size of the multiset view i [r, 1] obtained at line 4. In the worst case, when the correct processes start a new round r with at most k different estimates, view i [r, 1] may contain (k -1) different values, each appearing (W -1) times, and only one value that appears W times. Hence, view i [r, 1] must contain at least (W -1)(k-1)+W = (W -1)k+1 elements. As it follows from Algorithm 3 that |view i [r, 1] ≥ nt, we obtain the liveness constraint nt ≥ (W -1)k + 1.

On message identities

The messages PHASE() SVM-broadcast at line 4 and line 6 are identified by a pair [r, x] where r is a round number and x ∈ {1, 2} a phase number. Each of these messages gives rise to underlying messages ND AUX() (Algorithm 2), MV VAL() (Algorithm 1), and underlying sets witness() (Algorithm 1). Each of them inherits the pair identifying the message PHASE() it originates from.

On the messages DECIDE() Before a correct process decides a value v, it sends a message DECIDE(v) to each other process (line 8). Then, it stops its execution. This halting has not to prevent correct processes from terminating, which could occur if they wait forever underlying messages ND AUX() or MV VAL() from p i .

To this end, a message DECIDE(v) has to be considered as representing an infinite set of messages. More precisely if, while executing a round r, a process p i receives a message DECIDE(v) from a process p j , it considers that it has received from p j the following set of messages:

{ND AUX[r ′ , 1](v), ND AUX[r ′ , 2](v), MV VAL[r ′ , 1](v), MV VAL[r ′ , 2](v)} r ′ ≥r .
It is easy to see that the messages DECIDE() simulate a correct message exchange that could be produced, after it has decided, by a deciding but nonterminating process.

Another solution would consist in using a Reliable Broadcast abstraction that copes with Byzantine processes. In this case, a process could decide a value v as soon as it has RB-delivered (t + 1) messages DECIDE(v). An algorithm implementing such a reliable broadcast is presented in [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF]. This algorithm requires O(n 3 ) messages and assumes n < t/3, which is a necessary requirement to implement reliable broadcast in the presence of Byzantine processes. Proof let us assume by contradiction that p i is a correct process such that the predicate ⊥ / ∈ view i [r, 2] is satisfied (line 7), and p j a correct process such that the predicate view j [r, 2] = {⊥} is satisfied (line 10).

It follows from the SMV-Contribution property of the SMV-broadcast issued by i and j at line 6 that view i [r, 2] contains values contributed by at least (nt) processes, and similarly for the set view j [r, 2] of p j . As n > 3t, the intersection of any two sets of (nt) processes contains at least (t + 1) processes, i.e., one correct process. It then follows that there is a correct process that contributed to both view i [r, 2] and view j [r, 2], from which we conclude that either view i Let us now consider a correct process p j that proceeds to round (r + 1). Let p i be a process that decides at round r. It follows from Lemma 4 that the predicates ⊥ / ∈ view i [r, 2] and view j [r, 2] = {⊥} are mutually exclusive. Consequently, p j executes line 9 before progressing to the next round. Hence, p j updated est j to a non-⊥ value of view j [r, 2] ⊆ AUX Proof The proof is by contradiction. Let r be the first round at which a correct process p i blocks forever. It can block at line 4 or line 6. Let us first consider line 4. As no correct process blocked forever at a round r ′ < r, all correct processes start round r and invoke SMV broadcast PHASE[r, 1](-). It then follows from the MV-termination property that p i returns from its invocation. The same reasoning applies to line 6, which concludes the proof of the lemma. ✷ Lemma 6

Lemma 7. If a correct process decides during a round r, any other correct process that does not decide by round r, decides during the round (r + 1).

Proof

The proof is by contradiction. Let us suppose that a correct process p i decides v at round r (line 8) and a correct process p j , which does not decide by round r. Due to Lemma 6, p j proceeds to round (r + 1). Due to to Lemma 4 and the fact that p i decides at round r, it follows that view j [r, 2] = {⊥}. Hence, p j executes line 9, an assigns a non-⊥ of AUX Its design is based on a modular construction which rests on (i) a broadcast abstraction which guarantees that two non-faulty processes cannot receive distinct messages from the same (possibly Byzantine) sender, and (ii) the stacking of two all-to-all communication abstractions which generalize the "binary" communication abstractions introduced in [START_REF] Mostéfaoui | Signature-free asynchronous binary Byzantine consensus with t < n/3, O(n 2 ) messages, and O(1) expected time[END_REF] to the multivalue domain. An interesting feature of the propsed algorithm lies in the validity condition it ensures, namely, no value proposed only by Byzantine processes can be decided by non-faulty processes.

Theorem 3 .

 3 Algorithm 3 implements SMV-broadcast in the system model BAMP n,t [t < n/(m + 1)].

4 Lemma 5 .

 45 [r, 2] contains ⊥, or view j [r, 2] contains a non-⊥ estimate value. ✷ Lemma No more than k different values are decided by the correct processes. Proof Let r be the first round during which correct processes decide. They decide at line 8. Due to Lemma 2, the set AUX [r] contains at most k non-⊥ values. Moreover, due to the SMV-broadcast issued by the correct processes at line 6 that we have view i [r, 2] ⊆ AUX [r] at each correct process p i . Hence, due to line 7, a process that decides during round r can only decide a value of AUX [r].

5 Lemma 6 .

 56 [r] before progressing to the next round. It follows that the estimates of the correct processes progressing to the next round are non-⊥ values of AUX [r]. Hence, EST [r + 1] ⊆ AUX [r] \ {⊥}. It then follows from Lemma 3 that at most k values are decided.✷ Lemma No correct process blocks forever in a round.

  [r] to est j . As AUX [r] contains at most k non-⊥ values (Lemma 2), we have EST [r + 1] ⊆ AUX [r], i.e., the round (r + 1) starts with at most k non-⊥ values. Due to to the Lemma 3, p j decides in the round r + 1. A contradiction. ✷ Lemma 7

  execution, at most m different values are proposed by correct processes, where m depends on n and t, view i [r, 2] is a local approximation of AUX [r], namely, view i [r, 2] ⊆ AUX [r]. Then, the behavior of p i depends on the content of the set view i [r, 2]. • If ⊥ / ∈ view i [r, 2], p i decides any value in view i [r, 2] (lines 7-8). • If view i [r, 2] contains ⊥ and non-⊥ values, p i updates its current estimate est i to any non-⊥ value of view i [r, 2] and starts new round (line 9). • If view i [r, 2] contains only ⊥, p i starts a new round, but updates previously its current estimate est i to a random value (line 10

  value of EST [r]. Hence, aux i ∈ EST [r] at each correct process. Consequently AUX [r] ⊆ EST [r]. it then follows that the predicate of line 7 is satisfied at any correct process p i , which decides accordingly a value of view i [r, 2] ⊆ AUX [r] ⊆ EST [r], which concludes the proof of the lemma. ✷ Lemma 3 Lemma 4. Let p i and p j be two correct processes. At any round r, the predicates ⊥ / ∈ view i [r, 2] and view j [r, 2] = {⊥} are mutually exclusive.

A similar vocabulary will be used for the abstractions MV-broadcast and SMV-broadcast introduced in Section 3.

While the value of this set could be known by an external global observer, its value can never be explicitly known by a correct process. However, a process can locally build an approximation of it during the second phase, see below.

Let us remind that, due to the ND-broadcast used in the algorithm implementing SMV-broadcast, two correct processes cannot ND-deliver different values from the same Byzantine process.

Acknowledgments

This work has been partially supported by the French ANR project DISPLEXITY devoted to computability and complexity in distributed computing, and the Franco-German project DISCMAT devoted to the mathematics of distributed computing.

namely, n > m(t + 1). Finally, to rule out the trivial algorithm in which a correct process decides the value it proposes, we assume k < m.

Hence, assuming the non-triviality conditions k < m and k ≤ t, and the fact that, in any execution, at most m different values are proposed by the correct processes, the system model considered here to solve the ITB k-set agreement problem is BAMP n,t [t < n/(m + 1), LRC].

A randomized Byzantine k-set agreement algorithm

Local variables To solve the ITB k-set agreement problem, Algorithm 4, which is round-based, relies on a very modular construction. Each process p i manages two local variables whose scope is the whole execution: a local round number r i , and a local estimate of a decision value, denoted est i . It also manages three local variables whose scope is the current round r: a multiset view i [r, 1], an auxiliary variable aux, and a set view i [r, 2].

Description of the algorithm

When p i invokes propose k (v i ) it assigns v i to est i and initializes r i to 0 (line 1). Then p i enters a loop that it will exit at line 8 by executing return(v), which returns the decided value v and stops its participation in the algorithm.

(viewi[ri, 2] = {⊥}) then esti ← random(mv validi[1, 1]) (11) end case [START_REF] Lamport | The Byzantine generals problem[END_REF] end repeat.

Algorithm 4: Byzantine k-set agreement based on SMV-broadcast, and local random coins Each round r executed by a process p i is made up of two phases. During the first phase of round r, each correct process p i invokes SMV broadcast(est i ) (multiset version) and stores the multiset returned by this invocation in view i [r, 1]. Let us remind that this multiset contains only values SMV-broadcast by at least one correct process. The aim of this phase is to build a global set 2 , denoted AUX [r], which contains at most (k + 1) values, such that at most k of them are contributed by correct processes, and the other one is the default value ⊥. To this end, each correct process p i checks if there is a value v that appears "enough" (say W ) times in the multiset view i [r, 1]. If there is such a value v, p i adopts it (assignment aux ← v), otherwise it adopts the default value ⊥ (line 5).

The set AUX [r] is made up of the aux variables of all the correct processes. For AUX [r] to contain at most k non-⊥ values, W has to be such that (k +1)W > n (there are not enough processes for (k +1) different values such that each of them was contributed by W processes) 3 . Hence, W > n/(k + 1).

When it starts the second phase of round r, each correct process p i invokes SMV broadcast(aux) (set version) and stores the set it obtains in view i [r, 2]. Due to the properties of SMV-broadcast,

Proof of the algorithm

The proof considers the system model BAMP n,t [t < n/(m + 1), LRC], the algorithmic safety and liveness constraints on W , namely, W (k + 1) > n and nt ≥ (W -1)k + 1, and the non-triviality condition (k < m) ∧ (k ≤ t).

Preliminary remark 1

The proof considers the semantic of the messages DECIDE() described previously. This is equivalent to consider that, after it has decided, a correct process continues executing while skipping line 8.

Notation

Lemma 1. If a correct process decides a value, this value was proposed by a correct process.

Proof Let us consider the first round r = 1. It follows from the MV-Justification property of the SMVbroadcast invocation at line 4 that the multiset view i [1, 1] of any correct process p i contains only values SMV-broadcast by correct processes. The same is true for the set view i [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Borowsky | Generalized FLP Impossibility Results for t-Resilient Asynchronous Computations[END_REF] which, in addition, can also contain the default value ⊥. It follows that, if a correct process decides at lines 7-8, it decides a value proposed by a correct process. If a correct process progresses to the next round, it executes line 9 or line 10 (for line 10, this follows from the MV-Justification property of the of the MV-broadcast generated by the invocation SMV broadcast PHASE[1, 1](est i )). In both cases, its new estimate value is a value proposed by a correct process. Hence the estimate values of the processes that start the second round are values proposed by correct processes. Applying this reasoning to the sequence of rounds, it follows that no correct process can decide a value not proposed by a correct process.

✷ Lemma 9. All correct processes decide with probability 1.

Proof Due Lemma 7 if a correct process decides, all correct processes decides. Hence, let us assume by contradiction that no correct process decides. Due to the MV-Equality property of the MV-broadcast generated by the invocations of SMV broadcast PHASE[1, 1]() issued by the correct processes, there is a finite time τ after which the sets mv valid i [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF] of the correct processes remain forever non-empty and equal.

As no correct process blocks forever in a round (Lemma 6), all correct processes progress from round to round forever. Moreover, as the decision predicate of line 7 is never satisfied at a correct process, it follows that, after τ , any correct process executes line 9 or line 10. Let us consider a round r entered by all correct processes after time τ . There are three cases.

•

Conclusion

This paper presented a signature-free randomized distributed algorithm that solves k-set agreement in asynchronous message-passing systems where up to t ≥ k processes may commit Byzantine failures.


Achour Mostéfaoui

Michel Raynal

Time-Efficient Read/Write Register in Crash-prone Asynchronous Message-Passing Systems

Keywords: Asynchronous message-passing system, Atomic read/write register, Concurrency, Fast operation, Process crash failure, Synchronous behavior, Time-efficient operation

The atomic register is certainly the most basic object of computing science. Its implementation on top of an n-process asynchronous message-passing system has received a lot of attention. It has been shown that t < n/2 (where t is the maximal number of processes that may crash) is a necessary and sufficient requirement to build an atomic register on top of a crash-prone asynchronous messagepassing system. Considering such a context, this paper visits the notion of a fast implementation of an atomic register, and presents a new time-efficient asynchronous algorithm. Its time-efficiency is measured according to two different underlying synchrony assumptions. Whatever this assumption, a write operation always costs a round-trip delay, while a read operation costs always a round-trip delay in favorable circumstances (intuitively, when it is not concurrent with a write). When designing this algorithm, the design spirit was to be as close as possible to the one of the famous ABD algorithm (proposed by Attiya, Bar-Noy, and Dolev).

Introduction

Since Sumer time [START_REF] Kramer | History Begins at Sumer: Thirty-Nine Firsts in Man's Recorded History[END_REF], and -much later-Turing's machine tape [START_REF] Turing | On computable numbers with an application to the Entscheidungsproblem[END_REF], read/write objects are certainly the most basic memory-based communication objects. Such an object, usually called a register, provides its users (processes) with a write operation which defines the new value of the register, and a read operation which returns the value of the register. When considering sequential computing, registers are universal in the sense that they allow to solve any problem that can be solved [START_REF] Turing | On computable numbers with an application to the Entscheidungsproblem[END_REF].

Register in message-passing systems In a message-passing system, the computing entities communicate only by sending and receiving messages transmitted through a communication network. Hence, in such a system, a register is not a communication object given for free, but constitutes a communication abstraction which must be built with the help of the communication network and the local memories of the processes.

Several types of registers can be defined according to which processes are allowed to read or write it, and the quality (semantics) of the value returned by each read operation. We consider here registers which are single-writer multi-reader (SWMR), and atomic. 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, between is start event and its end event, (b) no two operations appear at the same point of the time line, and (c) 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]. Algorithms building multi-writer multi-reader (MWMR) atomic registers from single-writer single-reader (SWSR) registers with a weaker semantics (safe or regular registers) are described in several 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 | Concurrent programming: algorithms, principles and foundations[END_REF]).

Many distributed algorithms have been proposed, which build a register on top of a message-passing system, be it failure-free or failure-prone. In the failure-prone case, the addressed failure models are the process crash failure model, or the Byzantine process failure model (see, the textbooks [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]). 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, which is usually called ABD according to the names its authors, considers an n-process asynchronous system in which up to t < n/2 processes may crash (it is also shown in [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF] that t < n/2 is an upper bound of the number of process crashes which can be tolerated). This simple and elegant algorithm, relies on (a) quorums [START_REF] Vukolic | Quorum systems, with applications to storage and consensus[END_REF], and (b) a simple broadcast/reply communication pattern. ABD uses this pattern once in a write operation, and twice in a read operation implementing an SWMR register.

Fast operation To our knowledge, the notion of a fast implementation of an atomic register operation, in failure-prone asynchronous message-passing systems, was introduced in [START_REF] Dutta | How fast can a distributed atomic read be?[END_REF] for process crash failures, and in [START_REF] Dutta | Fast access to distributed atomic memory[END_REF] for Byzantine process failures. These papers consider a three-component model, namely there are three different types of processes: a set of writers W , a set of readers R, and a set of servers S which implements the register. Moreover, a client (a writer or a reader) can communicate only with the servers, and the servers do not communicate among themselves.

In these papers, fast means that a read or write operation must entail exactly one communication round-trip delay between a client (the writer or a reader) and the servers. When considering the process crash failure model (the one we are interested in in this paper), it is shown in [START_REF] Dutta | How fast can a distributed atomic read be?[END_REF] that, when

(|W | = 1) ∧ (t ≥ 1) ∧ (|R| ≥ 2), the condition (|R| < |S| t -2
) is necessary and sufficient to have fast read and write operations (as defined above), which implement an atomic register. It is also shown in [START_REF] Dutta | How fast can a distributed atomic read be?[END_REF] that there is no fast implementation of an MWMR atomic register if

(|W | ≥ 2) ∧ (|R| ≥ 2) ∧ (t ≥ 1) .

Content of the paper

The work described in [START_REF] Dutta | How fast can a distributed atomic read be?[END_REF][START_REF] Dutta | Fast access to distributed atomic memory[END_REF] is mainly on the limits of the three-component model (writers, readers, and servers constitute three independent sets of processes) in the presence of process crash failures, or Byzantine process failures. These limits are captured by predicates involving the set of writers (W ), the set of readers (R), the set of servers (S), and the maximal number of servers that can be faulty (t). Both the underlying model used in this paper and its aim are different from this previous work.

While keeping the spirit (basic principles and simplicity) of ABD, our aim is to design a time-efficient implementation of an atomic register in the classical model used in many articles and textbooks (see, e.g., [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF][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]). This model, where any process can communicate with any process, can be seen as a peer-to-peer model in which each process is both a client (it can invoke operations) and a server (it manages a local copy of the register that is built). 1Adopting the usual distributed computing assumption that (a) local processing times are negligible and assumed consequently to have zero duration, and (b) only communication takes time, this paper focuses on the communication time needed to complete a read or write operation. For this reason the term time-efficiency is defined here in terms on message transfer delays, namely, the cost of a read or write operation is measured by the number of "consecutive" message transfer delays they require to terminate. Let us notice that this includes transfer delays due to causally related messages (for example round trip delays generated by request/acknowledgment messages), but also (as we will see in the proposed algorithm) message transfer delays which occur sequentially without being necessarily causally related. Let us notice that this notion of a time-efficient operation does not involve the model parameter t.

In order to give a precise meaning to the notion of a "time-efficient implementation" of a register operation, this paper considers two distinct ways to measure the duration of read and write operations, each based on a specific additional synchrony assumption. One is the "bounded delay" assumption, the other one the "round-based synchrony" assumption. More precisely, these assumptions and the associated time-efficiency of the proposed algorithm are the following.

• Bounded delay assumption.

Let us assume that every message takes at most ∆ time units to be transmitted from its sender to any of its receivers. In such a context, the algorithm presented in the paper has the following time-efficiency properties.

-A write operation takes at most 2∆ time units.

-A read operation which is write-latency-free takes at most 2∆ time units. (The notion of write-latency-freedom is defined in Section 3. Intuitively, it captures the fact that the behavior of the read does not depend on a concurrent or faulty write operation, which is the usual case in read-dominated applications.) Otherwise, it takes at most 3∆ time units, except in the case where the read operation is concurrent with a write operation and the writer crashes during this write, where it can take up to 4∆ time units. (Let us remark that a process can experience at most once the 4∆ read operation scenario.) • Round-based synchrony assumption.

Here, the underlying communication system is assumed to be round-based synchronous [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Lamport | On interprocess communication, Part I: basic formalism[END_REF][START_REF] Raynal | Distributed algorithms for message-passing systems[END_REF]. In such a system, the processes progress by executing consecutive synchronous rounds. In every round, according to its code, a process possibly sends a message to a subset of processes, then receives all the messages sent to it during the current round, and finally executes local computation. At the end of a round, all processes are directed to simultaneously progress to the next round.

In such a synchronous system, everything appears as if all messages take the very same time to go from their sender to theirs receivers, namely the duration δ associated with a round. When executed in such a context, the proposed algorithm has the following time-efficiency properties.

-The duration of a write operation is 2δ time units.

-The duration of a read operation is 2δ time units, except possibly in the specific scenario where the writer crashes while executing the write operation concurrently with the read, in which case the duration of the read can be 3δ time units (as previously, let us remark that a process can experience at most once the 3δ read operation scenario.)

Hence, while it remains correct in the presence of any asynchronous message pattern (e.g., when each message takes one more time unit than any previous message), the proposed algorithm is particularly time-efficient when "good" scenarios occur. Those are the ones defined by the previous synchrony patterns where the duration of a read or a write operation corresponds to a single round-trip delay. Moreover, in the other synchronous scenarios, where a read operation is concurrent with a write, the maximal duration of the read operation is precisely quantified. A concurrent write adds uncertainty whose resolution by a read operation requires one more message transfer delay (two in the case of the ∆ synchrony assumption, if the concurrent write crashes).

Roadmap

The paper consists of 6 sections. Section 2 presents the system model. Section 3 defines the atomic register abstraction, and the notion of a time-efficient implementation. Then, Section 4 presents an asynchronous algorithm providing an implementation of an atomic register with time-efficient operations, as previously defined. Section 5 proves its properties. Finally, Section 6 concludes the paper.

System Model

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

A process may halt prematurely (crash failure), but executes correctly its local algorithm until it possibly crashes. 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 correct or non-faulty.

Communication

The processes cooperate by sending and receiving messages through bi-directional channels. The communication network is a complete network, which means that any process p i can directly send a message to any process p j (including itself). 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).

A process p i invokes the operation "send TAG(m) to p j " to send p j the message tagged TAG and carrying the value m. It receives a message tagged TAG by invoking the operation "receive TAG()". The macro-operation "broadcast TAG(m)" is a shortcut for "for each j ∈ {1, . . . , n} send TAG(m) to p j end for". (The sending order is arbitrary, which means that, if the sender crashes while executing this statement, an arbitrary -possibly empty-subset of processes will receive the message.)

Let us notice that, due to process and message asynchrony, no process can know if an other process crashed or is only very slow. Notation In the following, the previous computation model, restricted to the case where t < n/2, is denoted CAMP n,t [t < n/2] (Crash Asynchronous Message-Passing).

It is important to notice that, in this model, all processes are a priori "equal". As we will see, this allows each process to be at the same time a "client" and a "server". In this sense, and as noticed in the Introduction, this model is the "fully connected peer-to-peer" model (whose structure is different from other computing models such as the client/server model, where processes are partitioned into clients and servers, playing different roles).

Atomic Register and Time-efficient Implementation

Atomic register

A concurrent object is an object that can be accessed by several processes (possibly simultaneously). An SWMR atomic register (say REG) is a concurrent object which provides exactly one process (called the writer) with an operation denoted REG.write(), and all processes with an operation denoted REG.read(). When the writer invokes REG.write(v) it defines v as being the new value of REG. An SWMR atomic register (we also say the register is linearizable [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF]) is defined by the following set of properties [START_REF] Lamport | On interprocess communication, Part I: basic formalism[END_REF].

• Liveness. An invocation of an operation by a correct 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 terminated before an operation op2 started, then op1 appears before op2 in the sequence.

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

Notion of a time-efficient operation

The notion of a time-efficient operation is not related to its correctness, but is a property of its implementation. It is sometimes called non-functional property. In the present case, it captures the time efficiency of operations. 2As indicated in the introduction, we consider here two synchrony assumptions to define what we mean by time-efficient operation implementation. As we have seen, both are based on the duration of read and write operations, in terms of message transfer delays. Let us remember that, in both cases, it is assumed that the local processing times needed to implement these high level read and write operations are negligible.

Bounded delay-based definition of a time-efficient implementation

Let us assume an underlying communication system where message transfer delays are upper bounded by ∆.

Write-latency-free read operation and interfering write Intuitively, a read operation is write-latencyfree if its execution does "not interleave" with the execution of a write operation. More precisely, let τ r be the starting time of a read operation. This read operation is write-latency-free if (a) it is not concurrent with a write operation, and (b) the closest preceding write did not crash and started at a time τ w < τ r -∆.

Let opr be a read operation, which started at time τ r . Let opw be the closest write preceding opr. If opw started at time τ w ≥ τ r -∆, it is said to be interfering with opr.

Bounded delay-based definition An implementation of a read/write register is time-efficient (from a bounded delay point of view) if it satisfies the following properties.

• A write operation takes at most 2∆ time units.

• A read operation which is write-latency-free takes at most 2∆ time units.

• A read operation which is not write-latency-free takes at most -3∆ time units if the writer does not crash while executing the interfering write, -4∆ time units if the writer crashes while executing the interfering write (this scenario can appear at most once for each process).

Round synchrony-based definition of a time-efficient implementation

Let us assume that the underlying communication system is round-based synchronous, where each message transfer delay is equal to δ. When considering this underlying synchrony assumption, it is assumed that a process sends or broadcasts at most one message per round, and this is done at the beginning of a round.

An implementation of a read/write register is time-efficient (from the round-based synchrony point of view) if it satisfies the following properties.

• The duration of a write operation is 2δ time units.

• The duration of a read operation is 2δ time units, except possibly in the "at most once" scenario where the writer crashes while executing the write operation concurrently with the read, in which case the duration of the read can be 3δ time units.

What does the proposed algorithm As we will see, the proposed algorithm, designed for the asynchronous system model CAMP n,t [t < n/2], provides an SWMR atomic register implementation which is time-efficient for both its "bounded delay"-based definition, and its "round synchrony"-based definition.

An Algorithm with Time-efficient Operations

The design of the algorithm, described in Figure 1, is voluntarily formulated to be as close as possible to ABD. For the reader aware of ABD, this will help its understanding.

Local variables

Each process p i manages the following local variables.

• reg i contains the value of the constructed register REG, as currently known by p i . It is initialized to the initial value of REG (e.g., the default value ⊥). • wsn i is the sequence number associated with the value in reg i .

• rsn i is the sequence number of the last read operation invoked by p i .

• swsn i is a synchronization local variable. It contains the sequence number of the most recent value of REG that, to p i 's knowledge, is known by at least (n -t) processes. This variable (which is new with respect to other algorithms) is at the heart of the time-efficient implementation of the read operation. • res i is the value of REG whose sequence number is swsn i .

local variables initialization: regi ← ⊥; wsni ← 0; swsni ← 0; rsni ← 0. operation write(v) is (1) wsni ← wsni + 1; regi ← v; broadcast WRITE(wsni, v);

(2) wait WRITE(wsni, -) received from (nt) different processes ;

(3) return() end operation. operation read() is % the writer may directly return regi % (4) rsni ← rsni + 1; broadcast READ(rsni); ( 5) wait (messages STATE(rsn, -) received from (nt) different processes) ∧ (swsni ≥ maxwsn)

where maxwsn is the greatest sequence number in the previous STATE(rsn, -) messages ; (6) return(resi) end operation. %- ---------------------------------------when WRITE(wsn, v) is received do [START_REF] Kramer | History Begins at Sumer: Thirty-Nine Firsts in Man's Recorded History[END_REF] Client side: operation write() invoked by the writer When the writer p i invokes REG.write(v), it increases wsn i , updates reg i , and broadcasts the message WRITE(wsn i , v) (line 1). Then, it waits until it has received an acknowledgment message from (n -t) processes (line 2). When this occurs, the operation terminates (line 3). Let us notice that the acknowledgment message is a copy of the very same message as the one it broadcast.

Server side: reception of a message write(wsn, v) when a process p i receives such a message, and this message carries a more recent value than the one currently stored in reg i , p i updates accordingly wsn i and reg i (line 7). Moreover, if this message is the first message carrying the sequence number wsn, p i forwards to all the processes the message WRITE(wsn, v) it has received (line 8). This broadcast has two aims: to be an acknowledgment for the writer, and to inform the other processes that p i "knows" this value. 3Moreover, when p i has received the message WRITE(wsn, v) from (n -t) different processes, and swsn i is smaller than wsn, it updates its local synchronization variable swsn i and accordingly assigns v to res i (lines 9-11).

Server side: reception of a message READ(rsn) When a process p i receives such a message from a process p j , it sends by return to p j the message STATE(rsn, wsn i ), thereby informing it on the freshness of the last value of REG it knows (line 12). The parameter rsn allows the sender p j to associate the messages STATE(rsn, -) it will receive with the corresponding request identified by rsn.

Client side: operation read() invoked by a process p i When a process invokes REG.read(), it first broadcasts the message READ(rsn i ) with a new sequence number. Then, it waits until "some" predicate is satisfied (line 5), and finally returns the current value of res i . Let us notice that the value res i that is returned is the one whose sequence number is swsn i .

The waiting predicate is the heart of the algorithm. Its first part states that p i must have received a message STATE(rsn, -) from (n-t) processes. Its second part, namely (swsn i ≥ maxwsn), states that the value in p i 's local variable res i is as recent or more recent than the value associated with the greatest write sequence number wsn received by p i in a message STATE(rsn, -). Combined with the broadcast of messages WRITE(wsn, -) issued by each process at line 8, this waiting predicate ensures both the correctness of the returned value (atomicity), and the fact that the read implementation is time-efficient.

Proof of the Algorithm

Termination and atomicity

The properties proved in this section are independent of the message transfer delays (provided they are finite).

Lemma 1 If the writer is correct, all its write invocations terminate. If a reader is correct, all its read invocations terminate.

Proof Let us first consider the writer process. As by assumption it is correct, it broadcasts the message WRITE(sn, -) (line 1). Each correct process broadcasts WRITE(sn, -) when it receives it for the first time (line 8). As there are at least (n -t) correct processes, the writer eventually receives WRITE(sn, -) from these processes, and stops waiting at line 2.

Let us now consider a correct reader process p i . It follows from the same reasoning as before that the reader receives the message STATE(rsn, -) from at least (n -t) processes (lines 5 and 12). Hence, it remains to prove that the second part of the waiting predicate, namely swsn i ≥ maxwsn (line 5) becomes eventually true, where maxwsn is the greatest write sequence number received by p i in a message STATE(rsn, -). Let p j be the sender of this message. The following list of items is such that item x =⇒ item (x + 1), from which follows that swsn i ≥ maxwsn (line 5) is eventually satisfied.

1. p j updated wsn j to maxwsn (line 7) before sending STATE(rsn, maxwsn) (line 12).

2. Hence, p j received previously the message WRITE(maxwsn, -), and broadcast it the first time it received it (line 8).

3. It follows that any correct process receives the message WRITE(maxwsn, -) (at least from p j ), and broadcasts it the first time it receives it (line 8).

4. Consequently, p i eventually receives the message WRITE(maxwsn, -) from (n -t) processes.

When this occurs, it updates swsn i (line 10), which is then ≥ maxwsn, which concludes the proof of the termination of a read operation.

✷ Lemma 1

Lemma 2

The register REG is atomic.

Proof Let read[i, x] be a read operation issued by a process p i which returns the value with sequence number x, and write[y] be the write operation which writes the value with sequence number y. The proof of the lemma is the consequence of the three following claims.

• Claim 1. If read[i, x] terminates before write[y] starts, then x < y.

• Claim 2. If write[x] terminates before read[i, y] starts, then x ≤ y.

• Claim 3. If read[i, x] terminates before read[j, y] starts, then x ≤ y.

Claim 1 states that no process can read from the future. Claim 2 states that no process can read overwritten values. Claim 3 states that there is no new/old read inversions [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Raynal | Distributed algorithms for message-passing systems[END_REF].

Proof Due to (a) the definition of maxwsn ≥ z, (b) the predicate swsn i ≥ maxwsn ≥ z (line 5), and (c) the value of swsn i = y, it follows that y = swsn i ≥ z when read[i, y] stops waiting at line 5. As, z ≥ x, it follows y ≥ x, which proves the claim.

Proof of Claim 3. When read[i, x] stops waiting at line 5, it returns the value res i associated with the sequence number swsn i = x. Process p i previously received the message WRITE(x, -) from a set Q r1 of at least (n -t) processes. The same occurs for p j , which, before returning, received the message WRITE(y, -) from a set Q r2 of at least (n -t) processes.

As |Q r1 | ≥ n -t, |Q r2 | ≥ n -t, and n > 2t, it follows that Q r1 ∩ Q r2 is not empty. Hence, there is a process p k which sent STATE(, x) to p i , and later sent STATE(-, y) to p j . As swsn k never decreases, it follows that x ≤ y, which completes the proof of the lemma.

✷ Lemma 2

Theorem 1 Algorithm 1 implements an SWMR atomic register in CAMP n,t [t < n/2].

Proof The proof follows from Lemma 1 (termination) and Lemma 2 (atomicity). ✷ T heorem 1

Time-efficiency: the bounded delay assumption

As already indicated, this underlying synchrony assumption considers that every message takes at most ∆ time units. Moreover, let us remind that a read (which started at time τ r ) is write-latency-free if it is not concurrent with a write, and the last preceding write did not crash and started at time τ w < τ r -∆.

Lemma 3 A write operation takes at most 2∆ time units.

Proof The case of the writer is trivial. The message WRITE() broadcast by the writer takes at most ∆ time units, as do the acknowledgment messagesWRITE() sent by each process to the writer. In this case 2∆ correspond to a causality-related maximal round-trip delay (the reception of a message triggers the sending of an associated acknowledgment). ✷ Lemma 3

Proof The proof follows directly from the observation that the write operation terminates after a roundtrip delay, whose duration is 2δ. ✷ Lemma 7

Lemma 8

The duration of a read operation is 2δ time units if the writer does not crash while executing a write operation concurrent with the read. Otherwise, it can be 3δ.

Proof Considering a read operation that starts at time τ r , let us assume that the writer does not crash while concurrently executing a write operation. At time τ r + δ all processes receives the message READ(rsn) sent by the reader (line 4), and answer with a message STATE(rsn, -) (line 12). Due the round-based synchrony assumption, all these messages carry the same sequence number x, which is equal to both their local variable wsn i and swsn i . It follows that at time τ r + 2δ, the predicate of line 5 is satisfied at the reader, which consequently returns from the read operation.

If the writer crashes while concurrently executing a write operation, it is possible that during some time (a round duration), some processes know the sequence number x, while other processes know only x -1. But this synchrony break in the knowledge of the last sequence number is mended during the next round thanks to the message WRITE(x, v) sent by the processes which are aware of x (See Figure 2). After this additional round, the read terminates (as previously) in two rounds. Hence, the read returns at the latest at time τ r + 3δ.

✷ Lemma 8

Theorem 3 Algorithm 1 modified as indicated in Figure 2

Conclusion

This work has presented a new distributed algorithm implementing an atomic read/write register on top of an asynchronous n-process message-passing system in which up to t < n/2 processes may crash. When designing it, the constraints we imposed on this algorithm were (a) from an efficiency point of view: provide time-efficient implementations for read and write operations, (b) and from a design principle point of view: remain "as close as possible" to the flagship ABD algorithm introduced by Attiya, Bar-Noy and Dolev [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF].

The "time-efficiency" property of the proposed algorithm has been analyzed according to two synchrony assumptions on the underlying system.

• The first assumption considers an upper bound ∆ on message transfer delays. Under such an assumption, any write operation takes then at most 2∆ time units, and a read operation takes at most 2∆ time units when executed in good circumstances (i.e., when there is no write operation concurrent with the read operation). Hence, the inherent cost of an operation is a round-trip delay, always for a write and in favorable circumstances for a read. A read operation concurrent with a write operation during which the writer does not crash, may require an additional cost of ∆, which means that it takes at most 3∆ time units. Finally, if the writer crashes during a write concurrent with a read, the read may take at most 4∆ time units. This shows clearly the incremental cost imposed by the adversaries (concurrency of write operations, and failure of the writer).

• The second assumption investigated for a "time-efficient implementation" is the one provided by a round-based synchronous system, where message transfer delays (denoted δ) are assumed to be the same for all messages. It has been shown that, under this assumption, the duration of a write is 2δ, and the duration of a read is 2δ, or exceptionally 3δ when the writer crashes while concurrently executing a write operation.

It is important to remind that the proposed algorithm remains correct in the presence of any asynchrony pattern. Its time-efficiency features are particularly interesting when the system has long synchrony periods.

Differently from the proposed algorithm, the ABD algorithm does not display different behaviors in different concurrency and failure patterns. In ABD, the duration of all write operations is upper bounded by 2∆ time units (or equal to 2δ), and the duration of all read operations is upper bounded by 4∆ time units (or equal to 4δ). The trade-off between ABD and our algorithm lies the message complexity, which is O(n) in ABD for both read and write operations, while it is O(n 2 ) for a write operation and O(n) for a read operation in the proposed algorithm. Hence our algorithm is particularly interesting for registers used in read-dominated applications. Moreover, it helps us better understand the impact of the adversary pair "writer concurrency + writer failure" on the efficiency of the read operations.

Figure 1 :

 1 Figure 1: Time-efficient SWMR atomic register in AMP n,t [t < n/2]

  if (wsn > wsni) then regi ← v; wsni ← wsn end if; (8) if (not yet done) then broadcast WRITE(wsn, v) end if; (9) if WRITE(wsn, -) received from (nt) different processes[START_REF] Raynal | Communication and agreement abstractions for fault-tolerant asynchronous distributed systems[END_REF]

then if (wsn > swsni) ∧ (not already done) then swsni ← wsn; resi ← v end if

[START_REF] Raynal | Distributed algorithms for message-passing systems[END_REF]

end if. when READ(rsn) is received from pj do

[START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF]

send STATE(rsn, wsni) to pj.

  of Claim 1. This claim follows from the following simple observation. When the writer executes write[y], it first increases its local variable wsn which becomes greater than any sequence number associated with its previous write operations (line 1). Hence if read[i, x] terminates before write[y] starts, we necessarily have x < y.Proof of Claim 2. It follows from line 2 and lines 7-8 that, when write[x] terminates, there is a set Q w of at least (n -t) processes p k such that wsn k ≥ x. On another side, due to lines 4-5 and line 12, read[i, y] obtains a message STATE() from a set Q r of at least (n -t) processes.As |Q w | ≥ n -t, |Q r | ≥ n -t, and n > 2t, it follows that Q w ∩ Q r is not empty. There is consequently a process p k ∈ Q w ∩ Q r , such that that wsn k ≥ x. Hence, p k sent to p i the message STATE(-, z), where z ≥ x.

Considering the three-component model where each reader is also a server (i.e., R = S), we obtain a two-component model with one writer and reader-server processes. In this model, the necessary and sufficient condition (|R| < |S| t -2) can never be satisfied, which means that, it is impossible to design a fast implementation of a SWMR atomic register in such a two-component model.

Another example of a non-functional property is quiescence. This property is on algorithms implementing reliable communication on top of unreliable networks[START_REF] Aguilera | On quiescent reliable communication[END_REF]. It states that the number of underlying implementation messages generated by an application message must be finite. Hence, if there is a time after which no application process sends messages, there is a time after which the system is quiescent.

Let us observe that, due to asynchrony, it is possible that wsni > wsn when pi receives a message WRITE(wsn, v) for the first time.

Messages STATE(rsn, x) are sent by the processes that received READ(rsn) before τw, while the messages STATE(rsn, x + 1) are sent by the processes that received READ(rsn) between τw and τr + ∆ = τw + ǫ.

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 DISPLEXITY devoted to the study of computability and complexity in distributed computing.

When the writer does not crash while executing a write operation The cases where the writer does not crash while executing a write operation are captured by the next two lemmas.

Lemma 4 A write-latency-free read operation takes at most 2∆ time units.

Proof Let p i be a process that issues a write-latency-free read operation, and τ r be its starting time. Moreover, Let τ w the starting time of the last preceding write. As the read is write latency-free, we have τ w + ∆ < τ r . Moreover, as messages take at most ∆ time units, and the writer did not crash when executing the write, each non-crashed process p k received the message WRITE(x, -) (sent by the preceding write at time τ w + ∆ < τ r ), broadcast it (line 8), and updated its local variables such that we have wsn k = x (lines 7-11) at ime τ w + ∆ < τ r . Hence, all the messages STATE() received by the reader p i carry the write sequence number x. Moreover, due to the broadcast of line 8 executed by each correct process, we have swsn i = x at some time τ w + 2∆ < τ r + ∆. It follows that the predicate of line 5 is satisfied at p i within 2∆ time units after it invoked the read operation.

✷ Lemma 4

Lemma 5 A read operation which is not write-latency-free, and during which the writer does not crash during the interfering write operation, takes at most 3∆.

Proof Let us consider a read operation that starts at time τ r , concurrent with a write operation that starts at time τ w and during which the writer does not crash. From the read operation point of view, the worst case occurs when the read operation is invoked just after time τ w -∆, let us say at time τ r = τ w -∆ + ǫ.

As a message STATE(rsn, -) is sent by return when a message READ(rsn) is received, the messages STATE(rsn, -) received by p i by time τ r + 2∆ can be such that some carry the sequence number x (due to last previous write) while others carry the sequence number x + 1 (due to the concurrent write) 4 . Hence, maxwsn = x or maxwsn = x + 1 (predicate of line 5). If maxwsn = x, we also have swsn i = x and p i terminates its read. If maxwsn = x + 1, p i must wait until swsn i = x + 1, which occurs at the latest at τ w + 2∆ (when p i receives the last message of the (n -t) messages WRITE(y, -) which makes true the predicates of lines 9-10, thereby allowing the predicate of line 5 to be satisfied). When this occurs, p i terminates its read operation. As τ w = τ r +∆-ǫ, p i returns at the latest τ r +3∆-ǫ time units after it invoked the read operation.

When the writer crashes while executing a write operation The problem raised by the crash of the writer while executing the write operation is when it crashes while broadcasting the message WRITE(x, -) (line 1): some processes receive this message by ∆ time units, while other processes do not. This issue is solved by the propagation of the message WRITE(x, -) by the non-crashed processes that receive it (line 8). This means that, in the worst case (as in synchronous systems), the message WRITE(x, -) must be forwarded by (t + 1) processes before being received by all correct processes. This worst scenario may entail a cost of (t + 1)∆ time units. Figure 2 presents a simple modification of Algorithm 1, which allows a fast implementation of read operations whose executions are concurrent with a write operation during which the writer crashes. The modifications are underlined.

When a process p i receives a message READ(), it now returns a message STATE() containing an additional field, namely the current value of reg i , its local copy of REG (line 12).

When a process p i receives from a process p j a message STATE(-, wsn, v), it uses it in the waiting predicate of line 5, but executes before the lines 7-11, as if this message was WRITE(wsn, v). According to the values of the predicates of lines 7, 9, and 10, this allows p i to expedite the update of its local variables wsn i , reg i , swsn i , and res i , thereby favoring fast termination. The reader can check that these modifications do not alter the proofs of Lemma 1 (termination) and Lemma 2 (atomicity). Hence, the proof of Theorem 1 is still correct.

Lemma 6 A read operation which is not write-latency-free, and during which the writer crashes during the interfering write operation, takes at most 4∆ time units.

Proof Let τ r be the time at which the read operation starts. As in the proof of Lemma 4, the messages STATE(rsn, -, -) received p i by time τ r + 2∆ can be such that some carry the sequence number wsn = x (due to last previous write) while some others carry the sequence number wsn = x + 1 (due to the concurrent write during which the writer crashes). If all these messages carry wsn = x, the read terminates by time τ r + 2∆. If at least one of these messages is STATE(rsn, x + 1, -), we have maxwsn = x + 1, and p i waits until the predicate swsn i ≥ maxwsn (= x + 1) becomes true (line 5).

When it received STATE(rsn, x + 1, -), if not yet done, p i broadcast the message WRITE(rsn, x + 1, -), (line 8 of Figure 2), which is received by the other processes within ∆ time units.

If not yet done, this entails the broadcast by each correct process of the same message WRITE(rsn, x + 1, -). Hence, at most ∆ time units later, p i has received the message WRITE(rsn, x + 1) from (n -t) processes, which entails the update of swsn i to (x + 1). Consequently the predicate of line 5 becomes satisfied, and p i terminates its read operation.

When counting the number of consecutive communication steps, we have: The message READ(rsn) by p i , followed by a message STATE(rsn, x+1, -) sent by some process and received by p i , followed by the message WRITE(rsn, x + 1) broadcast by p i , followed by the message WRITE(rsn, x + 1) broadcast by each non-crashed process (if not yet done). Hence, when the writer crashes during a concurrent read, the read returns within at most τ r + 4∆ time units.

✷ Lemma 6

Theorem 2 Algorithm 1 modified as indicated in Figure 2 implements in CAMP n,t [t < n/2] an SWMR atomic register with time-efficient operations (where the time-efficiency notion is based on the bounded delay assumption).

Proof The proof follows from Theorem 1 (termination and atomicity), Lemma 3, Lemma 4, Lemma 5, and Lemma 6 (time-efficiency). ✷ T heorem 2

Time-efficient implementation: the round-based synchrony assumption

As already indicated, this notion of a time-efficient implementation assumes an underlying round-based synchronous communication system, where the duration of a round (duration of all message transfer delays) is δ.

Lemma 7

The duration of write operation is 2δ.