SUPERSYMMETRIES AND COHOMOLOGY OF GRAPH COMPLEXES. SERGUEI BARANNIKOV

Keywords: 1991 Mathematics Subject Classification. Primary 05C38, 15A15; Secondary 05A15, 15A18 Supersymmetry, moduli spaces, Chern-Simons

HAL is

Introduction.

I study the noncommutative generalisation of the Chern-Simons type construction of cohomology classes of graph complexe from [K2]. I propose the extension of the initial framework beyond the paradigm of homological algebra. My main initial ingredient is the h-invertible supersymmetry generator I acting on finitedimensional algebra, whose square is nonzero in general, I 2 = 0. The second principal result is the construction of boundaries on the stable ribbon graph complex associated to a pair of certain operators. It is used to construct the Virasoro algebra action on the stable ribbon graph complexe in [B3].

Notations. For an element a from super vector space A I denote by πa ∈ ΠA the same element considerd with inversed parity. char(k) = 0. The parity of a is denoted by a.

Let A be finite-dimensional Z/2Z-graded associative algebra with odd invariant inner product g(•, •) : S 2 A → Πk g(ab, c) = g(a, bc) g(a, b) = (-1) ab g(b, a)

If the algebra has an identity then such an inner product is the same as an odd trace l : A/[A, A] → Πk, g(a, b) = l(ab) In general the linear functional l is well defined via l(ab) = g(a, b) on the image of the multiplication map A ⊗2 → A.

Examples: q(n), H * DR on odd-dimensional manifold, Cl 1 .

Supersymmetry.

Let I be an odd derivation acting on A, preserving the inner product:

g(Ix, y) = (-1) x+1 g(x, Iy)

or, if the algebra has an identity, equivalently, l| im(I) = 0

Examples:[Λ, •] with Λ = 1, i v with v = 0, ... Notice that the square of the derivation I is an even derivation of A, which is nonzero in the general case. In the general case, the condition (1) implies ker(I) belongs to the orthogonal complement of itself, or since I is anti-selfadjoint,

ker(I) ⊂ Im(I)
Then the restriction of I on ker(I 2 ) induces an odd linear isomorphism (ker(I 2 ))/ ker(I)

I ≃ ker(I) One can choose subspaces L i , so that L i ⊕ ker(I) i = ker(I 2 ) i , i = 0, 1,
I| L ′ = 1 2 I -1 | L ′ .
It is easy to check that I is self-adjoint.

Definition 1. I call such a derivation I satisfying (2.1) h-invertible. This notion extends the notion of contractible differential to the case when I 2 = 0.

The ribbon graph complex.

Recall the definition of the (even) ribbon graph complex (C * , d), see ( [K2], [GK]). Definition 2. A ribbon graph G is a triple (F lag(G), σ, η), where F lag(G) is a finite set, whose elements are called flags, σ is a permutation from Aut(F lag(G)) with orbits of length greater than two, and η is a fixed-point free involution acting on F lag(G).

The vertices of the graph correspond to the cycles of the permutation σ. The set of vertices is denoted by V ert(G). The subset of F lag(G) corresponding to vertex v is denoted by F lag(v). The set F lag(v) has natural cyclic order since it is a cycle of σ. The cardinality of F lag(v) is called the valence of v and is denoted n(v). It is assumed that n(v) ≥ 3. The edges of the graph are the pairs of flags forming a twocycle of the involution η. The set of edges is denoted Edge(G). The subset of edges which are loops is denoted by Loop(G). The edges which are not loops are called "regular" and I denote the corresponding subset of Edge(G) by Edge r (G). The two element subset of F lag(G) correspoding to an edge e ∈ Edge(G) is denoted flag(e). I denote by S G the Riemann surface associated with the ribbon graph G (see [K1], [B1] and references therein). I denote by |G| the one-dimensional CW-complex which is the geometric realisation of the underlying graph G. Definition 3. The even ribbon graph complex is the vector space generated by equivalence classes of pairs (G, or(G)), where G is a connected ribbon graph, or(G) is an orientation on the vector space

⊗ v∈V ert(G) (k F lag(v) ⊕ k) and the relation (G, -or(G)) = -(G, or(G)) is imposed. The differential is d(G, or(G)) = e∈Edger(G) (G/{e}, induced orientation)
The identification of my definition of the orientation with that one from ([K2]) follows from ( [START_REF] Getzler | Modular operads[END_REF]4.14). A choice of orientation can be fixed by a choice of a flag from F lag(v) for all vertices v having even number of flags and a choice of an order on the set of such vertices. Two different choices are related by a set of some cyclic permutations on F lag(v) for vertices v having even number of flags and a permutation on the set of such vertices. The two corresponding orientations differ by the sign equal to the product of signs of all these permutations.

The induced orientation on G/{e} can be easily worked out. In the case when the edge e connects two vertices v 1 and v 2 with even number of flags, assume, that the order on the set of vertices with even number of flags is such that v 1 < v 2 and no other such vertices are between them, and that the flags f i ∈ F lag(v i ), i = 1, 2, fixing the orientation, form the edge e. Then the induced orientation for G/{e} is defined by placing the new vertex v 0 , obtained from v 1 and v 2 after shrinking of e, to the place of v 1 and by choosing the element corresponding to σ G (f 1 ) in F lag(v 0 ). In the case when the edge e connects two vertices v 1 and v 2 with odd number of flags, the induced orientation for G/{e} is defined by placing the new vertex v 0 , to the lowest level in the hierarchy of vertices with even number of flags, and by choosing the flag corresponding to σ G (f ) in F lag(v 0 ),where f is either of the two flags forming e.

I denote via (C * , δ) the complex dual to the (even) ribbon graph complex. We identify the generators of both complexes corresponding to oriented ribbon graphs when it does not seem to lead to a confusion.

The partition function.

Since g is odd, the symmetric dual inner product g -1 is defined on Π Hom(A, k), the dual space with parity inversed. If P denotes the isomorphism A → Π Hom(A, k) induced by g, then g -1 (ϕ, ψ) = g(P -1 ϕ, P -1 ψ).

Denote by I * the dual to I, odd symmetric operator, acting on Π Hom(A, k):

I * ϕ(a) = (-1) ϕ ϕ( Ia),
one can check that

I * = P IP -1 ,
since I is symmetric. The odd symmetric operator I * defines the even symmetric pairing g -1

I on Π Hom(A, k) : g -1 I (ϕ, ψ) = g -1 ( I * ϕ, ψ), g -1 I ∈ (ΠA) ⊗2
Definition 4. Given a ribbon graph G, the tensor product of the even symmetric tensors (g -1 I ) e , associated with every edge e of G, (g -1 I ) e ∈ (ΠA) ⊗f lag(e) , defines the canonical element

g -1 I,G = ⊗ e∈Edge(G) (g -1 I ) e , g -1 I,G ∈ (ΠA) ⊗F lag(G) . Definition 5. Define the (-1) n+1 -cyclically symmetric tensors α n ∈ Hom((ΠA) ⊗n , k), n ≥ 2 α n (πa 1 , . . . , πa n ) = (-1) Σ n-1 i=1 Σ i j=1 a j l(a 1 • a 2 • . . . • a n-1 • a n ) (the tensor from V ⊗n is (-1) n+1
-cyclically symmetric if under the elementary cyclic shift it is multiplied by the Koszul sign resulting from parities of elements of V plus the sign of the cyclic permutation, which is (-1) n+1 )

Notice that the space F lag(v) is canonically oriented for a vertex v ∈ V ert(G) of odd valency, n(v) ≡ 1 mod 2, thanks to the cyclic order. For a vertex v ∈ V ert(G) of valency n(v) ≡ 0 mod 2, let or(v) denotes an orientation on the vector space F lag(v). Because of cyclic order on F lag(v), or(v) is fixed canonically by a choice of an element f ∈ F lag(v). Definition 6. The tensors α 2n+1 , n ∈ N are cyclically symmetric and define canonical elements α v ∈ Hom((ΠA) ⊗F lag(v) , k) for all vertices of odd valence. The tensors α 2n , n ∈ N, are cyclically antisymmetric, they define canonical elements α v ∈ Hom((ΠA) ⊗F lag(v) , k) for all vertices of even valence equipped with a choice of orientation or(v). Proposition 2. Given an oriented ribbon graph G with orientation or(G), the product over all vertices v of the (-1) n(v)+1 -cyclically symmetric tensors α v defines the canonical element

