Michel Raynal

Julien Stainer

Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors

Keywords: asynchronous read/write model, decision task, distributed computability, failure detector, immediate snapshot object, iterated model, model equivalence, process crash, simulation, t-resilience, wait-freedom

The base distributed asynchronous read/write computation model is made up of n asynchronous processes which communicate by reading and writing atomic registers only. The distributed asynchronous iterated model is a more constrained model in which the processes execute an infinite number of rounds and communicate at each round with a new object called immediate snapshot object. Moreover, in both models up to n -1 processes may crash in an unexpected way. An important computability issue associated with these models concerns their respective computability power. When considering distributed computing problems whose main issue is to cope with asynchrony and failures called decision tasks (such as consensus, set agreement, etc.) two main results are associated with the previous models. The first states that these models are computationally equivalent for decision tasks. The second states that they are no longer equivalent when both are enriched with the same failure detector.

This paper shows how to capture failure detectors in each model in order both models become computationally equivalent. To that end it introduces the notion of a "strongly correct" process which appears particularly well-suited to the iterated model. It also presents simulations that proves the computational equivalence when both models are enriched with a failure detector. Interestingly, these simulations works for a large family of failure detector classes. The paper extends also the simulations to the case where the wait-freedom requirement is replaced by the notion of t-resilience. Last but not least, a noteworthy feature of the proposed approach lies in its simplicity.

Augmenter la puissance du calcul réparti itéré avec des détecteurs de fautes

Résumé : Les modèles de systèmes distribués asynchrones communicant par mémoire partagée sont équivalents, du point de vue de la calculabilité, au modèle itéré où les processus communiquent via une séquence d'objets write-snapshot. Cependant, il a été montré que l'utilisation naïve, dans le modèle itéré, des détecteurs de fautes définis pour la mémoire partagée n'apportait aucune puissance de calcul additionelle.

Cet article propose une méthode systématique pour porter les détecteurs de fautes du modèle classique communicant par mémoire partagée dans le modèle itéré, ceci en préservant les équivalences de modèles. Dans ce but, il introduit la notion de processus fortement corrects qui aide à décrire les possibilités de communication dans le modèle itéré.

L'article fournit des simulations génériques (ne dépendant pas ou peu du détecteur de faute) pour prouver les équivalences de modèles. Les cas de plusieurs détecteurs de fautes connus sont traités et le résultat est étendu au cas de la t-résilience. Enfin, un algorithme de consensus dans le modèle itéré augmenté du détecteur de faute correspondant à Ω illustre une des possibilités offertes par cette étude.

Mots clés : modèle asynchrone en mémoire partagée, calculabilité distribuée, détecteur de fautes, objet immediate-snapshot, modèle itéré, équivalence de modèles, défaillance de processus, simulation, t-résilience, sans attente

Introduction

Base read/write model and tasks The base asynchronous read/write (ARW) computation model consists of n asynchronous sequential processes that communicate only by reading and writing atomic registers. Moreover, any number of processes (but one) are allowed to crash in an unexpected way.

A decision task is the distributed analogous of the notion of a function encountered in sequential computing. Each process starts with its own input value (without knowing the input values of the other processes). The association of an input value with each process define an input vector of the task. Each process has to compute its own output value in such a way that the vector of output values satisfies a predefined input/output relation (this is the relation that defines the task). The most famous distributed task is the consensus task: each process proposes a value and processes have to decide the very same value which has to be one of the proposed values. The progress condition that is usually considered is called wait-freedom [START_REF] Herlihy | Wait-free synchronization[END_REF]. It requires that any process that does not crash eventually decides a value. It has been shown that the consensus task cannot be wait-free solved in the ARW model [START_REF] Loui | Memory requirements for for agreement among Unreliable Asynchronous processes[END_REF]. The tasks that can be wait-free solved in this base model are sometimes called trivial tasks.

The iterated immediate snapshot (IIS) model and its power The fact that, in the ARW model, a process can issue a read or write on any atomic register at any time makes difficult to analyze the set of runs that can be generated by the execution of an algorithm that solves a task in this model.

To make such analyses simpler and obtain a deeper understanding of the nature of asynchronous runs, Borowsky and Gafni have introduced the iterated immediate snapshot (IIS) model [START_REF] Borowsky | A simple algorithmically reasoned characterization of wait-free computations[END_REF]. In this model, each process (until it possibly crashes) executes asynchronously an infinite number of rounds and, in each round, processes communicate through a one-shot immediate snapshot object [START_REF] Borowsky | Immediate atomic snapshots and fast renaming[END_REF] associated with this round. Such an object provides the processes with a single operation denoted write_snapshot(). This operation allows the invoking process to deposit a value into the corresponding object and obtains a snapshot [START_REF] Afek | Atomic snapshots of shared memory[END_REF] of the values deposited into it. It is important to notice that each immediate snapshot object is accessed at most once by each process but can be simultaneously accessed by any number of processes.

A colorless decision task is a task such that any value decided by a process can be decided by any number of processes. The main result associated with the IIS model is the following one: A colorless decision task can be wait-free solved in the ARW model if and only if it can be wait-free solved in the IIS model. This result is due to Borowsky and Gafni [START_REF] Borowsky | A simple algorithmically reasoned characterization of wait-free computations[END_REF]. Said another way, the ARW model and the IIS model (which is more constrained as far as runs are concerned) have the same computational power for colorless decision tasks.

Enriching a model with a failure detector One way to enrich the base read/write model in order to obtain a stronger model consists in providing the processes with operations whose computational power in presence of asynchrony and process crashes is stronger than the one of the base read or write operations [START_REF] Herlihy | Wait-free synchronization[END_REF]. An example of such an operation is the compare&swap operation [START_REF] Herlihy | Wait-free synchronization[END_REF]. Another way to enrich the base read/write model consists in adding to it a failure detector [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF][START_REF] Raynal | Failure detectors for asynchronous distributed systems: an introduction[END_REF].

A failure detector is a device that provides each process with a read-only variable that gives it information on failures. According to the type and the quality of this information, several classes of failure detectors can be defined. As an example, a failure detector of the class Ω [START_REF] Chandra | The weakest failure detector for solving consensus[END_REF] provides each process p i with a read-only local variable denoted leader i that contains always a process identity. The property associated with these read-only local variables is the following: there is an unknown but finite time after which all the variables leader i contain forever the same identity and this identity is the one of a non-faulty process. A failure detector is non-trivial if it cannot be built in the base read/write model (i.e., if it enriches the system with additional power).

A natural question is then the following: Are the ARW model and the IIS model still equivalent for wait-free task solvability when they are enriched with the same non-trivial failure detector? It has been shown by Rajsbaum, Raynal and Travers that the answer to this question is "no" [START_REF] Rajsbaum | An impossibility about failure detectors in the iterated immediate snapshot model[END_REF]. It follows that, from a computability point of view, the ARW model enriched with a non-trivial failure detector is more powerful than the IIS model enriched with the same failure detector.

An approach aiming at introducing the power of failure detectors into the IIS model has been investigated in [START_REF] Cornejo | Failure Detectors as Schedulers (Brief Announcement)[END_REF][START_REF] Rajsbaum | The iterated restricted immediate snapshot model[END_REF]. This approach consists in requiring some property P to be satisfied by the successive invocations of write_snapshot() issued on the sequence of immediate snapshot objects. Hence the name iterated restricted immediate snapshot (IRIS) given to this model. For each failure detector class taken separately, this approach requires (a) to associate a specific property P with the considered failure detector class, (b) design an ad hoc simulation of the write_snapshot() operation suited to this failure detector class in order to simulate IIS in ARW and (c) design a specific simulation of the output of the failure detector to simulate ARW in IIS. Interestingly, this approach was the first to show that failure detectors are related to fairness and can be considered as schedulers (see also [START_REF] Pike | Failure detectors encapsulate fairness[END_REF]).

Content of the paper

Let C be a failure detector class defined in the context of the base ARW model. This paper is motivated by the following question: Is it possible to associate with C (in a systematic way) a failure detector class C * such that the ARW model enriched with C and the IIS model enriched with C * are equivalent for wait-free task solvability? To answer that question, the paper considers failure detector classes whose output eventually involves (a) at least one non-faulty process and possibly faulty processes (such as Ω k ) or (b) only non-faulty processes (such as P , Σ, ✸P or ✸S x ). The contributions of the paper are the following.

• The answer to the previous question is based on a simple modification of the definition of what is a correct process (i.e., a process that does not crash in a run of the base read/write model). The notion of a correct process is replaced in the IIS model by what we call a strongly correct process. Such a process is a process that does not crash and whose all invocations of write_snapshot() are seen (directly or indirectly) by all other non-crashed processes 1 .

Given this definition, and a failure detector class C designed for the ARW model, its IIS counterpart C * is obtained by a simple and systematic replacement of the words "correct process(es)" by "strongly correct process(es)" in the definition of C. • An immediate benefit of the previous definition is the fact that, when we want to simulate the ARW model in the IIS model, we can directly benefit from the simulation of the read and write operations defined in [START_REF] Borowsky | A simple algorithmically reasoned characterization of wait-free computations[END_REF] by Borowsky and Gafni. The only addition to that simulation that has to be done concerns the local outputs of the corresponding failure detector C. • Given the ARW model enriched with a failure detector class C, the paper presents a generic simulation of the IIS model enriched with C * . This simulation is generic in the sense that it works for any of the previously cited failure detectors. The simulation algorithm has only to be instantiated with a predicate associated with the corresponding failure detector C. • An interesting consequence of the fact that, given a failure detector class C, we have "for free" a corresponding failure detector for the IIS model, not only makes simpler the understanding of IIS enriched with a failure detector but allows for relatively easy proofs.

• The paper also generalizes the previous wait-free simulations to t-resilient simulations (let us remind that, in a system of n processes, wait-freedom is (n -1)-resilience).

Among other benefits, an important corollary result of the paper is the fact that if C is the weakest failure detector to solve a given task T in the base read/write model [START_REF] Delporte-Gallet | The weakest failure detectors to solve certain fundamental problems in distributed computing[END_REF], it follows from the previous simulations that (when considering all failure detector classes D * obtained from a detector class D designed for the read/write model) C * is the weakest failure detector to solve T in the IIS model and vice-versa.

Let ARW n [C] denote the base asynchronous read/write model with n processes enriched with a failure detector of the class C and IIS n [C * ] denote the IIS model enriched with the corresponding failure detector C * . The wait-free simulations presented in the paper are summarized in Figure 1.

