Pierre Coupechoux
email: pierre.coupechoux@laas.fr

Marc Demange
email: marc.demange@rmit.edu.au

David Ellison
email: david.ellison2@rmit.edu.au

Bertrand Jouve
email: bertrand.jouve@cnrs.fr

Online Firefighting on Trees

In the Firefighter problem, introduced by Hartnell in 1995, a fire spreads through a graph while a player chooses which vertices to protect in order to contain it. In this paper, we focus on the case of trees and we consider as well the Fractional Firefighter game where the amount of protection allocated to a vertex lies between 0 and 1. We introduce the online version of both Firefighter and Fractional Firefighter, in which the number of firefighters available at each turn is revealed over time. We show that the greedy algorithm on finite trees, which maximises at each turn the amount of vertices protected, is 1/2-competitive for both online versions; this was previously known only in special cases of Firefighter. We also show that, for Firefighter, the optimal competitive ratio of online algorithms ranges between 1/2 and the inverse of the golden ratio. The greedy algorithm is optimal if the number of firefighters is not bounded and we propose an optimal online algorithm which reaches the inverse of the golden ratio if at most 2 firefighters are available. Finally, we show that on infinite trees with linear growth, any firefighter sequence stronger than a non-zero periodic sequence is sufficient to contain the fire, even when revealed online.

Introduction and Definitions

Since it was formally introduced by B. Hartnell in 1995 ( [START_REF] Hartnell | Firefighter! An application of domination[END_REF], cited in [START_REF] Finbow | The firefighter problem: a survey of results, directions and questions[END_REF]) the firefighting problem -Firefighter -has raised the interest of many researchers. While this game started as a very simple model for fire spread and containment 1 INTRODUCTION AND DEFINITIONS 2 problems for wildfires, it can also represent any kind of threat able to spread sequentially in a network (diseases, viruses, rumours, flood . . . ).

It is a deterministic discrete-time one-player game defined on a graph. In the beginning, a fire breaks out on a vertex and at each step, if not blocked, the fire spreads to all adjacent vertices. In order to contain the fire, the player is given a number f i of firefighters at each turn i and can use them to protect vertices which are neither burning nor already protected. The game terminates when the fire cannot spread any further. In the case of finite graphs the aim is to save as many vertices as possible, while in the infinite case, the player wins if the game finishes, which means that the fire is contained.

This problem and its variants give rise to a generous literature; the reader is referred to [START_REF] Finbow | The firefighter problem: a survey of results, directions and questions[END_REF] for a broad presentation of the main research directions. A significant amount of theoretical work deals with its complexity and approximability behaviour in various classes of graphs [START_REF] Finbow | The firefighter problem for graphs of maximum degree three[END_REF][START_REF] Fomin | The firefighter problem on graph classes[END_REF][START_REF] Cai | Firefighting on trees: (1-1/e)-approximation, fixed parameter tractability and a subexponential algorithm[END_REF][START_REF] Bazgan | The firefighter problem with more than one firefighter on trees[END_REF] and recently its parametrised complexity (e.g. [START_REF] Bazgan | Parameterized complexity of firefighting[END_REF]). It is known to be very hard, even in some restrictive cases. In particular, the case of trees was revealed to be very rich and a lot of research focuses on it. The problem is NP-hard on finite trees [START_REF] Finbow | The firefighter problem for graphs of maximum degree three[END_REF], even in more restricted cases [START_REF] Bazgan | The firefighter problem with more than one firefighter on trees[END_REF]. Regarding approximability results on trees, it was first shown to be 1 2 -approximated by a greedy strategy [START_REF] Hartnell | Firefighting on trees: How bad is the greedy algorithm?[END_REF], improved to 1 -1 e [START_REF] Cai | Firefighting on trees: (1-1/e)-approximation, fixed parameter tractability and a subexponential algorithm[END_REF] and very recently to a polynomial time approximation scheme [START_REF] Adjiashvili | Firefighting on trees beyond integrality gaps[END_REF], which closes essentially the question of approximating firefighter problem in trees and motivates considering some generalisations. On general graphs the problem is hard to approximate within n 1-ε [START_REF] Anshelevich | Approximability of the firefighter problem -computing cuts over time[END_REF]. A related research direction investigates integer linear programming models for the problem, especially on trees [START_REF] Adjiashvili | Firefighting on trees beyond integrality gaps[END_REF][START_REF] Hartke | Attempting to narrow the integrality gap for the firefighter problem on trees[END_REF][START_REF] Macgillivray | On the firefighter problem[END_REF]. This line of research makes very natural a relaxed version where the amount of firefighters available at each turn is any non-negative number and the amount allocated to vertices lies between 0 and 1. A vertex with a protection less than 1 is partially protected and its unprotected part can burn partially and transmit only its fraction of fire to the adjacent vertices. Thus, the f i may take any nonnegative value. This defines a variant game called Fractional Firefighter which was introduced in [START_REF] Fogarty | Catching the Fire on Grids[END_REF].

Online optimisation [START_REF] Ausiello | On-line algorithms[END_REF] is a generalisation of approximation theory which represents situations where the information arrives over the time and one needs to make irrevocable decisions. We propose an online version of both firefighter problems and consider first results on trees. In our model, the graph is known and the sequence of available firefighters is revealed online. We then refer to the usual case where (f i ) i≥1 is known in advance as offline. To our knowledge, this is the first attempt at analysing online firefighter problems. Even though our motivation is mainly theoretical, this paradigm is particularly natural in emergency management where one has to make quick decisions despite lack of information. Any progress in this direction, even on simplified models, contributes to understanding how lack of information impacts the quality of the solution.

Given a tree T rooted in r, V (T ) and E(T ) will denote the vertex set and the edge set of T , respectively. Given two vertices v and v , v ≺ v denotes that v is an ancestor of v (or v is a descendant of v) and v v denotes that either

v = v or v ≺ v .
For any vertex v, let T [v] denote the sub-tree induced by v and its descendants. Let T i denote the i-th level of T rooted in r, where {r} = T 0 . The height h(T ) of T , rooted in r, is the maximum length of a path from r to a leaf. If i > h(T ), we have

T i = ∅.
If T is finite, the weight w(v) of a vertex v is the number of vertices in its sub-tree (including v), i.e. w(v) = |V (T [v])|. When no ambiguity may occur, we will simply write w v = w(v). For any vertex v ∈ T i and any i ≤

j ≤ i + h(T [v]), we denote by v j a vertex of maximum weight w vj in T j ∩ V (T [v]). While v j is not defined if i + h(T [v]) < j ≤ h(T ), we define wvj for all j ≤ h(T ) and v ∈ V (T ) via: wvj = w vj if j ≤ i + h(T [v]
) and 0 otherwise. We denote by B(T ) the tree obtained from T by fusing all vertices from levels 0 and 1 into a new root vertex r B : every edge u 1 u 2 ∈ E(T ) with u 1 ∈ T 1 and u 2 ∈ T 2 gives rise to the edge r B u 2 ∈ E(B(T )). For k ≤ h(T ), B k (T ) will denote the k th iteration of B applied to T : all vertices from levels 0 to k are fused into a single vertex denoted by r B k which becomes the new root.

2 The problems and preliminary results.

Firefighter and Fractional Firefighter on trees

In this paper we only play the game on finite or infinite trees. An instance of the Fractional Firefighter on trees is defined by a triple (T, r, (f i )), where T = (V (T ), E(T )) is a tree, r ∈ V (T ) is the root where the fire breaks out and (f i ) i≥1 is the non-negative real firefighter sequence. Turn i = 0 is the initial state where r is burning and all other vertices are unprotected, and i ≥ 1 corresponds to the different rounds of the game. At each turn i ≥ 1 and for every vertex v, the player decides which amount p(v) of protection to add to v. Throughout the game, for every vertex v the part of v which is burning is denoted by b(v). Let us note that if T is finite, the game will end in at most h(T ) turns where h(T ) is the length of a longuest path form the root to the leaves.

Solutions on trees have a very specific structure: at each turn i, the amounts of fire are non-increasing along any root to leaf path, which means that the fire will spread only towards the leaves. Note that for any solution which allocates a positive amount of protection at turn i to a vertex v ∈ T k , k > i, allocating the same amount of protection to v's father instead strictly improves the performance. So we may consider only algorithms that play in T i at turn i. For an optimal offline algorithm, this property was emphasised in [START_REF] Hartnell | Firefighting on trees: How bad is the greedy algorithm?[END_REF]. So, for any vertex v ∈ T i , the amounts of fire b(v) and protection p(v) on v will not change after turn i.