α G,or(G) = ⊗ v∈V ert(G) α v , α G,or(G) ∈ Hom((ΠA) ⊗F lag(G) , k).
Proof. The orientation or(G) is a choice of an element of F lag(v) for all vertices v of even valence, and a choice of an order on the total set of such vertices of even valencies. The first part gives a choice of orientation for all vertices of even valence. Notice that the parity of α n is even for odd n, and odd for even n. Therefore the choice of order on the set of vertices of even valency the product ⊗ v∈V ert(G) α v gives a well-defined element from Hom((ΠA) ⊗F lag(G) , k). In more details, the orientation or(G) fixes the signs in the definition of α G,or(G) ∈ Hom((ΠA) ⊗F lag(G) , k) by dictating for every vertex of even valence n(v) which element a i is to be placed the first inside α n(v) , and then in which order the tensors α n(v) are to be multiplied, the other choices are irrelevant because the sign of cyclic permutation is always positive for odd number of elements, and because α n defines an even tensor for odd n.

I * ϕ(a) = (-1) ϕ ϕ(Ia)
The action of any endomorphism of the super vector space Hom(ΠA, k) is naturally extended to its tensor algebra ⊕ n (Hom(ΠA, k)) ⊗n as a derivation, by the Leibitz rule. The dual action on ⊕ n (ΠA) ⊗n corresponds to the similar extension of the action of I on ΠA. Proposition 3. The result of action of the operator I on g -1

I is I(g -1 I ) = g -1
Proof.

I(g -1 I ) = g -1 I (I * ϕ, ψ) + (-1) ϕ g -1 I (ϕ, I * ψ) = g -1 ([I * , I * ]ϕ, ψ) = g -1 (ϕ, ψ)
Consider the partition functions of an oriented ribbon graph G and the graph G ′ = G/{e ′ } obtained from G by contracting the edge e ′ ∈ Edge r (G), with its induced orientation. The previous proposition shows that acting by I on the twotensor associated with the edge e ′ gives

I(g -1 I ) e ′ = g -1 e ′ ,
where g -1 e ′ ∈ (ΠA) ⊗{f,f ′ } , e ′ = (ff ′ ), denotes the two-tensor inverse to g, associated with the edge e ′ . I claim that inserting g -1 e ′ instead of (g -1 I ) e ′ for the edge e ′ which is not a loop gives Z Proof. The part of the contraction involving

g -1 e ′ is µ,ν (-1) ν α k+1 (v 1 . . . v k u µ )g -1 (u µ , u ν )α n-k+1 (u ν v k+1 . . . v n )
where {u µ } is a basis in (ΠA) and {u µ } is the dual basis, u µ and u ν represent the two flags of the edge e ′ , and

v 1 ⊗ . . . ⊗ v k ⊗ v k+1 . . . ⊗ v n ∈ (ΠA) ⊗F lag(v)
represents the flags corresponding to the new vertex of G/{e ′ } to which the edge e ′ shrinks. Using the linear algebra identity

b = µ u µ u µ (b) = µν (-1) ν u µ g -1 (u µ , u ν )g(u ν , b)
.

with b = v k+1 • . . . • v n I get α n (v 1 . . . v n ) = µ,ν (-1) ν α k+1 (v 1 . . . v k u µ )g -1 (u µ , u ν )α n-k+1 (u ν v k+1 . . . v n )
i.e. the tensor α v associated with the new vertex.

Next proposition shows that acting by I * on α n gives zero because I is a derivation of A, preserving g.

Proposition 5. I * (α n ) = 0 Proof. It follows from (5.2) n i=1 (-1) εi l(a 1 • . . . • (Ia i ) • . . . • a n ) = l(I(a 1 • . . . • a n )) = 0
where

ε i = i-1 j=1 a j , n ≥ 2.
6. The boundary of the cochain Z I .

Combining the three propositions we get the following theorem.

Theorem 1. The boundary of the cochain Z I (4.1) is given by the sum over graph with loops, each loop contributing the term similar to the one described in proposition 4 for regular edges:

δZ I = [G],Loop(G) =∅ (G, or(G))Z loop,(G,or(G)) I where Z loop,(G,or(G)) I = -( e∈Edger(G) (g -1 I ) e )I( l∈Loop(G) (g -1 I ) l ) ( v∈V ert(G) α v ).
Proof. The boundary of

Z I δZ I = [G ′ ] Z (G ′ ,or(G ′ )) I δ(G ′ , or(G ′ )) = [G] (G, or(G)) e∈Edger(G) Z (G/{e}, or(G/{e})) I
For any ribbon graph G we have 0

(Prop. 5) = ⊗ e∈Edge(G) (g -1 I ) e I * (⊗ v∈V ert(G) α v ) = = I ⊗ e∈Edge(G) (g -1 I ) e (⊗ v∈V ert(G) α v ) (Prop. 3,4) = =   e∈Edge r (G) Z (G/{e}, or(G/{e})) I   + Z loop,(G,or(G)) I 7.
Compactification and the stable ribbon graph complex (even scalar product case).

To remedy the problem with contribution of loops, since they are not contracted in the ribbon graph complex, one has to consider the complex in which all the edges, including the loops, are allowed to contract. This leads to the complex of stable ribbon graphs and the combinatorial compactification of the moduli space of Riemann surfaces, which was introduced by Kontsevcih in [K1], two years before [K2], from completely different point of view in connection with the proof of Witten conjecture. As far as I know it was not until the paper ( [B1]) that this compactification reappered in a new context more than ten yeras later, in my work devoted to study of noncommutative Batalin-Vilkovisky equation. In loc.cit I have related the complex of stable ribbon graphs with some modular variant of cyclic associative algebras. This leads, using in particular the dual to the map from loc.cit., proposition 11.3, and the same propagator (g -1 I ), to the construction of weights on the stable ribbon graphs, completing the cochain Z I to a coboundary free cochain. Definition 8. A stable ribbon graph G is a data (F lag( G), σ, η, λ, {γ v }), where F lag( G) is a finite set, whose elements are called flags, λ is a partition on the set F lag( G), σ is a permutation from Aut(F lag( G)), stabilizing λ, η is a fixed-point free involution acting on F lag( G) , and γ v ∈ Z ≥0 is a nonnegative integer attached to every cluster v of λ. The clusters of the partition λ are the vertices of stable ribbon graph G. The edges are the orbits of the involution η. This data satisfy the stability condition ...

In particular to any vertex v corresponds the integer γ v and a permutation σ v on the subset of flags F lag(v) frm the cluster v, so that σ = Π v σ v . I denote by Cycle(v) the set of cycles of the permutation σ v attached to a vertex v ∈ V ert( G), and by Cycle( G) the union of such sets which is the set of cycles of σ. For c ∈ Cycle( G) I denote by F lag(c) the corresponding subset of F lag( G). Denote b v = |Cycle(v)| 7.1. Contraction of edges on the stable ribbon graphs. In order to describe the action of the differential on the stable ribbon graph G one needs to describe the result of the contraction of an arbitrary edge G/{e}. The contraction of edges in the stable ribbon graphs is described combinatorially via compositions and contractions on permutations, see ( [B1]) and references therein, representing the corresponding geometric operations on S G . For the reader convenience I rephrase it here. For an edge ending at vertices with γ v = 0, b v = 1 this reproduces the standard contraction on ribbon graphs. I identify the permutation σ G with multicyclic order on F lag( G), i.e. the collection of cyclic orders on the orbits of σ. Then the result of the contraction of an edge e = (f f ′ ), f, f ′ ∈ F lag( G) is the stable ribbon graph G/{e} such that

F lag( G/{e}) = F lag( G)\{f, f ′ }, σ G/{e} = (ff ′ ) • σ G | F lag( G)\{f,f ′ } ,
as a multicyclic order, i.e. σ G/{e} is the multi-cyclic order induced on F lag( G)\{f, f ′ } by the multi-cyclic order on F lag( G) represented by the product (f

f ′ ) • σ G , natu- rally η G/{e} = η G | F lag( G)\{f,f ′ }
as a map, i.e. the involution η G/{e} is the restriction of the involution η G on the subset

F lag( G)\{f, f ′ }. If an edge e = (f f ′ ), f, f ′ ∈ F lag( G) is not a loop, i.e.
f, f ′ are from two distinguished clusters v and v ′ of λ, then the clusters v and v ′ collide to the new cluster having γ = γ v +γ v ′ . If an edge e is a loop then no vertices must collide and the partition λ

G/{e} on F lag( G)\{f, f ′ } is induced from λ G , if the flags f, f ′ are from the same cycle of σ G v then γ G/{e} v = γ G v and if they are from different cycles of σ G v then γ G/{e} v = γ G v . Lastly if f, f ′ are neighbors in a cycle of σ G v , i.e. say σ G v (f ) = f ′ ,
then, by definition, G/{e} = ∅ , so that such loop do not contribute to the boundary operator. This exception is dictated by the relation of the stable ribbon graphs with the combinatorial compactification of the moduli spaces from ( [K1]), and leads to the interesting condition on the algebra A.

8. The differential on the stable ribbon graph complex.

Definition 9. The (even) stable ribbon graph complex is the vector space generated by equivalence classes of pairs ( G, or( G)), where G is a stable ribbon graph, or( G) is an orientation on the vector space

