Michel Raynal

Julien Stainer

From a Store-collect Object and Ω to Efficient Asynchronous Consensus

Keywords: asynchronous shared memory system, building block, concurrent object, consensus, distributed algorithm, eventual leader, failure detector, fault-tolerance, modularity, multicore system, process crash, store-collect object système asynchrone, brique de base, mémoire partagée, objets distribués, consensus, algorithme distribué, leader inéluctable, détecteur de fautes, tolérance aux fautes, modularité, système multiprocesseur, défaillances de processus, objet store-collect

This paper presents an efficient algorithm that builds a consensus object. This algorithm is based on an Ω failure detector (to obtain consensus liveness) and a store-collect object (to maintain its safety). A store-collect object provides the processes with two operations, a store operation which allows the invoking process to deposit a new value while discarding the previous value it has deposited and a collect operation that returns to the invoking process a set of pairs (i, val) where val is the last value deposited by the process p i . A store-collect object has no sequential specification.

While store-collect objects have been used as base objects to design wait-free constructions of more sophisticated objects (such as snapshot or renaming objects), as far as we know, they have not been explicitly used to built consensus objects. The proposed storecollect-based algorithm, which is round-based, has several noteworthy features. First it uses a single store-collect object (and not an object per round). Second, during a round, a process invokes at most once the store operation and the value val it deposits is a simple pair r, v where r is a round number and v a proposed value. Third, a process is directed to skip rounds according to its view of the current global state (thereby saving useless computation rounds). Finally, the algorithm benefits from the adaptive wait-free implementations that have been proposed for store-collect objects, namely, the number of shared memory accesses involved in a collect operation is O(k)

where k is the number of processes that have invoked the store operation. This makes the proposed algorithm particularly efficient and interesting for multiprocess programs made up of asynchronous crash-prone processes that run on top of multicore architectures.

1 Introduction

On the implementation of consensus objects

Consensus object and its universality An implementation of any object (or service) is wait-free if the crash of any number of processes does not prevent the other processes from terminating their operation invocations on the constructed object [START_REF] Herlihy | Wait-free synchronization[END_REF]. It has been shown by M. Herlihy [START_REF] Herlihy | Wait-free synchronization[END_REF] that consensus objects are universal when one has to design wait-free implementation of any object (or service) defined from a sequential specification. This means that, as soon as we are provided with consensus objects and atomic read/write registers, it is possible to design algorithms (called universal constructions) that build wait-free implementations of any concurrent object defined by a sequential specification. Such implementations are said to be linearizable [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF].

A consensus object is a one-shot object that provides the processes with a single operation denoted propose() (one-shot means that a process invokes at most once the operation propose() on a consensus object). When a process invokes propose(v), we say that it "proposes v". A consensus object allows processes to agree (if the processes of a multiprocess program do not have to agree in one way or another, they are independent and do not constitute a distributed computation). More specifically a consensus object is defined as follows. Each process is assumed to propose a value and has to decide a value in such a way that the following properties are satisfied: each correct process which invokes propose() decides a value (wait-free termination), a decided value is a proposed value (validity) and no two processes decide different values (agreement).

Consensus impossibility and ways to circumvent it While consensus objects are fundamental objects for the design and the implementation of crash-prone distributed systems, the bad news is that they cannot be wait-free implemented in asynchronous systems where any number of processes may crash be the underlying communication medium a read/write shared memory [START_REF] Loui | Memory requirements for for agreement among Unreliable Asynchronous processes[END_REF] or an asynchronous message-passing system [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF]).

Several approaches to circumvent this impossibility have been investigated in the context of read/write shared memory systems. One consists in enriching the system model by providing the processes with registers stronger (from a computability point of view) than read/write atomic registers. This approach has given rise to the notion of consensus number introduced and developed by Herlihy [START_REF] Herlihy | Wait-free synchronization[END_REF]. An object X has consensus number n if n is the largest integer such that it is possible to wait-free implement n-process consensus objects from atomic read/write registers and objects X. If X allows to wait-free implement n-process consensus for any value of n > 0, the consensus number of the object X is +∞. It is shown it in [START_REF] Herlihy | Wait-free synchronization[END_REF] that there are objects (such as compare&swap or LL/SC registers) whose consensus number is +∞.

Another approach consists in enriching the base read/write system with a failure detector [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. Intuitively, a failure detector can be seen as a distributed module that provides each process with information on failures. According to the type and the quality of this information, several failure detectors can be defined. Failure detectors have initially been proposed for message-passing systems before being used in shared memory systems [START_REF] Lo | Using failure detectors to solve consensus in asynchronous shared memory systems[END_REF]. One of the most important result associated with the failure detector-based approach is the proof that the failure detector denoted Ω is the one that captures the minimal information on failures that allows processes to waitfree implement a consensus object despite asynchrony and process crashes [START_REF] Chandra | The weakest failure detector for solving consensus[END_REF]. A failure detector Ω is characterized by the following behavioral property: after a finite but unknown and arbitrary long period, Ω provides forever the processes with the same (non-crashed) leader.

Modular approach: on the liveness side Implementations of consensus objects have to ensure that a single among the proposed values is decided (safety) and that each process that proposes a value and does not crash eventually decides despite the behavior of the other processes (wait-freedom).

Interestingly, when considering round-based algorithms (i.e., algorithms in which the processes execute asynchronously a sequence of rounds), the safety and wait-freedom properties of a consensus object can be ensured by different means, i.e., by different object types. More precisely, the eventual leadership property provided by Ω can be used to ensure that at least one process will terminate (thereby entailing the termination of the other processes). Hence, an Ω failure detector constitutes a liveness building block on which implementations of consensus objects can rely in order to obtain the wait-freedom property.

Modular approach: on the safety side To our knowledge three types of read/write-based objects that ensure the safety properties of a consensus object have been proposed.

The first (which is given the name alpha in [START_REF] Guerraoui | The alpha of indulgent consensus[END_REF][START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF]) has been proposed by Lamport in [START_REF] Lamport | The part-time parliament[END_REF] in the context of message-passing systems and adapted to the read/write shared memory model by Lamport & Gafni [START_REF] Gafni | Disk Paxos[END_REF]. An alpha object is a round-based abstraction 1which is implemented with an array of n shared single-writer/multi-reader registers where n is the total number of processes. Each register contains two round numbers plus a proposed value or the default value ⊥.

The second object, denoted adopt-commit has been introduced by Gafni [START_REF] Gafni | Round-by-round fault detectors: unifying synchrony and asynchrony[END_REF]. It is a round-free object2 whose implementation requires two arrays of size n which are accessed by each process asynchronously and one after the other. As adopt-commit objects are roundfree, each round of an adopt-commit-based consensus algorithm requires its own adopt-commit object and, when it executes a round, a process accesses only the corresponding adopt-commit object.

A third object that has used to ensure the safety property of a consensus object is the weak set object type proposed by Delporte & Fauconnier [START_REF] Delporte-Gallet | Two consensus algorithms with atomic registers and failure detector Ω[END_REF]. This object is a set from which values are never withdrawn. Similarly to adopt-commit objects, these sets are roundfree objects but, differently from them, during each round a process is required to access three distinct sets (the ones associated to the previous, the current and the next rounds).

Content of the paper

Step complexity and number of objects The step complexity (number of shared memory accesses) involved by each invocation of an operation on an alpha, adopt-commit or weak set object is O(n).

On another side, the consensus algorithms based on adopt-commit or weak set objects requires one such object per round and, due the very nature of Ω, the number of rounds that have to be executed before processes decide is finite but can can be arbitrary large. This means that the number of adopt-commit or weak set objects used in an execution cannot be bounded and, consequently, these objects have to be dynamically created 3 . Interestingly, alpha-based consensus algorithms (e.g., [START_REF] Gafni | Disk Paxos[END_REF][START_REF] Guerraoui | The information structure of indulgent consensus[END_REF][START_REF] Lamport | The part-time parliament[END_REF]) needs a single alpha object.

A question Hence, the question: Is it possible to design a consensus object from Ω (for the consensus liveness part) and (for the consensus safety part) an object such that (a) a single instance of this object is necessary (as in alpha-based consensus) and (b) whose step complexity of each operation is adaptive (i.e. depends on the number of processes that have invoked operations and not on the total number of processes)? The paper answers positively the previous question. To that end it considers store-collect objects.

Store-collect object Such an object, which can be seen as an array with an entry per process, provides processes with two operations denoted store() and collect(). The first operation allows a process to deposit a new value in the store-collect object, this new value overwriting the value it has previously deposited. The second operation is an asynchronous read of the last values deposited by each process. A store-collect object has no sequential specification.

While a store-collect object has a trivial wait-free implementation based on an array of size n with operations whose step complexity is O(n), in a very interesting way, efficient adaptive wait-free implementations have been proposed. As an example, when considering the implementation described in [START_REF] Attiya | An adaptive collect algorithm with applications[END_REF], the step complexity of each invocation of collect() is O(k) where k, 1 ≤ k ≤ n, is the number of processes that have previously invoked the operation store()) and the step complexity of each invocation of store() by a process is O(1) but for its first invocation which can be up to O(k).

A variant of a store-collect object is one in which the operations store() and collect() are merged to obtain a single operation denoted store_collect() (whose effect is similar to store() followed by collect()). A wait-free implementation of such a variant is described in [START_REF] Englert | Fast collect in the absence of contention[END_REF] where it is shown that in some concurrency patterns the step complexity of store_collect() is O(1).

Content of the paper

The paper presents an algorithm that wait-free implements a consensus object from Ω (building block for wait-free termination) and a single store-collect object (building block for consensus safety).