A solution p is characterised by the values p(v), v ∈ V (T ). For any solution p, while p(v) represents the amount of protection received directly, vertex v also receives protection through its ancestors, the amount of which is denoted by P p (v) = v ≺v p(v ) (used in section 3). For any vertex v, we have the equality p(v)

+ P p (v) + b(v) = 1.
Any solution p for Firefighter or Fractional Firefighter will satisfy the constraints:

v∈Ti p(v) ≤ f i (i) ∀v, p(v) + P p (v) ≤ 1 (ii)
In [START_REF] Macgillivray | On the firefighter problem[END_REF], a specific boolean linear model has been proposed for solving Firefighter on a tree T involving these constraints. Solving Fractional Firefighter on T corresponds to solving the relaxed version of this linear programme.

Online version

We introduce online versions of Firefighter and Fractional Firefighter. The graph -a tree T in this work -and the ignition vertex -the root r -are known in advance but the firefighter sequence (f i ) i≥1 is revealed over time by a second player called adversary. At each turn i, the adversary reveals f i and then the player chooses where to allocate this ressource.

Let us consider an online algorithm OA for one of the two problems and let us play the game on a finite tree T until the fire stops spreading. The value λ OA achieved by the algorithm, defined as the amount of saved vertices, is measured against the best value performed by an algorithm knowing in advance the sequence (f i ). In the present case, it is simply the optimal value of the offline instance, referred to as the offline optimal value, denoted by β I when considering the online Firefighter (I stands for "Integral") and β F for the online Fractional Firefighter. We will call Bob such an algorithm able to see the future and guaranteeing the value β I or β F for online Firefighter and Fractional Firefighter.

OA is said to be γ-competitive, γ ∈]0, 1] for the online Firefighter (resp. Fractional Firefighter) if for every instance, λ OA β I ≥ γ (resp. λ OA β F ≥ γ). γ is also called the competitive ratio guaranteed by OA. An online algorithm will be called optimal if it guarantees the best possible competitive ratio.

Let us first note that one can reduce the problem to the case where f 1 > 0:

Proposition 1. We can reduce online (Fractional) Firefighter on trees to instances where f 1 > 0.

Proof.

If f i = 0 for all i such that 1 ≤ i ≤ k, then the instance (T, r, (f i )) is equivalent to the instance (B k (T ), r B k , (f i+k )).
In the infinite case we do not define competitivness but only ask whether the fire can be contained by an online algorithm. Sections 3 and 4 deal with the finite case while section 5 deals with a class of infinite trees.

Competitive analysis of a Greedy algorithm

Greedy algorithms are usually very good candidates for online algorithms, sometimes the only known approach. Mainly two different greedy algorithms have been considered in the literature for Firefighter on a tree [START_REF] Finbow | The firefighter problem: a survey of results, directions and questions[END_REF] and they are both possible online strategies in our set-up. The degree greedy strategy prioritises saving vertices of large degree; it has been shown in [START_REF] Bazgan | The firefighter problem with more than one firefighter on trees[END_REF] that it cannot guarantee any approximation ratio on trees, even for a constant firefighter sequence. A second greedy algorithm was introduced in [START_REF] Hartnell | Firefighting on trees: How bad is the greedy algorithm?[END_REF] for an integral sequence (f i ), maximising at each turn the weight of the vertices protected. We generalise it to any firefighter sequence for both the integral and the fractional problems: at each turn i, the algorithm Gr solves the linear programme P i with variables x(v), v ∈ T i and constraints:

P i :    max v∈Ti x(v)w(v) v∈Ti x(v) ≤ f i (i) ∀v, x(v) + P x (v) ≤ 1 (ii)
An optimal solution of P i is obtained by ordering vertices {v 1 , . . . , v |Ti| } of level i by non-increasing weight and taking them one by one in this order and greedily assigning to vertex v j the value x(v j ) = min(f i -k<j x(v k ), 1 -P x (v j )). Note that Gr is valid for both Firefighter and Fractional Firefighter.

It was shown in [START_REF] Hartnell | Firefighting on trees: How bad is the greedy algorithm?[END_REF] that the greedy algorithm on trees gives a 1 2 -approximation of the restriction of Firefighter when a single firefighter is available at each turn. They claim that this approximation ratio remains valid for a fixed number D ∈ N of firefighters at each turn. We extend this result to any firefighter sequence (f i ) i≥1 , integral or not. Since Gr is an online algorithm, the performance can also be seen as a competitive ratio for the online version.

Theorem 1. The greedy algorithm Gr is 1 2 -competitive for both online Firefighter and Fractional Firefighter on finite trees.

Proof. Let us first consider the fractional case with an online instance (T, r, (f i )) of Fractional Firefighter on a tree.

Let x(v) and y(v) be the amounts of firefighters placed on vertex v by Gr and Bob, respectively. We have λ Gr = v x(v)w(v) and β F = v y(v)w(v).

Recall that P x (v) = v ≺v x(v ) and P y (v) = v ≺v y(v ). We split y(v) into two non-negative quantities, y(v) = g(v) + h(v), with:

g(v) = min{y(v), max{0, P x (v) -P y (v)}} and h(v) = max{0, y(v) + min{0, P y (v) -P x (v)}}.
We now claim that ∀v ∈ T , v v g(v) ≤ P x (v ) and prove it by induction. Since g(r) = 0, it holds for the root r. Assuming that the inequality holds for a vertex v , let v be a child of v . If P x (v ) -P y (v ) ≥ 0, then we directly have:

v v g(v) = v≺v g(v) + g(v ) ≤ v≺v y(v) + (P x (v ) -P y (v )) = P x (v ).
Else g(v ) = 0 and using v v g(v) ≤ P x (v ) and P x (v ) ≥ P x (v ), the inequality holds for v ; which completes the proof of the claim.

Thus:

v v v g(v) ≤ v P x (v ) = v v≺v x(v) ≤ v v v x(v). Since w(v) = v v 1
, by inverting the sums on both sides, we obtain:

v g(v)w(v) ≤ v x(v)w(v) = λ Gr (1)
Let us now consider the coefficients h(v). We claim that the coefficients h(v) with v ∈ T i satisfy the constraints (i) and (ii) of P i : indeed for (i), we have h(v) ≤ y(v) and y satisfies constraint (i). For (ii) note that h(v)

+ P x (v) = max{P x (v), y(v) + min{P x (v), P y (v)}} ≤ max{P x (v), y(v) + P y (v)} ≤ 1.
Hence, ∀i, v∈Ti h(v)w(v) ≤ v∈Ti x(v)w(v) and therefore:

v∈T h(v)w(v) ≤ v∈T x(v)w(v) = λ Gr (2)
Finally, since g(v) + h(v) = y(v), we conclude from eqs. ( 1) and ( 2) that β F ≤ 2λ Gr . Hence the Greedy algorithm is 1 2 -competitive for the online Fractional Firefighter problem. Since the greedy algorithm gives an integral solution if (f i ) has integral values and since β F ≥ β I , it is also 1 2 -competitive for the Firefighter problem. This concludes the proof of theorem 1.

Conjecture 2.3 in [START_REF] Hartke | Attempting to narrow the integrality gap for the firefighter problem on trees[END_REF] (which is also Conjecture 3.5 in [START_REF] Finbow | The firefighter problem: a survey of results, directions and questions[END_REF]) claims that there is a constant ρ such that the optimal value of Fractional Firefighter is at most ρ times the optimal value of Firefighter. It was supported by extensive experimental tests [START_REF] Hartke | Attempting to narrow the integrality gap for the firefighter problem on trees[END_REF], but finding such a constant and proving the ratio is one of the open problems proposed in [START_REF] Finbow | The firefighter problem: a survey of results, directions and questions[END_REF] (Problem 7). It was shown in [START_REF] Chalermsook | New integrality gap results for the firefighters problem on trees[END_REF] that such a constant must be greater than e e-1 . Theorem 1 can be expressed by λ Gr ≤ β I ≤ β F ≤ 2λ Gr , which shows that ρ = 2 is such a constant: Corollary 1. In Fractional Firefighter, the amount of vertices saved is at most twice the maximum number of vertices saved in Firefighter.

Improved Competitive Algorithm for Firefighter

In this section, we investigate possible improvements for online strategies for denote the golden ratio, satisfying ϕ 2 = ϕ + 1 and 1 ϕ = ϕ -1. For any integer k ≥ 2, we denote