⊗ v∈V ert( G) (k F lag(v) ⊕ k Cycle(v) ) and the relation ( G, -or( G))) = -( G, or( G)) is imposed. The differential is d( G, or( G)) = e∈Edge( G) ( G/{e}, induced orientation)
Using the multi-cyclic order on F lag( G) ,as in section *** above, a choice of orientation is fixed by a choice of a flag from every cycle of σ of even lenght and a choice of order on the total set of such cycles. The induced orientation is also analogous to the case of usual ribbon graphs, see ( [B1]) for details. 9. Weights on stable ribbon graphs.

I start by constructing the tensor α σ v ,γ v ∈ Hom((ΠA) ⊗F lag(v) , k) for any given vertex v ∈ V ert( G) with permutation σ v ∈ Aut(F lag(v)) and integer γ v attached, together with a choice of orientation or(v) from k F lag(v) ⊕ k Cycle(v) . Let σ v = (ρ 1 . . . ρ r ) . . . (τ 1 . . . τ t ) be a representation of σ v compatible with or(v), in the for which the tensor α σv,γ v is odd. Therefore for a choice of or( G) the product ⊗ v∈V ert( G) α σv,γ v gives a well-defined element from Hom((ΠA) ⊗F lag( G) , k). Definition 10. A choice of orientation or( G) on a stable ribbon graph G allows to define the linear functional α G,or( G) on (ΠA) ⊗F lag( G) :

α G,or( G) = ⊗ v∈V ert( G) α σv,γ v
For the propagator I use the same bilinear form associated with h-inverse of the odd supersymetry I. Definition 11. Given a ribbon graph G, the tensor product of the even symmetric tensors (g -1

I

) e , associated with every edge e of G, (g -1

I

) e ∈ (ΠA) ⊗f lag(e) , defines the canonical element

g -1 I, G = ⊗ e∈Edge( G) (g -1 I ) e , g -1 I, G ∈ (ΠA) ⊗F lag( G) . Definition 12. The partition function Z G,or( G) I of an oriented stable ribbon graph G is the contraction of ⊗ v∈V ert( G) α σv,γ v with ⊗ e∈Edge( G) (g -1 I ) e . As above, the element Z G,or( G) I ( G, or( G)) of ( C * ,

δ) does not depend on the choice of or( G).

The sum over all equivalence classes of connected stable ribbon graphs defines the cochain Z I (9.4)

Z I = [G] Z G,or( G) I ( G, or( G)), Z I ∈ ( C * , δ)
10. The cancelation of anomaly.

In this section I discuss the condition imposed on A in order that the weights introduced below behave correctly with respect to the contraction of a loop encircling a boundary component. Condition 2. For any a ∈ A the super trace of the operator of multiplication by a is zero:

(10.1) µ (-1) µ g(u µ , a • u µ ) = 0
Below I describe different sufficient conditions for (10.1) to hold. All of them trivially hold in our basic examples.

Assume that I( i [p i , q i ]) = 0, p i , q i -symplectic basis in L 0 for g(I•, •) in particular, for example if ker(I) 1 = 0. Proposition 7. Assume that I( i [p i , q i ]) = 0, where p i , q i -symplectic basis in L 0 for g(I•, •) then (10.1) holds Proposition 8. Assume that A 0 is semisimple,then (10.1) holds Proof. The statement is trivial for a ∈ A 1 . Let {x µ |x µ ∈ A 0 } be a linear basis in A 0 and {ξ µ |ξ µ ∈ A 1 } be the dual basis in A 1 , so that where e µ is the orthonormal basis for t in A 0 ⊗ k k.

Proposition 9. Assume that the factor algebra by the nil radical A 0 /nil(A 0 ) is simple, then (10.1) holds.

Proposition 10. Contracting any loop whose flags are neighbors in the sense that σ(f ) = f ′ , so that the loop encircles some boundary component of the surface S( G), gives zero. ) e ′ = g -1 e ′ , where g -1 e ′ ∈ (ΠA) ⊗{f,f ′ } , e ′ = (f f ′ ), denotes the two-tensor inverse to g. The next proposition shows that, inserting g -1 e ′ instead of (g -1 I ) e ′ for arbitrary edge e ′ and contracting with α G,or( G) gives Z ) e for e = e ′ and h e ′ = g -1 e ′ . Proof. Consider first the case when e ′ is not a loop. Then the term of the contraction of

µν (-1) ν α k+2 (v 1 . . . v k u µ u ν )g -1 (u µ , u ν ) = 0 Proof. Taking a = v 1 • . . . • v k the statement
⊗ v∈V ert( G) α v with ⊗ e∈Edge( G) ′ h e , involving g -1 e ′ is µ,ν (-1) ν α σ v ,γ v (a 1 , . . . a k , U µ )g -1 (U µ , U ν )α σ v ′ ,γ v ′ (U ν , a k+1 , . . . , a n )
where {U µ } is a basis in (ΠA) and {U µ } is the dual basis in Hom((ΠA), k) , U µ and U ν represent the two flags of the edge e ′ . Using the identities (9.2) and ( 9.

= µ U µ U µ (b) = µν (-1) ν U µ g -1 (U µ , U ν )g(U ν , b). with b = (-1) ǫ µ 1 ,...,µ bv -1 a τ 2 . . . a τ t e µ 1 a ρ 1 . . . a ρ r e µ 1 e µ 2 . . . e µ bv -1 γ v i=1 ( ξ i ,ζ i e ξ i e ζ i e ξ i e ζ i )
I get the tensor α σv,γ v with b substituted instead of U µ . Using again (9.2) and (9.3) to bring it to the standard form( 9.1), I get precisely the tensor associated with the new vertex in G/{e ′ }, i.e. with the two permutations σ v ′ and σ v ′ merged at the flags of e ′ , with γ v new = γ v + γ v ′ etc. Let's now e ′ = (f f ′ ) is a loop , f, f ′ ∈ f lag(v). Then if f and f ′ are in the same cycle of σ v , assuming that flags f, f ′ are not neighbors, σ(f ) = f ′ , σ(f ′ ) = f . : e ′ instead of (g -1 I ) e ′ gives zero because of the property (10.1) imposed on A.

12. The boundary of the extended cochain Z I .

Combining the results from the previous sections I get the following theorem. Same arguments as in the previuos section show that if one modifies I via

I → I + [I, B]
then the cohomology cochain is modified by a coboundary .

Condition 1 .

 1 Let the kernel of the derivation I is isotropic with respect to the pairing: g(•, •)| ker(I) = 0 or, if the algebra has an identity, equivalently, l| ker(I) = 0 Proposition 1. Any such derivation is invertible in the following homotopic sense. There exists an odd self-adjoint operator I, acting on A, such that: (2.1) [I, I] = Id Proof. If ker(I) = 0 then I is a linear isomorphism. Then I take simply the one-half of the inverse to I

  and that L 0 is orthogonal to L 1 . Define I on ker(I) as the inverse to the odd isomorphism L I ≃ ker(I), where L = L 0 ⊕L 1 . Extend I to ker(I 2 ) by I| L = 0. Then [I, I]| ker(I 2 ) = Id. Let L ′ be the orthogonal complement to ker(I 2 ) in A. The inner product is non-degenerate on ker(I 2 ) and we have the direct sum decomposition (2.2) L ′ ⊕ ker(I 2 ) = A, preserved by I. Then restriction of I on L ′ is a linear isomorphism and I extend I to A by

Definition 7 .

 7 The partition function Z G,or(G) I of an oriented ribbon graph G is the contraction of ⊗ v∈V ert(G) α v with ⊗ e∈Edge(G) (g -1 I ) e . The sum over all equivalence classes of connected ribbon graphs defines the cochain Z I or(G)), Z I ∈ (C * , δ) Notice that the element Z G,or(G) I (G, or(G)) of (C * , δ) does not depend on the choice of or(G), since a change of orientation changes the signs of both Z G,or(G) I and (G, or(G)). 5. Action of I on the tensors g -1 I and α n . I denote by I * the dual to I odd antisymmetric operator, acting on Hom(ΠA, k):