When compared to consensus algorithms that needs an unbounded number of adopt-commit or weak set objects, the proposed algorithm (similarly to alpha-based consensus algorithms [START_REF] Gafni | Disk Paxos[END_REF][START_REF] Guerraoui | The alpha of indulgent consensus[END_REF][START_REF] Lamport | The part-time parliament[END_REF]) needs a single base (store-collect) object. Moreover, when compared to alpha-based algorithms, it has several noteworthy features. (a) A better step complexity (measured as the number of accesses to the shared memory) during each round. (b) The fact that an entry of the store-collect object has only two components (a round number plus a proposed value) while an entry of an alpha object has three components (two round numbers plus a proposed value). And (c) the fact that the next round executed by a process is dynamically computed from its current view of the global state and not a priori defined from a predetermined sequence (thereby allowing a process to skip useless computation rounds).

Hence, the paper presents a new consensus algorithm suited to shared memory systems which, from an efficiency point of view, compares favorably with existing algorithms. It is important to notice that, with the advent of multicore architectures, the design of such efficient fault-tolerant algorithms become a real challenge.

Roadmap

The paper is made up of 5 sections. Section 2 presents the computation model (base read/write registers, store-collect object and Ω), and the consensus object. Then, Section 3 describes, discusses and proves correct an efficient algorithm that builds a consensus object from Ω and a single store-collect object as underlying building blocks. Finally, Section 5 concludes the paper.

Computation model 2.1 Crash-prone asynchronous processes

The system is made up of a set Π of n sequential processes denoted p 1 , . . . , p n . The integer i is the index of the process p i . The processes are asynchronous which means that each process proceeds at its own speed which can vary arbitrarily. The execution of a sequential process is represented by a sequence of steps which are accesses to its local memory or to the shared memory (see below).

Any number of processes may crash. A crash is a premature halt. After it has crashed (if ever it does) a process executes no more step. It is only assumed that a process that does not crash eventually executes its next step as defined by the code of its algorithm. Given an execution, a process that crashes is said to be faulty, otherwise it is correct.

Cooperation model

From a notational point of view, the names of the objects shared by the processes are denoted with upper case letters (e.g., DEC ) while the name of a local variable of a process p i is denoted with lower case letters with i as a subscript (e.g., set i ).

Cooperation objects: an atomic register and a store-collect object The processes cooperate through an atomic multi-writer/multireader register denoted DEC (initialized to the default value ⊥) and a store-collect object denoted MEM defined below.

A store-collect object contains a set of pairs (i, v) where i is a process index and v a value. For any i, this set contains at most one pair (i, -). Initially, a store-collect object is empty.

The operation store() and collect() As indicated in the introduction, such an object has two operations denoted store() and collect(). A process p i invokes MEM .store(val) to deposit the value val, i.e., the pair (i, val) is added to the store-collect and overwrites the previous pair (i, -) (if any) 4 . Hence, when (i, val) belongs to the store-collect object, val is the last value stored by the process p i .

A process invokes MEM .collect() to obtain a value of the store-collect object. The set that is returned is called a view and contains the latest pairs deposited by the processes that have invoked MEM .store().

Partial order on the views

To define precisely the notion of "latest" pairs returned in a view, we use the following partial order relation on views. Let view1 and view2 be two views.

view1 ≤ view2 if, for every process p i such that (i, v1) ∈ view1, we have (i, v2) ∈ view2, where the invocation MEM .store(v2) by p i is issued after (or is) its invocation MEM .store(v1).

Properties of the operations store() and collect() The invocations of these operations satisfy the following properties.

• Validity. Let col be an invocation of collect() that returns the set view. For any (i, v) ∈ view, there is an invocation store(v) issued by the process p i that has started before the invocation col terminates.

This property means that a collect() operation can neither read from the future, nor output values that have never been deposited. • Partial order consistency. Let col1 and col2 be two invocations of the operation collect() that return the views view1 and view2, respectively. If col1 terminates before col2 starts, then view1 ≤ view2.

This property expresses the mutual consistency of non-concurrent invocations of the operation collect(): an invocation of collect() cannot obtain values older than the values obtained by a previous invocation of collect(). On the contrary, there is no constraint on the views returned by concurrent invocations of collect() (hence the name partial order for that consistency property). • Freshness. Let st and col be invocations of store(v) and collect() issued by p i and p j , respectively, such that st has terminated before col starts. The view returned by p j contains a pair (i, v ) such that v is v or a value deposited by p i after v.

This property expresses the fact that the views returned by the invocations of collect() are up to date in the sense that, as soon as a value has been deposited, it cannot be ignored by future invocations of collect(). If store(v) is executed by a process p i , the pair (i, v) must appear in a returned view (provided there are enough invocations of collect()) unless v has been overwritten by a more recent invocation of store() issued by p i . • Wait-free termination. Any invocation of an operation by a process that does not crash terminates.

It is easy to see from these properties that a store-collect object has no sequential specification (two invocations of collect() which obtain incomparable views cannot be ordered).

Wait-free implementations of store-collect objects Such implementations are described in several papers (see Chapter 7 of [START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF] for a survey). The implementations described in [START_REF] Afek | Long-lived adaptive collect with applications[END_REF][START_REF] Attiya | An adaptive collect algorithm with applications[END_REF] are based on atomic read/write registers. As noticed in the introduction, they are adaptive to the number k of processes that have invoked the operation store(). Let the step complexity of an operation be the maximum number of shared memory accesses it can issue. When considering the implementation presented in [START_REF] Attiya | An adaptive collect algorithm with applications[END_REF], the step complexity of an invocation of collect() or of the first invocation of store() by a process is O(k) and the step complexity of the other invocations of store() by the same process is O(1).

Fast store-collect object Such an object, introduced in [START_REF] Englert | Fast collect in the absence of contention[END_REF], is a store-collect object where the store() and the collect() operations are merged into a single operation denoted store_collect(). This object is particularly interesting when a process invokes repeatedly store() followed by collect() without executing other steps in between, which is exactly what the store-collect-based consensus algorithm presented in Section 3 does.

An implementation of such a store-collect object is presented in [START_REF] Englert | Fast collect in the absence of contention[END_REF], where the step complexity of an invocation of store_collect() converges to O(1) when, after some time, a single process invokes that operation 5 .

The failure detector Omega

This failure detector, which has been informally defined in the Introduction, has been proposed and investigated in [START_REF] Chandra | The weakest failure detector for solving consensus[END_REF]. It provides each process p i with a read-only variable denoted leader i that always contains a process index. The set of these variables satisfies the following property.

• Eventual leadership. There is a finite time τ after which the local variables leader i of all the correct processes contain the same process index and this index is the index of a correct process.

It is important to notice that, before time τ , there is an anarchy period during which the variables leader i can have arbitrary values (e.g, there no common leader and crashed processes can be leaders). Moreover, τ can be arbitrarily large and is never explicitly known by the processes.

As already indicated, Ω is the weakest failure detector that allows a consensus object to be wait-free implemented [START_REF] Chandra | The weakest failure detector for solving consensus[END_REF]. Moreover, as consensus cannot be solved in a pure asynchronous read/write system prone to process crashes, it follows that such a system has to be enriched with time-related behavioral assumptions in order Ω can be built. Examples of such assumptions and associated Ω algorithms are described in [START_REF] Fernández | A timing assumption and two t-resilient protocols for implementing an eventual leader service in asynchronous shared-memory systems[END_REF].

Notation The previous read/write system model enriched with the additional computability power provided by Ω is denoted ASM[Ω].

The store-collect-based consensus algorithm

This section presents and proves correct an algorithm that implements the operation propose() of a consensus object CONS . As previously announced, this construction is based on a store-collect object to ensure the consensus safety properties and a failure detector Ω to guarantee its wait-free termination property.

Description of the algorithm

Internal representation of the consensus object The two base objects used in the algorithm have been introduced in Section 2.2. The aim of the atomic register DEC is to contain the decided value. The aim of the store-collect object MEM is to guarantee that no two different values are decided.

The algorithm implementing the operation propose() Algorithm 1 is a round-based asynchronous algorithm. A process p i invokes CONS .propose(v i ) where v i is the value it proposes. Its invocation terminates when it executes the statement return(DEC ) where DEC contains the value it decides (line 17).

The local variable r i contains the current round number of p i while est i contains its current estimate of the decision value (these local variables are initialized at line 1). A process executes a while loop (lines 2-16) until it decides (or crashes). Moreover, it executes the loop body (lines 4-14) only if it is currently considered as a leader by Ω (predicate of line 3).

When it is considered as a leader, p i does the following. First it stores its current local state r i , est i into the store-collect object MEM and then reads its current content by invoking MEM .collect() (line 4). (Let us observe that line 4 can be replaced by the single statement mem i ← MEM .store_collect( r i , est i ) if one wants to use a fast store-collect object instead of a more general store-collect object.) Let us notice that line 4 is the only line where p i accesses the store-collect object, i.e., the part of the shared memory related

operation CONS .propose(v i ) is (1) r i ← 1; est i ← v i ; (2) while (DEC = ⊥) do (3) if (leader i = i) then (4) MEM .store( r i , est i ); view i ← MEM .collect(); (5) mem i ← { r, v | (-, r, v ) ∈ view i }; (6) rmax i ← max{r | r, -∈ mem i }; (7) if (r i = rmax i ) (8) then set i ← {v | r, v ∈ mem i where r ∈ {rmax i , rmax i -1}}; (9) if (r i > 1) ∧ (set i = {est i }) (10) then DEC ← est i (11) else r i ← r i + 1 (12)
end if [START_REF] Guerraoui | The alpha of indulgent consensus[END_REF] else

est i ← v such that rmax i , v ∈ mem i ; r i ← rmax i (14)
end if [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF] end if (16) end while; (17) return(DEC ) end operation.

Algorithm 1: The store/collect-based consensus operation propose() to the consensus safety property. All the other statements executed by p i in a round (but the write into DEC if it decides) are local statements.

