Achour Mostéfaoui

Matoula Petrolia

Michel Raynal

Claude Jard

Atomic Read/Write Memory in Signature-free Byzantine Asynchronous Message-passing Systems

Keywords: Asynchronous message-passing system, Atomic read/write register, Byzantine process, Linearizability, Reliable broadcast abstraction systèmes asynchrones à passage de messages, registres atomiques read/write, diffusion fiable, processus Byzantins

This article presents a signature-free distributed algorithm which builds an atomic read/write shared memory on top of an n-process asynchronous message-passing system in which up to t < n/3 processes may commit Byzantine failures. From a conceptual point of view, this algorithm is designed to be as close as possible to the algorithm proposed by Attiya, Bar-Noy and Dolev (JACM 1995), which builds an atomic register in an n-process asynchronous message-passing system where up to t < n/2 processes may crash. The proposed algorithm is particularly simple. It does not use cryptography to cope with Byzantine processes, and is optimal from a t-resilience point of view (t < n/3). A read operation requires O(n) messages, and a write operation requires O(n 2 ) messages.

Introduction

Shared memory abstraction on top of a message-passing system Informatics is a science of abstractions, and accordingly (as in sequential computing) the writing of distributed applications can be greatly facilitated by the design and the use of underlying appropriate abstractions.

This paper considers the design of such an abstraction, namely an atomic read/write memory, on top of an asynchronous messagepassing distributed system made up of n processes, and where up to t processes may commit failures. The case of crash failures was solved by Attiya, Bar-Noy and Dolev in [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF] (a) where it is shown that t < n/2 is an upper bound for the model parameter t, and (b) where a simple, elegant, and t-resilient optimal algorithm is proposed. This algorithm is called ABD in the following.

This paper focuses on the case where processes may commit Byzantine failures, i.e., may behave in a way that does not respect their intended behavior (as defined by their specification).

Related work

Considering the clients/servers distributed model, several articles have addressed the design of servers implementing a shared memory accessible by clients. The servers are usually managing a set of disks (e.g., [START_REF] Chockler | Active disk Paxos with infinitely many processes[END_REF][START_REF] Ittai | Byzantine disk paxos: optimal resilience with byzantine shared memory[END_REF][START_REF] Alvisi | A framework for dynamic Byzantine storage[END_REF]). Moreover, while they consider that some servers can be Byzantine, some articles restrict the failure type allowed to clients. As an example, [START_REF] Dobre | The complexity of robust atomic storage[END_REF][START_REF] Guerraoui | How fast can a very robust read be?[END_REF] explore the efficiency issues (relation between resilience and fast reads) in the context where only servers can be Byzantine, while clients (the single writer and the readers) can fail by crashing. As other examples, [START_REF] Ittai | Byzantine disk paxos: optimal resilience with byzantine shared memory[END_REF] considers that clients can only commit crash failures, while [START_REF] Attiya | Sharing memory with semi-Byzantine clients and faulty storage servers[END_REF] considers that clients can only be "semi-Byzantine" (i.e., they can issue a bounded number of faulty writes, but otherwise respect their code). The algorithm presented in [START_REF] Malkhi | Secure and scalable replication in Phalanx[END_REF] allows clients and some number of servers to be Byzantine, but requires clients to sign their messages. As far as we know, [START_REF] Aiyer | Bounded wait-free implementation of optimally resilient Byzantine storage without (unproven) cryptographic assumptions[END_REF] was the first paper considering Byzantine readers while still offering maximal resilience (with respect to the number of Byzantine servers) without using cryptography. However, the writer can fail only by crashing, and the fact that a -possibly Byzantine-reader does not write a fake value in a register (to ensure the "reader have to write" rule required to implement atomicity) is insured only with some probability.

In the peer-to-peer model (defined here as a model in which all processes are "equal"), the construction of an atomic register requires that each process manages a copy the register that is built. The first algorithm building a read/write shared memory in a message-passing system where processes may commit Byzantine failures is (to our knowledge) the one presented in [START_REF] Imbs | Reliable shared memory abstraction on top of asynchronous byzantine message-passing systems[END_REF]. This paper considers the implementation of an SWMR (single-writer/multi-reader) atomic register. It also shows that t < n/3 is an upper bound the resilience parameter t for such a construction. In this algorithm, each SWMR atomic read/write register is represented, at each process, by the full history of all its modifications.

The fact that an SWMR register is considered is due to the following observation: as a Byzantine process can corrupt any register it can write, the design of a multi-writer/multi-reader register with non-trivial correctness guarantees is impossible in the presence of Byzantine processes.

Content of the paper

This paper presents a new algorithm implementing an array of n SWMR atomic read/write registers (one per process) in an asynchronous message-passing system where up to t < n/3 processes may commit Byzantine failures. This algorithm does not require to enrich the underlying system with cryptography-based techniques.

When designing this algorithm, an aim was to obtain an algorithm whose "spirit" is "as close as possible" to ABD. We think that this is important from both understanding and pedagogical point of views. It helps better understand the "gap" between crash failures and Byzantine failures. From an algorithmic point of view, we have the following:

• With respect to the algorithm described in [START_REF] Imbs | Reliable shared memory abstraction on top of asynchronous byzantine message-passing systems[END_REF], the proposed algorithm requires a process to store only a single pair (value, sequence number) per atomic register. • With respect to ABD, there are two main differences:

-One is the way processes implement the "reads have to write" requirement needed to obtain the atomicity property of a register [START_REF] Lamport | On interprocess communication, Part II: algorithms[END_REF]. -The other one lies in the broadcast operation used to disseminate new values. While a simple unreliable broadcast 1 is sufficient in the presence of process crash failures, a stronger broadcast needs to be used to cope with Byzantine processes in a signature-free system.

The resulting algorithm is particularly simple. Moreover, when considering the non-faulty processes, a read costs O(n) messages and a write costs O(n 2 ) messages.