(

  G/{e ′ },or(G/{e ′ }) I . Proposition 4. The partition function Z G/{e ′ },or(G/{e ′ }) I, for a regular edge e ′ , is equal to the contraction of ⊗ v∈V ert(G) α v with ⊗ e∈Edge(G) ′ h e where h e = (g -1 I ) e for e = e ′ and h e ′ = g -1 e ′ .

  g(x µ , ξ ν ) = δ µν Let us denote by K a the operator of left multiplication by a acting on A and by R a the operator of right multiplication. Fromg(x µ , aξ µ ) = g(x µ a, ξ µ ) it follows that Tr K a | A1 = Tr R a | A0 Let us show that Tr R a | A 0 = Tr K a | A 0 . If A 0 is semisimple then t(a, b) = T rK ab | A 0 is a nondegenerate invarianteven inner product on A 0 and T rK a | A0 = µ t( e µ , a e µ ) = µ t( e µ a, e µ ) = Tr R a | A0

  is reduced to (10.1). 11. Action of I on the tensors α σv,γ v and g -1 I, G . 11.1. Action of I on the tensors α σv,γ v . Proposition 11. (11.1) I * (α σv,γ v ) = 0 Proof. It follows from the fact that I is a derivation of the multiplication and of the bilinear form. It follows from g(Ie ν , e µ ) + (-1) e ν g(e ν , Ie µ ) e µ (a+1) I(e µ )ae µ + ν (-1) (e ν +1)a e ν aI(e ν ) = 0 for any a ∈ A. Now (11.1) follows from (5.2). The immediate consequence is the invariance of α G,or( G) under the action of derivation I. Proposition 12. I * α G,or( G) = 0 11.2. Action of I on g -1 I, G and contractions of edges. As it was shown in the proposition 3, acting by I on the two-tensor associated with an edge e ′ gives I(g -1 I

(

  G/{e ′ },or( G/{e ′ }) I , the partition function of the oriented stable ribbon graph G/{e ′ }. Proposition 13. For arbitrary edge e ′ the partition function Z ( G/{e ′ },or( G/{e ′ }) I is equal to the contraction of α G,or( G) with ⊗ e∈Edge( G) ′ h e where h e = (g -1 I



  3) the tensor α σ v ′ ,γ v ′ can be represented in the form:l   (-1) ǫ ( µ 1 ,...,µ bv -1 U ν a τ 2 . .. a τ t e µ 1 a ρ 1 . . . a ρ r e µ 1 e µ 2 . . . e µ bv -1 γ v i=1 ( ξ i ,ζ i e ξ i e ζ i e ξ i e ζ i ))  Using as above the linear algebra identity b

  ν g -1 (U µ , U ν )e κ a ρ 1 . . . a ρ i U µ a ρ i+1 . . . a ρ j-1 U ν a ρ j . . . a ρ r e κ = = µ,κ e κ a ρ 1 . . . a ρ i e µ a ρ i+1 . . . a ρ j-1 e µ a ρ j . . . a ρ r e κ Using (9.3) it is transformed to µ,κ e κ a ρ 1 . . . a ρ i a ρ j . . . a ρ r e κ e µ a ρ i+1 . . . a ρ j-1 e µ And the tensor α σv,γ v is transformed to α σ new v ,γ v corresponding to the permutation σ new v obtained from σ v by dissecting one cycle into two at flags f and f ′ . Similarly if f and f ′ are in the two different cycles then the result is the tensor α σ new v ,γ new v corresponding to the permutation σ new v obtained from σ v by merging the two cycles at flags f and f ′ and with γ new v = γ v + 1. In both cases I get precisely the tensor corresponding to the tranformed vertex v in G/{e ′ }. Finally if f, f ′ are neighbors,say σ(f ) = f ′ , then the insertion of g -1

Theorem 2 .(

 2 The boundary of the cochain Z I (9.4) is zeroδ Z I = 0 Proof. The boundary of Z I δ Z I = [ G ′ ] Z ( G ′ ,or( G ′ )) I δ( G ′ , or( G ′ )) = [ G] ( G, or( G)) e∈Edge( G) Z ( G/{e}, or( G/{e})) I For any stable oriented ribbon graph G I have e∈Edge( G) (g -1 I ) e ⊗ v∈V ert( G) α ασ v ,γ v = = ⊗ e∈Edge( G) (g -1I) e I * ⊗ v∈V ert( G) α ασ v ,γ v Gauge transformations and coboundaries.

sense that the order ρ 1 < . . . < τ t on flags together with the order (ρ 1 . . . ρ r ) < . . . (τ 1 . . . τ t ) on cycles gives or(v), put (9.1) α σv,γ v (πa

where {e µ },{e µ } is a pair of dual basises in A, g(e µ , e ν ) = δ µ ν , ǫ is the Koszul sign (taking into acount the passing of all π's to the left and then putting a i inside (-1) Σµ i e µ 1 e µ 1 . . . e µ bv -1 e µ bv -1 ). Proposition 6. For any a, b ∈ A (9.2) µ (-1) e µ (a+b+1) e µ abe µ = (-1) ab ν (-1) e ν (a+b+1) e ν bae ν .

For any a, b ∈ A,

Therefore, It follows from (9.2) and ( 9.3) that for every cycle (ρ 1 . . . ρ r ) of σ v the expression (9.1) is (-1) r+1 -cyclically symmetric with respect to cyclic permutations of πa ρ 1 . . . πa ρ r . And that the expression (9.1) is invariant under the changing the order of cycles in the representation of σ, up to the sign taking into account that the total parity of e µ 1 a ρ 1 . . . a ρ r e µ 1 differs from the parity of πa ρ 1 . . . πa ρ r by the factor (-1) r+1 . Therefore, for a fixed choice of or(v), the expression (9.1) gives a well-defined element α σv,γ v ∈ Hom((ΠA) ⊗F lag(v) , k). Notice that for a vertex with γ v = 0 , b v = 1 this gives the tensor α v , defined above.

A choice of orientation or( G) on stable ribbon graph can be identified with a choice of orientation or(v) on every vertex plus a choice of order on the set of vertices with odd number of cycles of even length. These are precisely the vertices


Philippe Tanguy
email: philippe.tanguy1@insa-rennes.fr

Fabienne Nouvel

Patrice Maziéro

Power Line Communication standards for in-vehicle networks

This paper deals with the in-vehicle networks. We propose to study a network which do not need new wires called Power Line Communication (PLC). Indeed, the automotive communication networks has evolved and the electronic devices in-vehicle are widespread. For example, drive-by-wire systems have actuators, engine, sensor and microprocessor to replace mechanical or hydraulic systems in vehicles. Moreover, electronic control unit (ECU) communicates and exchanges data. These needs of data sharing between ECU or between new services like multimedia involve to research new buses of communication with high throughputs. The CAN, LIN and FlexRay are wire protocols of communication usually used in the same vehicles and FlexRay has the highest throughput (10 Mbps). It appears that with the increase of electronic devices there is a wire harness bottleneck. To reduce wires and to have high throughputs (> 10 Mbps), we propose to study the feasibility of PLC indoor standards in-vehicles. PLC are usually used in indoor networks. In this paper, a comparison of two PLC standards with throughput measurements thanks to commercial PLC modem in-vehicle is carried out: HomePlug Av (HPAV) and High Definition Power Line Communication (HD-PLC).

I. INTRODUCTION

The automotive industry use more and more electronic devices for the security, to replace the mechanic systems (Xby-Wire), for multimedia. A growth of wire harnesses appears and a need of high throughput involve to find new buses of communication. Up to now the CAN, LIN and FlexRay are buses of communication usually used in-vehicles. And FlexRay has the highest throughput (10 Mbps).

We propose to study network which do not need new wires called Power Line Communication (PLC). Indeed PLC is an interesting solution for indoor networks and now the PLC are commonly used. That's why, several standards appeared on the market like HPAV, HD-PLC Alliance, Spidcom or Universal Powerline Alliance (UPA). We study two different indoor PLC modems using HomePlug Av [START_REF]HomePlug Powerline Alliance[END_REF] and HD-PLC [START_REF]Official website of the High Definition Power Line Communication Alliance (HDPLCA)[END_REF] standards in order to have an idea about the feasibility to adapt these standards in a car for example. More particularly, we are interested by the behaviour of PHY/MAC parameters of these standards to evaluate the feasibility of high throughput over DC line in-vehicle. In this paper a comparison between the two standards is done in term of throughput. In fact, we studied the TCP throughput between two PC in different points of a car. We used different typical scenario like car moving in order to test several use cases.

II. PLC IN-VEHICLES

To our knowledge there is no PLC device in-vehicle with high throughput, i.e. throughput higher than FlexRay (10 Mbps). We can however mention a device of Yamar [3] company which proposed a solution based on transmission over DC lines and CAN protocol. But, the maximum throughput of the Yamar device, namely DCB500, is only 500 Kbps. In [START_REF] Nouvel | Code division multiple access for an automotive area network over power-lines[END_REF], a PLC communication in-vehicle has been demonstrated. This PLC communication was based on single carrier spread spectrum technology and it achieved a throughput of only 50 Kbps. In [START_REF] Gouret | High data rate network using automotive powerline communication[END_REF], [START_REF] Degardin | Performances of the homeplug PHY layer in the context of in-vehicle powerline communications[END_REF] a PLC communication based on a multicarrier modulation has been demonstrated and unlike the two previous applications, multicarrier modulation achieved higher throughputs.

III. COMPARISON OF MAC/PHY LAYER OF HPAV AND HD-PLC

We study MAC/PHY parameters of HPAV and HD-PLC standards. Tab I shows the interest of MAC/PHY parameters of standards HPAV and HD-PLC. Both use OFDM (Orthogonal Frequency Division Multiplex) multicarrier modulation but they do not use the same window shaping.

The HomePlug AV standard is the second generation of PLC systems developed by the HomePlug Powerline Alliance. Now it is suitable for multimedia applications like HDTV or VOIP. The PHY layer uses a Windowed-OFDM modulation. The HPAV can use different modulation order from BPSK (Binary phase-shift keying) up to 1024 QAM (Quadrature Amplitude Modulation) for each sub-carriers according to the channel characteristics. To counteract the channel multipath effects and so the intersymbol interferences, the HPAV uses a guard interval (GI). Moreover, several GI (5.56 µs, 7.56 µs or 47.12 µs) can be used depending on the channel and so the throughput can be improved. A frequency mask is used to avoid interferences mainly with amateur radio bands. This is the reason why the pulse-shaped OFDM symbols is different than the classic rectangular window. Thanks to this specific window, the out-of-band noise is reduced and the nocthes are deeper. The MAC layer is based on a hybrid acces mechanism: Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) and Time Division Multiple Access (TDMA). A Central Coordinator (CCo) controls the PLC network. A channel sounding is carried out by the receiver which communicates the result to the CCO. Then, the CCO uses this channel estimation in order to establish a specific QAM modulation for each OFDM sub-carrier. HPAV uses a two-level MAC framing scheme. Indeed, the MAC frames are divided into 512 bytes segments called PHY Block (PB). An uncorrectable Forward Error Correction (FEC) code is used and a header is added with the numbers of the PB. Therefore, with this strategy, it is possible to retransmit only the damaged PB detected.

The HD-PLC alliance [START_REF]Official website of the High Definition Power Line Communication Alliance (HDPLCA)[END_REF] (HD-PLC) is an additional group which promotes the PLC networks based on its HD-PLC technology. It is based on a specific OFDM modulation called Wavelet-OFDM which exploits the Wavelet transform. It appears with this modulation that the notches are deeper than OFDM realized with IFFT/FFT. Moreover, Wavelet-OFDM does not use guard interval and so it has a better spectral efficiency than OFDM modulation with guard interval. In contrast to HPAV, in the HD-PLC protocol, the baseband data are modulated by a Pulse-Amplitude Modulation (PAM) with an order from 2 to 32. The MAC layer uses an hybrid TDMA and CSMA/CA protocol synchronized thanks to the AC line cycle.

IV. THROUGHPUT MEASUREMENT: TESTBED

The study of PLC throughputs is realized with PLC modems used in indoor networks. Indeed, these modems are commonly used in indoor networks and high throughputs have been demonstrated. It seems to be interesting to used their invehicles. The power line network in-vehicle is however different of those in a house. That's why, the modems have been modified to be used and plug into a car. The only modifications affect the coupling and the power supply. For HPAV, we used a Devolo 200Av modem [7]. For HD-PLC, we used a PLC Panasonic BL-PA510KT modem [8]. Fig. 1 illustrates the wiring harnesses of the Peugeot 407 SW car that was used. It represents the electrical supply network, the different positions (A, H, . . . ) of our PLC measurement points and the ECUs that controls the electronic systems in the vehicle. We considered several use cases that can happen in-vehicles. Accordingly, four typical scenarios for measurements have been studied:

1) Car with engine turned off.

2) Car with engine-turned but not moving.

3) Car with engine-turned but not moving and effects of lightning, warnings, radio, windscreen wiper, electric windows. 4) The car in motion and the effects of the equipments like in 3). For our measurements, we use a test bed with two PLC modems and two computers (PC) which are plug into the different points shown Fig. 1. For example, if we want to study the TCP throughput measurement between A and D that we call path AD, we used a PC in A with a PLC modem and the same configuration in D.

The throughputs are measured associated with the payload ignoring headers. The throughput is also called Goodput according the definition in section 3.17 in [START_REF] Newman | Benchmarking Terminology for Firewall Performance[END_REF].

V. RESULTS AND DISCUSSION

A. Results

Fig. 2, we show a comparison between the power spectrum of HD-PLC and HPAV. A spectrum analyzer is used in point A during a PLC communication between point A and D. We used a resolution bandwidth (RBW) of 10 kHz and the MAX Hold function. The power spectral density specified in HD-PLC and HPAV standards is defined with a maximum power spectral density (PSD) of -50 dBm/Hz. Fig. 2 we show the power (in dBm) versus the frequency. Like P u = P SD + 10 × log 10 (RBW = 10kHz)) we can verified that the power spectral mask is compliant with PLC indoor specifications. Lastly, we can verified that HD-PLC has notches deeper than HPAV.