α I,k = inf T ∈T max OA∈A L min (fi)∈N N , i fi≤k λ OA β I ,
where T denotes the set of finite rooted trees and A L the set of online algorithms for Firefighter on finite trees, be the best possible competitive ratio for online Firefighter on finite trees if at most k firefighters are available. Note that the sequence (α I,k ) k is non-increasing. Then, α I = inf In what follows we give an optimal online algorithm for Firefighter on a finite tree in the case where at most two firefighters are available. Based on proposition 1 we may assume f 1 = 1 and such an online instance is characterised by when the second firefighter is presented.

Lemma 1. Let a and b be two vertices of maximum weights in T 1 . If i f i ≤ 2, there is an optimal offline algorithm for Firefighter which places the first firefighter on either a or b.

Proof. If the first firefighter is placed on v ∈ T 1 \ {a, b} by an optimal offline algorithm and since at most two firefighters are available, ∃u ∈ {a, b}, T [u] burns completely. Then replacing v by u when assigning the first firefighter would produce another optimal solution (necessarily w v = w u ).

We suppose Bob has this property but note that even if w a > w b , he will not necessarily choose a; as illustrated by the graph W 1,10,20 (fig. 1): if the firefighter sequence is (1, 0, 1, 0, . . .), then Bob's first move needs to be on x. Note also that, when the root is of degree at least 3, the second firefighter is not necessarily in

V (T [a]) ∪ V (T [b]).
We now consider algorithm 1 and assume that the adversary will reveal at most two firefighters. The case where f 1 = 2 is trivial since an online algorithm can make the same decision as Bob by assigning both firefighters to two unburnt vertices of maximum weights. So, we consider a binary firefighter sequence.

The algorithm works on an updated version T of the tree: if one vertex is protected, then the corresponding sub-tree is removed and all the burnt vertices are fused into the new root r so that the algorithm always considers vertices of level 1 in T . Before starting the online process, the algorithm computes all weights of vertices. Weights of unburnt vertices will not change when updating T . The value of h( T ), required in line 6 can be computed during the initial calculation of weights and easily updated with T . For clarity, we do not detail all update in the algorithm. The notation wvj used at line 6 is defined in section 1.

Theorem 2. Algorithm 1 is a 1 ϕ -competitive online algorithm for online Firefighter with at most two available firefighters. It is optimal for this case.

Proof. If the adversary does not present any firefighter before the turn h(T ), both algorithm 1 and Bob cannot save any vertex and by convention one considers then that the competitive ratio is 1.

Let us suppose that at least one firefighter is presented at some turn k ≤ h(T ); the tree still has at least one unburnt vertex. During the (k-1) first turns, the instance is updated into (B k (T ), r B k , (f i+k )) with one firefighter presented during the first turn and the root has at least one child. Proposition 1 ensures that it is equivalent to the original instance.

If the root has only one child a = b at line 5 and algorithm 1 selects a and saves all unburnt vertices inducing a competitive ratio of 1.

Algorithm 1

Require: A finite tree T with root r -An online adversary.

1: ( T , r) ← (T, r); Compute w v , ∀v ∈ V ( T ) 2: {Start of the online process} 3: At each turn, after fire spreads T is updated -burt vertices are fused to r; 4: if First Firefighter is presented and r has some child then if min 2≤i≤1+h( T )

wa+ wb i w b + wa i ≥ 1 ϕ then 7:
Place the first firefighter on a;

8:

else 9:
Place the first firefighter on b; 10: if Second Firefighter is presented and r has some child then 11:

Place the firefighter on a maximum weight child v of r

Else, a = b with w a ≥ w b (line 5). Suppose first that the adversary presents a single firefighter during the whole process, then algorithm 1 places him on a or b while Bob places him on a, saving w a . If w a ≥ ϕw b , then we have:

∀i, 2 ≤ i ≤ 1 + h(T ), w a + wbi w b + wai ≥ w a w b + w a ≥ ϕw b w b + ϕw b = 1 ϕ (3)
Therefore, (see line 6) the unique firefighter is placed on a by the algorithm, guaranteeing a competitive ratio of 1. Else we have w b > 1 ϕ w a and even placing the firefighter on b guarantees the ratio 1 ϕ . Suppose now that the adversary presents two firefighters. We consider two cases. Case (i): If algorithm 1 places the first firefighter on a in line 7 and if the adversary presents the second firefighter at turn i, then the algorithm will save w a + wxi for some x ∈ T 1 \ {a} such that wxi = max u∈T1\{a} wui . For the same instance Bob will save w v + wyi for some v ∈ {a, b} and y ∈ T 1 \ {v}. If both solutions are not of the same value (the optimal one is strictly better), then necessarily v = b and y = a. In this case the criterion of line 6 ensures that the related competitive ratio is 1 ϕ . Case (ii): Suppose now algorithm 1 places the first firefighter on b in line 9, and say the adversary presents the second firefighter at turn j. Line 5 ensures that:

∃i, 2 ≤ i ≤ 1 + h(T ), w a + wbi w b + wai < 1 ϕ (4)
It implies in particular that w a < ϕw b since in the opposite case eq. ( 3) would hold. In case (ii), algorithm 1 saves w b + wxj with x ∈ T 1 \ {b} such that wxj = max u∈T1\{b} wuj . Meanwhile, Bob selects v ∈ {a, b} and, if it exists, y j for some y ∈ T 1 \ {v}, for a total of w v + wyj saved vertices. If y = b, then wyj ≤ wxj , by definition of x, and thus:

w b + wxj w a + wyj ≥ w b + wxj w a + wxj ≥ w b w a > 1 ϕ (5)
Finally, if y = b, then v = a and the competitive ratio to evaluate is

w b + wx j wa+ wb j .
We claim that the following holds:

w a + wbi w b + wai × w b + wxj w a + wbj ≥ 1 ϕ 2 (6)
If i ≥ j we have wai ≤ waj and since a = b, waj ≤ wxj . Hence:

w b + wx j w b + wa i ≥ w b + wx j w b + wa j
≥ 1 and therefore:

w a + wbi w b + wai × w b + wxj w a + wbj ≥ w a + wbi w a + wbj ≥ w a w a + w b .
If now i < j, we get:

wa+ wb i wa+ wb j ≥ 1 and therefore:

w a + wbi w b + wai × w b + wxj w a + wbj ≥ w b + wxj w b + wai ≥ w b w a + w b .
In both cases, since wa wa+w b ≥ w b wa+w b ≥ 1 1+ϕ = 1 ϕ 2 we deduce eq. ( 6). Now, eqs. ( 4) and ( 6) imply that in case (ii), when y = b, we also have

w b + wx j wa+ wb j ≥ 1
ϕ . Together with eq. ( 5), this concludes case (ii) and shows that algorithm 1 is We conclude this section with a hardness result justifying that the greedy algorithm Gr is optimal while Algorithm 1 is optimal if at most two firefighters are available. Proposition 2. For all k ≥ 2, 1 2 ≤ α I,k ≤ 1 ϕ , more precisely: (i) α I = 1 2 , meaning that the greedy algorithm is optimal for Firefighter in finite trees; (ii) α I,2 = 1 ϕ meaning that Algorithm 1 is optimal if at most two firefighters are available; (iii) α I,4 < 1 ϕ .

Proof. Theorem 1 shows that α I ≥ 1 2 . Given integers l, m, k such that k|m -1, we define the graph W k,l,m as shown in fig. 1. We will assume that m > k 2 .

(i) Let us consider an online algorithm for W k,l,m . If f 1 = 1, the algorithm will protect either x or y. If x is selected and the firefighter sequence is (1, 1, 0, 0, . . .), our online algorithm protects the branch of x and one of the k chains, while the optimal offline algorithm protects y and the star. Its performance is then

l+ m-1 k l+m-1 .
If, however, y is protected instead during the first turn and if the firefighter sequence is (1, 0, 1, 1, . . .), the online algorithm protects the branch of y and one vertex of the star whilst the optimal algorithm protects the branch of x as well as the k chains, minus for k(k+1) 2 vertices. If l = m, for large values of m, the online algorithm which protects x is more performant and its competitive ratio tends to

1+ 1 k 2 . Considering, for instance, W k,k 3 ,k 3 , when k → +∞ shows that α ≤ 1 2 .
Since the greedy algorithm Gr guarantees α I ≥ 1 2

we have α I = 1 2 . (ii) Consider the sequence of graphs W 1,l, ϕl . If the online algorithm protects x, the adversary selects the sequence (1, 0, . . .), whereas if the online algorithm protects y, (1, 0, 1, 0, . . .) is selected. In both cases, the performance tends to 1 ϕ when l → +∞. (iii) If at most 4 firefighters are available, the graph W 4,901,1001 (fig. 1) gives an example where 1 ϕ cannot be reached. Ideed, if f 1 = 1 and the online algorithm protects x, then the adversary will select the sequence (1, 1, 0, . . .), as in the proof (i), for a performance of 1151 1901 . If the online algorithm protects y, since firefighters are limited to 4, the adversary will select (1, 0, 1, 1, 1, 0, . . .), for a performance of 1002 1645 . This second choice is slightly better, but 1002 1645 < 1 ϕ . We have also proved that Theorem 2 holds if three firefighters are presented (i.e., α I,3 = 1 ϕ ). However, the proof involves a much more technical case-by-case analysis and will not be detailed here.