Section 4

ARW n [C] IIS n [C * ]
[4] and Section 3 Roadmap The paper is made up of 6 sections. Section 2 introduces the IIS model and failure detectors. Section 3 provides simulations from the iterated immediate snapshot model enriched with a failure detector to the read/write model while Section 4 provides simulations in the other direction. Section 5 considers the t-resilience case (instead of wait-freedom). Finally, Section 6 concludes the paper. (For completeness, an Ω-based consensus algorithm suited to the IIS model is described in an appendix).

Base definitions

Notation Shared objects are denoted with uppercase letters. Local variables are denoted with lowercase letters (the index of the corresponding process is sometimes used as a subscript of a local variable).

Process model

In the rest of the paper, the n asynchronous and sequential processes are denoted p 1 , ..., p n ; i is called the index of p i . Moreover, any number of processes may crash (stop executing). A process that crashes in a run is said to be faulty in that run, otherwise it is correct in the corresponding run. A correct process executes an infinite number of steps. Given an execution, let C denote the set of processes that are correct in that execution and F the set of the faulty ones.

Decision tasks

A decision task is a one-shot decision problem specified in terms of an input/output relation ∆. Each process starts with a private input value and must eventually decide on a private output value. From a global observer point of view, an input vector I[1.

.n] specifies the input I[i] = v i of each process p i . Similarly, an output vector O[1.

.n] specifies a decision value O[j] for each process p j . A task is defined by a set of input vectors and a relation ∆ that describes which output vectors are correct for each input vector I. More precisely, for each valid input vector I, the values decided by the processes are such that there is an output vector O ∈ ∆(I) such that, for each j, O[j] is the value decided by p j and, if no value is decided by p j , it is because p j has crashed during the computation.

Base read/write model

This model, denoted ARW n [∅] in the following, has been presented in the introduction. Instead of atomic read/write registers, we consider here that the processes communicate through snapshot objects [START_REF] Afek | Atomic snapshots of shared memory[END_REF]. This is at no additional computability cost as the operations on a snapshot object can be wait-free implemented from single-writer/multi-reader atomic read/write registers. Given a snapshot object S, these operations are denoted S.write() and S.snapshot().

S is initially empty. When p i invokes S.write(v), it adds the pair i, v to S and suppresses the previous pair i,if any. When it invokes S.snapshot(), p i obtains a set containing all the pairs k, v k currently contained in S. Such a set is called a view that we denote arw_view i .

A snapshot object S is atomic (we also say said that it is linearizable [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF]). This means that each operation invocation appears as if it has been executed at a single point of the time line between its start event and its end event in such a way that no two invocations are associated with the same point of the time line. The corresponding total order is called a linearization.

The iterated immediate snapshot model

One-shot immediate snapshot object Basically, such an object is similar to a snapshot object where the write() and S.snapshot() operations are encapsulated into a single operation denoted write_snapshot() (where the write is executed just before the snapshot). Moreover, one-shot means that, given an object, each process invokes write_snapshot() at most once.

If several processes invoke concurrently IS .write_snapshot(), their write operations are executed concurrently followed by a concurrent execution of their snapshot operations. The invocations of IS .write_snapshot() are not linearizable but set-linearizable [START_REF] Neiger | Set Linearizability. Brief Announcement[END_REF]. This is similar to atomicity except that the same point of the time line can be associated with several concurrent invocations of IS .write_snapshot().

Let us consider a process p i that invokes IS .write_snapshot(v i ) where v i is the value it wants to write into IS . When it returns from its invocation, p i obtains a view of the object that we denote iis_view i , Moreover, let us define iis_view i = ∅ if p i never invokes IS .write_snapshot(). A one-shot immediate snapshot object is defined by the following properties associated with the views obtained by the processes.

• Self-inclusion. ∀ i : i, v i ∈ iis_view i . • Containment. ∀ i, j : (iis_view i ⊆ iis_view j ) ∨ (iis_view j ⊆ iis_view i ). • Immediacy. ∀ i, j : ( i, v i ∈ iis_view j ) ⇒ (iis_view i ⊆ iis_view j ).
The first property states that a process sees its write. The second property states that the views are totally ordered by containment. The third property states that, when a process invokes IS .write_snapshot(), its snapshot is scheduled just after its write. This last property can be re-written as follows: ∀ i, j