Fig. 3 and Fig. 4, we show insertion gain |S 21 |(dB) for different paths and three use cases. Fig. 3 shows paths between the rear area and the front area. Fig. 4 shows paths in the front area. We can see that from 17 MHz to 30 MHz the insertion gain of the paths AD, AF and AH, when the engine is turned off, are higher than the other cases. Therefore, we notice a difference when the engine is turning. Fig. 4, differences between use cases is less important. Moreover, the insertion gain are 10 dB higher for the paths in front area than Fig. 3. Fig. 5 shows different throughputs for different paths invehicle with scenario 1). Throughputs with HD-PLC modems are higher than HPAV for each paths in-vehicle with this scenario. Throughputs are higher than 40 Mbps and so higher than FlexRay protocol (10 Mbps) which is usually used in-vehicle. We observed also that all paths have the same throughput for each of PLC standards.

Fig. 6 and Fig. 7 show different throughputs for different paths in-vehicle and for three scenarios respectively for the HD-PLC and HPAV standards. Like for the scenario 1) throughputs are higher than FlexRay protocol (10 Mbps) but the throughputs are about 20 Mbps. However, we remark that HPAV throughputs are higher than HD-PLC. In fact, for all the paths, throughputs are about 20 Mbps for HD-PLC and 25 Mbps for HPAV. The path HD is however different than others with higher throughputs for the two standards. Moreover, for this path there is no differences between the scenarios. The measurements show also that the throughputs are not modified by the scenarios 2), 3) and 4).

Fig. 8 and Fig. 9, we consider an other analysis which use a spectrogram. The spectrogram is a representation of the spectrum over time. We recorded power spectrum during 150s and we displayed each recording versus frequency. With a spectrogram we can have a time frequency view of the channel and the transmission between two points. The same file size is sent from A to D with HPAV or with HD-PLC modems and with different scenarios during 150s. We remark a throughput fall when the ignition key is turned in position II like it is specified in [START_REF] Mohammadi | Measurement study and transmission for in-vehicle power line communication[END_REF].

Fig. 10, we show the PSD for an HPAV and HD-PLC communication between the point A and D. We show also in the same figure the maximum ambient noise. This result has been compute like the maximum at each frequency of a recording of several noise spectrum measurements during 140s.

Fig. 11, we show the maximum PSD noise in point D for several scenarios. Each curves have been compute like in Fig. 10. We can see that the ambient noise is high in the band [START_REF]Official website of the High Definition Power Line Communication Alliance (HDPLCA)[END_REF][3][START_REF] Nouvel | Code division multiple access for an automotive area network over power-lines[END_REF][START_REF] Gouret | High data rate network using automotive powerline communication[END_REF][START_REF] Degardin | Performances of the homeplug PHY layer in the context of in-vehicle powerline communications[END_REF][7] MHz and [START_REF] Newman | Benchmarking Terminology for Firewall Performance[END_REF][START_REF] Mohammadi | Measurement study and transmission for in-vehicle power line communication[END_REF][START_REF] Nouvel | X-by-wire and intra-car communications: power line and/or wireless solutions[END_REF][START_REF] Galli | Advanced signal processing for plcs: Wavelet-ofdm[END_REF] MHz and from 17 MHz up to 30 MHz the ambient noise is flat at about -110 dBm.

B. Discussion

In our measurements setup, the PSD of commercial modem is about -50 dBm/Hz (Fig. 10). With the injected power by the modified commercial modem on the DC line, the communication is not dependent of the topology. Indeed, all the paths have the same throughput whatever the scenario except for the path HD. In [START_REF] Degardin | Performances of the homeplug PHY layer in the context of in-vehicle powerline communications[END_REF], authors explain that the communication is dependent of the topology when the power injected is low. Indeed, according to they, with a PSD mask of -60 dBm/Hz, there is no differences between paths called direct and indirect. And with a PSD of -80 dBm/Hz the throughputs are dependent of the topology. We observe however that throughput are not the same if we take into account the scenarios. When we compare the throughput versus the scenario, we see a difference between the scenario 1) and 2), 3), and 4). Moreover, the same throughput fall is observed for HD-PLC and HPAV standards. According to us, this difference can be explained by the channel gain. Indeed, Fig. 3 and Fig. 4, we can see that the channel gain is lower except for the path HD with the scenario 2), 3) and 4). In [START_REF] Mohammadi | Measurement study and transmission for in-vehicle power line communication[END_REF] a similar phenomenon has been observed and his impact of the channel gain. The differences of throughputs between scenarios are also show thanks to the spectrograms Fig. 8 and Fig. 9. These measurements show the throughput fall when the ignition key is in position II. Moreover, the ambient noise on the DC line increase when the key is in position II. When the ignition key is in position II, the insertion gain is lower and the noise level is higher, therefore the bit-loading algorithms of HD-PLC and HPAV provide an adaptively modulate different sub-carriers according to the new signal-to-noise ratio (SNR). That's why, we have a throughput fall of about half in order to have a robustness communication.