Firefighting on Trees with Linear Growth

In this section, we consider infinite trees. We say that a rooted tree (T, r) has linear growth if the number of vertices per level increases linearly, i.e. |T i | = O(i).

Remark 1. The linear growth property of T remains if we choose a different root r . Indeed, if d is the distance between r and r , the set of vertices at distance i from r is included in i+d j=i-d T j , the cardinal of which is a O(i).

Given two firefighter sequences (f i ) and (f i ), we say that (f i ) is stronger than

(f i ) if for all k, k i=1 f i ≥ k i=1 f i .
Lemma 2. If the fire can be contained in an instance (G, r, (f i )) and if (f i ) is stronger than (f i ), then the fire can also be contained in (G, r, (f i )).

Proof. Given a winning strategy in the instance (G, r, (f i )), if (f i ) firefighters are available, we contain the fire by protecting the same vertices, eventually earlier than in the initial strategy. Theorem 3. Let (T, r, (f i )) be an online instance of Fractional Firefighter. If T has linear growth and (f i ) is stronger than some non-zero periodic sequence, then the fire can be contained.

The proof of theorem 3 will use the following lemma: Proof. Since T has linear growth, let C be such that ∀i, |T i | ≤ Ci. For all n, let (δ n|i ) denote the firefighter sequence where one firefighter is available every n turns; i.e. δ n i is equal to 1 if n|i and 0 otherwise. That the sequence (f i ) is stronger than a non-zero periodic sequence means that (f i ) is stronger than (δ n|i ), for all n greater than some m. First we will give an offline strategy to contain the fire with one firefighter every n turns. Then, we will show that online instances with (f i ) stronger than a (δ n|i ) known to the player are winning. Finally, we will describe the winning strategy when such a (δ n|i ) is unknown.

Given an integer n, let us first consider the instance (T, r, (δ n|i )). It follows from lemma 3 that there exists an integer N such that 2Cn ≤ N . Since N firefighters remain to be placed between turns N and h(n), the strategy is winning in at most h(n) turns.

If the player knows that (f i ) is stronger than (δ n|i ), the above strategy can be adapted using lemma 2.

In the general case, the player knows that (f i ) is stronger than (δ n|i ) for some n, but he does not know which n. The strategy proceeds as follows: we initially play as though under the assumption that (f i ) is stronger than (δ n0|i ), with n 0 = 100. If the fire is not contained by turn h(n 0 ), or later on by turn h(n k ), we choose n k+1 = h(n k )( S h(n k ) + 1), where S n = n i=1 f i . We now assume that (f i ) was stronger than (δ h(n k )|i ). It follows that after cancelling the first h(n k ) terms of (f i ), the resulting sequence is stronger than (δ n k+1 |i ). So we can consider that the first h(n k ) turns were wasted and follow the strategy for n k+1 until turn h(n k+1 ). Eventually, this strategy will win when n k is large enough.

Final remarks

In this paper, we introduce the online version of (Fractional) Firefighter and propose first results for both the finite and the infinite cases. To our knowledge, theorem 1 is the first non trivial competitive (but also approximation) analysis for Fractional Firefighter and a first question would be to investigate whether a better competitive ratio can be obtained for Fractional Firefighter in finite trees. Even though the case of trees is already challenging despite allowing many simplifications, the main open question will be to study online (Fractional) Firefighter problem in other classes of finite graphs.

Firefighter

  on finite trees. Let ϕ = 1+ √ 5 2

k≥2α

  I,k is the best possible competitive ratio for online Firefighter on finite trees. The index I stands for Integral and refers to the problem Firefighter.

5 :

 5 Let a and b denote two children of r with maximum weight w a , w b and w a ≥ w b (a = b if r has only one child); 6:

1 ϕ

 1 -competitive. Even though complexity analyses are not usually proposed for online algorithms, it is worth noting that line 6 only requires the weights of vertices in V (T [a]) ∪ V (T [b]) and the maximum weight per level in T [a] and T [b] and consequently Algorithm 1 requires O(|V (T [a])| + |V (T [b])|) to choose the position of the first firefighter and O(|V (T )|) in all.

Figure 1 :

 1 Figure 1: The fire on graph W k,l,m starts at vertex r. Whether the firefighter should protect x or y on the first turn depends on the firefighter sequence.

Lemma 3 .

 3 For any a > 0, lim n→+∞

  h(n) = 2nN . A winning strategy is obtained by protecting at turn nj the unprotected vertex of T nj with the highest number of descendants in level h(n). Since |T nj | ≤ Cnj, the remaining number of unprotected vertices in T h(n) is reduced by at least 1 Cnj of its previous value. So the number of unprotected vertices of T h(n) remaining after nN turns is less than |T h(n) |

We acknowledge the support of GEO-SAFE, H2020-MSCA-RISE-2015 project # 691161.


Kris Tiri
email: tiri@ee.ucla.edu

Ingrid Verbauwhede
email: ingrid@ee.ucla.edu

Design Method for Constant Power Consumption of Differential Logic Circuits

Side channel attacks are a major security concern for smart cards and other embedded devices. They analyze the variations on the power consumption to find the secret key of the encryption algorithm implemented within the security IC. To address this issue, logic gates that have a constant power dissipation independent of the input signals, are used in security ICs. This paper presents a design methodology to create fully connected differential pull down networks. Fully connected differential pull down networks are transistor networks that for any complementary input combination connect all the internal nodes of the network to one of the external nodes of the network. They are memoryless and for that reason have a constant load capacitance and power consumption. This type of networks is used in specialized logic gates to guarantee a constant contribution of the internal nodes into the total power consumption of the logic gate.

Introduction

Encryption algorithms are designed to be secure against cryptanalysis that has access to plaintext and ciphertext. The physical implementation however, provides the attacker with important information. Numerous attacks have been presented that use 'sidechannels', such as the time delay and the power consumption of the encryption operation, as an extra source of information to find the secret key [START_REF] Hess | Information Leakage Attacks Against Smart Card Implementations of Cryptographic Algorithms and Countermeasures -a Survey[END_REF]. These socalled side-channel attacks threaten any device of which the integrated circuit is easily observable such as smart cards and embedded devices. The differential power analysis [START_REF] Kocher | Differential Power Analysis[END_REF] in particular is of great concern. It is very effective in finding the secret key and can be mounted quickly with off-the-shelf devices. The attack is based on the fact that logic operations have power characteristics that depend on the input data. It relies on statistical analysis to extract the information from the power consumption that is correlated to the secret key.

All embedded applications, such as for example PDAs, cellphones, smart cards and sensor nodes in an ambient intelligent environment need to communicate with their environment. Therefore, they will need cryptographic capabilities for authentication and confidentiality. Some efforts have recently been made during special sessions at premier design conferences to raise the awareness for the danger that side-channel attacks pose to all embedded devices [START_REF] Renaudin | High Security Smart-cards[END_REF], [START_REF] Kocher | Security as a New Dimension in Embedded System Design[END_REF].

At first, the differential power analysis attack has been fought with ad hoc countermeasures. For instance, the addition of random power consuming operations or a current sink obscured the data dependent variations in the power consumption. These techniques do not solve the problem; they only increase the number of measurements for a DPA attack. Subsequently, countermeasures have been conceived at different abstraction levels of the security application. One illustration at the algorithmic level is masking [5]. This technique prevents that intermediate variables depend on an easily accessible subset of the secret key.

However, the best solution is to try not to create any side channel information. This can be done at the logic level with specialized circuit techniques [START_REF] Tiri | Securing Encryption Algorithms against DPA at the Logic Level: Next Generation Smart Card Technology[END_REF], [START_REF] Fournier | Security Evaluation of Asynchronous Circuits[END_REF] The goal of these countermeasures is to make the power consumption of the individual logic gates independent of their input signals or the Hamming distances between subsequent input signals. When the power consumption of the smallest building block is a constant and independent of the signal activity, no information is leaked through the power supply and power attacks are impossible.