Then, p i stores into mem i the pairs r, v contained in the view view i it has obtained (line 5) and computes the greatest round rmax i that, from its point of view, has ever been attained (line 6). Its behavior depends then on the fact that it is or not late with respect to rmax i .

• If it is late (r i < rmax i ), p i jumps to the round rmax i and adopts as new estimate a value that is associated with rmax i in the view it has previously obtained (line 13). • If it is "on time" from a round number point of view (r i = rmax i ), p i checks if it can write a value into DEC and decide. To that end, it executes lines 8-12. It first computes the set set i of the values that are registered in the store-collect object with a round number equal to rmax i or rmax i -1, i.e., the values registered by the processes that (from p i 's point of view) have attained one of the last two rounds.

If p i has passed the first round (r i > 1) and its set set i contains only the value kept in est i , it writes it into DEC (line 10) just before deciding at line 17. If it cannot decide, p i proceeds to the next round without modifying its estimate est i (line 11).

Hence, the base principle on which rests this algorithm is pretty simple to state. (It is worth noticing that this principle is encountered in other algorithms that solve other problems such as termination detection of distributed computations). This principle can be stated as follows: processes execute asynchronous rounds (observation periods) until a process sees two consecutive rounds in which "nothing which is relevant has changed".

Discussion

A particular case It is easy to see that, when all processes propose the same value, no process decides in more than two rounds whatever the pattern failure and the behavior of Ω. Similarly, only two rounds are needed when Ω elects a correct common leader from the very beginning. In that sense, the algorithm is optimal from a "round number" point of view [START_REF] Keidar | On the cost of fault-tolerant consensus when there are no faults[END_REF].

On the management of round numbers In adopt-commit-based or alpha-based consensus algorithms, the processes that execute rounds do execute a predetermined sequence of rounds 6 .

Differently, the proposed algorithm allows a process p i that executes rounds to jump from its current round r i to the round rmax i which can be arbitrarily large (line 13). These jumps make the algorithm more efficient. More specifically, let us consider a time τ of an execution such that (a) up to time τ , when a process executes line 9, the decision predicate is never satisfied, (b) processes have executed rounds and mr is the last round that has been attained at time τ , (c) from time τ , Ω elects the same correct leader p at any process p i , and (d) p starts participating at time τ . It follows from the algorithm that p executes the first round during which it updates r to mr, and then (according to the values in the store-collect MEM ) at most either the rounds mr and mr + 1 or the rounds mr, mr + 1 and mr + 2. As the sequence of rounds is not predetermined, p saves at least mr -2 rounds.

Proof of the algorithm

This proof is based only on the properties of Ω and the store-collect object MEM . It does not require MEM to be built from atomic registers.

Lemma 1 If a process p i invokes MEM .store( r, -) and later invokes MEM .store( r , -), we have r > r.

Proof Let us first observe that, due to lines 4-6, for any process p i we always have r i ≤ rmax i . The lemma then follows directly from the fact that, for any r, if a process p i neither crashes nor writes into DEC after it has stored r i ,into MEM (line 4), it proceeds to the round r i + 1 if r i = rmax i (line 11) or to the round rmax i if r i < rmax i (line 13).

2 Lemma 1

Lemma 2 Let r > 1. If a process p i invokes MEM .store( r, v ) at time τ , then there is a process p j that has invoked MEM .store( r -1, v ) at a time τ < τ .

Proof Let p i be the first process that starts MEM .store( r, v ) and ri the last value of r i before r i = r. There are two cases.

• Process p i executes line 13 and updates r i from ri to r. In that case, p i adopts the pair r, v when it executes that line. If follows that there is a process p j that has previously invoked MEM .store( r, v ) at some time τ < τ . But this contradicts the fact that p i is the first process that invokes MEM .store( r, v ). Hence, this case cannot occur. • Process p i executes line 11 and updates r i from ri = r -1 to r. In that case, p i does not modify est i and consequently it has previously invoked MEM .store( r, v ) at some time τ < τ .

2 Lemma 2

Lemma 3 A decided value is a proposed value.

Proof Let us observe that a decided value is a value that has been written into the atomic register DEC and a process p i can write into DEC only at line 10 where it assigns it the current value of its local variable est i . The proof amounts consequently to show that any est i is assigned only proposed values.

Let us first observe that a local variable est i is initially assigned the value proposed by p i (line 1) from which we conclude that any pair 1, v written into MEM is such that v is a proposed value. The proof follows then directly from Lemma 2.

2 Lemma 3

Lemma 4 No two processes decide different values.

Proof As a decided value is a value that has been written into DEC and a process writes at most once into DEC , the proof consists in showing that distinct processes do not write different values into DEC . Preliminary definitions. Let view r i be the value of view i obtained by p i during round r. Let τ (i, r, b, st) and τ (i, r, e, st) be the time instants at which process p i starts and terminates, respectively, the invocation of the operation store() during round r. τ (i, r, b, c ) and τ (i, r, e, c ) have the same meaning when considering the invocation of the operation collect().

Let r be the first round during which processes write into DEC , p i one of these processes and v the value it writes. Let us observe that, due to line 9, r > 1; hence r -1 exists. We claim that, for any w such that (-, r, w ) is returned by an invocation of collect() we have w = v (Claim C1). It follows (a) from this claim that no process can decide a value different from v at round r and (b) from this claim, Lemma 1 and Lemma 2 that no process ever writes r , w with r > r and w = v. Consequently, no value different from v can be decided which proves the consensus agreement property.

Proof of the claim C1. Let w be any value such that (-, r, w ) is returned by an invocation of collect(). To prove the claim (i.e., w = v), let us consider the following definition given for each value w.

1. Let τ (k w , r w , e, c ) be the first time instant at which a process (let p kw denote this process) returns from an invocation of collect() (let r w denote the corresponding round) and the view it obtains is such that (-, r, w ) ∈ view rw kw . 2. Let j w be a process index such that (j w , r, w ) ∈ view rw kw (hence p jw invokes store( r, w )).

We claim that (a) p jw executes round r -1, and during that round (b) invokes store( r -1, w ) and (c) executes line 11, i.e., it executes r jw ← r jw + 1 (Claim C2 whose proof is given below).

To prove the claim C1, let us consider any process p i that writes into DEC at round r (the first round during which processes write into DEC ). This process obtained view r i when it invoked collect() at round r. Considering any value w and its associated process p jw as previously defined, we analyse the different cases which can occur according to value r such that (j w , r , v ) ∈ view r i or the fact that no pair (j w , -) belongs to view r i . • (j w , r , -) is such that r > r. This case is not possible because otherwise we would have rmax i ≥ r > r when p i executes round r and it would consequently execute line 13 and not line 10 (the line at which it writes into DEC ).

• (j w , r , v ) is such that r = r. In that case, it follows from line 8 and the predicate evaluated by p i at line 9 that we necessarily have v = v. Moreover, as p jw writes at most once in a round (Lemma 1), it follows from the definition of j w (see Item 2 above) that v = w. Hence, w = v. • (j w , r , v ) is such that r = r -1. In that case, it follows from Item (b) of Claim C2 that p jw has invoked store( r -1, w ).

Then the proof is the same as in the previous case, and we have w = v. • (j w , r , v ) is such that r < r -1 or there is no pair (j w , -) in view r i . It then follows from Item (a) of Claim C2 that p jw executes the round r -1 and we have then τ (i, r, b, c ) < τ (j w , r -1, e, st) (otherwise the freshness property of the store-collect object would be violated). According to the sequential code executed by p jw and p i we consequently have τ (i, r, e, st) < τ (i, r, b, c ) < τ (j w , r -1, e, st) < τ (j w , r -1, b, c ).

It then follows from the previous line, the freshness property of the store-collect object and the fact that p i does not write the store-collect object after it has written into DEC , that (i, r, v ) ∈ view r-1 jw . Consequently, p jw reads r,during round r -1, it executes line 13 which contradicts Item (c) of Claim C2 (which states that p jw executes line 11 during round r -1). Hence, this case cannot appear, which concludes the proof of Claim C1.

Proof of the claim C2. Considering the context of Claim C1, C2 states that (a) p jw executes round r -1, and during that round (b) invokes store( r -1, w ) and (c) executes r jw ← r jw + 1.

Let us first observe that r > 1 (because p i does not decide during the first round). As r > 1 and no process skips the first round, p jw executes at least one round r such that 1 ≤ r < r. Let rj be the last of these rounds.

The proof is by contradiction. let us assume that p jw executes line 13 during round rj before proceeding to round r. Due to its definition, p jw invokes store( r, w ) during round r. As it stores the value w = est jw , it follows that during the previous round it has executed (namely round rj ), p jw has updated est jw to w and we conclude that (-, r, w ) ∈ view rj jw . It follows from the definition of p kw (first process that obtains (-, r, w ) in a view) that we have τ (k w , r w , e, c ) ≤ τ (j w , rj , e, c ). Moreover, due to the definition of p kw and p jw (more explicitly, because (j w , r, w ) ∈ view rw kw ) and the validity of the store-collect object, we have τ (j w , r, b, st) < τ (k w , r w , e, c ).

It follows from the two previous inequalities that τ (j w , r, b, st) < τ (k w , r w , e, c ) ≤ τ (j w , rj , e, c ). But this contradicts the fact that p jw executes the round rj before the round r, i.e., the fact that τ (j w , rj , e, c ) < τ (j w , r, b, st). Hence, during the round rj , p jw does not execute line 13 but line 11. Consequently, we have rj = r -1 and p jw does not modify its estimate est jw during the round rj = r -1. Moreover, as p jw has not changed its estimate during round r -1, it has invoked store( r -1, w ) at the beginning of that round.

It follows that p jw (a) executes round r -1 and during that round, (b) invokes store( r -1, w ) and (c) executes r jw ← r jw + 1, which concludes the proof of the claim C2.

2 Lemma 4

Lemma 5 Let assume that the eventual leader elected by Ω participates. Any correct process decides a value.

Proof Let us first observe that, as soon as a process has written a value into DEC , all correct processes decide. Hence, let us assume by contradiction that no process ever writes into DEC . It follows from the definition of Ω, that there is a time τ after which there is a single correct process, say p , such that leader = . Hence, there is a finite time τ ≥ τ after which only p executes the lines 4-15. This means that p executes an infinite number of rounds while each other correct process loops forever but executes a finite number of rounds. Let r be the first round such that p is the only process that executes the rounds r, r + 1, etc. Moreover, let v be the value of est when it starts round r.

It follows that r, v is the only pair r,stored in MEM at round r. Moreover, we have then r = rmax = r and, consequently, p i executes the lines 8-12. If the predicate of line 9 is satisfied, p writes v into DEC which contradicts the fact that it executes an infinite number of rounds. Hence, this predicate is false and p proceeds to the next round and r = r + 1 (line 11). As p is the only process which executes the round r + 1 and est has not been modified, r + 1, v is the only pair that p can store into MEM . As r = rmax = r + 1 when p check the predicate of line 7, it executes the lines 8-12.

As the only pairs r, v and r + 1, v ever stored into MEM are the ones stored by p we have v = v = v i.e., set = {v}. As est has not been modified by p during the rounds r and r + 1, it follows that set = {est } and consequently p executes line 10, a contradiction which concludes the proof of the lemma.

2 Lemma 5

Theorem 1 Let assume that the eventual leader elected by Ω participates. Algorithm 1 is a wait-free implementation of a consensus object in the system model ASM[Ω].

Proof The proof follows from Lemma 3, Lemma 4 and Lemma 5.

4 When the Omega-defined leader does not participate

The problem It is possible that, in some executions, the participating processes decide before an eventual correct leader has been elected by Ω which is consequently useless in these executions. But, there are executions in which Ω is required to ensure the waitfreedom property. This is why the previous construction requires that the correct leader eventually elected by the failure detector Ω participate in the algorithm. This (sometimes left implicit) requirement is common to all the Ω-based constructions of a consensus object, be them designed for shared memory systems (e.g. [START_REF] Delporte-Gallet | Two consensus algorithms with atomic registers and failure detector Ω[END_REF][START_REF] Gafni | Disk Paxos[END_REF][START_REF] Guerraoui | The alpha of indulgent consensus[END_REF] or message-passing systems (e.g., [START_REF] Guerraoui | The information structure of indulgent consensus[END_REF][START_REF] Mostéfaoui | Leader-based consensus[END_REF][START_REF] Raynal | Communication and agreement abstractions for fault-tolerant asynchronous distributed systems[END_REF]).

Hence the question: How to modify Ω in such a way that the eventually common leader that is elected be always a correct participating process?

The failure detector Ω X (eventually restricted leadership) Let X be a non-empty set of processes. The failure detector associated with this set X and denoted Ω X provides each process with a read-only local variable leader i (X) such that the following properties are satisfied.

• Validity. At any time, leader i (X) contains a process index, i.e., leader i ∈ {1, . . . , n}.

• Restricted eventual leadership. If X contains correct processes, there is a finite time τ and a correct process p such that (a) ∈ X and (b) after τ we have forever leader i (X) = for each correct process p i of X.

It is easy to see that Ω Π (Π is the whole set of processes) is nothing else than Ω. Ω X is the instance of Ω customized for the set of processes X. This failure detector has been proposed independently in [START_REF] Guerraoui | The weakest failure detectors to boost obstruction-freedom[END_REF] and [START_REF] Raynal | In search of the Holy Grail: looking for the weakest failure detector for wait-free set agreement[END_REF]. It is used in [START_REF] Guerraoui | The weakest failure detectors to boost obstruction-freedom[END_REF] to boost an obstruction-free object implementation into a non-blocking implementation and it is also shown that this failure detector is the weakest that allows such a boosting. It is used in [START_REF] Raynal | In search of the Holy Grail: looking for the weakest failure detector for wait-free set agreement[END_REF] to solve the k-set agreement problem when the participating processes can be any subset of processes.

Modifying the construction When the participating processes can be any subset of processes, the system is enriched with a failure detector Ω X , for any non-empty subset X ⊆ Π, and Algorithm 1 is modified as follows.

• A new store-collect object, denoted PART and initially empty, is introduced. Moreover, the statement PART .store() is added to line 1 to indicate that, from now on, p i is a participating process. • The statement X ← PART .collect() is introduced between line 3 and 4. Hence, X denotes the set of participating processes as currently known by p i . X is initialized to any non-empty subset of Π (the set of process indexes). • Finally the predicate of line 3 is replaced by leader i (X) = i, i.e., p i checks if it is leader among the processes it sees as participating processes.

The extended construction is correct The fact that this extended algorithm is correct follows from from the correction of the base algorithm plus the following two observations. 1. The fact that two processes p i and p j , while executing the same round r, are such that leader i (X) = i and leader j (X ) = j with X = X , does not create a problem. This is because the situation is exactly as if X = X and Ω X has not yet stabilized to a single leader. Hence, the consensus safety property cannot be compromised. 2. The consensus termination property cannot be compromised for the following reason. There is a finite time after which each participating process p i has executed PART .store() . When, this has occurred, All the correct participating processes have the same set X and, due to the restricted eventual leadership property of Ω X , one of them will be elected as their common leader.

Conclusion

This paper was motivated by the use of store-collect objects to build a consensus object. It has presented such an algorithm based on a single store-collect object in which a value stored by a process is a simple pair made up of a round number and a proposed value. Due to the fact that it uses a single store-collect object, the algorithm is practically interesting. Moreover, as it can benefit from the adaptive wait-free implementations that have been proposed for store-collect objects and it directs processes to skip rounds (thereby saving "useless" computation), this consensus algorithm is also particularly efficient and relevant for practical implementations. These features, together with its simplicity, make it attractive for multiprocess programs made up of asynchronous crash-prone processes that run on top of multicore architectures.

An alpha object has a single operation denoted deposit() which takes a value and a round number as input parameters and returns a proposed value or a default value ⊥ indicating that the current invocation is aborted. Round-based abstraction means that the specification of deposit() involves the round number which is passed as a parameter.Collection des Publications Internes de l'Irisa c IRISA

Which means that its specification does not depend on round numbers.

Due to the distributed nature of the computation and the possibility of failures, such dynamic object creations are much more difficult to manage than iterative or recursive objects creation in sequential or parallel failure-free computing.Collection des Publications Internes de l'Irisa c IRISA

In the algorithm proposed in Section 3 a value val is a pair made up of a round number r and a proposed value v. To prevent confusion, the notation (-, -) is used for a pair written into a store-collect object, while the notation -,is used for a pair val.

Collection des Publications Internes de l'Irisa c IRISA

As we will see, this is exactly what does occur in the proposed algorithm after Ω elects forever the same correct process.

In an adopt-commit-based algorithm each process that executes rounds does execute the predetermined sequence of rounds numbered 1, 2, etc., while, in an alphabased algorithm each process p i that executes rounds does execute the predetermined sequence of rounds numbered i, i + n, i + 2n, etc.Collection des Publications Internes de l'Irisa c IRISA


François Malgouyres
email: francois.malgouyres@math.univ-toulouse.fr

Nicolas Lermé
email: nicolas.lerme@lipn.univ-paris13.fr

Non-heuristic reduction of the graph in graph-cut optimization

During the last ten years, graph cuts had a growing impact in shape optimization. In particular, they are commonly used in applications of shape optimization such as image processing, computer vision and computer graphics. Their success is due to their ability to efficiently solve (apparently) difficult shape optimization problems which typically involve the perimeter of the shape. Nevertheless, solving problems with a large number of variables remains computationally expensive and requires a high memory usage since underlying graphs sometimes involve billion of nodes and even more edges. Several strategies have been proposed in the literature to improve graph-cuts in this regards. In this paper, we give a formal statement which expresses that a simple and local test performed on every node before its construction permits to avoid the construction of useless nodes for the graphs typically encountered in image processing and vision. A useless node is such that the value of the maximum flow in the graph does not change when removing the node from the graph. Such a test therefore permits to limit the construction of the graph to a band of useful nodes surrounding the final cut.

Introduction

Shape optimization is a field which has many practical applications. Among shape optimization methods, graph-cut methods have recently received a growing interest because of their ability to minimize pairwise Markov Random Fields of the form

E(u) = β p∈P E p (u p ) + (p,q)∈(P×P) E p,q (u p , u q ), β ∈ R + , (1)
among u ∈ {0, 1} P , for a set of pixels P ⊂ Z d and for a positive integer d. Indeed, when the terms E p,q (.) are submodular, Kolmogorov and Zabih (see [1]) give a way to build a graph such that for any S ⊂ P, we have val

G (S) = E(u S ) + K, (2)
for some constant K ∈ R (irrelevant in the current minimization context), for u S ∈ {0, 1} P defined for all p ∈ P by

u S p = 1 , if p ∈ S, 0 , if p ∈ S, , (3)
and val G (S) is the value of the cut defined by S ⊂ P (see next section for a precise definition).

Moreover, since (3) makes a one to one correspondence between cuts and elements of {0, 1} P , we trivially obtain from (2) that to any minimum cut (min-cut) in G corresponds a minimizer of (1) and vice versa. Moreover, a min-cut can efficiently be computed with a maximum flow (max-flow) algorithm such as the one described in [2].

One drawback of graph-cuts is that the graph contains as many nodes as the number of pixels and that its number of edges behaves like

O   p∈P #σ(p)   ,
where #σ(p) is the number of neighbors of a pixel p ∈ P (see Section 2 for a detailed description of the graph). Such a memory requirement is a strong limitation when minimizing (1) for #P large and/or for d large (#σ(p) typically grows like a radius raised to the power d...)

Except some exact methods [3,[START_REF] Strandmark | CVPR[END_REF][START_REF] Lempitsky | CVPR[END_REF], the heuristics generally fail to accurately preserve thin structures [START_REF] Lombaert | [END_REF]7,8,9,10]. As previous band-based strategies [START_REF] Lermé | A reduction method for graph cut optimization[END_REF]8,[START_REF] Lempitsky | CVPR[END_REF]7,[START_REF] Lombaert | [END_REF], the nodes are typically located in a narrow band surrounding the object edges.

In this paper, we propose not to build any node satisfying a local test. This test is similar to the ones in [START_REF] Lermé | ICIP[END_REF][START_REF] Lermé | A reduction method for graph cut optimization[END_REF]. The nodes that fail to comply with the test are built in the reduced graph. The difference with the results stated in [START_REF] Lermé | ICIP[END_REF][START_REF] Lermé | A reduction method for graph cut optimization[END_REF] is that the test has been slightly modified in order to obtain a formal statement guaranteeing that the value of the max-flow in the reduced graph is equal to the value of the max-flow in the initial graph. As a consequence, any max-flow in the reduced graph is also a max-flow in the initial graph and the cut defined by this flow is a min-cut in the initial graph. In other words, despite the graph reduction, the max-flow algorithm still permits to build a minimizer of E.

The proof of the result presented in this paper as well as experiments are provided in [START_REF] Lermé | Réduction de graphes et application la segmentation de tumeurs pulmonaires[END_REF] and will also be submitted for publication in a long version of the current paper.

Definition of the graph

The graph constructed in [1] has the form described below. This constitute the main motivation for considering this graph structure.

We consider two terminal nodes s and t and the set of nodes

V = P ∪ {s, t}.
We consider a set of directed edges E ⊂ (V × V) such that (V, E) is a simple directed graph. We also assume that for every p ∈ P, (p, s) ∈ E and (t, p) ∈ E.

We denote the neighbors of any nodes p ∈ V by σ E (p) = {q ∈ V, (p, q) ∈ E or (q, p) ∈ E}.

We define the capacities as a mapping c : (V × V) → R + and denote the capacity of any edge (p, q) ∈ (V × V) by c p,q ≥ 0.

Notice that usually, the capacities are only defined over E. We extend their definition to (V × V) in order to simplify notations. This extension is performed by setting c p,q = 0, whenever (p, q) ∈ E.

We assume, without loss of generality (see [1]), that capacities are such that for every p ∈ P c s,p = 0 ⇒ c p,t = 0.

We therefore summarize the capacities of the edges linked to the terminal nodes and set for all p ∈ P c p = c s,pc p,t .

For any S ⊂ P, we denote by val G (S) the value of the s-t cut (S ∪ {s}, (P \ S) ∪ {t}) , in G.

We also define flows in the graph as any mapping f : (V × V) → R + satisfying both the capacity constraints 0 ≤ f p,q ≤ c p,q , for all (p, q) ∈ (V × V),

and the flow conservation

q∈σ E (p) f q,p = q∈σ E (p)
f p,q , for all p ∈ P.

We have not clarified that (q, p) ∈ E (resp. (p, q) ∈ E) in the above left (resp. right) summation. This is because, ( 4) and ( 5) guarantee that f p,q = 0, whenever (p, q) ∈ E.

As usual, the value of the flow f in G is defined by

val G (f) = p∈σ E (s) f s,p . (7)
Notice that we use the same notation for the value of a flow and the value of a s-t cut in G. This abuse of notation will never be ambiguous, once in context. We call max-flow any solution f * of the linear program max f val G (f) , under the constraints ( 5) and ( 6).

In the sequel, we also consider a subset B ⊂ Z d and assume that B and G are such that

∀p ∈ P, (σ E (p) ∩ P) ⊂ B p , (8)
where

B p = {p + q, q ∈ B}. (9)
In practice, we typically think of B as a ball centered at the origin. In such a case, (8) means that neighbors in the graph G are close to each other in Z d .

Main result of the paper

Before stating the main result of the paper, we remind the convention that the summation over an empty set of indexes is null. More precisely, whatever (a p,q ) (p,q)∈V×V ∈ R V×V , (p,q)∈∅ a p,q = 0.

Theorem 1 Let G be a graph as defined in Section 2, let B satisfy (8) and let us assume that p ∈ P satisfies either ∀q ∈ B p , c q ≥ q ′ ∈Bp c q,q ′ , or ∀q ∈ B p , c q ≤q ′ ∈Bp c q ′ ,q .

Then, there exists a max-flow f in G such that ∀q ∈ σ E (p), f p,q = f q,p = 0.

As a consequence, removing the node p from the graph G does not modify its max-flow value.

Algorithmically, the above theorem guarantees that we can test every node, during the graph construction, before it is added to the graph. If the node satisfies (10), it is not useful to the max-flow evaluation. It can therefore be removed from the graph G without modifying its max-flow value.

Let us describe the meaning of the test corresponding to the upper line of (10). For every node q in B p

• either q is inside B p in which case, for all q ′ ∈ B p , c q,q ′ = 0 and the test simply becomes c q ≥ 0. • or q is on the border of B p and then the test takes the form c q ≥ q ′ ∈Bp c q,q ′ ≥ 0 and is generally more difficult to satisfy. Notice also that a similar theorem with the test either ∀q ∈ B p , c q ≥ q ′ ∈σ E (q) c q,q ′ , or ∀q ∈ B p , c q ≤q ′ ∈σ E (q) c q ′ ,q , is easy to obtain. The two results should not be confused.

Let us now describe how to build the minimizer of (1), once the minimum cut S ∪ {s} , (P \ {p}) \ S ∪ {t} ,

where S ⊂ (P \ {p}), has been computed in the graph from which the node p satisfying (10) has been removed. The minimizer u * ∈ {0, 1} P of (1) is defined by

u * r =       
1 , if r = p and ∀q ∈ B p , c q ≥ q ′ ∈Bp c q,q ′ , 0 , if r = p and ∀q ∈ B p , c q ≤q ′ ∈Bp c q ′ ,q , 1 , if r = p and r ∈ S, 0 , if r = p and r ∈ S.


Heiba Zaghloul

Bharat Bhushan

Patrick Pons

George Papaioannou

Fabio Coccetti

Robert Plana

U Zaghloul

Nanoscale characterization of different stiction mechanisms in electrostatic RF-MEMS switches

Keywords: Stiction, dielectric charging, RF-MEMS switch, adhesion force, force-distance, field-induced meniscus I

  L'archive ouverte pluridisciplinaire

INTRODUCTION

In spite of the outstanding performance of capacitive RF-MEMS switches, their commercialization is still hindered by reliability issues [START_REF] Rebeiz | RF MEMS theory, design, and technology[END_REF]. Among various reported reliability concerns for electrostatic capacitive MEMS switches, the dielectric charging and its resulting stiction is considered the main failure mechanism of these devices [START_REF] Czarnecki | Effect of substrate charging on the reliability of capacitive RF MEMS switches[END_REF]. On the other hand, capillary condensation of water vapour results in the formation of meniscus bridges between contacting and nearcontacting asperities of two surfaces in close proximity to each other. This leads to an intrinsic attractive force which may lead to high adhesion and stiction [START_REF] Bhushan | Nanotribology and Nanomechanics -An Introduction[END_REF]. The meniscus formation is also reported to be highly affected by the electric filed [START_REF] Gómez-Monivas | Fieldinduced formation of nanometer-sized water bridges[END_REF][START_REF] Sacha | Induced water condensation and bridge Formation by electric fields in Atomic Force Microscopy[END_REF]. Thus, the applied bias used to actuate MEMS switches and the resulting dielectric charging are expected to affect the meniscus formation at the interface between the switch bridge and the dielectric film. Therefore, the adhesion or stiction between the switch bridge and the dielectric film could be also affected by the meniscus formation. The individual impact of the two different stiction mechanisms (charging induced and meniscus force induced) and their interaction under different electrical stress conditions and relative humidity levels are not understood and have not been studied before.

In this study a novel characterization technique is presented in order to study different stiction mechanisms which exist in MEMS switches. The proposed methodology makes use of the AFM tip in order to simulate a single asperity contact with the dielectric surface [START_REF] Zaghloul | A systematic reliability investigation of the dielectric charging process in electrostatically actuated MEMS based on Kelvin probe force microscopy[END_REF][START_REF] Zaghloul | Nanoscale characterization of the dielectric charging phenomenon in PECVD silicon nitride thin films with various interfacial structures based on Kelvin probe force microscopy[END_REF]. For the first time the adhesive force measured on the nanoscale under different relative humidity levels and electrical stress conditions is presented. The induced surface potential over the dielectric surface was measured, and used in order to explain the obtained results. Force-distance measurements was performed on the nanoscale and are used to measure the adhesive force. The individual and combined influence of the meniscus force and dielectric charging on adhesive force was studied. This provides an accurate evaluation of the individual effect of each stiction mechanism. Finally, a correlation between the obtained nanoscale results and the literature reported data from MEMS switches measurements, was performed .

II. EXPERIMENTAL DETAILS

The investigated samples consist of PECVD SiN x films with 300 nm thickness deposited over 500 nm Au layers, which were evaporated over Si substrates (see sub figure in Fig. 1). Since no photolithography steps are required in order to prepare the required samples, the proposed technique provides a low cost and quite fast assessment solution compared to other characterization methods. The adhesion experiments were performed under different relative humidity levels in order to study the effect of meniscus force. For each humidity level, the adhesive force was measured while different bias amplitudes were applied to the Au layer underneath the SiN x film. Due to the dielectric charging, the SiN x film is charged and this results in an induced surface potential over the dielectric film. The applied bias, therefore, corresponds to the voltage used to actuate the MEMS switch and/or the induced surface potential over the dielectric film due to the dielectric charging.

Force-distance measurements were used to measure the adhesive force between the AFM tip and the SiN x film as well as the adsorbed water film thickness over the SiN x surface [START_REF] Bhushan | Nanotribology and Nanomechanics -An Introduction[END_REF]. An example of the force-distance curve for the investigated samples is presented in Fig. 1. The force-distance measurement starts at a large separation (point A) where there is no deflection of the cantilever. As the piezo moves towards the sample, a sudden mechanical instability occurs between point B and point C, and the tip jumps into contact with the adsorbed water film and wicks up around it to form a meniscus. The cantilever bends downwards because of the attractive meniscus force acting on the tip. As the piezo further approaches the SiN x surface, the deflection of the cantilever increases while the tip travels in the water film and eventually contacts the underlying SiN x surface at point C, and then the cantilever starts to bend upwards. Once the piezo reaches the end of its designated ramp size at point D, it is retracted to its starting position. The tip goes beyond zero deflection (point E) and enters the adhesion region. At point E, the elastic force of the cantilever becomes equivalent to the adhesive force, causing the cantilever to snap back to point F. The piezo travel distance used in this study is 500 nm which is comparable to the air gap of MEMS switches.

The adhesive force, which is the force needed to pull the tip away from the sample, can be calculated from the force distance curve by multiplying the vertical distance between E and F with the stiffness of the cantilever as explained in Fig. 1. Also, as the tip travels in the adsorbed water film from point B to C, it is deflected as well. The tip deflection occurs in the same direction as the piezo travels for the AFM used in this study. The water film thickness is therefore the sum of the travel distance of the piezo (h 1 ), and the deflection of cantilever (h 2 ) as highlighted in Fig. 1[3].

III. RESULTS AND DISCUSSION

A. Effect of meniscus formation when no bias is applied

Figure 2 shows that the adhesive force increases considerably when the relative humidity (RH) increases from 1% to only 20%, and the increase tends to saturate at larger RH. The measured thickness of the adsorbed water film over the SiN x surface also increases with humidity as highlighted in the figure. The increase of the water film thickness enhances the meniscus formation, and consequently results in increasing the adhesive force. Though the measured increase in the water film thickness when increasing RH from 1% RH to 80% RH is found to be relatively small, the adhesive force increases considerably. In addition, when the RH increases, the meniscus becomes easier to form and more difficult to rupture [START_REF] Yumei | Capillary liquid bridges in atomic force microscopy: Formation, rupture, and hysteresis[END_REF]. This leads to stronger attractive capillary force between the tip and the sample, and hence larger adhesive force with increasing the RH. The considerable change in the adhesive force when RH increases to only 20% indicates that the SiN x material is very sensitive to any tiny amount of water molecules adsorbed over its surface.

B. Effect of applied bias on adhesive force

In order to validate the force-distance curve experiments under different applied bias, it was first applied to measure the adhesive force over a charged dielectric film implemented in electrostatic capacitive MEMS switches. MEMS switches with high frequency (HF) PECVD deposited silicon nitride films of 300nm thickness were used for this experiment (Fig. 3a). The switch was actuated first for 2 min using 40 V. Then, the suspended Au bridge was removed in order to make the SiN x surface naked. The force-distance measurements were used to then measure the adhesive force in different positions over the dielectric film. Figure 3b shows the obtained adhesive force map for the scanned area over the SiN x charged surface (right) and the corresponding optical image for the suspended Au bridge over this area (left). It is obvious from the adhesive map that the adhesive force in the contact areas is much larger compared to the etch holes positions, and therefore the holes' locations can be easily identified. This is because charge injection takes place in contact areas where it does not occur in holes positions. The correlation between the etch holes positions in the adhesive force map and in the optical image of the suspended electrode is quite clear. The separate and combined effect of the two mentioned stiction mechanisms were studied by using three different groups of samples (A, B, and C). Group A and B were dehydrated just before performing the experiments through two cycles of heating (150 °C) and cooling steps under vacuum. This removes a considerable amount of the adsorbed water over the dielectric surface. Then, group A was measured under a very low RH level (1%), while group B was stored under high RH (60%) for 60 min, and then was measured under 60% RH. Group C was not dehydrated, and was measured under a low humidity level (1%) similar to group A. The thickness of the adsorbed water layer for group A is therefore smaller than groups B and C. Consequently, the contribution of the meniscus force to the measured adhesive is expected to be much smaller for group A compared to groups B and C. Comparing groups A and B, the influence of the water molecules adsorbed during a time duration of 60 min under high relative humidity (60%) could be assessed. Also, the comparison between groups A and C reveals the influence of the annealing step.

Figure 4 presents the measured adhesive force under different applied bias for the three mentioned sample groups (A, B, and C). For the three groups, the adhesive force is found to increase with the applied bias as shown in Fig. 4a. This increase is attributed to the increase in the attractive electrostatic force between the AFM tip and the SiN x surface as the applied bias increases. In addition, the increase in the adhesive force with bias is found to be very small for group A compared to groups B and C. In these experiments, the adhesive force was measured while the bias is applied between the AFM tip and the sample. So, the SiN x film is charged, and this results in an induced potential over the dielectric surface which reduces the effective applied bias between the AFM tip and the sample. The induced surface potential for the three groups of samples were measured, and the effective applied bias is calculated, and the results are plotted in Fig. 4a. Figure 4a highlights that for a given applied bias, the effective bias is much smaller for group B compared to group A. Therefore, the electrostatic attractive force for group B is much smaller than group A for all investigated applied bias. In spite of that, the adhesive force measured under different bias for group B is found to be much larger compared to group A. The measured adhesive force as a function of the effective bias is shown in Fig. 4b. It is evident from the figure that at the same effective bias, hence the same electrostatic force, the adhesive force for group B is much larger compared to group A. Also the increase in the adhesive force with the effective bias is much higher for group B compared to group A. Therefore, the difference in the trend of the adhesive force versus the applied bias between both groups cannot be attributed to the electrostatic attractive force. Additionally, the relatively small difference in the adhesive force between the two groups when no bias is applied clearly indicates that the large difference between both groups at higher bias cannot be explained by the liquid mediated meniscus formation. Since the individual impact of the attractive electrostatic force and the liquid mediated meniscus formation does not explain the high difference in the adhesive force between groups A and B, there must be other adhesion mechanisms.

There are different mechanisms behind the meniscus formation as shown in Fig. 5. When mechanical instability occurs (between points B,C in Fig. 1), the tip jumps into contact with the adsorbed water film and wicks up around it to form a meniscus (Fig. 5a). This is called liquid mediated meniscus. It has been also reported that the adsorbed water film between the AFM tip and the sample surface grows under the influence of the electric field, forming a meniscus that becomes unstable when a critical field is reached [START_REF] Gómez-Monivas | Fieldinduced formation of nanometer-sized water bridges[END_REF][START_REF] Sacha | Induced water condensation and bridge Formation by electric fields in Atomic Force Microscopy[END_REF]. At this point, the meniscus suddenly forms a bridge between the tip and surface as shown in Fig. 5b. This is called a field-induced meniscus. A modeling study shows that the height of the water film under the tip almost doubles upon the formation of the field-induced meniscus [START_REF] Gómez-Monivas | Fieldinduced formation of nanometer-sized water bridges[END_REF]. Therefore, the increase in the water film thickness caused by field-induced meniscus is much higher compared to the increase in the water film thickness caused by increasing the relative humidity (see Fig. 2). Also, due to the attraction of water molecules towards the tip under the electric field, the volume of the meniscus surrounding the tip will increase considerably. This leads to the conclusion that the field-induced meniscus and its resulting considerable increase in the water film volume surrounding the tip will result in increasing the adhesive force between the AFM tip and sample surface considerably. Also, the influence of the field-induced meniscus on the adhesive force is expected to be much higher compared to the liquid mediated meniscus formed when no bias is applied. The threshold voltage required to induce the formation of water bridges between a metallic tip and a flat metallic sample is given by [START_REF] Sacha | Induced water condensation and bridge Formation by electric fields in Atomic Force Microscopy[END_REF] where D is the distance at which the field-induced meniscus forms, and RH is the employed relative humidity. Based on Eq. 1, for a given tip-sample separation, the required threshold field for the formation of water bridges decreases considerably when the relative humidity increases. For example, at 5 nm tipsample separation, the calculated value of V th for RH of 1% and 60% are found to be 24.7 V and 8.2 V, respectively. Effective bias (V)

) / 1 ln( 5 . 3 RH D V th  (1)
Figure 4b shows that for sample group B the adhesive force increases considerably at relatively small effective bias (around 5 V), and this increase is attributed to the field-induced meniscus formation. The considerable increase in adhesive force indicates obviously that the threshold field required to induce the formation of liquid bridges between AFM tip and the SiN x surface has been reached. This is supported by the small calculated value of the threshold voltage at 60% RH from Eq. 1 which is 8.2 V. In addition, higher RH would lead to a stronger attractive capillary force since the adhesive force becomes longer ranged as explained earlier. According to that, the field-induced meniscus can persist at a longer tip-sample separation before bridge rupture [START_REF] Yumei | Capillary liquid bridges in atomic force microscopy: Formation, rupture, and hysteresis[END_REF]. Therefore the adhesive force measured at 60% RH (group B) will increase considerably by the field-induced meniscus formation. For group A of samples, the maximum effective bias is found to be larger compared to group B as shown in Fig . 6d. In spite of that the increase in the adhesive force with the effective bias for group A is found to be smaller compared to group B. This indicates that for group A the threshold field required for the field-induced meniscus has not been reached by the range of applied bias used in these experiments. Comparing the adhesive force for groups A and B at higher bias, it can be concluded that at higher RH levels the adhesive force resulting from the field-induced meniscus is much higher compared to the adhesive force caused by the attractive electrostatic force and/or the liquid mediated meniscus.

Two categories of capacitive MEMS switches (switch-A and switch-B) are assumed, which employ the sample groups A and B. When no bias is applied and assuming that the surfaces of both the dielectric film and the switch bridge come in contact with each other, the interface will look like Fig. 6a and Fig. 6b for switch-A and switch-B, respectively. The figures shows that the interfaces of both switches have many contacting and near-contacting asperities. Also the liquid mediated meniscus in switch-B is much higher than switch-A.

When bias is applied in order to actuate the switch, fieldinduced meniscus will be formed in the positions of contacting and near-contacting asperities for switch-B (Fig. 6d). This might also occur in switch-A if the actuation voltage is large enough to reach the threshold voltage (Fig. 6c). Under any condition, the formation of the field-induced meniscus will be much higher in switch-B compared to switch-A, similar to the obtained results for samples B and A. This results in the formation of a water meniscus between the near-contacting asperities in switch-B as shown in Fig. 6d. Also, the volume of liquid mediated meniscus previously formed at the contacting asperities will increase in switch-B. When the applied bias is removed, the adhesive force between the switch bridge and the dielectric layer occurs under the effect of induced surface potential over the dielectric surface. Since the induced surface potential in sample B is much larger compared to sample A (Fig. 2), the enhancement of the field-induced meniscus in switch-B is much larger compared to switch-A. Also, the attractive electrostatic force in switch-B will be much higher compared to switch-A. Based on this analysis, the adhesive force between the switch bridge and the dielectric film will be much larger in switch-B compared to switch-A.

Based on the previous analysis, the adhesion or stiction between the switch bridge and the dielectric will be much faster in switch-B compared to switch-A. This explains why MEMS switches operated at larger RH have shorter lifetimes as reported in [START_REF] Van Spengen | The influence of the package environment on the functioning and reliability of RF-MEMS switches[END_REF]. For switch-B, the main mechanism behind the stiction is the field-induced meniscus formation which is enhanced by the dielectric charging phenomenon. For MEMS switch-A, if the induced surface potential reaches the critical threshold, field-induced meniscus will be formed, and the high resulting adhesive force will cause the switch stiction. If the induced surface potential in the long time range does not reach the threshold voltage, the stiction will be caused by the electrostatic attractive force. Figure 2 also highlights that the increase in the adhesive force with the applied bias for sample group C is much higher compared to group A. The effective applied bias, hence, the electrostatic force, is relatively smaller for group C compared to group A. Therefore the higher increase rate of adhesive force with the applied bias for group C compared to group A is attributed to the field-induced meniscus formation. Once again, two types of MEMS switches are assumed, switch-A and switch-C, which resembles the investigated samples A and C, respectively. When bias is applied to actuate switch-C, the volume of the meniscus surrounding the contacting asperities will increase due to the field-induced meniscus formation (Fig. 6d). Also, bridging the near-contacting asperities by water will be further supported by the field-induced meniscus in switch-C. This is because the gap between the near-contacting asperities will be smaller due to the thicker water film in switch-C, and therefore the threshold voltage will be smaller. In other words the field-induced meniscus formation is expected to be much higher in switch-C compared to switch-A. Based on this analysis the stiction between the switch bridge and the dielectric film for switch-C will be much faster compared to switch-A. This explains why annealing MEMS switches increases the device lifetime as reported in [START_REF] Czarnecki | Effect of substrate charging on the reliability of capacitive RF MEMS switches[END_REF].

IV. CONCLUSION

The individual impact of the charging induced stiction and meniscus induced stiction in electrostatic capacitive RF-MEMS switches is presented. Also, the interaction between both stiction mechanisms was investigated. The adhesive force resulting from the field-induced meniscus is found to be a dominant stiction mechanism. The adhesive force induced by meniscus formation due to the adsorbed water layer is found to be relatively small when the dielectric layer is not electrically stressed. When bias is applied, the adhesive force increases considerably for dielectric films which have not been annealed even after being measured at a very low humidity level, due to the field-induced meniscus. For the annealed samples, the contribution of the field-induced meniscus is found to be very high when the sample is stored under larger relative humidity for a short time. The nanoscale characterization performed in this study explains well why MEMS switches operated at larger relative humidity have shorter lifetimes. Also, it explains why annealing MEMS switches increases the device lifetime.

Figure 1 .

 1 Figure 1. Force-distance curve for the investigated samples.

Figure 2 .

 2 Figure 2. The influence of the relative humidity on adhesive force and adsorbed water film thickness.

Figure 3 .

 3 Figure 3. Adhesive force map obtained using the force-distance curve tecnique for a charged dielectric film implemented in MEMS switch.

Figure 4 .

 4 Figure 4. The impact of applied bias on adhesive force.

Figure 5 .

 5 Figure 5. Different mechanisms of meniscus formation between the AFM tip and the sample surface.

Figure 6 .

 6 Figure 6. A cartoon showing the meniscus formation at the interface between the switch bridge and the dielectric film for MEMS switches.


Patrick Pons
email: ppons@laas.fr

Hervé Aubert

Philippe Menini

Manos Tentzeris

Wireless Passive Autonomous Sensors with Electromagnetic Transduction

Keywords: wireless sensor, passive sensor, electromagnetic transduction, radar interrogation I

Wireless sensors market is growing very fast these last years tanks to the availability of cheap, small and efficient micro-sensors, batteries, analog and RF circuits, and to the presence of standardized communication protocols. Even if these active sensors are very attractive for a lot of applications, they suffer from weak energy autonomy and they are not compatible with harsh environment. In order to overcome these problems, we have developed a new kind of wireless sensors using electromagnetic transducers and radar interrogation. These passive sensors (battery-less and without electronic components) have been studied for pressure, temperature and gas applications.

INTRODUCTION

Since late 1999, "Ambient Intelligence" (also called or "Internet of Thinks") is the subject of intense research in the world with the objective to interconnect many objects like sensors, actuators, tags, mobile phones, …. [START_REF] Atzori | The Internet of Things: A survey[END_REF][START_REF]Internet of Things in 2020 : A roadmap for the future[END_REF]. These entire new intelligent objects will have the possibility to give information about its environment and to share this information on the basis of wireless telecommunications. In this context, wireless sensors appear as a key technology for a lot of applications both in domestics and industrials fields as, e.g. healthcare, intelligent home, environment, structural health monitoring, agriculture and food monitoring. [START_REF] Sardini | Passive and Self-Powered Autonomous Sensors for Remote Measurements[END_REF][START_REF] Ruiz-Garcia | A Review of Wireless Sensor Technologies and Applications in Agriculture and Food Industry: State of the Art and Current Trends[END_REF][START_REF] Alemdar | Wireless sensor networks for healthcare: A survey[END_REF].

One can divided wireless sensors technologies into two main classes: active sensors which require power source and passive sensors that are battery-free.

Active sensors can be described by three different functional parts: a transducer which converts the input to be analysed into electrical signal, electronic circuits for the signal conditioning and a communication unit for data transmission (Figure 1). The power source, supplied by an embedded battery, is the key limiting factor for the sensor autonomy. This drawback can be reduced using rechargeable battery coupled with harvesting module. Nevertheless the sensor life time is driven by embedded quantity of energy (mainly the battery size), the data transmission rate and the interrogation distance. However very long interrogation distance (up to several hundred of meters) can be achieved with this technology. Solutions also exist without battery, called semi-active, where harvested power is directly supplied to transducer and electronic circuits through dedicated electronic converter. In this case the reading distance is reduced to several meters and the data transmission rate is low. Then, despite the disadvantages of this kind of active sensors, a lot of companies propose now wireless active sensor products (with or without battery) that are suitable for different applications. That was made possible by the availability on the market of low cost and efficient (low consumption, low size) transducers, electronic circuits (from DC to RF) and batteries but also the availability of standardized transmission protocol (Wifi, Zigbee, ..). The main research studies in this field to increase the active sensor autonomy are concentrated on the development of new energy micro-source with high power (electrochemical, nuclear, thermo-electric, thermo-ionic, …), high efficiency of energy harvesting (solar, vibration, thermoelectric, Radio-Frequency, ..) and low consumption electronic circuits. Otherwise, passive sensors can be described by two main parts : a passive transducer with only passive elements and a remote reader capable to analyze the transducer response (Figure 2). The wireless communication between the two parts can exploit electric, magnetic, electromagnetic, acoustic or optic link. The most popular are magnetic and electromagnetic links, related to the availability of several solutions for electronic readers. Inductive coupling is used generally with capacitive sensors in order to realize LC resonator, but the main drawback of this technique is the very short reading distance (few centimeters).

Reader

Input to be analyzed

Electromagnetic interrogation, based on the analysis of backscatter wave by the transducer, allows overcoming this limitation. The first sensors using this electromagnetic interrogation are Surface Acoustic Wave (SAW) sensors [START_REF] Springera | Wireless identi®cation and sensing using surface acoustic wave devices[END_REF][START_REF] Oh | SAW based passive sensor with passive signal conditioning using MEMS A/D converter[END_REF][START_REF] Wen | A Novel Dual Track SAW Gas Sensor Using Three-IDT and Two-MSC[END_REF][START_REF] Friedt | A wireless interrogation system exploiting narrowband acoustic resonator for remote physical quantity measurement[END_REF]. These sensors are based on piezoelectric substrate on which inter-digital electrodes, connected to an antenna, allow converting the electromagnetic waves into acoustic waves (for the input signal) and acoustic waves into electromagnetic waves (for the output signal). The reader generally analyzes the propagating time inside the piezoelectric transducer that is related to the acoustic wave velocity inside the piezoelectric material. As this velocity is modified by temperature and stress but also by thin layers at the piezoelectric material surface, it is possible to realize different kind of sensors (temperature, stress, pressure, gas, biological) depending on materials and design choices. Nevertheless these sensors suffer from the low efficiency of the coupling coefficient between electromagnetic and acoustic waves (between 0.1% to 5%) leading to reading distance lower than 10 meters.

In order to overcome these low coupling rates, we have chosen to realize full electromagnetic transducers. The principle of electromagnetic transduction is based on the modification of the electromagnetic descriptor (as, e.g. the resonant frequency of a millimeter-wave resonator) by the phenomena one wants to measure. This modification can be obtained by the variation of the electromagnetic propagation medium surrounding the resonator. There are two main possibilities to affect this propagation. The first one is to move a mechanical part close to the resonator. The second one is based directly on the modification of the electrical permittivity of the material used to fabricate the resonator. With these two main principles, a lot of sensors can be developed as physical and chemical sensors.

In the following, we give examples of sensors with electromagnetic transduction we are working on.

II. PRESSURE SENSOR

We started this study in 2005 and details about obtained results can be found in references [START_REF] Jatlaoui | Radio Frequency Pressure Transducer[END_REF] to [START_REF] Jatlaoui | Phenomenological theory and experimental characterizations of passive wireless EM pressure micro-sensor prototype[END_REF]. The sensor we developed is based on a planar halfwavelength resonator coupled with a high resistivity silicon membrane (Figure 3). When the silicon membrane is far away from the resonator, the electromagnetic propagation medium of the resonator is only built by Pyrex (underneath resonator) and air (above resonator). From a given air gap between the silicon membrane and the resonator, evanescent waves start to couple with silicon membrane modifying strongly the effective permittivity of the medium (Figure 4) and then the resonant frequency of the resonator (Figure 5).

The sensor has been fabricated using classical microtechnology process and characterized with a specific pressure probe module allowing on wafer S 21 parameters. The sensor exhibits a very high sensitivity close to 0.37GHz/bar (Figure 6).

More recently, passive pressure sensors with other resonator types have been published, but with lower sensitivity [START_REF] Thai1 | A Novel Front-End Radio Frequency Pressure transducer based on a Dualband Resonator for Wireless Sensing[END_REF][START_REF] Amr Ibrahim | Passive single chip wireless microwave pressure sensor[END_REF][START_REF] Senior | Wireless passive sensing application using a cavity loaded evanescent mode half mode substrate integrated waveguide resonator[END_REF]. Resonant frequency (GHz) We started this study in 2009 in collaboration with Georgia Institute of Technology and more details are given in [START_REF] Thai | A Novel Passive Wireless Ultrasensitive Temperature RF Transducer for Remote Sensing[END_REF][START_REF] Thai | A Novel Passive Ultrasensitive RF Temperature Transducer for Remote Sensing and Identification utilizing Radar Cross Sections Variability[END_REF][START_REF] Thai | Design and development of a millimetrewave novel passive ultrasensitive temperature transducer for remote sensing and identification[END_REF]. No similar works have been found in literature up to now.

The temperature transducer consists of split ring resonators fabricated on top side of substrate and excited by a coplanar transmission line located on wafer back side (Figure 7). The slits of the rings are covered with bimorph micro-cantilevers whose layers are made from two different materials. A temperature shift induces the cantilever deflection and then a modification of the coupling capacitance between the two arms of the ring, which leads to the change of the resonant frequency.

The principle has been validated at 30GHz by simulation with a 500µm-thick Pyrex substrate and with uniform displacement of a purely metallic cantilever (Figure 8). The sensor exhibits a very high sensitivity close to 2.6GHz/µm.

To overcome technological problems, a demonstrator has been first fabricated at 3GHz using classical technology. The rings and the coplanar line are deposited on a 787µm-thick Neltec substrate (Figure 9). The bilayers cantilever is obtained by the lamination of a 100µm thick aluminum sheet and a 50µm thick polyethylene (PET) sheet ( Figure 10). Two different temperatures are simulated by two different anchorage thicknesses using PET sheet. The S 21 parameter obtained with these two configurations shows a relative resonant frequency shift around 0.2%/µm (Figure 11). IV. GAS SENSOR This study started in 2007 and more details can be found in [START_REF] Hallil | Novel Microwave Gas sensor using Dielectric Resonator With SnO2 Sensitive Layer[END_REF][START_REF] Hallil | New microwave gas detector using dielectric resonator based on Whispering-Gallery Mode[END_REF][START_REF] Hallil | Novel millimeter-wave gas sensor using dielectric resonator with sensitive layer on TiO2[END_REF][START_REF] Hallil | Feasibility of passive Gas sensor based on whispering gallery modes and its RADAR interrogation: theoretical and experimental investigations[END_REF][START_REF] Hallil | Feasibility of Wireless Gas Detection with an FMCW RADAR Interrogation of Passive RF Gas Sensor[END_REF]. No other passive gas sensors with electromagnetic transduction are reported up to now in the literature.

The gas transducer consists of two Coplanar Wave Guide (CPW) coupled with a cylindrical Dielectric Resonator (DR) (Figure 12), allowing the excitation of whispering galleries modes inside the dielectric resonator. The spacer, located in the center part of the DR, allows adjusting the vertical coupling between CPW and DR. The sensor principle is based on the dielectric relaxation effect (that corresponds to the dielectric resonator permittivity modification with gas absorption), which leads to the change of the resonance frequency.

Simulations performed with a TiO 2 DR have shown that resonant frequency of whispering galleries modes are very sensitive to the modification of the dielectric resonator permittivity (Figure 13). A prototype has been fabricated using CPW on a micro-machined silicon substrate, in order to reduce the silicon losses, and a DR in BaSmTiO x . TiO 2 DR sensitive to gas are under fabrication in order to validate the sensor response. V. RADAR INTERROGATION

The interrogation system is based on the FMCW (Frequency Modulated Continuous Wave) Radar. From the measured Radar Cross Section (electromagnetic echo) of the sensors, the physical quantity can be remotely and wirelessly derived and the identification of the sensor can also be performed [START_REF] Jatlaoui | Wireless Interrogation Techniques for a Passive Pressure Micro-sensor using an EM Transducer[END_REF], [START_REF] Jatlaoui | Original Identification technique of passive EM Sensors using Loaded Transmission Delay Lines[END_REF][START_REF] Jatlaoui | Phenomenological theory and experimental characterizations of passive wireless EM pressure micro-sensor prototype[END_REF], [START_REF] Chebila | Reconfigurable Multi-band Scatterers for Micro-Sensors Identification[END_REF][START_REF]Dispositif de mesure comprenant un diffuseur électromagnétique[END_REF].

The simplified block diagram of the interrogation unit, operating in homodyne principle, is shown in Figure 14. The Voltage Control Oscillator generates a frequency signal which increases linearly for a frequency sweep period. This signal propagates from the transmission horn antenna to the sensor target that is composed by an antenna loaded by the sensor die. This signal is then reflected back by the target, recovered by the receiving antenna of the reader and mixed with the input signal to obtain the intermediate frequency. The analysis of this frequency beat level permits then to detect the variation of the sensor load (that is linked to the shift of the sensor resonant frequency and then to the measured value).

A Radar, operating between 26GHz and 31GHz has been designed and fabricated (Figure 15). The interrogation principle up to 30m has been first validated using 1 cm 2 passive target and few mW for Radar emission. An example of Radar response is given in Figure 16 for the pressure sensor. The sensor die was connected via RF probes to an external horn antenna, placed at 3m from the Radar. The principle of new passive sensors has been validated for several applications (pressure, temperature, gas). These sensors are based on electromagnetic transduction and on Radar reader. The main advantages of this new kind of sensors are: a very simple transducer part without battery and without embedded electronic circuits that allows addressing applications with harsh environment and a wireless reading distance greater than 30m.

This electromagnetic transduction with a Radar reader can be adapted to other physical or chemical sensors as stress sensors [START_REF] Thai | Design of a Highly Sensitive Wireless Passive RF Strain Transducer[END_REF]. Nevertheless our main objective now is focused on the realization of sensors with given specifications (sensitivity, accuracy, …) for specific applications.

VII. ACKNOWLEDGMENT

Part of this work is supported by the French Project of 'Pôle de compétivité' entitled 'Système Autonome Communicant En Réseau' (SACER). All these studies have been performed with PhD students (Mehdi JATLAOUI, Hamida HALLIL, Franck CHEBILA, Thai TRANG).

Figure 1 :

 1 Figure 1 : Synoptic of active wireless sensor

Figure 2 :

 2 Figure 2 : Synoptic of passive wireless sensor

Figure 3 :Figure 4 :

 34 Figure 3 : Pressure sensor topology

Figure 5 :

 5 Figure 5: Resonant frequency versus air gap. Results with 300µm thick silicon membrane and uniform membrane displacement

Figure 6 :

 6 Figure 6: Resonant frequency versus pressure Experimental results 45µm thick silicon membrane

Anchorage

Figure 7 :Figure 8 :Figure 9 :Figure 10 :Figure 11 :

 7891011 Figure 7 : Temperature sensor topology. Ring resonators on substrate front side and CPW on back side.

SpacerFigure 12 :

 12 Figure 12 : Gas sensor topology

Figure 13 :

 13 Figure 13 : S 13 parameter versus frequency for different dielectric permittivity (simulations)

Figure 14 :

 14 Figure 14 : Simplified block diagram of the interrogation unit

Figure 15 :

 15 Figure 15 : Photographies of the fabricated Radar prototype

Figure 16 :Figure 17 :

 1617 Figure 16 : Radar response of pressure sensor