Finally, if we compare these results with an other PLC communication standard (Spidcom) studied in a previous study [START_REF] Nouvel | X-by-wire and intra-car communications: power line and/or wireless solutions[END_REF], we notice that HD-PLC and HPAV throughputs are better. For example, for the AD path, we have only a maximum throughput of 16.5 Mbps for Spidcom.

VI. CONCLUSION

We have setup an in-vehicle PLC communication system using existing wires based on commercial solution. Throughputs higher than FlexRay have been achieved. The HD-PLC and HPAV standards have similar performances over the DC line in-vehicle. Indoor PLC standards HD-PLC and HPAV are very similar and the greatest number of the PHY parameters can be used in-vehicles. However, some algorithms to enhance the efficiency can not be used in-vehicles like the 50 Hz synchronization or like channel adaptation based on cyclostationnary noise of indoor PLC. Moreover, specific PHY parameters optimisation can be achieved to improve the PHY rate thanks to in-vehicle channel measurements and characterization. Moreover in term of complexity Wavelet OFDM and Windowed OFDM are also similar [START_REF] Galli | Advanced signal processing for plcs: Wavelet-ofdm[END_REF]. Finally, the PLC network in-vehicle seems to be an efficient solution for high throughput applications like multimedia or rear camera [START_REF] Nouvel | Wireless and power line communication in vehicule[END_REF].

Fig. 1 .

 1 Fig. 1. Measurement scheme: the different uppercases represent the measurement points.

Fig. 2 .

 2 Fig. 2. Power spectrum of HDPLC versus HPAV ; Path AD; measured in A; scenario 1); Spectrum analyzer: Max Hold, RBW=10 kHz.

  Fig. 3. Insertion gain ; Path AD, AF and AH which are paths between rear and front area; Engine OFF, engine-turned and engine-turned + equipments.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Insertion gain ; Path FD and HD which are paths in front area; Engine OFF, engine-turned and engine-turned + equipments.

Fig. 6 .

 6 Fig.6. HD-PLC throughputs for different paths in-vehicle for scenario 2), 3) and 4).

Fig. 7 .

 7 Fig.7. HPAV throughputs for different paths in-vehicle for scenario 2), 3) and 4).

FrequencyFig. 8 .

 8 Fig. 8. Spectrogram measured in D; HDPLC communication for the path AD and for several scenarios.

FrequencyFig. 9 .

 9 Fig. 9. Spectrogram measured in D; HPAV communication for the path AD and for several scenarios.

Fig. 10 .

 10 Fig. 10. PSD HPAV and HD-PLC in point D for a PLC communication between A and D; maximum ambient noise in point D.

  Fig. 11. Maximum ambient noise in point D.

ACKNOWLEDGMENT

This work has been carried out by the CIFAER project, initiated and supported by the ANR and ID4CAR.


Keywords: Grid Computing, Re-deployment, Co-deployment, Autonomic Computing

Experimentations with CORDAGE, a generic service for co-deploying and re-deploying applications on Grids

Introduction

Federating physical resources located in different universities, institutes and companies leads to the concept of grid computing. These infrastructures are particularly outfitted to support the heavy data-computing and data-management demand coming from distributed applications, for instance heavy simulation scientific codes. Unfortunately, both applications and infrastructures are complex to deal with, especially in the phase of initial deployment. In this paper we focus on the deployment of such applications over large-scale environments.

Two aspects have to be considered. First, such environments are often dynamic, in the sense that resources may appear and disappear while the applications are running. Such a dynamicity can be supported by task migration and checkpointing mechanisms embedded in the applications. These mechanisms lead to a dynamic reconfiguration of the application, which includes some form of deployment. In this paper we do not address this aspect, which has been studied in many contributions.

In contrast, we address another aspect, which has often been overlooked by (pure...) scientists, but which practical impact is of major importance. Actually, the behavior of such applications is often unpredictable at launching time : the needs in physical resources can vary during the execution time. For instance, a distributed data-storage system cannot predict its future requirements of storage nodes, as they depend on clients demands. Another example is a scientific application which consists of a succession of computational steps. Each of these steps often requires a varying set of computing nodes. Thus, the system must dynamically expand over additional storage nodes during the run. However, for the sake of usage fairness, it should as well retract from them when they are not needed. We call re-deployment such a process of expanding and retracting at runtime.

Another issue regarding deployment comes from the dynamic co-ordination of several applications. As an example, consider a workflow of two applications A and B, where B consumes the flow of results produced by A. One has to make sure that B is deployed and is ready to consume data before A starts producing. Furthermore, one has to make sure that both applications are located on resources that are close enough to efficiently transfer data. This results in a set of temporal and spatial constraints. This close co-ordination has to be guaranteed even in the case of dynamic re-deployment. We call co-deployment such a process. However, this aspect is not addressed in the experiments reported in this paper.

The purpose of the CORDAGE service is precisely to provide support to automatically handle the co-deployment and the re-deployment of applications on grids. Such a system should meet three requirements : Transparency : The applications, and even more the user, should remain unaware of the low-level interactions with services and tools that manage resources. Versatility : In addition to standard generic deployment actions, such as configuring, launching and monitoring, the service should also provide support for ad-doc, application-specific actions. Neutrality : The service should handle application without any restriction regarding their software model (component-based approach, message-passing approach, etc.), and it should be minimally intrusive into their source code. A large number of systems have been proposed to investigate various approaches towards the deployment of complex applications over large-scale infrastructures. One of the most promising approach relies on the concept of Autonomic Computing [START_REF] Kephart | The vision of autonomic computing[END_REF] proposed by IBM. Autonomic systems are able to self-manage, as exemplified by sys- tems such as Dynaco [START_REF] Buisson | Dynamic adaptation for Grid computing[END_REF], Entropy [START_REF] Hermenier | Power management in Grid computing with Xen[END_REF], and Jade [START_REF] De | Autonomic administration of clustered J2EE applications[END_REF]. These systems can dynamically reconfigure themselves, including the ability to redeploy some additional parts during the execution. Thus, Autonomic Computing offers transparency regarding resources management, as well as versatile support for application-specific operations. Unfortunately, most of the systems are very intrusive, as they require the use of particular software models such as component-based models. Another approach consists in submitting applications to a remote execution environment, through a client interface. This approach is illustrated by systems such as XtreemOS [START_REF] Cortes | XtreemOS : a vision for a grid operating system[END_REF], Vigne [START_REF] Jeanvoine | Vigne : executing easily and efficiently a wide range of distributed applications in Grids[END_REF], DIET [START_REF] Caron | DIET : a scalable toolbox to build network enabled servers on the Grid[END_REF], and Zorilla [START_REF] Drost | Simple locality-aware co-allocation in peer-to-peer supercomputing[END_REF]. They are in charge of selecting and allocating physical resources, then deploying the application in a transparent way. This approach is also very close to job schedulers such as OAR [START_REF] Capit | A batch scheduler with high-level components[END_REF] and GridEngine [START_REF] Gentzsch | Sun Grid Engine : towards creating a compute power Grid[END_REF], in which the user submits a set of jobs to be executed over the grid. Remote execution environments and job schedulers offer a transparent resource management, whereas being neutral and non-intrusive for the application. Unfortunately, it is very difficult, or even impossible, to take into account very specific needs in term of deployment, like the co-deployment of multiple applications. These systems are mainly designed to address load balancing and task migration issues.

Finally, one can use low-level toolboxes like Globus [START_REF] Foster | Globus : a metacomputing infrastructure toolkit[END_REF], GridLabGAT [START_REF] Allen | The Grid Application Toolkit : toward generic and easy application programming interfaces for the Grids[END_REF], and Saga [START_REF] Goodale | SAGA : a simple API for Grid applications -high-level application programming on the Grid[END_REF], as well as deployment systems like ADAGE [START_REF] Lacour | Generic application description model : toward automatic deployment of applications on computational Grids[END_REF], GoDIET [START_REF] Caron | GoDIET : a deployment tool for distributed middleware on Grid'5000[END_REF], APST [START_REF] Casanova | The AppLeS parameter sweep template : user-level middleware for the Grids[END_REF], and DeployWare [START_REF] Flissi | Deploying on the Grid with DeployWare[END_REF]. They are widely used on grid infrastructures, as they do not require the installation of heavy middleware, nor dedicated operating systems. They specifically assist the deployment of applications, offering basic services to discover and reserve physical resources, transfer files and remotely start processes. However, as a counterpart, these systems are far from making resource management and application deployment transparent for the user.