The circuit techniques can be categorized in two groups. One group uses gates composed of standard logic gates [START_REF] Tiri | A Logic Level Design Methodology for a Secure DPA Resistant ASIC or FPGA Implementation[END_REF], [START_REF] Sokolov | Improving the Security of Dual-Rail Circuits[END_REF], the other group uses custom made gates [START_REF] Tiri | A Dynamic and Differential CMOS Logic with Signal Independent Power Consumption to Withstand Differential Power Analysis on Smart Cards[END_REF], [START_REF] Mace | A Dynamic Current Mode Logic to Counteract Power Analysis Attacks[END_REF], [START_REF] Guilley | CMOS Structures Suitable for Secured Hardware[END_REF]. Custom made gates offer a higher security because the designer has full control over the internal organization of the cells. Yet, there is a tradeoff with the costs of developing a custom designed library. In dynamic current mode logic (DyCML) [START_REF] Allam | Dynamic Current Mode Logic (DyCML): A New Low-Power High-Performance Logic Style[END_REF], proposed in [START_REF] Mace | A Dynamic Current Mode Logic to Counteract Power Analysis Attacks[END_REF], the transistor sizes even depend on the final layout of the interconnect wiring after place & route as they are based on the output capacitance. DyCML also requires a complex clock delay network as gates at different logic depth need different clock delays. Major disadvantages of the logic style proposed in [START_REF] Guilley | CMOS Structures Suitable for Secured Hardware[END_REF] are the limited libraryonly the AND-NAND gate-, the large transistor count -112 transistors for the AND-NAND gate-and the asynchronous design approach, which still lags behind that of synchronous designs.

For sense amplifier based logic (SABL), our previous work proposed in [START_REF] Tiri | A Dynamic and Differential CMOS Logic with Signal Independent Power Consumption to Withstand Differential Power Analysis on Smart Cards[END_REF], only gates with two or fewer inputs have been presented. The logic style requires a special structure of the differential pull down network (DPDN) to control the contribution of the internal nodes into the power consumption. The main requirement is that the network must be fully connected. This means that for any complementary input combination all the internal nodes of the network connect to one of the external nodes of the network. As a result, all the internal nodes go through a discharge-charge cycle and have a constant power dissipation. The main contribution of this paper is a systematic design method to generate fully connected differential pull down networks for an arbitrary logic function.

The remainder of this paper is organized as follows. The next section enumerates the characteristics of constant power dissipating logic. Section 3 discusses the fully connected differential pull down network in detail. In section 4, design methods are formulated to create fully connected differential pull down networks given a Boolean expression or given an existing differential pull down network. The design example implements a complex fully connected differential pull down network. Section 5 describes an enhancement to avoid early propagation. Finally, a conclusion will be formulated.

Constant Power Dissipating Logic

The power dissipation of traditional logic depends on the signal activity. When the output of the logic gate makes a 0 to 1 transition, a current comes from the supply and charges the output capacitance. On the other hand, when the output sees a 1 to 0 transition or no transition at all, no energy is consumed from the power supply. Two conditions must be satisfied to have constant power dissipating logic: (1) a logic gate must have exactly one charging event per clock cycle; and (2) the logic gate must charge a constant capacitance in that charging event.

Dynamic and differential logic fulfills the first condition. In a differential logic family, a signal is represented by both the true and the false value. A dynamic logic family alternates precharge and evaluation phases. In the precharge phase, the output is pre-charged to 1, and in the evaluation phase the output is conditionally evaluated to 0. For the combination of dynamic and differential logic this means that exactly one of the two outputs will evaluate to 0 as the output must be differential during the evaluation phase. During the subsequent precharge phase, the discharged output will be pre-charged to 1. In other words, every signal transition, including the events in which the input signals remain constant, is represented with an actual switching event, in which the logic gate charges a capacitance. All the logic families that have been introduced to thwart the DPA [START_REF] Fournier | Security Evaluation of Asynchronous Circuits[END_REF], [START_REF] Tiri | A Logic Level Design Methodology for a Secure DPA Resistant ASIC or FPGA Implementation[END_REF], [START_REF] Sokolov | Improving the Security of Dual-Rail Circuits[END_REF], [START_REF] Tiri | A Dynamic and Differential CMOS Logic with Signal Independent Power Consumption to Withstand Differential Power Analysis on Smart Cards[END_REF], [START_REF] Mace | A Dynamic Current Mode Logic to Counteract Power Analysis Attacks[END_REF], [START_REF] Guilley | CMOS Structures Suitable for Secured Hardware[END_REF] employ some form of dynamic differential logic.

Besides a 100% switching factor, it is essential in order to achieve constant power consumption that a fixed amount of charge is used per transition. Differential logic has a load capacitance at each output. Since only one output undergoes a transition per switching event, the total load at the true output should match the total load at the false output. This means that the load capacitances at the differential output should be matched. The load capacitance has three components: the intrinsic output capacitance of the gate, the interconnect capacitance and the intrinsic input capacitance of the load. Intrinsic capacitances are parasitic node capacitances of the logic gate.

(Dis)charging parasitic capacitances, which are internal to the gate itself, have an influence on the power consumption as well. Simulations indicate that e.g. for the AND-NAND gate in cascode voltage switch logic (CVSL) [START_REF] Heller | Cascode Voltage Switch Logic: A differential CMOS Logic Family[END_REF], the variation on the power consumption can be as large as 50% [START_REF] Tiri | A Dynamic and Differential CMOS Logic with Signal Independent Power Consumption to Withstand Differential Power Analysis on Smart Cards[END_REF]. This is caused by asymmetry in the gate. Depending on the input, different parasitic capacitances that are internal to the differential pull down network discharge during the evaluation phase. In the succeeding power consuming precharge phase, these capacitances are recharged. This phenomenon is also referred to as memory effect.

Sense amplifier based logic [START_REF] Tiri | A Dynamic and Differential CMOS Logic with Signal Independent Power Consumption to Withstand Differential Power Analysis on Smart Cards[END_REF] uses advanced circuit techniques to guarantee that the load capacitance has a constant value. The logic style completely controls the portion of the load capacitance that is due to the logic gate. The intrinsic capacitances at the differential in-and output signals are symmetric. Additionally, the special structure of the differential pull down network guarantees that all the internal nodes go through a discharge-charge cycle and no nodes are left floating. As a result it discharges and charges each of the internal nodes in every cycle together with one of the balanced output capacitances. Hence, it discharges and charges a constant capacitance value.

The generic sense amplifier based logic gate is shown in Fig. 1. The gate consists of the sense amplifier of the StrongArm110 flip-flop [START_REF] Montanaro | A 160-MHz[END_REF] of which the input differential pair is exchanged by a differential pull down network. In the precharge phase, both the true and the false value of all input signals are set at 0. The true and the false output signal are precharged to 1. During the evaluation phase, the input becomes complementary and the network connects one of the network output nodes, X or Y, to the common node Z. This will make the logic gate switch and one gate output will discharge to 0. Note that whichever branch of the differential pull down network is on, X and Y are connected through transistor M 1 and both nodes will eventually be discharged. This leaves the gate in a stable state until the next precharge phase.

Fully Connected DPDN

A fully connected differential pull down network is designed such that for any complementary input combination all internal nodes of the network are connected to one of the module output nodes X or Y. As a result, since both nodes X and Y eventually discharge, all the internal nodes are discharged during the evaluation phase and will be charged during the next precharge phase. The requirement of fully connected differential pull down networks in constant power dissipating logic is in contrast with genuine logic, where the design constraints are to minimize the device count and the number of stacked levels [START_REF] Chu | Design Procedures for Differential Cascode Voltage Switch Circuits[END_REF].

As an example, Fig. 2 (left) and (right) show the implementation of the AND-NAND function with a genuine and with a fully connected differential pull down network respectively. The genuine network has one internal node, node W. This node can become floating for some input combinations. For example when both A and B remain at 0 during the transition from the precharge phase to the evaluation phase (and A and B both switch from 0 to 1), node W is disconnected from node X as well as from node Z. There is no path for the charge to flow away and node W keeps it charge on the parasitic capacitance. On the other hand, when both A and B switch from 0 to 1 ( A and B both remain at 0), node W is connected to node Z and the parasitic capacitance discharges. The difference in power dissipation between both input events will come from the fact that for the latter event, the capacitance at node W will need to be charged in the subsequent precharge phase. For a genuine differential pull down network several discharge events with different combinations of parasitic capacitances exist. This means that the total load capacitance, and thus the power consumption, is signal dependent. It is impossible to match the total load capacitance of the different discharge events by manipulating transistor sizes and/or layouts. The contribution of the internal node capacitances can only be controlled by making sure that they all discharge independently of the input event. Repositioning transistor M 2 , which is located between nodes Y and Z and is driven by input A , between nodes Y and W achieves this effect. This operation does not alter the functionality of the individual branches of the differential pull down network