: ( i, v i ∈ iis_view j ) ∧ ( j, v j ∈ iis_view i ) ⇒ (iis_view j = iis_view i ) (which means that concurrent invocations of IS .write_snapshot() obtain the same view).
The operation write_snapshot() can be wait-free implemented from atomic read/write registers (i.e., in the base read/write model (e.g., [START_REF] Borowsky | Immediate atomic snapshots and fast renaming[END_REF][START_REF] Castañeda | The renaming problem in shared memory systems: an introduction[END_REF]). Hence, it does not add computational power to the read/write model.

The iterated immediate snapshot model In the base IIS model (denoted IIS n [∅]), the shared memory is made up of an infinite number of immediate snapshot objects IS [START_REF] Afek | Atomic snapshots of shared memory[END_REF], IS [2], ... These objects are accessed sequentially and asynchronously by the processes according to the following round-based pattern executed by each process p i . The variable r i is local to p i and denotes its the current round number. r i ← 0; ℓs i ← initial local state of p i (including its input, if any); repeat forever (asynchronous IIS rounds)

r i ← r i + 1; iis_view i ← IS [r i ].write_snapshot(ℓs i ); computation of a new local state ℓs i (which contains iis_view i ) end repeat.
It is easy to see that the runs of an algorithm in IIS n [∅] are more structured than runs in ARW n [∅]. As indicated in the Introduction, the most important result associated with this model, which is due to Borowsky and Gafni, states that the ARW n [∅] and IIS n [∅] models have the same computability power for colorless wait-free decision tasks [START_REF] Borowsky | A simple algorithmically reasoned characterization of wait-free computations[END_REF].

Full information algorithm

As the aim of the IIS model is to address computability issues (and not efficiency), we consider full information algorithms for this computation model. This means that, at each round r, a process p i writes its current local state ℓs i into IS [r]. Consequently, the view it obtains from its invocation IS [r].write_snapshot(ℓs i ) contains all its causal past (hence the name full information). More precisely, for any k and any x, let ℓs k [x] be the local state of process p k at beginning of the round x. "Full information" means that, if j, ℓs j [r] belongs to the view obtained by p i during round r, then ℓs j [r] is part of ℓs i [r + 1] (let us observe that this definition is recursive).

Failure detectors

A failure detector is a device that provides processes with information on failures [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. As already said in the introduction, several classes of failure detectors can be defined according to the type and the quality of the information given to the processes. We consider here that the information given to each process is a set of process indexes. This information is given by a failure detector to a process through a local read-only variable.

Classes of failure detectors that eventually output only correct processes We consider three classes of such failure detectors: the classes P of perfect failure detectors and ✸P of eventually perfect failure detectors (defined in [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]) and the class Σ of quorum failure detectors (defined in [START_REF] Delporte-Gallet | The weakest failure detectors to solve certain fundamental problems in distributed computing[END_REF]).

• A failure detector of the class P provides each process p i with a set trusted i that, at any time τ , contains all the processes that have not crashed by time τ and eventually contains only correct processes.2 • The class ✸P is weaker than the class P . Namely, there is an arbitrary long finite period during which the sets trusted i can contain arbitrary values and when this period terminates a failure detector of ✸P behaves as a failure detector of P . • A failure detector of the class Σ provides each process p i with a set qr i that eventually contains only correct processes and is such that the value of qr i at any time τ and the value of any qr j at any time τ ′ have a non-empty intersection.

Classes of failure detectors that eventually output correct and possibly faulty processes We consider here the class of eventual leaders failure detectors denoted Ω k which has been proposed in [START_REF] Neiger | Failure detectors and the wait-free hierarchy[END_REF]. This class class is a straightforward generalization of the failure detector class Ω introduced in [START_REF] Chandra | The weakest failure detector for solving consensus[END_REF]. Actually, Ω 1 is Ω which has been shown to be the weakest failure detector class for solving the consensus task in shared memory systems [START_REF] Chandra | The weakest failure detector for solving consensus[END_REF][START_REF] Lo | Using failure detectors to solve consensus in asynchronous shared-memory systems[END_REF]. A failure detector of the class Ω k provides each process p i with a read-only local variable leaders i that always contains k process indexes and satisfies the following property.

• The local variables leaders i offered by a failure detector of the class Ω k are such that, after some unknown but finite time τ , they all contain forever the same set of k process indexes and at at least one of these indexes is the one of a correct process.

Let us notice that, before time τ , the sets leaders i can contain arbitrarily changing sets of k process indexes.

Strongly correct processes (wrt the IIS model)

Motivation When considering the base read/write model, if a process issues a write into a snapshot object S, the value it has written can be read by any process that invokes S.snapshot(). This is no longer the case in the IIS model. As an example, let us consider an IIS execution in which, at any round r, the very same process p x is always the first to invoke IS [r].write_snapshot(ℓs x ) and this invocation is not concurrent with any other invocation of IS [r].write_snapshot(). If follows that, at each round r, view x contains only the pair x, ℓs x . Hence, p ℓ never sees values written by other processes.

The previous observation motivates the definition of a strongly correct process. Such a process is a process whose writes into the immediate snapshot objects are seen (directly or indirectly) infinitely often by the all correct processes. A process that is not strongly correct is consequently a process such that only a finite number of its writes into immediate snapshot objects are eventually propagated to all the correct processes.

Formal definition Let iis_view j [r] be the view obtained by p j at round r. Let SC 0 be the set defined as follows (let us remember that C denotes the set of correct processes):

SC 0 def = { i such that |{r such that ∀ j ∈ C : ∃ i, -∈ iis_view j [r]}| = ∞ },
i.e., SC 0 is the set of processes that have issued an infinite sequence of (not necessarily consecutive) invocations of write_snapshot() and these invocations have been seen by each correct process (this is because these invocations are set-linearized in the first position when considering the corresponding one-shot immediate snapshot objects).

Let us observe that, as soon as we assume that there is at least one correct process, it follows from the fact that the number of processes is bounded that |SC 0 | = 0. Given k > 0 let us recursively define SC k as follows:

SC k def = { i such that |{r such that ∃ j ∈ SC k-1 : ∃ i, -∈ iis_view j [r]}| = ∞ }.
Hence, SC k contains all the correct processes that have issued an infinite sequence of (not necessarily consecutive) invocations of write_snapshot() which have been seen by at least one process of SC k-1 . It follows from the self-inclusion property of the views and the definition of SC k that SC 0 ⊆ SC 1 ⊆ • • • . Moreover, as all the sets are included in {1, . . . , n}, there is some K such that

SC 0 ⊆ SC 1 ⊆ • • • ⊆ SC K = SC K+1 = SC K+2 = • • • .
SC K defines the set of of strongly correct processes which is denoted SC. This is the set of processes that have issued an infinite sequence of (not necessarily consecutive) invocations of write_snapshot() which have been propagated to all the correct processes.

IIS enriched with a failure detector Let C be a failure detector class. C * denotes the same failure detector class where the word "correct" is replaced by the word "strongly correct". Moreover, IIS n [C * ] denotes the IIS model enriched with a failure detector of the class C * where, during each round r, a process p i reads its failure detector variable at the beginning of round r and saves its value fd i in its local state ℓs i before writing it into IS [r].

3 From IIS n [C * ] to ARW n [C]
This section describes a simulation in IIS n [C * ] of a run of an algorithm designed for ARW n [C]. Except for the simulation of the detector output, this simulation is from [START_REF] Borowsky | A simple algorithmically reasoned characterization of wait-free computations[END_REF]. In order not to confuse a simulated process in ARW n [C] and its simulator in IIS n [C * ], the first one is denoted p i while the second one is denoted q i .

Description of the simulation

It is assumed, without loss of generality, that the simulated processes communicate through a single snapshot object S. A simulator q i is associated with each simulated process p i . It locally executes the code of p i and uses the algorithms described in Figure 2 when p i invokes S.write(-), S.snapshot() or queries the failure detector.

Immediate snapshot objects of IIS n [C * ] These objects are denoted IS [START_REF] Afek | Atomic snapshots of shared memory[END_REF], IS [START_REF] Anceaume | A necessary and sufficient condition for transforming limited accuracy failure detectors[END_REF], ... Each object IS [r] stores a set of triples (this set is denoted ops i in Figure 2). If the triple (j, sn, x) ∈ ops i , then the simulator q i knows that the process p j (simulated by q j ) has issued its sn-th invocation of an operation on the simulated snapshot object S; x = ⊥ means that this invocation is S.write(x) while x = ⊥ means that it is S.snapshot().

Local variables of a simulator q i The variable r i contains the current round number of the simulator q i . It is increased before each invocation of IS n [r i ].write_snapshot(ops i ) (line 3). As this is the only place where, during a round, a simulator invokes the operation write_snapshot(), the simulators obey the IIS model.

The local variable sn i is a sequence number that measures the progress of the simulation by q i of the process p i . It is increased at line 1 when p i starts simulating a new invocation of S.write() or S.snapshot() on behalf on p i .

As already indicated, the local variable ops i contains the triples associated with all the invocations of S.write() and S.snapshot() that have been issued by the processes and are currently known by the simulator q i . This local variable (which can only grow) is updated at line 1 when q i starts simulating the next operation S.write() or S.snapshot() issued by p i or at line 4 when q i learns operations on the snapshot object S issued by other processes.

The local variable iis_view i stores the value returned by the last invocation of IS [r i ].write_snapshot() issued by the simulator q i (line 3). When simulating an invocation of S.snapshot() issued by p i , q i computes for each simulated process p j the sequence number max_snj i (line 12) of the last value it knows (saved in v_snj i at line 13) that has been written by p j in the snapshot object S. This allows q i to compute the view arw_view i (line 14) that it returns (line 17) as the result of the invocation of S.snapshot() issued by p i .

The local variable fd i is used to store the last value obtained by the simulator q i from its read-only local failure detector variable denoted C * .read().

Init: ops i ← ∅; r i ← 0; sn i ← 0; iis_view i ← ∅; fd i ← C * .read(). internal operation publicize&progress (x) is (1) sn i ← sn i + 1; ops i ← ops i ∪ {(i, sn i , x)}; (2) repeat r i ← r i + 1; fd i ← C * .read(); (3) iis_view i ← IS [r i ].write_snapshot(ops i ); (4) ops i ← k,ops k ∈iis_view i ops k (5) until (i, sn i , x) ∈ k,ops k ∈iis_view i ops k end repeat; (6) return(). operation S.write(v) is (7) publicize&progress (v); return(). operation S.snapshot() is (8) publicize&progress (⊥); (9) arw_view i ← ∅; (10) for each j in {1, . . . , n} do (11) if ∃v | (j, -, v) k,ops k ∈iis_view i ops k ∧ v = ⊥ (12) then max_snj i ← max{sn | (j, sn, v) ∈ k,ops k ∈iis_view i ops k ∧ v = ⊥}; (13) vj i ← v such that (j, max_snj i , v) ∈ ops i ; (14) arw_view i ← arw_view i ∪ { j, vj i } (15) end if (16) end for; (17) return (arw_view i ). operation C.read() is return (fd i ). Figure 2: Simulation of ARW n [C] in IIS n [C * ]
: code for a simulator q i (extended from [START_REF] Borowsky | A simple algorithmically reasoned characterization of wait-free computations[END_REF]) Simulation of S.write(v) To simulate the invocation of S.write(v) issued by p i , the simulator q i invokes the internal operation publicize&progress(v). It first increments sn i and adds the triple (i, sn i , v) to ops i (line 1). Then, it repeatedly invokes write_snapshot(ops i ) on successive immediate snapshot objects and enriches its set of triples ops i (lines 2-4) until it obtains a view iis_view i in which all the simulators it sees in that view are aware of the invocation of the operation S.write(v) that it is simulating (line 6).

Simulation of S.snapshot()

To simulate an invocation of S.snapshot() issued by p i , the simulator q i first invokes publicize&progress(⊥). When this invocation terminates, q i knows that all the simulators it sees in the last view iis_view i it has obtained are aware of its invocation of S.snapshot(). Moreover, as we have seen, the execution of publicize&progress(⊥) makes q i aware of operations simulated by other simulators.

Then the simulator q i browses all the operations it is aware of in order to extract, for each simulated process p j , the last value effectively written by p j (lines [START_REF] Delporte-Gallet | The weakest failure detectors to solve certain fundamental problems in distributed computing[END_REF][START_REF] Gafni | Distributed Programming with Tasks[END_REF][START_REF] Herlihy | Wait-free synchronization[END_REF][START_REF] Herlihy | The topological structure of asynchronous computability[END_REF][START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF][START_REF] Lo | Using failure detectors to solve consensus in asynchronous shared-memory systems[END_REF][START_REF] Loui | Memory requirements for for agreement among Unreliable Asynchronous processes[END_REF]. This (non-⊥) value is extracted from the triple with the largest sequence number among all those that appear in all the sets ops k that belong to the view iis_view i returned to q i by its last invocation of write_snapshot().

Simulation of C.read() When a process p i reads its local failure detector output, the simulator q i simply returns it the current value of fd i .

From strongly correct simulators to correct simulated processes

Strongly correct vs weakly correct simulators Let WC = C \SC (the set of weakly correct simulators). It follows from the definition of the strongly correct simulators that, for any simulated process p i whose simulator q i is such that i ∈ WC, there is a round rmin i such that, ∀j ∈ SC, ∀r ≥ rmin i : i, -/ ∈ iis_view j [r], which means that, for r ≥ rmin i , no invocation IS [r].write_snapshot() issued by the simulator q i is seen by a strongly correct simulator.

This means that, after rmax = max{rmin i } i∈WC and after all simulator crashes have occurred, the invocations of write_snapshot() by the simulators of SC are always set-linearized strictly before the ones of the simulators of WC. Said differently, there is a round after which no strongly correct simulator ever receives information from a weakly correct simulator. From the point of view of a strongly correct simulator, any weakly correct simulator appears as a crashed simulator. Differently, any weakly correct simulator receives forever information from all the strongly correct simulators 3 .

Crashed and slow IIS simulators simulate crashed ARW processes An important feature of the simulation described in Figure 2 is that, not only the crash of a simulator q i gives rise to the crash of the associated simulated process p i , but a slow simulator q j entails the crash of its simulated process p j .

As an example, let us consider a correct simulator q j which, at any round r, is always strictly the last simulator which invokes IS [r].write_snapshot(). It follows that no other simulator is ever informed of the operations S.write() and S.snapshot() issued by the process p j simulated by q j . When the simulator q j executes line 3, it is informed of the operations issued by the strongly correct simulators q i on the behalf of the processes they simulate but, as the operation of p j it is simulating (which is encoded in the triple (j, sn j , x)) is never known by the other simulators, it follows that q j loops forever in the repeat loop (lines 2-5). Hence, the simulation of p j does not longer progress and p j is considered as a crashed process in the simulated ARW model. This means that the simulation described in Figure 2 guarantees wait-freedom for the processes simulated by the strongly correct simulators only.

To summarize When simulating ARW n [C] on top of IIS n [C * ], we have the following: (a) a faulty or weakly correct simulator q i gives rise to a faulty simulated process p i and (b) a strongly correct process gives rise to a correct simulated process

p i in ARW n [C].
The next theorem captures the previous discussion. As it is a simple formalization of this discussion, its proof is given only in Appendix A.

Theorem 1 Let A be an algorithm solving a colorless task in the ARW n [C] model. Let us consider an execution of A simulated in the IIS n [C * ] model by the algorithms S.write(), S.snapshot() and C.read() described in Figure 2. A process p i is correct in the simulated execution if and only if its simulator q i is strongly correct in the simulation.

4 From ARW n [C] to IIS n [C * ]
This section presents a generic simulation of

IIS n [C * ] in ARW n [C].
Its generic dimension lies in the fact that C can be any failure detector class cited in the Introduction and defined in Section 2.5 (namely, P , Σ, ✸P , Ω, Ω k , Ω k and others such as S, ✸S [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF] and ✸S x [START_REF] Anceaume | A necessary and sufficient condition for transforming limited accuracy failure detectors[END_REF]). As far terminology is concerned, q i is used to denote a simulated IIS process while p i is used to denote the corresponding ARW simulator process. The simulation is described in Figure 3. Differently from the simulation described in Figure 2, the algorithms of Figure 3 are not required to be full-information algorithms.

Description of the simulation

The simulated model IS [START_REF] Afek | Atomic snapshots of shared memory[END_REF], IS [START_REF] Anceaume | A necessary and sufficient condition for transforming limited accuracy failure detectors[END_REF], ... denote the infinite sequence of one-shot immediate snapshot objects of the simulated IIS model. Hence, a simulated process q i invokes IS [r].write_snapshot() and C * .read(). Each object S[r] can be accessed by two operations denoted collect() and arw_write_snapshot(). The later is nothing else than the operation write_snapshot() (which satisfies the self-inclusion, containment and immediacy properties defined in Section 2.4). It is prefixed by "arw" in order not to be confused with the operation of the IIS model that it helps simulate. The operation collect() is similar to the operation snapshot(), except that it is not required to be atomic. It consists in an asynchronous scan of the corresponding S[r] object which returns the set of pairs it has seen in S[r]. Both collect() and arw_write_snapshot() can be wait-free implemented in ARW n [∅] (an implementation of arw_write_snapshot() is described in Appendix B).

Shared objects of the simulation

FD _VAL is an array of single-writer/multi-reader atomic registers. The simulator p i stores in the register FD _VAL[i] the last value it has read from its local failure detector variable which is denoted C.read(). This comes from the fact that, in all executions, we need to guarantee a correct association between the schedule of the (simulated) invocations of IS[r].write_snapshot() and the outputs of the simulated failure detector C * . This, which depends on the output of the underlying failure detector C, requires to appropriately synchronize, at every round r, the simulation of the invocations of IS[r].write_snapshot(). Once, this is done, the set-linearization of the simulated invocations of IS[r].write_snapshot() follows from the set-linearization of these invocations in the ARW n [C] model.

operation IS [r].write_snapshot(v) is (1) if (r mod n) + 1 = i (2) then repeat arw _view i ← S[r].collect(); FD_VAL[i] ← C.read() (3) until PROP C (arw _view i ) end repeat (4) else FD_VAL[i] ← C.read() (5) end if; (6) iis_view ← S[r].arw_write_snapshot(v); (7) return (iis_view ). operation C * .read() is return (FD_VAL[i]).
Associate each round with a simulator The simulation associates each round r with a simulator (we say that the corresponding simulator "owns" round r) in such a way that each correct simulator owns an infinite number of rounds. This is implemented with a simple round-robin technique (line 1).

Simulation of IS [r].write_snapshot(v)

To simulate an invocation IS[r].write_snapshot(v) issued by the simulated process q i , the simulator p i first checks if it is the owner of the corresponding round r. If it is not, it refreshes the value of FD _VAL[i] (line 4) and executes the "common part", namely, it invokes S[r].arw_write_snapshot(v) (line 6) which returns it a set iis_view that constitutes the result of the invocation of IS[r].write_snapshot(v).

If the simulator p i is the owner of the round, it repeatedly reads asynchronously the current value of the implementation object S[r] (that it stores in arw_view i ) and refreshes the value of FD _VAL[i] (line 2). This repeat statement terminates when the values of arw_view i it has obtained satisfy some predicate (line 3). This predicate, denoted PROP C (), which depends on the failure detector class C, encapsulates the generic dimension of the simulation. Then, after it has exited the loop, the simulator p i executes the "common" part, i.e., lines 6-7. It invokes S[r].arw_write_snapshot(v) which provides it with a view iis_view which is returned as the result of the invocation of IS[r].write_snapshot(v).

The fact that, during each round, (a) some code is executed only by the simulator that owns r, (b) some code is executed only by the other simulators and (c) some code is executed by all simulators, realizes the synchronization discussed above that allows for a correct set-linearization of the invocations of IS

[r].write_snapshot() in IIS n [C * ].
Simulation of C * .read() When a simulated process q i wants to read its local failure detector output, its simulator p i returns it the last value it has read from its local failure detector variable.

To summarize When simulating IIS n [C * ] on top of ARW n [C], we have the following: (a) a faulty simulator p i gives rise to a faulty simulated process q i and (b) a correct simulator p i gives rise either to a strongly correct, a weakly correct or a faulty simulated process q i in IIS n [C * ] (this can depend on PROP C ()).

Moreover, whatever C, we have to show that there is at least one correct process in IIS n [C * ]. This amounts to show that there is a simulator p i that executes the infinite sequence {IS [r].write_snapshot()} r≥1 . To that end, we have to show that each object IS [r] is non-blocking [START_REF] Herlihy | Wait-free synchronization[END_REF] (i.e., whatever the round r and the concurrency pattern, at least one invocation of IS [r].write_snapshot() terminates). The corresponding proof is given when we consider specific failure detector classes (see below). Then, due to the structure of the IIS model, the very existence of at least one correct process in IIS n [C * ] entails the existence of at least one strongly correct process in this model (see the definition of the set SC in Section 2.6).

Instantiating the simulation with C = Ω k

When C = Ω k , the property PROP C (arw _view ) can be instantiated at each simulator p i as follows:

PROP Ω k (arw _view i ) = ∃ ℓ ∈ FD _VAL[i] : (ℓ = i ∨ ∃ ℓ, -∈ arw_view i ) .
Let leaders i = FD _VAL[i] (the last value of Ω k read by the simulator p i ). The previous predicate directs the simulator p i , at each round r it owns, to wait until i ∈ leaders i or until it has seen the simulation of IS [r].write_snasphot() issued by a simulator q j such that j ∈ leaders i . Proof The proof has to show that: (a) there is at least one correct process in IIS n [Ω * k ] (consequently, as we have seen previously, there is a strongly correct process in IIS n [Ω * k ]); (b) there is a one-to-one correspondence between correct simulators (p i ) and correct simulated processes (q i ); (c) the behavior of the local failure detector variables of the processes in IIS n [Ω * k ] is the one defined by Ω * k ;

and, for any round r, (d) the invocations of IS [r].write_snapshot() satisfy the self-inclusion, containment, and immediacy properties (defined in Section 2.4).

Proof of (a). As (by definition) one of the leaders eventually output by Ω k is a correct simulator p i , there is a finite time τ after which the predicate PROP Ω k returns always true when evaluated by the simulator p i . Hence, this simulator can never be blocked forever at line 3 when it executes (on behalf of the simulated process q i ) the algorithm implementing the operation IS [r].write_snapshot(). It follows from this observation that there is at least one correct simulated process q i . Proof of (b). The correct simulator p i which eventually belongs forever to the output of Ω k invokes arw_write_snapshot(v) at each simulated round r (line 6). Let τ r be the finite time instant at which this invocation terminates. As there is a finite time τ ′ ≥ τ after which i belongs to all the failure detector outputs, it follows that, at some finite time τ ′′ ≥ max(τ ′ , τ r ), the evaluation of PROP Ω k by any correct simulator returns true at round r. Hence that any correct simulator terminates its simulation of IS [r].write_snapshot(). As this is true for any round r, any correct simulator simulates an infinite number of rounds of the IIS model. Consequently, if a simulator p j is correct in ARW n [Ω * k ] the associated simulated process q j is correct in IIS n [Ω * k ] (which entails that, at any round r, the simulation of the operation IS [r].write_snapshot() is wait-free). Finally, a faulty simulator p i trivially gives rise to a faulty simulated process q i which concludes the proof of Item (b).

Proof of (c). To show that the behavior of the local failure detector variables at each simulated process q x is the one defined by Ω * k , let us first observe that, it follows directly from lines 2 and 4 that the outputs of Ω * k are outputs of Ω k . Hence, we have only to show that, after some time, Ω k outputs forever a set L such that there is a simulator p i with i ∈ L ∩ C (let us remember that C is the set of correct simulators) and the simulated process q i associated with the simulator p i is strongly correct.

Let r be a round such that all the faulty simulators have crashed before r and, after r, all correct simulators obtain forever the same set of leaders L from Ω k . Due to PROP Ω k , in all rounds r ′ ≥ r, each correct simulator p j , j / ∈ L, has to wait (at each round it owns) until a correct simulator p i , i ∈ L, has written into S[r ′ ] (execution of S[r ′ ].arw_write_snapshot() by p i at line 6 and execution of S[r ′ ].collect() by p j at line 2). It follows that, in the simulated system, the invocation of IS [r ′ ].write_snapshot() issued by any simulated process q j , j / ∈ L, is set-linearized after the invocation of IS [r ′ ].write_snapshot() issued by a simulated process p i such that i ∈ L.

Let q j be a strongly correct simulated process (since there are some correct simulated processes, there is at least one strongly correct one). As q j executes an infinite number of rounds and 1 ≤ |L ∩ C| ≤ k, it follows that there is a correct simulated process q ℓ such that ℓ ∈ L ∩ C and there is an infinite number of rounds r ′′ such that the invocation of IS [r ′′ ].write_snapshot() issued by q j is set-linearized after the one of q ℓ . It follows that q ℓ is a (simulated process which) is strongly correct. 4Proof of (d). The fact that, at any round r, the invocations of IS [r].write_snapshot() satisfy the self-inclusion, containment and immediacy properties follow directly (as already indicated) from the fact that invocations of the underlying operation S[r].arw_write_snapshot() satisfy these properties.

✷ T heorem 2

The following corollary is an immediate consequence of the previous theorem.

Corollary 1 A colorless task T is solvable in ARW n [Ω k ] iff it is solvable in IIS n [Ω * k ].

Instantiating the simulation with C = ✸P

The failure detector class C = ✸P When C = ✸P , the property PROP ✸P (arw _view ) can be instantiated at each simulator p i as follows:

PROP ✸P (arw _view i ) = ∀ j ∈ FD _VAL[i] : (j = i ∨ j, -∈ arw_view i ) .
This property forces the corresponding simulator p i , at each round r it owns, to wait until all the simulators p j that it currently trusts (i.e., any j ∈ fd _val i (i)) have invoked S[r].arw_write_snapshot() (i.e., have written a pair j,into S[r]). Proof The proof is similar to the previous one. We show here only that each correct simulator p i gives rise to a strongly correct (simulated) process q i .

The proof is by contradiction. Let us suppose that a correct simulator loops forever in the repeat (lines 2-3) when it executes the algorithm simulating IS [r].write_snapshot(). Let r denote the first round during which this happens and let p i be the simulator that owns this round (hence, p i is the first simulator that loops forever).

Let us notice that, as i = (r mod n) + 1, it is the only simulator which loops at round r. Hence, all other correct simulators eventually invoke S[r].arw_write_snapshot() at line 6 and consequently return from their simulation of IS [r].write_snapshot().

As the failure detector ✸P eventually outputs a set including only correct simulators, the evaluation of the predicate PROP ✸P (r, -, -) eventually returns true to p i which terminates its simulation of IS [r].write_snapshot(). A contradiction. It follows from this contradiction that every correct simulator executes an infinite number of rounds, which means that, at any round r, the implementation of the operation IS [r].write_snapshot() is wait-free.

Finally, as, at each round it owns, each correct simulator p i waits for all other correct simulators, each correct simulator sees the simulation of IS [r].write_snapshot() by the other correct simulators infinitely often. Hence, each correct simulator p i simulates a strongly correct process q i . ✷ T heorem 3

4.4 Instantiating the simulation with C = P, Σ, S, ✸S, S x , ✸S x

The same predicate PROP C as the one used for ✸P works for these failure detector classes.

The failure detector classes C = P, Σ, S, ✸S The previous proof can be easily translated for the the failure detector classes C = P, Σ, S, ✸S. This follows from the observation that, as ✸P , each of these failure detector classes permanently (C = P ) or eventually (C = Σ, S, ✸S) output only sets of correct processes.

The failure detector classes C = S x , ✸S x These failure detector classes (introduced in [START_REF] Anceaume | A necessary and sufficient condition for transforming limited accuracy failure detectors[END_REF]) extend the classes S and ✸S. Intuitively, they restrict the properties defining S and ✸S to be only on a dynamically determined subset of processes Q such that |Q| = x (hence their name: limited scope failure detector classes). It is possible to show that the algorithms of Figure 3 instantiated with the previous predicate PROP ✸P () allows for a correct simulation of

IIS n [C * ] in ARW n [C] for C = S x , ✸S x .
Let us also remark that, for any r, the simulation of the operation IS [r].write_snapshot() is wait-free (each simulated process q i whose simulator p i is correct executes an infinite number of IIS rounds). However, while each correct simulator simulates a strongly correct process when C ∈ {P, ✸P }, no conclusion can be drawn from the number of strongly correct simulated processes (except that there is at least one) when C ∈ {Σ, S x , ✸S x }. From IIS n,t [C * ] to ARW n,t [C] Theorem 1 has shown that the simulation described in Figure 2 (which is a simple extension to failure detectors of the simulation described in [START_REF] Borowsky | A simple algorithmically reasoned characterization of wait-free computations[END_REF]) ensures that (a) any strongly correct simulator in IIS gives rise to a correct simulated process in ARW and (b) a weakly or faulty simulator gives rise to a faulty simulated process. It follows that if |SC| ≥ nt in IIS n,t [C * ] we have at most t faulty process in the simulated system ARW n,t [C].

From ARW n,t [C] to IIS n,t [C * ] In this direction, the simulation from ARW n [C] in IIS n [C * ] presented in Figure 3 can be easily adapted in order to simulate ARW n,t [C] in IIS n,t [C * ].
It is indeed sufficient to replace PROP C by PROP C ∧ |arw _view i | ≥ (nt -1) (it is of course assumed that we do not have |arw _view i | ≥ (nt -1) ⇒ ¬ PROP C ). In this way, at every round r it owns, each correct simulator p i is constrained to wait until at least nt -1 processes have invoked S[r].arw_write_snapshot() before being allowed to invoke its own. The correction of this extended simulation is captured in the following theorem. Proof The proof consists in showing that (a) each correct simulator that would simulate an infinite number of IIS rounds when considering only PROP C does simulate an infinite number of rounds when considering PROP C ∧ (arw _view i ≥ nt -1); and (b) there is at least (nt) strongly correct processes in the simulated IIS model.

Proof of (a). The proof by contradiction. Let us suppose that a correct simulator p i that, at some round r, blocks forever because the predicate (arw _view i ≥ nt -1) is never satisfied. Let r be the first round at which this occurs. By assumption, at least nt -1 simulators p j eventually invoke S[r].arw_write_snapshot(), it follows that the predicate (arw _view i ≥ nt -1) eventually becomes true. Hence the predicate PROP C ∧ (arw _view i ≥ nt -1) eventually becomes true which concludes the proof of item (a).

Proof of (b). Due to the previous item, there is a correct simulator p i that that simulates a strongly correct process. Let p i such a simulator. This simulator p i simulates an infinite number of rounds and, in each round r it owns, it simulates IS [r].write_snapshot() on behalf of q i , after (or simultaneously with) the invocations of IS [r].write_snapshot() issued by at least nt processes (nt -1 other processes plus itself). As there is a bounded number of processes, p i consequently simulates its write-snapshots infinitely often after (or simultaneously with) those of at least nt simulators. Hence at least nt simulated processes are strongly correct and (b) follows.

✷ T heorem 4

Conclusion

This paper has addressed the respective power of the base asynchronous read/write model ARW and the iterated immediate snapshot model IIS when both are enriched with the same non-trivial failure detector (non-trivial means that the failure detector cannot be implemented in the base ARW model). The paper has shown that, once enriched with the same failure detector, both models have the same computational power when the notion of a correct process used in the ARW model is replaced by the notion of a strongly correct when considering the IIS model. This notion is related to the writes seen by a process at each round of the IIS model, more precisely, a process is strongly correct if all its writes into the sequence of immediate snapshot objects are eventually propagated to all the processes that do not crash.

The paper has presented a formal definition of a strongly correct process and two simulations, a first one from IIS to ARW and a second one from ARW to IIS. It has also proved these simulations and shown how they can be extended when the wait-freedom is replaced by t-resilience. An appendix of the paper has also presented a consensus algorithm suited to the IIS model enriched with an eventual leader failure detector. of rounds, that simulator propagates this triple to a simulator SC k-2 . This continues recursively and, in a finite number of rounds, the triple (i, sn, x) written by q i is added to the set ops y of known operations by a simulator q y , y ∈ SC 0 . Then, it follows from the definition of SC 0 that q y propagates the triple that becomes eventually known by all correct simulators. After that, the next invocation of S[r ′ ].write_snapshot() issued by q i is such that the predicate of line 5 is satisfied and q i can terminate its simulation of the operation S.write() or S.snapshot() issued by the process p i . It follows that the simulated process p i always progresses and it is consequently correct with respect to the simulated execution in ARW n [C].

✷ T heorem 1

B An implementation of the arw_write_snapshot() operation

For a completeness purpose, this appendix presents a wait-free implementation of the operation write_snapshot() This algorithm, described in Figure 4. is due to Borowsky and Gafni [START_REF] Borowsky | Immediate atomic snapshots and fast renaming[END_REF]. It considers that each process invokes the operation at most once and uses two arrays of single-writer/multi-reader atomic registers denoted REG [1..n] and LEVEL [1..n] (only p i can write REG[i] and LEVEL[i]). A process p i first writes its value in REG[i]. Then the core of the implementation of write_snapshot() is based on the array LEVEL[1..n]. That array, initialized to [n + 1, . . . , n + 1], can be thought of as a ladder, where initially a process is at the top of the ladder, namely, at level n + 1. Then it descends the ladder, one step after the other, according to predefined rules until it stops at some level (or crashes). While descending the ladder, a process p i registers its current position in the ladder in the atomic register LEVEL [i].

(called arw_write_snapshot( in Section 4) suited to ARW n [∅]. operation write_snapshot(vi) is REG[i] ← vi; repeat LEVEL[i] ← LEVEL[i] -1; for j ∈ {1, . . . , n} do leveli[j] ← LEVEL[j] end for; viewi ← j : leveli[j] ≤ LEVEL[i]}; until (|viewi| ≥ LEVEL[i]) end repeat; return({ j, REG[j] such that j ∈ viewi}).
After it has stepped down from one ladder level to the next one, a process p i computes a local view (denoted view i ) of the progress of the other processes in their descent of the ladder. That view contains the processes p j seen by p i at the same or a lower ladder level (i.e., such that level i [j] ≤ LEVEL[i]). Then, if the current level ℓ of p i is such that p i sees at least ℓ processes in its view (i.e., processes that are at its level or a lower level) it stops at the level ℓ of the ladder. Finally, p i returns a set of pairs determined from the values of view i . Each pair is a process index and the value written by the corresponding process. This algorithm satisfies the self-inclusion, containment and immediacy properties stated in Section 2.4.

For the interested reader, a recursive algorithm implementing the operation write_snapshot() is described in [START_REF] Castañeda | The renaming problem in shared memory systems: an introduction[END_REF][START_REF] Gafni | Distributed Programming with Tasks[END_REF].

C A consensus algorithm for the IIS model

C.1 Description of the algorithm

Global variables As we consider the IIS model, there is an infinite array IS of immediate snapshot objects, such that IS [r] is accessed by a process only when it executes round r.

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

• r i is the local round number.

• est i is the local estimate of the decision value. It is initialized to v i , the value proposed by p i .

• r_leader i is the leader known by p i at the current round. It is initialized to the default value ⊥.

cur_leader i is an auxiliary variable that contains the leader id obtained by p i at the beginning of the current round.

• dec i is a one-write boolean variable initialized to false. It is set to true when p i decides and keeps then that value forever.

Collection des Publications Internes de l'Irisa c IRISA The first property one states that, if a process sees at least two different leaders in the view it obtains from IS [r].write_snapshot(), then all processes that have their invocation of IS [r].write_snapshot() set-linearized after p i 's one see also at least two different leaders.

(The proof follows directly from the containment property of the write_snapshot() operation.) On the other hand, the second property ensures that there can be at most one round leader for a given round. (This follows from both the containment and immediacy properties of the write_snapshot() operation.) It is thus possible to define ℓ[r] as the unique non-⊥ leader of the round r or as ⊥ if ∀i : ℓ i [r] = ⊥. Remark that a process p i that writes a tuple carrying the flag val_ld_seen = true during round r necessarily verifies (1) ℓ i [r-1] = ⊥ and (2) the value it retrieves from Ω * at the beginning of round r is ℓ[r -1]. It follows from that remark and from the second property of ℓ i [r] that all the tuples written at a given round with the tag val_ld_seen = true carry the same value of r_leader.

Let now p ℓ be a process such that (1) a process p i writes -, ℓ, true, false during a round r and (2) no process writes -, ℓ, true, f alse during the round r-1 (note that all tuples written into W S [START_REF] Afek | Atomic snapshots of shared memory[END_REF] are such that val_ld_seen = f alse). The previous observations entail that ℓ[r -1] = ℓ and that all the tuples of the type -, ℓ, true, false written during the round r carry the same estimate. Indeed, the processes that wrote these tuples have necessarily executed line 13 at the end of round r -1, hence their first predicate of line 12 was verified (this cannot be due to the second predicate of line 12 since their predicate line 11 was verified and no process writes -, ℓ, true, f alse during round r -1). They consequently all verified the first part of the predicate line 12 and all adopted the unique estimate value written by p ℓ at round r -1.

Similarly, all the processes that write a tuple -, ℓ, true, f alse during the round r+1 (if there are some) have adopted their estimate at line 13, so it is the only one present in the immediate snapshot object IS [r] (and recursively while there are such processes). It follows that during a given round r, all the tuples carrying a flag val_ld_seen = true also contain the same estimate and the same round leader, which proves Claim C1.

Consider the first round r during which a process decides, let p i be such a process and v the value it decides. Necessarily p i decides because the predicate line 9 is true (otherwise another process would have decided during round r -1 which would contradicts the definition of r). Hence, according to Claim C1 and the containment property of the immediate snapshot objects, all the processes that decide during round r decide the same value. Moreover, since p i obtains a view where all tuples are such that v, -, true, f alse , all other processes that terminates round r obtain a view where there is at least one such tuple. They consequently execute line 13 or line 15 according to the value of the predicate line 11. In both cases they adopt v at the end of round r. The only value written in all the objects IS [r ′ ], r ′ > r, is then v and the agreement property follows.

✷ Lemma 3

Theorem 5 When executed in IIS n [Ω * ], the algorithm described in Figure 5 solves the the consensus problem.

Proof The proof follows directly Lemma 1, Lemma 2 and Lemma 3. ✷ T heorem 5

Figure 1 :

 1 Figure 1: From ARW n [C] to IIS n [C * ] and vice-versa

  The simulation uses an infinite sequence of objects S[1], S[2], ... The object S[r] is used to implement the corresponding one-shot immediate snapshot object IS [r].

Figure 3 :

 3 Figure 3: A generic simulation of IIS n [C * ] in ARW n [C]: code for a simulator p i

Theorem 2

 2 Let A be an algorithm solving a colorless task in the IIS n [Ω * k ] model. The simulation of A on top of ARW n [Ω k ] where the invocations of IS [r].write_snapshot() and C * .read() are implemented by the algorithms described in Figure 3 and the predicate PROP C is instantiated by PROP Ω k , produces an execution of A that could have been obtained in IIS n [Ω * k ]. Moreover, there is a one-to-one correspondence between the correct (simulated) processes in IIS n [Ω * k ] and the correct simulators in ARW n [Ω k ].

Theorem 3

 3 Let A be an algorithm solving a colorless task in the IIS n [✸P * ] model. The simulation of A on top of ARW n [✸P ] where the invocations of IS [r].write_snapshot() and ✸P * .read() are implemented by the algorithms described in Figure3and the predicate PROP C is instantiated by PROP ✸P , produces an execution of A that could have been obtained in IIS n [✸P * ]. Moreover, there is a one-to-one correspondence between the correct (simulated) processes in IIS n [✸P * ] and the correct simulators in ARW n [✸P ] and all correct simulated processes are strongly correct.

5

  From wait-freedom to t-resilience Notation Let IIS n,t [C] denote the extended IIS n [C] model in which at least nt processes are strongly correct, i.e., |SC| ≥ nt and |WC| + |F | ≤ t. Similarly, let ARW n,t [C] denote the extended ARW n [C] model in which at most t processes are faulty.

Theorem 4

 4 Let A be an algorithm solving a colorless task in the IIS n [C * ] model. For the failure detector classes studied in this paper, The simulation of A on top of ARW n [C] where the invocations of IS [r].write_snapshot() and C * .read() are implemented by the algorithms described in Figure 3 and the predicate PROP C is replaced by PROP C ∧ |arw _view i | ≥ (nt -1), produces a correct execution of A in IIS n [C * ] in which nt processes are strongly correct.

Figure 4 :

 4 Figure 4: Borowsky-Gafni's wait-free algorithm for write_snapshot() in ARW n [∅]: code for p i .

For

  completeness, this appendix presents an algorithm designed for an IIS n [C * ] model, namely, a consensus algorithm for IIS n [Ω * ].

•

  ∀ i : (ℓ i [r] = ⊥) ⇒ (∀j : ( i, -∈ iis_view j [r] ⇒ ℓ j [r] = ⊥)) , • ∀ i, j : (ℓ i [r] = ⊥ ∧ ℓ j [r] = ⊥) ⇒ (ℓ i [r] = ℓ j [r]) .

Although it is not explicitly defined in[START_REF] Rajsbaum | The iterated restricted immediate snapshot model[END_REF], the notion of a strongly correct process is implicitly used in the proof of a theorem in that paper. It is not used to define failure detectors suited to the IIS model.Collection des Publications Internes de l'Irisa c IRISA

The traditional definition of P provides each process p i with a set faulty i that does not contain a process before it crashes and eventually contains all faulty processes. It is easy to see that trusted i = {1 . . . , n} \ faulty i .Collection des Publications Internes de l'Irisa c IRISA

Collection des Publications Internes de l'Irisa c IRISA

This situation is similar to the case where, in the base read/write model, after some finite time, some subset of processes (the ones corresponding here to the set of weakly correct simulators) commit forever send omission failures with respect to the correct processes (the ones corresponding here to the set of strongly correct simulators).Collection des Publications Internes de l'Irisa c IRISA

Let us observe that, while this proves that there is a correct simulator that gives rise to a strongly correct simulated process, we cannot determine how many simulated processes are strongly correct. This number depends on the execution.Collection des Publications Internes de l'Irisa c IRISA

Acknowledgments

This work has been partially supported by the French ANR project DISPLEXITY devoted to the computability and complexity in distributed computing.

A Proof of Theorem 1

Theorem 1 Let A be an algorithm designed for the ARW n [C] model. Let us consider an execution of A simulated in the IIS n [C * ] model by the algorithms described in Figure 2. A process p i is correct in the simulated execution if and only if its simulator q i is strongly correct.

Proof Let us first observe that a simulated process whose simulator eventually crashes in IIS n is faulty (it cannot issue an infinite number of steps since its simulator crashes after a finite number of steps). Hence, it remains to show that (a) all simulators in WC simulate faulty processes and (b) all simulators in SC simulate correct processes .

Proof of (a). Let us first remark that, as there is a bounded number of simulators and (by assumption) at least one of them is correct, |SC| ≥ 1. If C = SC (i.e., WC = ∅), (a) trivially follows. Hence, let us consider that there is at least one weakly correct simulator q i .

Let rmax be a round number such that (1) ∀i ∈ WC, ∀j ∈ SC, ∀r ≥ rmax : i, -/ ∈ is_view j [r] and (2) no faulty simulator starts round rmax. At any round r ≥ rmax, any strongly correct simulator issues its invocation of IS [r].write_snapshot() strictly before those of any weakly correct simulator. Consequently, when after round rmax, q i , i ∈ WC, executes the algorithm that simulates the next invocation of S.write() or S.snapshot() issued by p i , encoded in the triple (i, sn, x), the only simulators that can see this triple are weakly correct simulators. Then, as after rmax the simulator q i sees all the triples written or known by the strongly correct simulators, its predicate of line 5 will never be verified and q i will loop forever. Hence the simulated process p i never ends its invocation of S.write() or S.snapshot(): it does no longer progress and appears as a crashed process in the simulated execution in

Proof of (b). Let now q i be a strongly correct simulator. By definition of SC, there is a set SC k such that i ∈ SC k and there is an infinite sequence of invocations of IS [r].write_snapshot() issued by q i which occur before those of some simulators of SC k-1 . It follows that, each time q i simulates a S.write() or S.snapshot() invocation on behalf of p i , after a finite number of rounds, the corresponding triple (i, sn, x) is added to the set of its known simulated operations by a simulator of SC k-1 . Then, in the same way and in a finite number

∨ ∃v : ∀ j, est, -, val_ld_seen, -∈ iis_view i : (val_ld_seen = true ∧ est = v) [START_REF] Delporte-Gallet | The weakest failure detectors to solve certain fundamental problems in distributed computing[END_REF] then

end if [START_REF] Mostefaoui | On the Computability Power and the Robustness of Set Agreement-oriented Failure Detector Classes[END_REF] end if [START_REF] Neiger | Set Linearizability. Brief Announcement[END_REF] end if [START_REF] Neiger | Failure detectors and the wait-free hierarchy[END_REF] end repeat end operation. The algorithm is described in Figure 5. When a process invokes propose (v i ) where v i is the value it proposes, it first initializes its local variables (line 1). Then it enters an infinite loop (lines 2-19). Within the loop, the behavior of a process p i can be decomposed into three phases.

• A process p i first increases r i (line 3) and reads the current value of its local failure detector output (line 4). If the leader has changed since the last round, p i resets accordingly val_ld_seen i to false and r_leader i (line 5). • Then, p i invokes IS [r].write_snapshot() to write its local state which abstracted as a tuple of 4 values est i , r_leader i , val_ld_seen i , de

When it returns from that invocation, it obtains a view made up of pairs j, est, r_leader, val_ld_seen, dec deposited by other processes (line 6). • Then the behavior of p i depends on dec i . If it has already decided, p i proceeds directly to the next round. Otherwise it checks a decision predicate (lines 9-10). This predicate is true if the view iis_view i just obtained by p i contains a value v already decided by a process (line 9) or all the processes p j that appear in iis_view i have written the same estimate value est = v and this value comes from the same leader, namely val _ld _seen = true (line 10).

-It the predicate is satisfied, p i adopts v as new estimate, decides (line 10) and proceeds to the next round.

-If the decision predicate is false, p i strives to progress to a decision. To that end, it checks if all the processes in its view have the same leader p ℓ (line 11). * If all the processes in its view have the same leader p ℓ and p i knows the estimate v of p ℓ (first predicate of line 12) or knows that a process knows that value (first predicate of line 12), then it adopts v as its new estimate value est i and sets val_ld_seen i to true (line 13). If none of this predicates is satisfied, est i and val_ld_seen i keep their previous values. * If the processes in its view do not share the same leader, p i sets val_ld_seen i to false and, if its view contains a tuple v, -, true, -, it updates its estimate est i to v (line 15).

As we can see, the principle of the algorithm is the following. A process that is considered as a leader tries to impose its estimate value as the decision value. As Ω * does not guarantee a common leader since the very beginning, the processes are required to "vote" when they see a common leader in their view (this is captured by the boolean variables val_ld_seen i ). This idea is made operational by the lines 8-17.

C.2 Proof of the consensus algorithm

Lemma 1 When executed in IIS n [Ω * ], the algorithm described in Figure 5 satisfies the consensus validity property.

Proof All the decided values are read from the local variables est i (line 10). These variables are initialized to proposed values (line 1). They are then updated with values v read from tuples contained in iis_view i (lines 10, 13 and 15). The views iis_view i are returned from the immediate snapshot objects (line 6). The rest of the proof shows that any tuples written in an immediate snapshot object contains a proposed values.

Let us consider the value est contained in a tuple written by a given in IS [r] by a process p i , with r > 1 (line 6). It is either a tuple p i has written in IS [r -1] (if one of its predicates at line 7, 12 or 15 was false during round r -1), or the one it has adopted from IS [r -1] (through iis_view i at line 10, 13 or 15). In both cases that tuple has been written in the immediate snapshot object during the previous round. Since only proposed values belong to tuples written in IS [START_REF] Afek | Atomic snapshots of shared memory[END_REF] (est i is not modified between line 1 and 6), the only values inside tuples written in IS [r], r > 0 are proposed values and the validity follows.

✷ Lemma 1

Lemma 2 When executed in IIS n [Ω * ], the algorithm described in Figure 5 satisfies the consensus termination property, i.e., any strongly correct process decide.

Proof Let us first observe that, as soon as a process decide (invocation of decide() at line 10), it repeatedly write tuples carrying the value it has decided together with the flag dec i = true (line 6). Moreover, when a process retrieves such a tuple from an invocation IS [r].write_snapshot() it also immediately decides (lines 8 and 10) and consequently writes tuples with the same decided value in the following rounds (if it does not crash). For any process p i and any round number r such that p i invokes IS [r].write_snapshot(), let P r i be the non-empty set of processes that see this write in the view they obtain from their own invocation of IS [r].write_snapshot(). If a process p i decides at round r, the processes of P r+1 i that have not decided yet decide during round r + 1. Then, at the beginning of round r + 2, all the processes of P r+1 i have decided, and it follows that all the processes of j∈P r+1 i P r+2 j have decided by the beginning of round r + 3 and recursively. It follows that all processes that would have been informed of p i state at round r in a full information algorithm following the same schedule eventually decide. By definition of the strongly correct processes, it follows that, if one of them decide, then, in a finite number of round, all alive processes decide.

Suppose now that no strongly correct process ever decide. Let then p ℓ be the strongly correct leader elected by Ω * . It follows from the definition of "strongly correct process" and Ω * that there is a round number rmax such that: (1) all faulty processes have crashed before invoking IS [rmax].write_snapshot(), (2) for all r ≥ rmax, the invocations of IS [r].write_snapshot() issued by the strongly correct processes are set-linearized strictly before those of weakly correct processes, and (3) all the reads of Ω * issued by strongly correct processes after the beginning of rmax return ℓ. Consequently, after the beginning of rmax, the predicate of line 11 is always true for all the strongly correct processes.

Since p ℓ is correct and never decides, it executes an infinite number of rounds without ever invoking decide()(line 10). When it executes the round rmax, the view it obtains from IS [rmax].write_snapshot() contains only pairs written by strongly correct processes. As it does not decide, it checks the predicate line 11 and according to the definition of rmax, this predicate returns true. Process p ℓ then makes true the first part of the predicate of line 12 and (according to the self-inclusion property of the immediate snapshot object IS [rmax]) p ℓ consequently sets val_ld_seen ℓ to true at the end of round rmax.

According to the definition of rmax, it follows that, after the beginning of round rmax + 1, the predicate of line 5 is never satisfied while the predicate of line 11 is always satisfied by any strongly correct process. These processes consequently never reset their variables val_ld_seen to false. Hence, after round rmax, each strongly correct process p k that eventually verifies the predicate of line 12 sets val_ld_seen k to true and keep doing it forever.

After rmax+1, p ℓ and all the processes that obtain the tuple in their view repeatedly write tuples carrying the flag val _ld _seen = true. Like in the case of tuples carrying dec = true, these flags eventually reach all alive processes. Consequently, all strongly correct processes eventually set val_ld_seen = true and then keep it so forever.

Let us consider now that the following claim (proved below in Lemma 3) is verified: (C1) if two processes write tuples with val_ld_seen = true and dec = f alse in the same IS [r] object, then these tuples carry also the same est. It follows from this claim that, as soon as all strongly correct processes have (1) reached the round rmax+ 1 and (2) set their variable val_ld_seen to true, they all verify the predicate line 9 and decide, what contradicts the initial hypothesis. This ends the proof of termination under the assumption that C1 is true.

✷ Lemma 2

Lemma 3 When executed in IIS n [Ω * ], the algorithm described in Figure 5 satisfies the consensus agreement property.

Proof Let us consider an execution of the algorithm of Figure 5, where p i a process that terminates its invocation of IS [r].write_snapshot(), r > 0, and iis_view i the view it obtains. Let ℓ i [r] be a process identity or the default value ⊥ according to the following rules:

• ∀ j, -, ℓ j , -, -∈ iis_view i : ℓ j = ℓ ⇒ ℓ i [r] = ℓ,

• ∃ j, -, ℓ j , -, -, k, -, ℓ k , -, -∈ iis_view i :

Namely, if all processes seen by p i during round r agree on the same round leader, then ℓ i [r] is this leader, otherwise it is ⊥. (Let us remark that one could replace the predicate of line 11 by ∃ℓ = ⊥ : ℓ i [r i ] = ℓ.)

The set-linearizability of the invocations of write_snapshot(), implies these two properties, where iis_view i [r] denotes the view obtained by a process p i during round r:

Collection des Publications Internes de l'Irisa c IRISA


Adrien Broue

Jérémie Dhennin

Frédéric Courtade

Pierre-Louis Charvet

Patrick Pons

Robert Plana

Novamems

An experimental characterization of Au-and Ru-based microcontacts for MEMS switches

Micro-switches are one of the most promising field of MNT for commercial applications. The high-reliability level required for further integration of these technologies in complex systems is currently a challenging issue. Indeed, the TRL level of these devices hardly managed to increase in the past few years. Particularly, studying the behaviour of the electrical microcontact remains difficult due to small size at stakes. One of the main failures occurring when aging the devices is the increase of the electrical contact resistance. The key issue is the electromechanical behaviour of the materials used at the contact interface when the current is flowing through the contact asperities. Indeed metal contacting switches have a large and complex set of failure mechanisms driven by the current level, which depend of several mechanical and operating parameters.

From several years, we have developed a new set-up for the characterization of contact materials used in micro-switches. This approach is based on the coupling of a commercial nanoindenter with electrical measurements on adapted specimen. The diamond tip is considered as a mechanical actuator, which applies a punctual load on the free-standing electrode. Previous works showed the relevance of such an approach to simulated a distributed pressure actuation [START_REF] Broue | Validation of bending test by nanoindentation for micro-contact analysis of RF-MEMS switches[END_REF]. Thus, this paper reports first results obtained on several pairs of contact materials.

Works on FEM structural-contact analysis were reported at Memswave 2009 where temperature was studied at the contact interface [START_REF] Solazzi | Contact Modelling of RF MEMS Switches Based On FEM Simulations[END_REF]. Fortini presented a nanoscale comparison of Au and Ru contact behaviour using molecular dynamics simulation [START_REF] Fortini | Asperity contacts at the nanoscale : Comparison of Ru and Au[END_REF]. In the field of experiment, previous researchers have published data using nanoindenter testing [START_REF] Gilbert | A Nanoindenter Based Method for Studying MEMS Contact Switch Microcontacts[END_REF], piezo actuator [START_REF] Kwon | Investigation of the electrical contact behaviours in Au-to-Au thin-film contacts for RF MEMS switches[END_REF] and atomic force microscope (AFM) [START_REF] Yang | A new test facility for efficient evaluation of MEMS contact materials[END_REF] to investigate the behaviour of Au and Au-Ni alloys as contact materials by mechanical actuation with increasing force. To our knowledge, the micro-scale heating effects on contact material are not fully understood. However these phenomena are key issue for the designers to understand the capability of the contact to sustain the current before reaching critical temperature values for the used material [START_REF] Solazzi | Contact Modelling of RF MEMS Switches Based On FEM Simulations[END_REF]. The analysis of the impact at low to medium power level on Au, Ru and Au/Ru based RF MEMS contacts differs from previous works as the contact temperature study is based on the experimental results. An environmental chamber is used in order to control temperature and humidity. Dedicated validation tests and FEM modelling are presented to assess this methodology. The contact response is analyzed for 5 µm² square bumps under electromechanical stress. Dedicated test structures have been designed and successfully fabricated by LETI. These are metallic micro bridges suspended over metallic lines. Both are coated either with gold or with ruthenium. A particular attention is paid to avoid any parasitic resistance measurement thanks to a cross-rods design.

The data obtained provides a better understanding of micro-contact behaviour related to the impact of current at low-to medium-power levels. The stability of the contact resistance, when the contact force increases, is studied for contact pairs of soft material (Au/Au contact), harder material (Ru/Ru contact) and mixed configuration (Au/Ru contact). The super-temperature of the contacts have been calculated and compared to the theoretical values of softening temperatures for each material. It can be shown that this temperature can be reached for gold and ruthenium material, with different levels of current intensity. However, no softening behaviour has been highlighted for mixed contact. An enhanced stability of the bimetallic contact Au/Ru was demonstrated considering sensitivity to power increase, related to creep effects and topological modifications of the contact surfaces. These results are discussed in a theoretical way by considering the temperature distribution around the hottest niveau-surface at the contact interface. Consequently an enhanced reliability can be expected for contacts made with two different materials.


P Yameogo
email: pyameogo@laas.fr

U Heiba

M Al Bahri

P Pons

Self Calibrating pressure sensor for biomedical applications

In this paper we present for the first time a wireless self calibrating pressure sensor for biomedical applications. The proposed system consists of a piezoresistive pressure sensor implemented on a thin silicon membrane, a catheter tube and finally a protection capsule fabricated from a biocompatible polymer (PEEK). A double side flex with embedded conductors has been used to create the interconnections between the pressure sensor and the control circuit which is further connected to a wireless transceiver. The auto calibration capability of the proposed sensor enables to avoid the existing problem of drift with time and hence provides an excellent solution for long term monitoring. Moreover, the catheter of the proposed system has a reduced length of only 200mm in comparison to the 1m length for the existing wired solutions.

I.

INTRODUCTION

Intracranial Pressure (ICP) monitoring is considered to be one of the bases of modern neurointensive care. Basically, the brain parenchyma is nearly incompressible, enclosed in a nonexpandable case of bone and besides it is a complex system with an equilibrium between blood and cerebrospinal fluid (CSF) circulation [START_REF] Czosnyka | Monitoring and interpretation of intracranial pressure[END_REF]. When a traumatic brain injury occurs, subarachnoid haemorrhage, stroke, intracerebral, Haematoma or meningitis, this equilibrium can be break and ICP rises. Thus, secondary injury, which may cause permanent neurological damage if undetected and untreated, could be detected through monitoring the ICP value.

Historical modern way to ICP measurement is Ventricular puncture, which is composed with a catheter filled of physiological serum which connect brain ventricule to an external pressure transducers. This technology has been develop in early 60's and the main drawback is the risk of intracranial infection during prolonged pressure measurements (more than 5days). At the end of 70's, a new type of sensor appears, catheter-tip transducer, which allows intra parenchymental monitoring and, with using of cranial bolt, reduces morbidity due to septic risk. Two technologies are used today, the first is based on a flexible diaphragm placed at the tip of a narrow optical fiber catheter. Light is reflected off the diaphragm and these changes in light intensity are interpreted in terms of pressure. The second transducer consists of a miniature solid state pressure sensor mounted in a very small titanium case at the tip of a 100 cm long flexible nylon tube. The transducer tip contains a silicon microchip with diffused piezoresistive strain gauges which are connected by wires in the nylon tube to complete a Wheatstone bridge type circuit. The main limitation of a catheter-tip transducer is that it is not possible to calibrate it in situ and it should be replaced or recalibrate if monitoring is longer than five days, because of possible drift [START_REF] North | INTRACRANIAL PRESSURE MONITORING[END_REF][START_REF] Stendel | Clinical evaluation of a new intracranial pressure monitoring device[END_REF].

A cranial bolt is necessary to fix catheter in skull and make sealing, not for pressure, but for limit septic risk, and prevent infection to gain CSF which is not protected by immunity system.

Next sections will present a new generation of catheter-tip transducer which try to overcome to main drawbacks of catheter-tip sensor. This new sensors is based on solid state pressure sensor coupled with an electrostatic actuator which allows in situ calibration. Besides this sensor is connected to an electronic with wireless ability to remove wires between ICP monitor and patient's head. Figure 1 presents a 3D model of the proposed wireless catheter-tip sensor. As can be shown, the system consists of four main components; a silicon pressure sensor, a capsule, a catheter tube and the interconnections. A piezoresistive pressure sensor has been implemented on a thin silicon b a c membrane in order to convert the pressure into an electrical signal. A tiny polymer capsule is used in order to package the pressure sensor. A double side flex with embedded conductors has been used to create the interconnections between the pressure sensor and the control circuit which is further connected to a wireless transceiver (fig.1.b). A flexible polyamide has been used in order to fabricate the catheter tube through which the interconnections will go. Finally a new ergonomic package has been implemented in order to enclose the catheter, the control circuitry and the wireless transceiver. The catheter of the proposed system (fig. 1.a) has a diameter of 3.5French (1.16mm) and a reduced length of only 200mm in comparison to a 1m length for the existing wired systems.

II. INTEGRATED SYSTEM OVERVIEW

The proposed wireless catheter-tip sensor can be inserted easily through the cranial bone and meninges into the brain parenchyma in order to measuring the ICP. The main goal from the proposed system is twofold. First, in contrast with the existing wired sensors, the wireless capability of the proposed sensor enables the patient to move freely for any other medical inspections. Second, the usage of the biocompatible polymer (PEEK) in the fabrication of the cranial bolt (fig. 1.c). As seen from figure 2, the proposed ICP sensor consists of an absolute piezoresistive pressure sensor [START_REF] Kanda | Piezoresistance effect of silicon[END_REF][START_REF] Maj | Analytical method of strain gauge-based pressure sensor design[END_REF] and an electrostatic actuator [START_REF] Yilmaz | Design and integration of a bimorph thermal microactuator with electrostatically actuated microtweezers[END_REF][START_REF] Sakata | Micromachined relay which utilizes single crystal silicon electrostatic actuator[END_REF]. Two silicon electrodes have been used in order to implement the electrostatic actuator. The bulk silicon reassembles the bottom electrode and is used as a vacuum reference while the membrane itself has been used as the top electrode.

III. FABRICATION PROCESS FLOW

The pressure sensor has been implemented through the direct bonding between two wafers; a standard silicon substrate and an SOI wafer. Eight-mask process has been used in order to fabricate the sensor as shown in fig. 3 and involves direct-bonding and ion implantation techniques. The fabrication process starts with a standard 4", n-type, (100) and 4-6.cm resistivity wafers. The first step is to grow a 2µm thick thermal silicon dioxide layer (fig. 3.a) which defines the reference cavity depth. Then, the first mask is used in order to pattern a cavity with 300µm x 300µm dimensions through BHF wet etching (fig. 3.b). Basically, the cavity pattern defines the dimensions of the pressure sensor's membrane. Another oxide layer is then thermally grown over both the processed standard silicon substrate as well as the SOI wafer (n-type, (100) and 4-6.cm resistivity) in order to electrically isolate the bottom and top electrodes that form the electrostatic actuator. Then, both wafers are direct bonded under vacuum (at least ) to create the pressure sensor's reference cavity and electrostatic actuator(fig. 3.c). The bulk of the SOI wafer is then etched using the KOH in order to release the membrane (fig. 3.d). The main purpose from using the SOI wafer is to control accurately the membrane thickness which is fixed to be 5µm. The buried oxide layer of the SOI wafer is then wet etched using BHF. In order to access bulk which is the bottom electrode, Reactive ion etch has been used on the 5µm silicon layer followed by a BHF wet etching (fig. 1.e). This is followed by growing a 50nm oxide layer(fig. 3.f). Ion implantation is then used in order to create the strain gages (P), interconnection between gages (P++) and the contact zone of the membrane and the electrodes (N++)(fig. 3.g). Next step is to open contact areas in silicon dioxide layer and this is followed by a deposition and patterning of 100nm/800nm titanium-gold layer (fig. 3.h) to have a connection with the Wheatstone bridge, electrostatic actuator and temperature sensor. Then the fabricated structure is passivated using a 1µm thick SU-8 photoresist which is well known to be compliant with many levels of the iso 10993 biocompatibility standard [START_REF] Kotzar | Evaluation of MEMS materials of construction for implantable medical devices[END_REF][START_REF] Voskerician | Biocompatibility and biofouling of MEMS drug delivery devices[END_REF]. Finally, the back side of the standard wafer is grinded and the final structure is diced. At this step, the pressure sensor is finished and is ready to be packaged as will be explained in the next section. The pressure sensor has dimension of 2000µm length, 690µm width and 200µm thick and the sensitivity is between 30-40µV/V/mmHg. The direct bonding step is considered to be the most critical step in the proposed fabrication process. For a reliable bonding, wafers surfaces which have to be bonded must be well cleaned and activated [START_REF] Huang | Fabricating Capacitive Micromachined UltrasonicTransducers With Wafer-Bonding Technology[END_REF][START_REF] Tong | Semiconductor Wafer Bonding: Science and Technology[END_REF]. In order to remove all photoresist residuals, wafers are cleaned with Piranha solution (3:1 Sulfuric Acid: Hydrogen Peroxide) for 10 min and then they are rinsed in DI water and finally dried in N2 atmosphere. Besides, in order to improve the bonding energy, wafers are activated in RCA1 solution for 10 min followed by rinsing and drying in N2 as well. Then the wafers are initially direct bonded in a wafer bonder in vacuum at 200°C. Finally, the direct bonding step is completed by annealing the wafers at 1100°C for two hours under nitrogen flow.

The proposed pressure sensor is based on the well know silicon piezoresistive phenomena and makes use of the classic Wheatstone bridge concept. The sensitivity curve of the proposed sensor is presented in Fig. 4. As can be seen, the relation between the applied pressure and the measured differential voltage is quite linear. Besides, the sensor features a sensitivity of around 35µm/V/mmHg for a range of 0-150mmHg. One important advantage of the proposed pressure sensor is the in-situ auto-calibration. This is done basically through applying a voltage between the electrostatic actuator's electrodes which results in a controlled membrane displacement. This displacement is further converted into a specific reference pressure which is controlled through the applied voltage. The basic operation of the auto-calibration process is shown in Fig. 5 where the reference pressure is controlled by the applied voltage.

V. CONCLUSION

A new concept of self calibrating pressure sensor has been proposed and verified experimentally. The dynamic calibration capability of the proposed sensor makes it of great importance for biomedical implantable pressure sensors considering that the long term drift is being avoided. Besides, a catheter tip packaging which is compliant with the biocompatibility standard (iso 10993) has been fabricated and proved to be an enabling technology for the in-vivo evaluation. This work is being resumed through the development of embedded wireless transceiver as well as the fabrication of a new cranial bolt in order to be used in ICP measurement.

Figure 1 .

 1 Figure 1. Classic ICP sensor in use (left) and 3D model of the proposed wireless sensor (right)

Figure 2 .

 2 Figure 2. A finished piezoresistive pressure sensor after the passivation step.

  mbar

Figure 3 .

 3 Figure 3. fabrication process flow.

Figure 4 .

 4 Figure 4. The measured voltage versus the applied pressure for the proposed pressure sensor (Bridge's voltage : 1,25V).

Figure 5 .

 5 Figure 5. The measured voltage signal and the corresponding pressure values versus time for a generated electrostatic pressure through applying a square wave signal of 1.25Hz and 20V amplitude.

Fig. 6

 6 Fig.6presents a 3D model of the proposed pressure sensor focusing on the catheter tip. As shown, the pressure sensor is mounted on the tip of a catheter in order to be inserted directly into intra parenchymental space. Thanks to the wireless transceiver, the catheter length is reduced to only 200mm. A double side flexible printed circuit board (PCB) with eight conductors has been used to create the interconnections between the control circuit on a side and the pressure sensor, an electrostatic actuator and a temperature sensor on the other side. The flexible PCB (fig.6.b) has four connexions on each side and has a 200mm length, 690µm width, 100 µm thick and 140 µm Conductors' pitch. The four top conductors have been used to connect the Wheatstone bridge using wire bonding (ball or wedge bonding). Then, two bottom conductors have been used to connect the electrostatic actuator electrodes while the remaining two conductors are used to connect to the

Figure 7 .

 7 Figure 7. The catheter-tip packaging.

ACKNOWLEDGMENT

This work has been supported by the French National Research Agency (Agence Nationale de la Recherche)