The CORDAGE approach is to leverage the capabilities of a number of dynamic deployment tools, in order to meet the three properties of Transparency, Versatility and Neutrality. In our case, these are the OAR scheduler [START_REF] Capit | A batch scheduler with high-level components[END_REF] and the ADAGE deployment tool [START_REF] Lacour | Generic application description model : toward automatic deployment of applications on computational Grids[END_REF], which enjoy Neutrality, but lack Versatility and Transparency. The problem with low-level tools such as OAR and ADAGE is that the user is still responsible for scheduling the numerous and tedious elementary actions needed to perform and monitor a dynamic deployment, as shown on Figure 1(a). The user has still to 1) select and reserve some resources, then 2) retrieve the resource list, then 3) provide the deployment tool information like the description of the application, the resource list and some additional placement constraints, so that 4) the deployment tool can launch the application. In contrast, CORDAGE takes the user out of the loop and orchestrates these multiple actions on the behalf of the user according to a set of highlevel orders, as displayed on Figure 1(b). As far as the user is concerned, everything is then transparent, versatile and neutral, as all the specific, ad-hoc details are handled within CORDAGE.

This paper is based on an improved version of the CORDAGE service already presented in a previous paper [START_REF] Gabriel Antoniu | CoRDAGe : towards transparent management of interactions between applications and ressources[END_REF], as described in Section 2. Section 3 describes our case study, based on the JUXMEM data-sharing service [START_REF] Gabriel Antoniu | JuxMem : an adaptive supportive platform for data-sharing on the grid[END_REF], which is dynamically deployed over the GRID'5000 experimental grid testbed [START_REF] Cappello | Grid'5000 : a large scale, reconfigurable, controllable and monitorable grid platform[END_REF]. Then, Section 4 provides a detailed report on the experimental behavior of CORDAGE deploying and re-deploying JUX-MEM under various near-real conditions. These experimentations show the impact of using multiple clients and multiple applications, as well as the impact of spreading the service across multiple grid sites.

Towards dynamic deployment

CORDAGE introduces a model, in which applications and resources are represented by logical trees. This hierarchical approach allows to perform a consistent preplanning of the deployment, by mapping the application components onto a set of physical resources with respect to the hierarchical constraints as shown on Figure 2.

In order to allow dynamic application re-deployment, the representation can then be updated during the execution. It makes it possible to dynamically expand or retract #include cordage.hh cdgclient * app1 = new cdgclient(conf app1); cdgclient * app2 = new cdgclient(conf app2); app1→add sub application(app2); app1→deploy application(); app2→perform specific action(ADD PROVIDER, 2); delete app1; delete app2; ¦ FIG. 3 -Minimal coding scheme to let an application interact with the CORDAGE server.

the configuration of the deployed application, respectively adding or deleting logical groups and nodes. Such a alteration is triggered by some application-specific requests sent by CORDAGE clients. These clients can be embedded in user applications, monitoring tools, or execution systems that are part of an autonomic framework.

The model can also handle the co-deployment of multiple applications. A logical tree is built for each application involved in the global deployment. These trees are then merged into a single tree, following specific rules. The resulting tree is thereafter mapped onto the physical tree and all applications are deployed in a co-ordinated manner.

This model is transparent, as the mapping concept allows the user to express his high-level deployment requests without any reference to the low-level interactions with services and tools that manage resources.

As CORDAGE is seen as an external service by the application, it can be freely expanded with ad-hoc plugins to offer a set of additional specific actions as needed. This enables arbitrary versatility without any modification of the application.

The CORDAGE architecture is based on a client-server paradigm, which is as neutral as possible regarding the software model of the application. The only requirement is to insert a few lines of code at suitable places within the application, typically at places where the application makes decisions regarding expanding or retracting its configuration. To get a concrete feeling of using CORDAGE, the code lines displayed on Figure 3 are sufficient to let an application app1 request the CORDAGE server to add another application app2 as its sub-application, trigger the co-deployment of app1 and app2 in a co-ordinated way, and request the execution of an application-specific action ADD PROVIDER to update the current configuration with 2 additional providers.

Deploying JUXMEM, a data-sharing service for the grid

The CORDAGE approach has been tested and evaluated in the context of the deployment of a distributed data-sharing service called JUXMEM [START_REF] Gabriel Antoniu | JuxMem : an adaptive supportive platform for data-sharing on the grid[END_REF] over the GRID'5000 experimental grid platform, using various configurations, including multiple clients, multiple applications and multiple grid sites.

The JUXMEM grid data-sharing service offers transparent and efficient access to data stored in the physical memory of grid processing nodes, later referred as providers. Providers self-organize as multiple cluster groups, which can be deployed on possibly INRIA different grid sites. The number of providers determines the overall storage capacity and the level of fault tolerance of the service. JUXMEM is primarily intended to be used as a reliable storage for scientific grid applications.

Before CORDAGE, the deployment of JUXMEM was essentially based on the OAR reservation tool and the ADAGE deployment tool, as introduced in Section 1. In this former approach, the user has first to manually issue a request to the OAR scheduler to be granted a set of grid nodes. This request returns the user with a reservation identifier. Then, the user manually invokes the ADAGE deployment tool with this OAR reservation identifier. The user also has to manually provide ADAGE with a static description of the JUXMEM service, including the declaration of the various cluster groups, the configuration of the providers to be deployed (listening port numbers, memory space allocated to the service, maximal service time, etc.), and a set of spatial and temporal deployment constraints. All these information are provided by the user as XML files. Based on this information, ADAGE generates a deployment plan : it transfers the proper configuration files towards the storage nodes and there starts the processes. All this latter phase is done in a generic and transparent way.

This former approach has several drawbacks. First, the user has still to manually handle a large and complex set of information : the user has to interact with a number of sophisticated tools, consuming the data produced by one to feed another, translating the data format on the fly by hand. Moreover, if the initial reservation request to OAR fails, then the user is left alone to react and to provide OAR with another request. All these steps have to be made in the case of the deployment of any application over a grid.

Second, the case of JUXMEM is even more complex, as it is obviously very difficult to predict how large data will be stored into the service during its lifetime. It may well happen that the initial configuration falls short of storage space, and that deploying additional providers is needed at some point to serve the storage requests. Conversely, some storage providers may be left unused at some point. A fair share of the grid resources commends then to release this nodes to the other grid users. Therefore, the service configuration has to dynamically expand and retract all over its lifetime, based on the external requests. In this former approach, it is up to the user to take care about all the elementary actions needed for such a reconfiguration.

The goal of the CORDAGE approach is to make the deployment of JUXMEM transparent for the user. CORDAGE automates all these elementary actions, regarding both the initial deployment and successive expansions and retractions. For instance, COR-DAGE is able to dynamically redeploy providers, taking into account specific requests from the JUXMEM service itself. A key aspect is to enforce that all the providers of each individual JUXMEM cluster group are deployed on the same grid site for performance purpose. In contrast, the various cluster groups should be deployed over different grid site for fault tolerance purpose.

The CORDAGE hierarchical model described in Section 2 has precisely been introduced for this purpose. The corresponding logical tree contains one virtual root node, each child of which corresponds to a cluster group to be deployed on a particular grid site. As shown on Figure 4, the entities added into the same second-level logical node will be deployed within the same grid site. In contrast, as shown on Figure 7, the entities belonging to different logical nodes will be deployed over different grid sites.

Specific actions have been added to the CORDAGE server to enable the JUXMEM service to reconfigure itself : expanding by creating new storage providers into existing cluster groups, or even creating new cluster groups ; retracting by deleting providers or groups. This is done by creating or deleting logical nodes, groups and entities within the logical tree. The goal of the experiments below is to present and analyze the behavior of COR-DAGE when used for managing the dynamic deployment of the JUXMEM service.

Experimenting with CORDAGE

Various configurations of the CORDAGE service are studied. In each of them, a single CORDAGE server is set up to serve the requests of possibly multiple clients regarding possibly multiple JUXMEM applications.

The experimentations are conducted within the GRID'5000 platform, an experimental and distributed testbed that gathers up to 5000 nodes distributed in 9 sites France-wide. The protocol starts with the deployment of one CORDAGE server, followed by the deployment of a minimal JUXMEM topology. This topology consists of one node, in charge of organizing the set of JUXMEM providers. Then, synthetic clients perform re-deployment requests to the CORDAGE server, as the JUXMEM service would do in a real behavior.