( B . A B . A and B B . A B A
) but it guarantees that for any complementary input combination, node W is connected to one of the module output nodes. Hence, independently of the input event in the evaluation phase, node W will be discharged.

Fig. 3 shows two transient SPICE simulations of a discharging event in the evaluation phase followed by a charging event in the precharge phase of the sense amplifier based logic AND-NAND gate for two different inputs. The figure shows that the instantaneous output voltages and the supply current are independent of the input event applied to the gate. Fig. 4 demonstrates that for both events all the internal node capacitances and one of the balanced output nodes are discharged. In each event, the same amount of charge is needed to charge the same capacitances, and hence the same amount of energy, is used.

Designing fully connected DPDNs

This section formulates a design method to create a fully connected differential pull down network for a logical function f given either a Boolean expression or an existing differential pull down network.

Given a Boolean expression

The design procedure to create a fully connected differential pull down network for a logical function f consists of five steps.

Step 0: Create the Boolean expression of the logical function f . The complementary output will be referred to as f .

Step 1: Identify 2 expressions x and y that combine to the logical function f . The result is either an AND- operation ( y x f . ) or an OR-operation, ( y x f

).

Step 2: Complement the expression of f in x and y to get the dual expression f . The result is an OR- operation (

y x f
) or an AND-operation, ( y x f . ). The results of the previous 2 steps are two dual expressions:

either case A) or case B)

y x f . y x f y x f y x f .
Step 3: Transform the OR-operation. The Boolean expression is translated to a differential PDN in the traditional way. An AND operation is represented by a series of switches, an OR operation by a parallel connection of switches [START_REF] Rabaey | Digital Integrated Circuits: A design perspective[END_REF]. At this abstraction level, only the series combination has an internal node.

In case A), we transform the parallel connection into y y x .

, put network y at the bottom of the y x. connection and share network y between the two branches y

x. and y y x .

. In case B) we transform the parallel connection into y y x .

, put network y at the bottom of the y x. connection and share network y between the two branches y

x. and y y x .

.

Step 4: Decompose and repeat the procedure for the logical expressions x and y until the network consists of only 1 literal, which corresponds to a single transistor.

Step 5: Substitute the results.

Given an existing DPDN

The above design method can also be implemented directly on a differential pull down network. For a given schematic of a genuine differential pull down network, the design procedure is a transformation. The transformation repositions transistors in the genuine network in three steps. The total number of devices remains the same between the genuine and the fully connected network. The evaluation depth, which is defined by the maximum number of devices in series, may increase.

Step 1: Identify all the networks in series.

Step 2a: Open the corresponding dual parallel networks. Each parallel network is opened at the bottom of the component that corresponds with the dual component that is at the top of the series network.

Step 2b: Connect the opened parallel connections to the internal nodes of the corresponding series connections.

Step 3: Unroll the network.

Design example

Fig. 5 illustrates both design procedures. The design example consists of a complex differential pull down network used in an OAI22 logic gate (or-and-invert with 2 and 2 inputs). Both design methods produce a network that is fully connected.

In the resulting differential pull down network, both the true and the false of an input signal control a device for every internal node. Consequently independent of the complementary input in the evaluation phase, every internal node is connected to another node. This is either an external node or another internal node, for which both the true and the false of an input signal control a device. As a result independent of the input, every internal node is connected to an external node and the network is fully connected.

Enhanced fully connected DPDN

The fully connected differential pull down network can be further enhanced to have an evaluation depth that is independent of the discharge events. The evaluation depth is defined as the number of transistors in series between the nodes X or Y to the common ground node Z. A passgate is inserted if different discharge paths do not have the same number of transistors. We insert a pass-gate for all the input signals that do not control a transistor in that particular discharge path. A pass-gate, which is built by a parallel combination of two transistors driven by both the signal and its complement, is always open for a complementary input. The enhanced fully connected differential pull down network implementing the AND-NAND function is shown in Fig. 6. The trade-off is an increase in area and total load capacitance.

The introduction of the dummy transistors has two desired effects. First, since the evaluation depth is independent of the discharge event, there is now a constant resistance in the discharge path between outputs X or Y and the common node Z. As a result, each gate has a constant delay as now both the resistance and the capacitance are independent of the inputs. Second, early evaluation has been eliminated. No evaluation will start before all inputs are stable and complementary. As a result, since the logic gate can not produce any anticipated results, the delay of a combination of gates is a constant as each gate evaluates when the input-pair with the longest

Conclusions

We have illustrated that fully connected differential pull down networks, which are differential transistor networks for which all internal nodes connect to an output node when a complementary input is applied, are necessary to avoid memory effects and to guarantee a constant contribution of the internal nodes into the power consumption of a logic gate. We have presented a design methodology to create fully connected networks. They can be constructed from a given Boolean expression or from a given genuine differential pull down network. Pass gates can be inserted to enhance the fully connected network. The dummy devices ensure a network evaluation depth that is independent of the input signals and eliminate early propagation effects.

Fig. 1 .

 1 Fig. 1. Generic sense amplifier based logic gate.

Fig. 2 .

 2 Fig. 2. Implementation of AND-NAND function with genuine DPDN (left); and fully connected DPDN (right).

Fig. 3 .Fig. 4 .

 34 Fig. 3. Output signals and supply current of SABL AND-NAND gate: transient simulation for (0,1)-input (top); and (1,1)-input (bottom). Note that in the precharge phase all inputs (A, A , B, B) are at 0 and that subsequently in the evaluation phase either A or A and either B or B become 1.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Transformation of a complex DPDN to a fully connected DPDN: design example.

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgements

The authors would like to acknowledge the support of the National Science Foundation (CCR-0098361).


Andrei G Shvarts
email: andrei.shvarts@mines-paristech.fr

Vladislav A Yastrebov
email: vladislav.yastrebov@mines-paristech.fr

Georges A Cailletaud
email: georges.cailletaud@mines-paristech.fr

A strong fluid/structure coupling scheme for thin incompressible flow in the contact interface at the roughness scale

Keywords: mechanical contact, fluid/structure coupling, surface roughness, trapped lubricant

A strong fluid/structure coupling scheme for thin incompressible flow in the contact interface at the roughness scale

Introduction

Natural and industrial surfaces always have roughness under certain magnification, and the contact in most applications occurs on separate patches corresponding to asperities of the surfaces [START_REF] Yastrebov | Contact between representative rough surfaces[END_REF][START_REF] Yastrebov | From infinitesimal to full contact between rough surfaces : Evolution of the contact area[END_REF]. The evolution of the real contact area under increasing external load determines essential contact properties, such as friction, wear, adhesion, but also it strongly affects heat and mass transport in and through contact interfaces.

We consider here the problem of coupling the mechanical contact with the thin fluid flow in the interface between the contacting surfaces. On the one hand, the boundary value problems for fluid transport depends on the solution of the mechanical contact problem. On the other hand, the solution of the latter in turn is influenced by the hydrostatic and hydrodynamic pressures of the fluid, which results in the strong coupling between these two problems.

We use the multiscale approach : by performing simulations with the roughness of the contacting surfaces taken into account at microscale, we are able to refine the existing models of the considered phenomenas at the macroscopic scale, which are relevant for such industrial applications, as problems of contact seals and mixed lubrication. The former one is essential for aeronautic, automotive and nuclear industries, and these applications demand generalization of the solution of the coupled problem at the microscopic scale for the macroscopic scale using the roughness-dependent leakage laws. The mixed lubrication is crucial for systems in which either relative sliding velocity between the components can be rather low (starting of rotation in gear boxes, bearings, turbines, etc.) or can reverse (e.g. in pistons), or the external pressure is sufficiently high (metal forming). Again, simulations on the microscopic roughness level enable us to refine the existing macroscopic lubrication models.

In recent years, the problem of fluid transport along the contact interface between two solid bodies with representative rough surfaces has received much attention [START_REF] Persson | Theory of the leak-rate of seals[END_REF][START_REF] Dapp | Self-affine elastic contacts : percolation and leakage[END_REF]. Preliminary results for simulation of the contact of an elastic 3D body with a rigid plane and incompressible thin fluid flow in the interface are shown in Fig. 1. An example of the morphology of the contact patches is presented in Fig. 1a, and the simulation of the fluid flow through the resulting channels in the contact interface in Fig. 1b. Note that out-of-contact regions completely surrounded by a contact area are easily distinguishable, i.e. some of the contact patches are non-simply connected, see Fig. 1c. Therefore, under the increasing external load, applied to the solid body, the fluid may become trapped in these regions, which would inevitably add additional pressure on the contact interfaces and may affect the geometry of the surfaces.