Roadmap

The paper is composed of 6 sections. Section 2 presents the computation model, and the underlying reliable broadcast abstraction. Section 3 presents a specification of an SWMR read/write atomic register in the presence of Byzantine processes. Then, Section 4 presents the algorithm, and Section 5 proves its correctness. Finally, Section 6 concludes the paper.

Computation model

Process model, communication model, and failure model

Computing entities

The system is made up of a set Π of n sequential processes, denoted p 1 , p 2 , ..., p n . These processes are asynchronous in the sense that each process progresses at its own speed, which can be arbitrary and remains always unknown to the other processes.

Communication model

The processes cooperate by sending and receiving messages through bi-directional channels. The communication network is a complete network, which means that each process p i can directly send a message to any process p j (including itself). It is assumed that the Byzantine processes cannot control the network, hence when a process receives a message, it can unambiguously identify its sender. Each channel is reliable (no loss, corruption, or 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 bound on message transit times).

A process p i invokes the operation "send TAG(m) to p j " to send the message tagged TAG and carrying the value m. It receives a message tagged TAG by invoking the operation "receive TAG()". "broadcast TAG(m)" is a macro-operation that expands as "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 subset of processes of processes will receive the message.)

Byzantine failures

The model parameter t is an upper bound on the number of processes that can exhibit a Byzantine behavior [START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Pease | Reaching agreement in the presence of faults[END_REF]. A Byzantine process is a process that behaves arbitrarily: it can crash, fail to send or receive messages, send arbitrary messages, start in an arbitrary state, perform arbitrary state transitions, etc. Hence, 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. Moreover, while they cannot modify the content of the messages sent by non-Byzantine processes, they can read their content and reorder their deliveries. More generally, Byzantine processes can collude to "pollute" the computation.

A Byzantine process is also called a faulty process. A process that commits no failure (i.e., a non-Byzantine process) is also called a correct process.

Notation

In the following, the previous computation model, restricted to the case where t < n/3, is denoted BAMP n,t [t < n/3].

Reliable broadcast abstraction

This section presents a reliable broadcast abstraction (denoted r-broadcast) that will be used to build a read/write register (Section 4). This abstraction is a simple generalization of a reliable broadcast due to Bracha [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF]. While Bracha's abstraction is for a single broadcast, the proposed abstraction considers that each process can issue a sequence of broadcasts. It is shown in [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] that t < n/3 is a necessary requirement to cope with the net effect of asynchrony and Byzantine failures.

Specification

The reliable broadcast abstraction is defined by two operations denoted R_broadcast() and R_deliver(). When a process p i invokes R_broadcast() we say that "p i r-broadcasts a value". Similarly, when p i returns from an invocation of R_deliver() and obtains a value, we say "p i r-delivers a value".

The operation R_broadcast() has two input parameters: a broadcast value v, and an integer sn, which is a local sequence number used to identify the successive r-broadcasts issued by each process p i . The sequence of numbers used by each (correct) process is the increasing sequence of consecutive integers.

• RB-Validity. If a correct process r-delivers a pair (v, sn) from a correct process p i , then p i invoked the operation R_broadcast(v, sn).

• RB-Integrity. Given any process p i , a correct process r-delivers at most once a pair (-, sn) from p i .

• RB-Uniformity. If a correct process r-delivers a pair (v, sn) from p i (possibly faulty), then all the correct processes eventually r-deliver the same pair (v, sn) from p i .

• RB-Termination. If the process that invokes R_broadcast(v, sn) is correct, all the correct processes eventually r-deliver the pair (v, sn).

RB-Validity is on correct processes and relates their outputs to their inputs, namely no correct process r-delivers spurious messages from correct processes. RB-Integrity states that there is no r-broadcast duplication. RB-Uniformity is an "all or none" property (it is not possible for a pair to be delivered by a correct process and to be never delivered by the other correct processes). RB-Termination is a liveness property: at least all the pairs r-broadcast by correct processes are r-delivered by them. For completeness, an algorithm (due to Bracha [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF]), which implements the r-broadcast abstraction in the model BAMP n,t [t < n/3], is described in Appendix A. As already noticed in the Introduction, the "single-writer" requirement is natural in the presence of Byzantine processes. If registers could be written by any process, it would be possible for the Byzantine processes to pollute the whole memory, and no non-trivial computation could be possible.

On write operations by Byzantine processes A Byzantine process p k may invoke the write operation REG[k].write() to assign a new value to REG[k]

, but it may also try to modify REG[k] without using this operation. In such a case, its fraudulent attempt to modify REG[k] may succeed or not. If it succeeds, the corresponding modification of REG[k] is considered (from an external observer's point of view) as if it has been produced by an invocation of REG[k].write() 2 . This is because no correct process can distinguish such a modification of REG[k] from a call to the write operation by p k . Let us nevertheless notice that this does not prevent the fact that the value assigned to REG[k] can be a fake value. Moreover, at the abstraction level defined by REG [1..n], as p k is sequential, its modifications of REG[k] appear as if they have been executed sequentially.

Definitions

•

Specification

The correct behavior of the array of registers REG[1.

.n] is defined by the following set of properties.

• Termination (liveness). Let p i be a correct process.

-Each invocation of REG[i].write() terminates.

-For any j, any invocation of REG[j].read() by p i terminates.

• Consistency (safety) 3 . Let p i and p j be correct processes and p k any process.

-Read followed by write: (read[i, k, x] terminates before write[k, y] starts) ⇒ (x < y).

-Write followed by read: (write[j, x] terminates before read[i, j, y] starts) ⇒ (x ≤ y).4 -No read inversion: (read[i, k, x] terminates before read[j, k, y] starts) ⇒ (x ≤ y).

As there is no way to constrain the behavior of a Byzantine process, the termination property is only on correct processes, and there is no requirement on the value returned by a read issued by a Byzantine process. The safety property concerns only the values read by correct processes. The first property states that there is no read from the future, while the second property states that no read can obtain an overwritten value. Due to the possible concurrent accesses to a same register, these two properties actually defines a regular register [START_REF] Lamport | On interprocess communication, Part I: basic formalism[END_REF]. Hence the "no read inversion" property, which allows to obtain an atomic register from a regular register [START_REF] Chaudhuri | One-write algorithms for multivalued regular and atomic registers[END_REF][START_REF] Lamport | On interprocess communication, Part I: basic formalism[END_REF][START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF].

Linearizability

Atomic registers were formally defined in [START_REF] Lamport | On interprocess communication, Part I: basic formalism[END_REF][START_REF] Misra | Axioms for memory access in asynchronous hardware systems[END_REF]. Then, the atomicity concept was extended to any concurrent object defined by a sequential specification under the name linearizability [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF]. Hence in our context, the terms "atomic register" and "linearizable register" are synonymous. The properties provided by linearizability are investigated in [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF].

Definition Given a register REG[i], linearizability [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF] means that it is possible to totally order the executions of its read and write operations in such a way that (a) each operation appears as if it has been executed at a single point of the time line between its start event and its end event, (b) no two operation executions appear at the same point, and (c) each read operation returns the value written by the closest write operation that precedes it in the sequence (or the initial value if there is no such write operation).

A register is linearizable if its operations satisfy the previous items (a), (b), and (c). The linearization point of an operation is the point of the timeline at which this operation appears to have been instantaneously executed.

An important property of Linearizability An important theorem associated with linearizability is the following [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF]: If each object (here a register) is linearizable, then the set of all the objects, considered as a single object, is linearizable. This means that linearizable objects compose for free.

Theorem 1

The register specification defined in Section 3 defines atomic (linearizable) registers.

Proof As linearizable (atomic) objects compose for free [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF], it is sufficient to consider a single register and, starting from its specification defined in Section 3.1, show that it is linearizable.

Let REG[i] be a register. Let H i be the sequence of values written by p i in REG[i]. 5 The proof consists in building a sequence S i which (a) includes all the read operations of REG[i] issued by the correct processes plus the writes of REG[i] issued by p i , and (b) satisfies the definition of linearizability.

To simplify and without loss of generality, let us assume that there is an initial write that gives REG[i] its initial value. Let us start with S i being the sequence of write operations that produced the sequence H i .

Let read[j, i, x] be a read operation issued by a correct process p j . Let write[i, a] be the last write of REG[i] that terminates before read[j, i, x] starts. Let write[i, a+1], ..., write[i, a+c] be (if any) the writes of REG[i] that are concurrent with read[j, i, x]. If there is no such writes c = 0. Let b = c + 1. Hence, if any, write[i, b] is the first write of REG[i] starting after read[j, i, x] has terminated. We have the following.

• It follows that from the properties "read followed by write" and "write followed by read" that x ∈ {a, a + 1, ..., a + c}.

• It follows from the "no read inversion" property that if read[ℓ, i, x ′ ] (issued a correct process p ℓ ) starts after read[j, i, x], we have x ≤ x ′ .

The operation read[j, i, x] is added to S i just after write[i, x]. It there are two (or more) operations read[j 1 , i, x] and read[j 2 , i, x] issued by correct processes, they are placed one after the other in the sequence S i . All the read operations issued by the correct processes are added to S i as described.

It is easy to see that the execution associated with S i is linearizable (i.e., satisfies the items (a), (b), and (c) stated above). ✷ T heorem 1

Construction of Single-Writer/Multi-Reader Atomic Registers

An algorithm constructing an SWMR atomic (linearizable) register in the presence of up to t Byzantine processes, is described in Figure 1. As it assumes t < n/3, this algorithm is suited for the computing model BAMP n,t [t < n/3]. The algorithm presents the code associated with a correct process p i . The design of the algorithm strives to be as close as possible to the ABD algorithm [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF], which implements an atomic register in an asynchronous system where at most t < n/2 may crash. 6 It uses a wait(condition) statement. The corresponding process is blocked until the predicate condition becomes satisfied. While a process is blocked, it can process the messages it receives.

Local variables

Each process p i manages the following local variables whose scope is the full computation (local variables are denoted with lower case letters, and sub-scripted by the process index i).

• The operation REG[i].write(v) This operation is implemented by the client lines 1-4 and the server lines 11-12 (which are similar to the algorithm implementing a write operation in a crash-prone system [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF]). Process p i first increases wsn i and r-broadcasts the message WRITE(v, wsn i ). Let us remark that this is the only use of the reliable broadcast abstraction by the algorithm. The process p i then waits for acknowledgments (message WRITE_DONE(v, wsn i )) from (n -t) distinct processes, and finally terminates the write operation. As we will see (Lemma 2), the intersection of any two quorums of (n -t) processes contains at least (t + 1) correct processes. This intersection property will be used to prove the consistency of the register REG[i].

When p i r-delivers a message WRITE(v, wsn) from a process p j , it waits until wsn = reg i [j] + 1 (line 12). Hence, whatever the sender p j , its messages WRITE() are processed in their sending order. When this predicate becomes true, p i updates accordingly its local with respect to REG[j] (line 13), and sends back to p j an acknowledgment to inform it that its new write has locally been taken into account (line 14).

Write of REG[j]

by a Byzantine process p j Let us observe that the only way for a process p i to modify reg i [j] is to r-deliver a message WRITE(v, wsn) from a (correct or faulty) process p j . Due to the RB-Uniformity of the r-broadcast abstraction, it that, if a correct process p i r-delivers such a message, all correct processes will r-deliver the same message, be its sender correct or faulty. Consequently each of them will eventually execute the statements of lines 12-14.

Hence, when a faulty process invokes R_broadcast WRITE(v, wsn) (be the r-broadcast invocation involved in an invocation of REG [j].write(v) or not), its faulty behavior is restricted to broadcast fake values for v and wsn.

The operation REG[j].read()

This operation is implemented by the client lines 5-11 and the server line 15. The corresponding algorithm is the core of the implementation of an SWMR atomic register.

When p i wants to read REG[j], it first broadcasts a read request (message READ(j, rsn i [j])), and waits for corresponding acknowledgments (message STATE(rsn i [j], -)). Each of these acknowledgment carries the sequence number associated with the current value of REG[j], as known by the sender of the message (line 15). For p i to progress, the wait predicate (line 7) states that its local representation of REG[j], namely reg i [j], must be fresh enough (let us remember that the only line where reg i [j] can be modified is line 13, i.e., when p i r-delivers a message WRITE(-, -) from p j ). This freshness predicate states that p i 's current value of reg i [j] is as fresh as the current value of at least (n -t) processes (i.e., at least (n -2t) correct processes). If the freshness predicate is false, it will become true when p i will have r-delivered WRITE(-, -) messages, which have been r-delivered by other correct processes, but not yet by it.

When this waiting period terminates, p i considers the current value w, wsn of reg i [j] (line 8). It then broadcasts the message CATCH_UP(j, wsn), and returns the value w as soon as its message CATCH_UP() is acknowledged by (n -t) processes (lines 9-10).

The aim of the CATCH_UP(j, wsn) message is to allow each destination process p k to have a value in its local representation of REG[j] (namely reg k [j].val) at least as recent as the one whose sequence number is wsn (line 15). The aim of this value local variables initialization: ------------------------------- ------------------------------- resynchronization is to prevent read inversions. When p i has received the (n -t) acknowledgments it was waiting for (line 10), it knows that no other correct process can obtain a value older than the value w it returns.

reg i [1..n] ← [ init 0 , 0 , . . . , initn, 0 ]; wsn i ← 0; rsn i [1..n] ← [0, • • • , 0]. %-
- operation REG[i].write(v) is (1) wsn i ← wsn i + 1; (2) R_broadcast WRITE(v, wsn i ); (3) wait WRITE_DONE(wsn i ) received from (n -t) different processes; (4) return() end operation. operation REG[j].read() is (5) rsn i [j] ← rsn i [j] + 1; (6) broadcast READ(j, rsn i [j]); (7) wait reg i [j].sn ≥ max(

Message cost of the algorithm

In addition to a reliable broadcast (whose message cost is O(n 2 )), a write operation generates n messages WRITE_DONE. Hence the cost of a write is O(n 2 ) message. A read operation cost 4n messages, n messages for each of the four kinds of messages READ, STATE, CATCH_UP and catch_up_done.

Comparing with the crash failure model It is known that the algorithms implementing an atomic register on top of an asynchronous message-passing system prone to process crashes, require that "reads have to write" [START_REF] Attiya | Efficient and robust sharing of memory in message-passing systems[END_REF][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] Lamport | On interprocess communication, Part II: algorithms[END_REF][START_REF] Raynal | Communication and agreement abstractions for fault-tolerant asynchronous distributed systems[END_REF]. More precisely, before returning a value, in one way or another, a reader must write this value to ensure atomicity (otherwise, we have only a "regular" register [START_REF] Lamport | On interprocess communication, Part I: basic formalism[END_REF]). Doing so, it is not possible that two sequential read invocations, concurrent with one or more write invocations, be such that the first read obtains a value while the second read obtains older value (this prevents read inversion).

As Byzantine failures are more severe than crash failures, the algorithm of Figure 1 needs to use a mechanism analogous to the "reads have to write" to prevent read inversions from occurring. As previously indicated, This is done by the messages CATCH_UP() broadcast at line 9 and the associated acknowledgments messages CATCH_UP_DONE() received at line 10. As previously indicated, these messages realize a synchronization during which (n-t) processes (i.e., at least (n-2t) correct processes) have resynchronized their value, if needed (line 15).

A comparison of two instances of the ABD algorithm [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF] and the algorithm of Figure 1 is presented in Table 1. The first instance is the version of the ABD algorithm which builds an array of n SWMR (single-writer/multi-reader) atomic registers (one register per process). The second instance is the version of the ABD algorithm which builds a single MWMR (multi-writer/multi-reader) atomic register.

As they depend on the application and not on the algorithm, the size of the values which are written is considered as constant. The parameters n and t have the same meaning as before; m denotes an upper bound on the number of read and write operations on each register. The value log n is due to the fact that a message carries a constant number of process identities. Similarly, log m is due to the fact that (a) a message carries a constant number of sequence numbers, and (b) there is a constant number of message tags (including the underlying reliable broadcast).

Proof of the construction

The model assumption n > 3t is implicit in all the statements and proofs that follow.

Preliminary lemmas

Lemma 1 If a correct process p i r-delivers a message WRITE(w, sn) (from a correct or faulty process), any correct process rdelivers it.

Proof This is an immediate consequence of the RB-Uniformity property of the the r-broadcast abstraction.

✷ Lemma 1
Lemma 2 Any two sets (quorums) of (n -t) processes have at least on correct process in their intersection.

Proof Let Q 1 and Q 2 be two sets of processes such that

|Q 1 | = |Q 2 | = n -t.
In the worst case, the t processes that are not in Q 1 belong to Q 2 , and the t processes that are not in As there are least (n -t) correct processes, p i receives such acknowledgments from at least (n -t) different processes, and terminates its first invocation (lines 3-4). As, for any given any process p j , all correct processes process the messages WRITE() from p j in their sequence order, the lemma follows from a simple induction (whose previous paragraph is the proof of the base case).

Q 2 belong to Q 1 . It follows that |Q 1 ∩ Q 2 | ≥ n -2t. As n > 3t, it follows that |Q 1 ∩ Q 2 | ≥ n -2t ≥ t + 1,
✷ ) is eventually satisfied. Let wsn be one of the previous sequence number, and p k the correct process that send it. This means that reg k [j].sn = wsn (line 15), from which we conclude (as p k is correct) that p k has previously r-delivered a message WRITE(-, wsn) and updated accordingly reg k [j] at line 13 (let us remember that this is the only line at which the local register reg k [j] is updated). It follows from Lemma 1 that eventually p i r-delivers the message WRITE(-, sn). It follows then from line 13 that eventually we

Conclusion

This paper presented a signature-free algorithm building an array of n single-writer/multi-reader atomic registers (with a register per process) in an n-process asynchronous message-passing system where up to t < n/3 processes may commit Byzantine failures. This algorithm relies on an underlying reliable broadcast [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF], an appropriate freshness predicate and a value resynchronization mechanism which ensure that a correct process always reads up-to-date values. A noteworthy property of this algorithm lies in its conceptual simplicity.

According to the result of [START_REF] Imbs | Reliable shared memory abstraction on top of asynchronous byzantine message-passing systems[END_REF] this algorithm is optimal from a t-resilience point of view. While the cost of a read operation is linear with respect to n, a problem which remains open lies in its O(n 2 ) complexity for write operations. This cost is due to the use of a Byzantine-tolerant reliable broadcast. Hence the question: Is it possible to reduce it, or is O(n 2 ) a lower bound when one has to implement an atomic register in a signature-free message-passing distributed system prone to Byzantine failures? We conjecture it is a lower bound.

operation R_broadcast APP(v, sn):

(1) broadcast APP(v, sn). when a message APP(v, sn) from p j is received:

(2) if no message APP(-, sn)) received from p j [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF] then wait (next i [j] = sn); [START_REF] Attiya | Sharing memory with semi-Byzantine clients and faulty storage servers[END_REF] broadcast ECHO(j, v, sn) (5) end if. when a message ECHO(j, v, sn) is received: (6) if ECHO(j, v, sn) received from strictly more than n+t 2 different processes [START_REF] Chaudhuri | One-write algorithms for multivalued regular and atomic registers[END_REF] ∧ READY(j, v, sn) never sent [START_REF] Chockler | Active disk Paxos with infinitely many processes[END_REF] then broadcast READY(j, v, sn) (9) end if. when a message READY(j, v, sn) is received: [START_REF] Guerraoui | How fast can a very robust read be?[END_REF] if READY(j, v, sn) received from at least t + 1 different processes (11) ∧ READY(j, v, sn) never sent [START_REF] Imbs | Reliable shared memory abstraction on top of asynchronous byzantine message-passing systems[END_REF] then broadcast READY(j, v, sn) (13) end if; [START_REF] Lamport | The Byzantine generals problem[END_REF] • Finally, when p i has received the message READY(j, v, sn) from (t + 1) different processes, it broadcasts the same message READY(j, v, sn), it not yet done. This is required to ensure the RB-termination property. If p i has received "enough" messages READY(j, v, sn) (as before "enough" means "from more than (n + t)/2 different processes"), it r-delivers the message APP(v, sn) r-broadcast by p j .

Proofs that this algorithm satisfies the properties defining the reliable broadcast abstraction can be found in [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Mostéfaoui | Communication and agreement abstractions in the presence of Byzantine processes[END_REF].

Collection des Publications Internes de l'Irisa c IRISA

3

  Atomic Read/Write Registers in the Presence of Byzantine Processes 3.1 Definitions and specification Single-writer/multi-reader (SWMR) registers The fault-tolerant shared memory supplied to the upper abstraction layer is an array denoted REG[1..n]. For each i, REG[i] is a single-writer/multi-reader (SWMR) register. This means that REG[i] can be written only by p i . To that end, p i invokes the operation REG[i].write(v) where v is the value it wants to write into REG[i]. Differently, any process p j can read REG[i]. It invokes then the operation REG[i].read().

Figure 1 :

 1 Figure 1: Atomic SWMR Registers in BAMP n,t [t < n/3] (code for process p i )

  reg i [1..n] is the local representation of the array REG[1..n] of atomic SWMR registers. Each local register reg i [j] contains two fields, a sequence number reg i [j].sn, and the corresponding value reg i [j].val. It is initialized to the pair init j , , where init j is the initial value of REG[j].• wsn i is an integer, initialized to 0, used by p i to associate sequence numbers with its successive write invocations.• rsn i [1..n] is an array of sequence numbers (initialized to [0, • • • , 0]) such that sn i [j] is used by p i to identify its successive read invocations of REG[j].7

  wsn 1 , ..., wsn n-t ) where wsn 1 , ..., wsn n-t are from messages STATE(rsn i [j], -) received from nt different processes ; (8) let w, wsn the value of reg i [j] which allows the previous wait to terminate; (9) broadcast CATCH_UP(j, wsn); (10) wait CATCH_UP_DONE(j, wsn) received from (nt) different processes ;

	(11) return(w)
	end operation.
	%-

  when a message WRITE(v, wsn) is R_delivered from p j do (12) wait(wsn = reg i [j].sn + 1); (13) reg i [j] ← v, wsn ; (14) send WRITE_DONE(wsn) to p j . when a message READ(j, rsn) is received from p k do (15) send STATE(rsn, reg i [j].sn) to p k . when a message CATCH_UP(j, wsn) is received from p k do (16) wait (reg i [j].sn ≥ wsn); (17) send CATCH_UP_DONE(j, wsn) to p k .

Table 1 :

 1 Crash vs Byzantine failures: cost comparisons

	algorithm	failure type requirement msgs/write msgs/read	msg size	local mem./proc.
	ABD: n SWMR	crash	t < n/2	O(n)	O(n)	O(log n + log m)	O(n log m)
	ABD: 1 MWMR	crash	t < n/2	O(n)	O(n)	O(log n + log m)	O(n log m)
	Fig. 1: n SWMR	Byzantine	t < n/3	O(n 2 )	O(n)	O(log n + log m)	O(n log m)

Proof of the termination properties Lemma 3

  which concludes the proof of the lemma. Let p i be a correct process. Any invocation of REG[i].write() terminates.Proof Let us consider the first invocation of REG[i].write() by a correct process p i . This write operation generates the r-broadcast of message WRITE(-, 1) (lines 1-2). Due to Lemma 1, all correct processes r-deliver this message, and the waiting predicate of line 13 is eventually satisfied. Consequently, each correct process p k eventually sets reg k [i].sn to 1, and sends back to p i an acknowledgment message WRITE_DONE[START_REF] Aiyer | Bounded wait-free implementation of optimally resilient Byzantine storage without (unproven) cryptographic assumptions[END_REF].

	✷ Lemma 2
	5.2

  Lemma 4 Let p i be a correct process. For any j, any invocation of REG[j].read() terminates.Proof When a correct process p i invokes REG[j].read(), it broadcasts a message READ(j, rsn) where rsn is a new sequence number (lines 5-6). Then, it waits until the freshness predicate of line 7 becomes satisfied. As p i is correct, each correct process p k receives READ(j, rsn), and sends back to p i a message STATE(rsn, wsn), where wsn is the sequence number of the last value of REG[j] it knows (line 15). It follows that p i receives a message STATE(j, -) from at least (n -t) correct processes. Let STATE(j, wsn 1 ), • • • , STATE(j, wsn n-t ) be these messages.To show that the wait of line 7 terminates we have to show that the freshness predicate reg i [j].sn ≥ max(wsn 1 , • • • , wsn n-t

	Lemma 3

Piecing together the lemmas Theorem 2

  Collection des Publications Internes de l'Irisa c IRISA When p j invokes REG[k].read() it broadcasts the message READ() and waits until the freshness predicate is satisfied (lines 7). The messages STATE(-, -) it receives are from (n -t) different processes. Let Q 2 be this set of (n -t) processes.It follows from Lemma 2 that at least one correct process p ℓ belongs toQ 1 ∩ Q 2 .According to the fact that read[i, k, x] terminates before read[j, k, y] starts, it follows that p ℓ sent CATCH_UP_DONE(k, x) to p i before sending the message STATE(-, s) to p j . As reg ℓ [k].sn never decreases, it follows that x ≤ s. It finally follows that, when the freshness predicate is satisfied at p j , we have reg j [k].sn ≥ s. As y = reg j [k].sn (lines 8-11), it follows that x ≤ y, which concludes the proof. The algorithm described in Figure1implements an array of n SWMR atomic (linearizable) registers (one register per process) in the system model BAMP n,t [t < n/3].ProofThe proof follows from Lemmas 3-8 and Theorem 1.✷ T heorem 2

	✷ Lemma 8
	5.4

  if READY(j, v, sn) received from at least 2t + 1 different processes (15) ∧ APP(v, sn) by p j never R_delivered (16) then R_deliver APP(v, sn) from p j ; (17) next i [j] ← next i [j] + 1 (18) end if. Figure 2: Reliable Broadcast in BAMP n,t [t < n/3], (code for process p i )

c IRISA -Campus de Beaulieu -35042 Rennes Cedex -France -+33 2 99 84 71 00 -www.irisa.fr

Collection des Publications Internes de l'Irisa c IRISA

As we will see, at the operational level, when a modification of REG[i] by a Byzantine process p i succeeds, the underlying messages generated by p i could have been sent by a correct implementation of the operation write().

It would be possible to associate a start event and an end event with each read[i, j, x] and each write[i, y] issued by a correct process, and a start event with each write[j, y] issued by a Byzantine process, so that all these events define a total order from which the notion of "terminates before" could be formally defined (as in[START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF][START_REF] Lamport | On interprocess communication, Part I: basic formalism[END_REF][START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF]). To not overload the presentation, we do not use this formalization here.Collection des Publications Internes de l'Irisa c IRISA

Let us notice that this property considers that the write of REG[j] is issued by a correct process. This is because it is not always possible to define when the modification of REG[j] has terminated when p j is Byzantine.

As we have seen, if p i is Byzantine, this sequence contains all the modifications of REG[i] which cannot be distinguished by the correct processes from invocations of REG[i].write() by p i .Collection des Publications Internes de l'Irisa c IRISA

In addition to the stronger necessary and sufficient condition t < n/3, this presentation style allows people aware of the ABD algorithm to see the additional statements needed to go from crash failures to Byzantine behavior.

If we assume that no correct process p i reads its own register REG[i], rsn i [i] can be used to store wsn i .Collection des Publications Internes de l'Irisa c IRISA

Acknowledgments

This work has been partially supported by the French ANR project DISPLEXITY devoted to computability and complexity in distributed computing, the Franco-German ANR-DFG project DISCMAT (devoted to connections between mathematics and distributed computing), and the French ANR project CO 2 Dim.

have reg i [j].sn ≥ sn. As this is true for any sequence number in {wsn 1 , ..., wsn n-t }, it follows that the freshness predicate is eventually satisfied, and consequently the wait statement of line 7 is satisfied.

Let us now consider the wait statement of line 10, which appears after p i has broadcast the message CATCH_UP(j, wsn), where wsn = reg i [j].sn (sequence number in reg i [j] just after p i stopped waiting at line 7). We show that any correct process sends back to p i an acknowledgment CATCH_UP_DONE(j, wsn) at line 17. Process p i updated reg i [j].sn to wsn at line 13, and this occurred when it r-delivered a message WRITE(-, wsn). The reasoning is the same as in the previous paragraph, namely, it follows from Lemma 1 that all correct processes r-deliver this message and consequently we have reg k [j].sn ≥ wsn at every correct process p k . Hence, the value resynchronization predicate of line 16 is eventually satisfied at all correct processes, that consequently sends back a message CATCH_UP_DONE(j, wsn) at line 17, which concludes the proof of the lemma.

✷ Lemma 4

Proofs of the consistency (atomicity) properties

The next lemma shows that a sequence H i , as defined in Section As write[j, y] defines H j [y], it follows that a message WRITE(-, y) is r-delivered from p j at each correct process p k which executes reg k [j] ← -, y at line 13. As this occurs after read[i, j, x] has terminated, we necessarily have x < y.

✷ Lemma 6

Lemma 7 Let p i and p j be correct processes. If write[i, x] terminates before read[j, i, y] starts, we have x ≤ y.

Proof Let p i a correct process that returns from its x th invocation of REG[i].write(). It follows from line 1 that the sequence number x is associated with the written value. It follows from the r-broadcast of the message WRITE(v, x) issued by p i (line 2), and its r-delivery (line 12) at each correct process (RB-uniformity of the r-broadcast), that p i receives (n -t) messages WRITE_DONE(x) (line 3). Let Q 1 be this set of (n -t) processes that sent these messages (line 14). Let us notice that there are at least (n -2t) correct processes in Q 1 and, due to line 13, any of them, say p k , is such that reg k [i].sn ≥ x. Let p j be a correct process that invokes REG[i].read(). The freshness predicate of line 7 blocks p j until reg j [i].sn ≥ max(wsn 1 , ..., wsn n-t ). Let Q 2 be the set of the (n -t) processes that sent the messages STATE() (line 15) which allowed p j to exit the wait statement of line 7.

It follows from Lemma 2 that at least one correct process p k belongs to

A A Reliable Broadcast Algorithm

The r-broadcast algorithm presented in Figure 2 is Bracha's algorithm [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] enriched with sequence numbers. Each process p i manages a local array next i [1.

.n], where next i [j] is the sequence number sn of the next application message (namely, APP(-, sn)) from p j , that p i will process (line 3). Initially, for all i, j, next i [j] = 1. When a process p i invokes R_broadcast APP(v, sn), it broadcasts the message APP(v, sn) (line 1) where sn is its next sequence number. On its "server" role, the behavior of a process p i is as follows.

• When a process p i receives a message APP(v, sn) from a process p j for the first time, it first waits until it can process this message (line 3). Process p i then broadcasts a message ECHO(j, v, sn) (line 4). If the message just received is not the first message APP(-, sn), p j is Byzantine and the message is discarded. • Then, when p i has received the same message ECHO(j, v, sn) from "enough" processes (where "enough" means "more than (n + t)/2 different processes"), and has not yet broadcast a message READY(j, v, sn), it does it (lines 6-9).

The aim of (a) the messages ECHO(j, v, sn), and (b) the cardinality "greater than (n + t)/2 processes", is to ensure that no two correct processes can r-deliver distinct messages from p j (in the case where p j is Byzantine). The aim of the messages READY(j, v, sn) is related to the liveness of the algorithm. Namely, its aim is to allow (at least when p j is correct) the rdelivery by the correct processes of the very same message APP(v, sn) from p j , and this must always occur if p j is correct. It is nevertheless possible that a message r-broadcast by a Byzantine process p j be never r-delivered by the correct processes.


D Coadour
email: damien.coadour@ensta-bretagne.fr

O Reynet

C Gillet

CODESIGNED AND COCONSTRUCTED LEADERSHIP TRAINING OF ENGINEERS

Keywords: Leadership, Co-creation, Reflexivity, Evaluation

INTRODUCTION

Teaching team management and leadership to future engineers is far from easy, as this discipline demands both reflection on oneself and on one's relations with others. Moreover, it is not easy to create representative didactic transpositions of future situations in a student's professional life, within the standard framework of the classroom. Yet, the objective of this training module is to broach effectively the questions and problematic issues related to the management of teams, leadership and evaluation, with the aim of stimulating a better handling of collective situations. Indeed, the success of a team depends on the contribution of each individual and especially on the climate of confidence that must be established by the leader. Moreover, the latter should establish objectives, remove obstacles, make choices and assume responsibility. Teachers often fall back on case studies to illustrate good practices. However, leadership is action, a praxis that is mainly learned through the reality test: the experience of others, then our own. [START_REF] Lapierre | Enseigner le leadership ou former vraiment des leaders?[END_REF]. That is why our approach consists in combining experience on the field, gained through challenges, with experience derived from anticipation, projection and reflexive retro-analysis in the classroom. This combined experience places the students in a human and environmental pedagogical context which they are not familiar with, producing a loss of bearings and a true learning opportunity. To put these principles into practice, we have set up a training system based on strong pedagogical convictions: firstly, we used discovery-based activities implementing the Houssayrian triangle [START_REF] Houssaye | Théorie et pratique de l'éducation[END_REF], that is to say a context where the training content is not accessible without the participation and collaboration of the teacher and the students. Then, we applied the Devolution Principle [START_REF] Brousseau | Théorie des situations didactiques[END_REF])a principle which proposes that teachers loosen their control over lessons and delegate their responsibility to the students to construct a co-creation of the pedagogical content to induce an individual, sometimes reciprocal (student and teacher), and auto-regulated learning process. The students and teachers are thus co-players of the targeted reflections and contents. This article starts off providing a detailed description of the organization of the pedagogical activity. The participants then proceed to explain how they sought to produce tangible documents that could illustrate the reflexive leadership learning experience, and they present the first results of their analysis. Finally, an assessment of the activity is made, and the prospects for future improvements are outlined in the conclusion.

DESCRIPTION

This training activity was integrated into our school curriculum in the form of a oneweek event. It proved extremely unifying for the students of a single cohort, as they experienced an original, collective and educational activity from a pedagogical point of view. This event was a new keystone in the human and social training of our school and mobilized all the de-compartmentalized skills required to succeed. All the teaching staff in the Human and Social Sciences Department of the school were involved and co-created this activity; for example, each member proposed a challenge based on his discipline: the language teachers suggested an activity based on communication in English, the management teachers set a challenge based on reaching a consensus etc.

The activity was divided into several phases and took place over several geographical locations, as detailed in Figure 1: the first and last days were organized at school; while the central activity was a 2-day bivouac in a military camp, which engendered a strong sense of disorientation, despite its proximity to the school (50km), in an unfamiliar yet safe environment. In a challenging scenario imagined by the teaching staff, a group of engineers had to survive an attack by terrorists who were trying to take them hostage. To escape, they had to succeed in a set of 8 tasks2 . The success of the tasks depended on the capacity of the team to understand and share the objective, to find a solution together and to put this solution into practice. Each member of the team would become task leader in turn. The tasks had been devised so that they could not be solved by an individual acting alone.

Fig. 1: General organization of the pedagogical activity

The teams were composed of 6 to 8 students chosen at random and not by affinity. During the anticipatory stage, they discovered the objectives set by the teachers, the composition of their team and the three pivotal roles of the particular task they were to be attributed: that of Team Member and Task Leader, Head of Workshop and Controller. Some students were French and foreign civilians while others were French and foreign military cadets destined to become officers 3 . According to their status, different roles were entrusted to the students as described in Table 1.

Table 1 : Pivotal roles in the leadership training activity

Roles Student's status Mission

Head of Workshop

Civilian or military

Lead a workshop on the field Controller Military Be responsible for the team, the adherence to the safety rules and timelines Task Leader Civilian As team coordinator, ensure the completion of a particular task Still in the anticipatory stage, the students were called upon to reflect individually and collectively upon the roles and responsibilities of each of the members of the group during a challenge. To initiate this reflection, each team was asked to construct the longest bridge possible using spaghetti. They were then given an individual written assessment of their understanding of the stages necessary to succeed in the challenge and the roles they identified within their team. Then, together with the teachers, they collectively constructed an evaluation grid for each pivotal role in the task. This team reflection paved the way for a presentation in the final stage. The first day ended in the amphitheater with a presentation of the evaluation criteria by the students. The teams were formed and the students had to prepare to be at school the next morning for the 7.30 start. The 2-day bivouac on the field followed, with the completion of the eight tasks by all teams.

The last training day was organized so as to collate their experiences by means of two activities, namely the evaluation and feedback on their reflection, initiated during the anticipatory stage. For the evaluation, each student had to evaluate two activities that he encountered as specified in Figure 2 and negotiate with the group the mark proposed according to the pre-established grid. The reflexive activity in the anticipatory stage consisted in encouraging them to question and analyze the roles retrospectively within a constituted group, allowing them to take up a challenge and to share their analyses in the amphitheater. The organization of the activity in this way made it possible to recover very interesting feedback about the perception of the students before and after experiencing the training and underlying learning process.

Fig. 2: Cross evaluations of the different pivotal roles

THE TOOLS OF CO-CREATION

During the anticipatory stage, the students were invited to reflect upon the roles and responsibilities that they were likely to assume during the tasks. The deliverables were matrices which simply described their roles by means of a verb and their attitudes through an adjective, as well as the evaluation grids for each of the roles. All these elements constituted the material analyzed in this study. The idea was to compare the output of the students concerning their perception of leadership before and after the bivouac. The limitation of the verbs and adjectives was motivated by considerations of efficiency and recurrent observations of the writing capacities of the students over a very short period. If an additional day had been possible, the composition of complete descriptive texts would have been desirable. The analysis of the feedback by the authors is still underway. However, the first results are available 4 : they concern the preconceived ideas of the students about the roles they were to play during the bivouac. The initial data of the students contain 1146 verbs and 805 adjectives. Figure 3 and Figure 4 show the verbs and adjectives most frequently chosen by the students to describe these roles. If the capacities to listen and analyze a situation seem essential, the distribution of the verbs act, help, understand, lead, explain, as well as the adjectives suggest that they clearly identified with the roles that we wanted them to play (Head of Workshop , Team Member and Task Leader).

CONCLUSION AND FUTURE WORK

The feedback from the students, the teachers, the school's directors and our military hosts is very encouraging for a first experiment. They have encouraged us to go further and to make this a permanent event. In order to do so, we are analyzing the data that we have collected with the help of text-data-mining software. This software has enabled us to identify trends and perspectives to improve this activity. From the start, it would seem that the co-creation and the complementarity of the learning processes throughout our activity are key to its success. As Brougère and Ulmann (2009) remind us, there are traditionally two pedagogical approaches: learning

Figure 3 :Figure 4 :

 34 Figure 3: Frequency of the verbs chosen by the students to define their roles

A task is a challenge presented in the form of a problematic issue that the team must tackle. For example, one of them requires the team to coordinate to create a system out of paper designed to slow the fall of a live grenade, ready to explode at the slightest knock (represented by a raw egg) falling vertically from 2 meters; all in the strictest silence.

Indeed, our school trains a certain number of Ingénieurs En Techniques de l'Armement (IETA) (Arms Technologies Engineers) for the DGA (French Procurement Agency) who are thus military students.

43rd Annual SEFI Conference June 29 -July 2, 2015 Orléans, France

through transmission linked to teaching and learning through participation if more importance is given to the student's activity. Our activity relies on all that the teachers have transmitted to the students during the first four semesters of school. Furthermore, it fully encourages students to be co-players in their education, to participate in activities of co-creation and co-evaluation, thus endowing their leadership training with meaning: inspire, tempt, convince, guide, rather than threaten, proscribe and impose.

SUMMARY

This article presents a reflexive and co-created leadership skills activity, applied within the context of an engineering school. It consists in confronting the students with practical experience in leadership inducing cogitation and auto-evaluation. The co-created evaluation tools put in place by the teaching team are examined.