Using multiple clients

In a first scenario, we consider that the CORDAGE server is in charge of managing one single JUXMEM application. Several clients perform concurrent requests to add new providers to the service. In order to keep the application representation consistent, the CORDAGE server does not allow parallel operations on the same application. Therefore, the requests of the various clients are separately processed in a FIFO-ordered queue. Figure 4 displays the evolution of the logical representation, as the requests for adding a new provider are processed. Each request creates a new logical group in the logical node corresponding to the single JUXMEM cluster group. This new group contains the single new provider entity to be deployed. We run two experiments : the first one uses two concurrent clients and the second one uses four concurrent clients. The clients repeatedly add new providers into the unique instance of JUXMEM, without any intermediate synchronization. The clients requests are accumulated into a FIFO queue at the CORDAGE server level.

Figure 5(a) displays the time to process each successive request on the CORDAGE server, whichever the sender is, during the whole experiment time. The experiment with 2 clients leads to processing 150 requests in 28 minutes. The average time to process a request is 11 seconds. The experiment with 4 clients leads to processing 143 requests in 29 minutes. The average time to process a request is 12 seconds. Processing a request on the server breaks down into 3 phases : Update the logical representation. This includes all synchronization mechanisms, the mapping of the logical tree onto the physical tree as well as some ancillary operations. In both configurations, this step takes less than 0.20 seconds per request, that is, less than 2 % of the overall processing time. Interact with the OAR reservation tool. This step takes an average time of around 7 seconds per request in the 2-client configuration and 9 seconds in the 4-client one. This step takes nearly 70 % of the overall processing time. Interact with the ADAGE deployment tool. This updates the configuration of the JUXMEM service by transferring the configuration files and starting the processes. This step takes an average time of 3 seconds per request in both configurations. This step takes around 30 % of the overall processing time. One major observation coming from Figure 5(a) is that the processing time for each request on the server is not significantly impacted by the number of clients acting on the same application. This can be explained by the serialization of the requests by the CORDAGE server : each request is fully processed by the server without any timesharing mechanism.

In contrast, the overhead coming from the number of clients can be witnessed on Figure 5(b). This figure displays times measured in the same experiment as above. Yet, the request time is measured on the client side instead of the CORDAGE server side, including the time spent by the requests in the server queue. The more clients are acting on the same application, the longer they have to wait for their requests to be processed. The clients wait an average time of 8 seconds in a single-client configuration, 21 seconds in a 2-client configuration and 46 seconds in a 4-client configuration.

The reader will have noticed the presence of two peak points on both figures, in both configurations. These points correspond to the resource saturation of the grid site currently used to deploy new providers : no more nodes are available for reservation by the OAR tool. CORDAGE incurs an almost 80-second overhead. The server checks OAR about the availability of the requested nodes every second. After 45 unsuccessful checks, the server decides the current grid site cannot be used any longer. It selects another one from a list of available sites, and then requests OAR for new resources in this latter site. These peaks occur more or less at the same moment in both configurations because the experiments were run on the same day, without any major changes in the overall grid reservation status : the sites reached saturation after adding the same number of providers in both experiments. Yet, there is a noticeable shift between the peaks in the 2-client configuration and the 4-client configuration. This is due to the fact that the average time for processing requests in the 4-client configuration is slightly larger than that in the 2-client configuration at the beginning of the experiments. Therefore, all subsequent request occurrence times are shifted away by some fixed amount.

Impact of using multiple applications

The CORDAGE server is also able to manage several concurrent applications at the same time. This makes for example sense in the context of co-deployment. In this section, we study the impact of managing several applications with only one server on the request processing time. We use the previous configuration involving a minimal topology of JUXMEM that is expanded by sequentially adding new providers. We run two successive experiments, one with 2 independent instances of the JUXMEM service, and then 3 instances of it, all the instances being managed by the same CORDAGE server. For each instance of the JUXMEM service, one specific synthetic client repeatedly issues requests to the CORDAGE server to add new providers. At the CORDAGE level, all the JUXMEM instances share the same instance of the OAR reservation tool, whereas a dedicated instance of the ADAGE deployment tool is used for each of them. This arrangement actually suits the GRID'5000 environment, as most of the other grid platforms : all users must interact with a unique, centralized job scheduler, but they are free to use their own deployment tool.

Figure 6(a) displays the time to process requests measured on the clients, using the 2-and the 3-application configurations. The average time is around 11 seconds. This time is stable and comparable to results with one client and one application : managing additional applications does not increase the client waiting time for a request to be processed. Actually, the client requests do not have to wait for any lock before being Step #1

Step #2

Step #6 FIG. 7 -Expanding the JUXMEM topology by sequentially adding providers into four cluster groups located on different grid sites.

processed by the CORDAGE server. Then, the concurrent client requests at the level of the CORDAGE server result in concurrent reservation requests at the level of the OAR scheduler, which are effectively handled in parallel, with a stable request time. Also, they result in concurrent deployment requests at the level of the ADAGE deployment tools : all these requests are effectively handled in parallel as one instance of ADAGE is used per application instance.

Using multiple grid sites

The previous experiments were conducted within one grid site at a time. In this section we evaluate the CORDAGE prototype using 4 different sites at the same time. We start with a minimal JUXMEM topology made of one single JUXMEM cluster group, which is then expanded with 3 additional sibling cluster groups. Then, a synthetic client repeatedly adds new providers, one in each cluster group in turn. According to this scenario, the logical representation of the application evolves as displayed on Figure 7.

Figure 6(b) displays the time needed to process the successive provider launching requests. Observe that this request processing time, as measured on the client side, only includes launching the system process which runs the provider applicative code. It does not include the time needed to fully set up the provider and let it serve the application requests within the JUXMEM service. Once a provider has joined the JUXMEM service, we let it send an acknowledgment ready message to the CORDAGE server, so that Figure 6(b) can display the number of ready providers.

In this experiment, we use 4 grid sites. On each site, an instance of the OAR reservation tool is made available to locally manage the resources. These instances are running on various types of machines, and they manage various set of resources, so that the interaction times vary from site to site. This explains the periodic patterns displayed by Figure 6(b) : the smaller values correspond to requests made in a particularly reactive site. Again, peaks correspond to sites reaching saturation, as CORDAGE selects a fresh grid site if no reservation has been granted after a number of unsuccessful requests to OAR. In this experiments, the timeout was set to around 45 seconds, so as to include several site shifting within the overall time.

Conclusion

Today, the management of complex distributed applications over large-scale infrastructures requires the use of dedicated external systems. These systems help in facing, in a transparent way, the dynamicity introduced by both applications and infrastructures. In a previous paper [START_REF] Gabriel Antoniu | CoRDAGe : towards transparent management of interactions between applications and ressources[END_REF] we have introduced CORDAGE, a co-deployment and re-deployment tool that satisfies the three properties of transparency, versatility and non-intrusiveness.

In this paper we have described the evaluation of a prototype based on this model, used to deploy the JUXMEM data-sharing service over the GRID'5000 platform. The CORDAGE server relies on a number of grid tools : a reservation tool (OAR) and a deployment tool (ADAGE). CORDAGE takes the user out of the loop and orchestrates these multiple interactions on behalf of the user according to a set of high-level orders. As far as the user is concerned, everything is then transparent, versatile and neutral, as all the specific, ad-hoc details are handled within CORDAGE.

We have shown that the CORDAGE server can effectively interact with these tools, with a minimal overhead (less than 2 %). It can handle several applications at the same time, either dependent as in a co-deployment, or independent, taking advantage of the parallelization of the requests.

An interesting perspective of this work is the ability to let multiple CORDAGE servers communicate. They could for instance exchange information about resources and applications in order to optimize deployments, and to provide load balancing and fault tolerance features. More generally, CORDAGE could be integrated as one of the executive tools of a generic autonomic framework like DYNACO [START_REF] Buisson | Dynamic adaptation for Grid computing[END_REF].

FIG. 1 -

 1 FIG. 1 -Deploying an application (a) by hand, and (b) using the CORDAGE tool.

INRIAFIG. 5 -

 5 FIG. 5 -Multiple clients : time to process requests (a) on the server and (b) on the clients.

FIG. 6 -

 6 FIG.6-On the left, multiple sites : time to process requests on the clients and number of ready. On the right, multiple applications : time to process requests on the clients.

RR n°7086

Acknowledgments

This work has been supported by Sun Microsystems, the Regional Council of Brittany, and the LEGO (ANR-05-CIGC-11) and RESPIRE (ARA MDMSACS) Projects of the French National Agency for Research (ANR).

The experiments reported in this paper were carried out using the GRID'5000 experimental testbed, an initiative from the French Ministry of Research through the ACI GRID incentive action, INRIA, CNRS and RENATER and other contributing partners (see http://www.grid5000.fr/).