This paper is organized as follows. The 2nd section is devoted to the trapped fluid problem : the framework is developed for monolithic coupling of the mechanical contact problem with pressurized fluid trapped in the wavy contact interface, and the real contact area, maximal frictional force and global coefficient of friction evolution under increasing external loading are studied. In the 3rd section different numerical approaches for the fluid/structure interaction are discussed and the problem statement for thin fluid flow through the wavy contact interface is presented. The 4th section summarizes the obtained results.

Trapped fluid problem 2.1 Background of the problem

Lubrication is an efficient mechanism of minimizing the direct contact of solids bodies, which consequently reduces friction and wear. However, if the applied external loads, pushing the contacting bodies together, are high enough or if the sliding velocities are small, the asperities of both surfaces can get in contact despite the presence of the lubricant, thus inevitably increasing friction. However, at the same time the lubricating fluid may be trapped in the valleys (pools) between contact patches, which would have a strong effect on the contact properties, especially if the fluid is highly incompressible. First, the trapped fluid resists to compression and thus opposes to the growth of the real contact area. Second, the external load is shared between the contacting asperities of the bodies and the pressurized fluid. Therefore, the integral value of the normal pressure in the contact area is reduced, and, since the maximal tangential frictional stress (in Couloumb's friction law) is proportional to the normal pressure, macroscopic friction coefficient between the two solid bodies is decreasing.

The effect of lubricant trapping on reduction of friction has been first understood in applications for cold metal forming processes [START_REF] Kudo | A note on the role of microscopically trapped lubricant at the tool-work interface[END_REF][START_REF] Nellemann | Real area of contact and friction stress -The role of trapped lubricant[END_REF]. In [START_REF] Azushima | Direct Observation of Contact Behaviour to Interpret the Pressure Dependence of the Coefficient of Friction in Sheet Metal Forming[END_REF] the regimes of lubrication corresponding to different levels of external pressure are studied, in particular, the escape of the trapped fluid from the pools into the contact area is predicted at sufficiently high loads, a regime when both real contact area and coefficient of friction decrease with increasing load. In [START_REF] Azushima | Permeation of Lubricant Trapped Within Pocket Into Real Contact Area on the End Surface of Cylinder[END_REF] experimental results and FEM simulations on the entrapment and escape of the fluid in the contact interface during upsetting of a cylinder are presented.

Kuznetsov [START_REF] Ye | Effect of fluid lubricant on the contact characteristics of rough elastic bodies in compression[END_REF] proposed an analytical solution for the 2D plane strain problem of contact between an elastic body with a wavy surface and a rigid half-space, taking into account compressible fluid trapped in the valleys between contacting peaks of the wavy profile. Kuznetsov used Westergaard's solution [START_REF] Westergaard | Bearing Pressures and Cracks[END_REF][START_REF] Johnson | The contact of elastic regular wavy surfaces[END_REF] for the contact pressure distribution without influence of the fluid, which is based on the assumption of the small slope of the wavy profile. Kuznetsov's solution describes the reduction of the contact reaction force, compared to Westergaard's solution, and therefore can predict the decrease of the global coefficient of friction. However, due to the assumption of the small slope, it cannot describe the escape of the lubricant and depletion of the real contact area.

Problem statement

We here the mechanical contact problem between a periodic elastic wavy surface and a flat rigid plane (the case which was historically the starting point in the study of contact of rough surfaces [START_REF] Westergaard | Bearing Pressures and Cracks[END_REF][START_REF] Johnson | The contact of elastic regular wavy surfaces[END_REF][START_REF] Ye | Effect of fluid lubricant on the contact characteristics of rough elastic bodies in compression[END_REF]) and take into account the influence of compressible or incompressible fluid trapped in the free volume between the two bodies, see Fig. 2a. The geometry of the problem and an example of the structural mesh are presented in Fig 2b, simulations were performed on a FE mesh with 1024 elements on the top surface of the solid body (19364 nodes in total). We assumed the plane strain state and the linear elastic isotropic constitutive law for the solid.

The initial gap between the surface of the body and the rigid plane, as well as the volume of this gap are given by :

g(x) = ∆ 1 -cos 2πx λ , V g = λ 0 ∆ 1 -cos 2πx λ dx = λ∆, (1)
where ∆ and λ are the amplitude and wavelength of the wavy surface profile, respectively. We apply the symmetry boundary conditions on the vertical walls of the considered solid body and a far-field external pressure p ext or a vertical displacement on the bottom surface.

2.3 Numerical simulation of the coupled mechanical contact/trapped fluid problem using the monolithic approach

Contact constraints

In case of unilateral contact between an elastic deformable body and a fixed rigid plane, the motion of the body is restricted by the plane. This geometrical constraint is formalized upon introduction of the normal gap function g n -a signed distance from the points on the surface of the deformable body to the rigid plane :

g n > 0 when the point is separated from the plane (inactive contact state), -g n < 0 when the point penetrates the plane (which is forbidden), -g n = 0 when the point is on the plane (active contact state). We will denote by Γ c the active contact zone, where the contact pressure σ n is non-zero. The constraints governing the unilateral frictionless contact problem are known as the Hertz-Signorini-Moreau conditions [START_REF] Yastrebov | Numerical methods in contact mechanics[END_REF] :

g n ≥ 0, σ n ≤ 0, σ n g n = 0 at ⇔ g n = 0, σ n < 0, at Γ c g n > 0, σ n = 0, at Γ \ Γ c . (2)
The constrained minimization problem for the energy of the mechanical system Π(u), where u is the displacement field, can be solved using the Lagrange multipliers method [START_REF] Yastrebov | Numerical methods in contact mechanics[END_REF][START_REF] Wriggers | Computational Contact Mechanics[END_REF]. The Lagrangian function is defined as :

L(u,λ c ) = Π(u) + Γ c λ c g n (u) dΓ c , (3)
where λ c ≤ 0 is the Lagrange multiplier function, the values of which are equal to the contact pressure.

Geometrical constraint for incompressible fluid

Let us denote by Γ f the part of the surface of solid body, which interacts with the pressurized fluid. The volume of the gap V g in the presence of trapped incompressible fluid must satisfy the following geometrical constraint :

V g ≥ V f = const, V g (u) = Γ f g n (u) d Γ f , (4)
where V f is the constant volume of the fluid inside the closed trap and Γ f is the projection of Γ f on the rigid plane. The trapped fluid may fill completely or partially the gap between the contacting surfaces, therefore it can be present in two different states : "inactive", when V f < V g and the fluid if not pressurized, and "active", when V f = V g , and the fluid is under pressure p f , see Fig. 3a, 3b. We may formulate this two states in a way similar to Hertz-Signorini-Moreau conditions

V ≥ V f , p f ≥ 0, p f (V g -V f ) 0 V g = V f , p f 0, (active state) V g > V f , p f = 0, (inactive state). (5)

Solution of the coupled problem with the Lagrange multipliers method

In the case of the inactive state of the trapped fluid, we have only the mechanical contact problem between the elastic body and the rigid plane, while if the fluid is in the active state, we must consider additionally the gap volume constraint [START_REF] Dapp | Self-affine elastic contacts : percolation and leakage[END_REF]. The Lagrange multiplier method may be used again in order to fulfill this constraint, which defines the combined functional for the coupled problem :

L(u,λ c , λ f ) = Π(u) + Γ c λ c g(u) dΓ c -λ f (V g (u) -V f ), (6)
where λ f ≥ 0 is the Lagrange multiplier for the trapped fluid problem, which is equal to the fluid pressure. The solution of the coupled problem is a stationary point of the Lagrangian (6), which requires the calculation of the variation :

δL(u, λ c , λ f ) = δΠ(u) + Γ c [δλ c g n (u) + λ c δg n (u)] dΓ c -δλ f (V g (u) -V f ) -λ f δV g (u) = 0. ( 7
)
To solve this problem, we implemented in FEM framework a monolithic coupling scheme in the framework of the Z-set software [14].

Simulation of the compressible fluid using the penalty method

The solution of the discussed problem can also be obtained with the penalty method. At the same time, the formulation under the penalty method is equivalent to considering compressible fluid. In accordance with the linear penalty method, instead of the λ f (V g (u) -V f ), the following term should be added in [START_REF] Nellemann | Real area of contact and friction stress -The role of trapped lubricant[END_REF] to take into account the trapped fluid constraint :

W f (u) = ε 2 V f -V g (u) 2 , x = x, if x > 0, 0, if x ≤ 0, ( 8
)
where ε is the penalty parameter and • is the Macauley bracket operator. Let us assume that the fluid is in active state. Calculating the variation of (8), we obtain the contribution of the trapped fluid to the balance of the virtual work :

δW f (u) = ε (V f -V g (u))δV g (u) = ε (V f -V g (u)) ∂V g (u) ∂u δu, (9)
where the term ε (V f -V g (u)) represents the fluid pressure p f . Note that under the penalty formulation, the current volume of the active fluid V g (u) is always smaller, than the initial fluid volume V f , which means that the fluid can no longer be considered as incompressible. For the linear penalty method the parameter ε corresponds to the modulus of compressibility K of the fluid -coefficient of proportionality between the change of volume of fluid and the hydrostatic fluid pressure, see [START_REF] Ye | Effect of fluid lubricant on the contact characteristics of rough elastic bodies in compression[END_REF] : p = p 0 + K (V 0 -V 0 where p 0 is the pressure in fluid, when it has volume V , and pressure p corresponds to a smaller volume V . If we that initially, when the volume was 0 , the fluid was not pressurized, then the connection between penalty parameter ε and modulus of compressibility of fluid K becomes transparent : ε = K/V f .

The influence of the incompressible trapped fluid on the contact problem

Results of our simulations of the coupled contact/trapped fluid problem show, that once the fluid becomes active, the real contact area reaches its maximum value and during the consequent loading is only monotonically decreasing, reaching zero value, i.e. opening the trap, at a certain step of the external loading. In Fig. 4a the evolution of the real contact area is presented for different ratios of the amplitude to the wavelength of the profile (∆/λ) and different ratios of the initial volume of the fluid to initial gap volume V f /V 0 . It is important to note, that for the case when the fluid fills completely the initial gap volume, the real contact area equals zero during the whole process of loading.

The computational results allow us to estimate the evolution of the value of the global coefficient of friction between an elastic body and a rigid plane under increasing external load affected by the presence of trapped fluid in the interface. We distinguish between global and local coefficients of friction by observing the problem from macroscopic (calculating the reaction forces on the solid body) and microscopic (studying the stress vector components on the rough contact surface) levels respectively. Due to the presence of the pressurized fluid, the macroscopic normal reaction force is the sum of integrals of the normal stress component over the contact and the fluid areas of the interface, while for calculation of the macroscopic tangential reaction force shear forces in the fluid are neglected, since the static friction is considered :

|F n | = Γ c |σ n | dΓ c + Γ f |p f | dΓ f , |F t | = Γ c σ t dΓ c . (10)
In the above formulas σ n and σ t are the normal and tangential components of the stress vector, respectively, and p f is the fluid pressure. The global coefficient of friction is introduced as the coefficient of proportionality between the maximal macroscopic tangential and normal reaction forces :

|F max t | = µ glob |F n |. Now let
us observe the problem on the microscopic level. We introduce the local coefficient of friction by the Coulomb's law : |σ t | ≤ µ loc |σ n |. The maximal tangential reaction can be expressed as :

|F max t | = µ loc Γ c |σ n | dΓ c . (11)
The evolution of the maximal reaction force is presented in Fig. 4b. Finally, we obtain the estimative value of the ratio between global and local coefficients of friction :

µ glob µ loc = Γ c |σ n | dΓ c Γ c |σ n | dΓ c + Γ f |p f | dΓ f . (12) (a) (b) (c)
FIGURE 4 -Evolution of the real contact area (a), the normalized contact normal reaction (b) and the global coefficient of friction (c) with respect to normalized external pressure for different ratios of the amplitude to the wavelength of the profile and different ratios of the initial volume of the fluid to initial gap volume. E * is the effective elastic modulus of the solid body [START_REF] Johnson | The contact of elastic regular wavy surfaces[END_REF].

From the above formulas it follows that global coefficient of friction is smaller or equal, than the local one : 0 ≤ µ glob ≤ µ loc . The results on the estimation of the ratio between global and local coefficients of friction are presented in Fig. 4c.

3 Coupling contact problem with thin fluid flow in the interface

Numerical approaches

Two different approaches of numerical solution of the fluid-structure interaction problem exist : Partitioned approach : Numerical solvers for the mechanical contact and fluid transport are separated and work sequentially, so that the data exchange between them must be established. Different resolution schemes under this approach exist, in the order of increasing accuracy :

-Unilateral coupling : both problems are solved only once each at every load step, and the mechanical solver provides the fluid solver the geometry of the contact interface, while the influence of the fluid on the mechanical problem is neglected.

-Weak coupling : at every load step the mechanical problem is solved and data is sent to the fluid transport solver, which in its turn solves the problem on updated geometry. At the next load step the mechanical problem is solved with additional pressure coming from the previous load step of the transport solver, however, the convergence of this coupled problem is not ensured.

-Strong coupling : the fluid transport problem is solved on the updated geometry after each iteration of the mechanical problem (the numerical simulation of contact is nonlinear and requires iterative resolution, e.g. Newton-Raphson method), which takes into account the updated value of the fluid pressure, and a convergence criterion is introduced and verified at the end of each load step.

Monolithic approach : The fluid pressure values are added as degrees of freedom (DOFs) to the nodes of the structural mesh, and the surface elements for solving the fluid problem are appended to this mesh. Therefore, the equations governing fluid flow are rendered into the global system of equations, which is solved at each iteration. When a convergence criteria is fulfilled, the solution is obtained for both displacement and fluid pressure fields.

Problem statement for incompressible flow in the contact interface

The problem of the fluid/structure interaction for the case of the thin fluid flow in the wavy contact interface between a 3D elastic body and a rigid plane (see Fig. 5) can be formulated as the following system of equations and constraints :

         ∇ • σ = 0 in Ω (13a) g n ≥ 0, p ≥ p f , (p -p f ) g n = 0 on Γ (13b) ∇ • g n (u) 3 ∇p f = 0 in Γ f (13c) p f | inlet = p i , p f | outlet = p o (13d)
for the unknown displacement field u and a scalar value of fluid pressure p f . Here σ is the mechanical stress tensor, defined in the solid body Ω, p is the pressure on the wavy surface Γ, g n is the gap between this surface and the rigid flat, (13a) is the balance of the momentum equation and (13b) are the Hertz-Signorini-Moreau conditions, modified to take into account the external fluid pressure p f , (13c) is the Reynolds equation for thin isoviscous incompressible flow, and Γ f ⊂ Γ is the part of the surface, which is out of contact. We apply periodic boundary conditions and the external pressure on the rigid flat, and p i and p o are the fluid pressure at the inlet and outlet, respectively.

Conclusions

We develop in the FEM framework a monolithic resolution scheme for coupling mechanical contact with the thin fluid flow in the interface. This complex problem is split into two sub-problems : the study of the trapped fluid in the contact interface and of the fluid flow through a wavy channel. For both problems strong monolithic coupling schemes are elaborated and implemented in the FEM software Z-set. We demonstrated that the trapped fluid influence on the solution is more complicated, than it can be predicted analytically under the assumption of infinitively small slope of the roughness profile :

-If the compressibility modulus of the fluid is higher then the one of the solid (e.g. if the fluid is considered incompressible), then once the fluid becomes pressurized, the contact area is monotonically decreasing under increasing external load.

-If the incompressible fluid fills completely the gap between the surfaces, it cannot be trapped.

-If the fluid fills the initial gap partially, the static friction force becomes a non-monotonic function of the applied external pressure, does have a maximum value and decreases to zero value under consequent load.

For the problem of the fluid flow through a wavy contact interface we implement both partitioned and monolithic coupling approaches, compare their performance and verify the results using an approximate analytical solution, which was also derived.

FIGURE 1 -

 1 FIGURE 1 -(a) Morphology of contact patches for the contact of a 3D body with a rigid plane : black is the contact area, white is out of contact and red is "trapped". (b) Incompressible fluid flow through the same contact interface (color represents the flow intensity). (c) An example of non-simply connected contact patch : A is the contact area, A t is out-of-contact (trapped) area.

FIGURE 2 -

 2 FIGURE 2 -(a) Problem statement. (b) Geometry of the model example FE mesh.

  Trapped fluid is in the "inactive" state. g is the normal gap between the contacting surfaces, V g -volume of this gap, V f -volume of the fluid.

  Trapped fluid is in the "active" state, the fluid fills the whole gap volume, p ext is the external pressure, p f is the fluid pressure, σ n is the contact normal pressure.

FluidFIGURE 5 -

 5 FIGURE 5 -Fluid flow through a periodic wavy contact interface.

Acknowledgments

The authors acknowledge the financial support from MINES ParisTech (Thèse-Open) and Safran Tech. Enriching discussions and help of Julien Vignollet are greatly appreciated.