Amel Zergane

OVERALGEBRAS AND SEPARATION OF GENERIC COADJOINT ORBITS OF SL(n, R)

Keywords: Subject Classification. 37J15, 22E45, 22E27, 22D30 overalgebra almost separating, generic coadjoint orbits, semi-simple and deployed Lie algebra

For the semi simple and deployed Lie algebra g = sl(n, R), we give an explicit construction of an overalgebra g + = g ⋊ V of g, where V is a finite dimensional vector space. In such a setup, we prove the existence of a map Φ from the dual g ⋆ of g into the dual (g + ) ⋆ of g + such that the coadjoint orbits of Φ(ξ), for generic ξ in g ⋆ , have a distinct closed convex hulls. Therefore, these closed convex hulls separate 'almost' the generic coadjoint orbits of G.

1991 Mathematics

Introduction

In this paper, we prove that, for n > 2, the Lie algebra g = sl(n, R) admits an overalgebra almost separating of dgree n, but g does not admit an overalgebra of degree 2. More precisely:

There exist a Lie overalgebra g + = sl(n, R) ⋊ V and an application Φ of degree n, Φ : g ⋆ -→ g +⋆ such that:

1. p • Φ = id g ⋆ , where p is the canonical projection p : g +⋆ -→ g ⋆ , 2. Φ(Coad(SL(n, R))ξ) = Coad(G + )Φ(ξ), 3. if ξ is generic, then Conv (Φ(Coad(SL(n, R)ξ))) = Conv (Φ(Coad(SL(n, R))ξ ′ ))

if and only if Coad(SL(n, R))ξ ′ belongs to a finite set of coadjoint orbits of sl(n, R) (here: a singleton if n is odd, a singleton or a set of two elements if n is even).

We identify (g + ) ⋆ the dual of g + with the space g ⋆ ⊕ V ⋆ . The condition 1. means Φ(ξ) = ξ + φ(ξ), where φ is a polynomial of degree n from g ⋆ to V ⋆ . We say that (g + , φ) is an overalgebra almost separating of g (of degree n).

But there is no separating overalgebra of degree 2, (g + 2 , φ), i.e there is neither a Lie overalgebra g + 2 = sl(n, R) ⋊ V 2 nor φ : g ⋆ -→ V ⋆ 2 of degree 2 such that :

1. p • Φ = id g ⋆ , if p is the canonical projection p : g +⋆ 2 -→ g ⋆ , 2. Φ(Coad(SL(n, R))ξ) = Coad(G + )Φ(ξ), 3. if ξ is generic then, Conv (Φ(Coad(SL(n, R)ξ))) = Conv (Φ(Coad(SL(n, R))ξ ′ ))
if and only if Coad(SL(n, R))ξ ′ belongs to a finite family of coadjoint orbits.

Finally, we show that sl(4, R) does not admit an overalgebra almost separating of degree 3.

2. Description of orbits of sl(n, R) 2.1. Invariant functions of sl(n, R).

Since the Lie algebra sl(n, R) is simple, we can identify the adjoint action and coadjoint action of the Lie group G = SL(n, R). More precisely, we consider the non degenerate bilinear invariant form on sl(n, R) defined by: X, Y = T r(XY ).

Denote ξ an element of the dual of sl(n, R) and X an element of sl(n, R). The functions defined on the dual g * = sl(n, R) of the Lie algebra g by:

T k (ξ) = T r(ξ k ), 2 ≤ k ≤ n
are invariant: T k (gξg -1 ) = T k (ξ) for all ξ and all g.

The ring of the polynomial invariant functions on C is C[T 2 , . . . , T n ] (cf. [W]).

2.2. Description of Ω = {ξ ∈ sl(n, R), #Sp(ξ) = n}. This is classic. We recall this only for completeness.

Denote Ω the set of matrices ξ of sl(n, R) which are diagonalizable on C and have n distinct eigenvalues. The spectrum of this matrix ξ is Sp(ξ) = {c 1 , . . . , c r , a 1 ± ib 1 , . . . , a s ± ib s , with c i , a j , b j ∈ R, b j > 0, r + 2s = n}.

Denote by (a, b) < (a ′ , b ′ ) the lexicographic order :

(a, b) < (a ′ , b ′ ) ⇐⇒      a < a ′ or a = a ′ and b < b ′ .
We note also (the same if the eigenvalues are not stored in lexicographic order ) :

D(c 1 , . . . , c r , a 1 + ib 1 , . . . , a s + ib s ) =              c 1 . . . c r a 1 b 1 -b 1 a 1 . . . a s b s -b s a s             
.

We fix r and s such that r + 2s = n. If r > 0, we put :

Σ r,s = {D(c j , a k + ib k ), c 1 < c 2 < • • • < c r , b k > 0, (a 1 , b 1 ) < (a 2 , b 2 ) < • • • < (a s , b s )}
If r = 0, we note :

Σ + 0,s = {D(a k + ib k ), b k > 0, (a 1 , b 1 ) < (a 2 , b 2 ) < • • • < (a s , b s )} and Σ - 0,s = {D -(a k + ib k ), b k > 0, (a 1 , b 1 ) < (a 2 , b 2 ) < • • • < (a s , b s )}, where
D -(a 1 + ib 1 , . . . , a s + ib s ) =           a 1 -b 1 b 1 a 1 a 2 b 2 -b 2 a 2 . . . a s b s -b s a s          
.

Finally, we put

Σ =          r>0, r+2s=n Σ r,s Σ + 0, n 2 ∪ Σ - 0, n 2 if n is even r>0, r+2s=n Σ r,s if n is odd.
The set Ω is invariant since the spectrum Sp(ξ) of ξ coincides with the spectrum of

gξg -1 = Ad(g)(ξ) (g ∈ SL(n, R)), or if we prefer, if C ξ is the characteristic polynomial of the matrix ξ, then the adjoint orbit G • ξ 0 of ξ 0 is included in {ξ, such that C ξ = C ξ 0 }.

Adjoint orbits in Ω.

Lemma 2.1.

For all matrix ξ in Ω, the adjoint orbit G • ξ of the matrix ξ contains a point of Σ.

Proof.

Let ξ be a matrix in Ω, ξ is diagonalizable on C, with eigenvalues all distinct. If Sp(ξ) = {c j , a k ± ib k }, where the eigenvalues are ordered as above,

c 1 < • • • < c r and (a 1 , b 1 ) < • • • < (a s , b s ), b 1 > 0, . . . , b s > 0, then there exist vectors E j ∈ C n and F k ∈ C n such that ξE j = c j E j and ξF k = (a k + ib k )F k .
Since ξ is real, we can choose E j real (in R n ) and if we put F k = E r+2k-1 + iE r+2k (E r+t are real), then we obtain a basis of R n . If P is the basis change matrix , then the matrix of ξ is written in the new basis as follows :

ξ ′ = P ξP -1 = D(c 1 , . . . , c r , a 1 + ib 1 , . . . , a s + ib s ).
a. If det P > 0, then there exists g = 1 n √ det P P , such that ξ ′ = gξg -1 and g ∈ SL(n, R). The adjoint orbit G • ξ of the matrix ξ contains a point of Σ. b. If det P < 0 and r > 0, then we replace E 1 by E ′ 1 = -E 1 . The matrix P becomes P ′ = D(-1, 1, . . . , 1)P , P ξP -1 = P ′ ξP ′-1 and det(P ′ ) > 0. As above, the adjoint orbit G • ξ of the matrix ξ contains a point of Σ.

c. If det P < 0 and r = 0, then we replace E 1 by E ′ 1 = E 2 and E 2 by E ′ 2 = E 1 . The matrix P becomes P ′ = D(-1, 1, . . . , 1)P , P ξP -1 = P ′ ξP ′-1 and det(P ′ ) > 0. The adjoint orbit G • ξ of the matrix ξ contains the point

ξ ′ = P ′ ξP ′-1 = D -(a 1 + ib 1 , . . . , a s + ib s ) of Σ. Lemma 2.2.
Σ is a section for the action of SL(n, R) in Ω, i.e each orbit of Ω contains only a single point of Σ.

Proof.

Let ξ 0 be an element in Σ and G • ξ 0 its orbit. If ξ ∈ G • ξ 0 ∩ Σ, then, since the spectrum of ξ is the same as ξ 0 and the order of eigenvalues is fixed, we obtain:

If r > 0 then ξ = ξ 0 . If r = 0, we have either ξ = ξ 0 , or

G • ξ 0 ∩ Σ = {ξ, ξ 0 } = {D + (a k + ib k ), D -(a k + ib k ) = gD + (a k + ib k )g -1 }.
with det(g) = 1.

In the latter case, the sub eigenspaces V ec C (E 2k-1 + iE 2k ) and V ec C (E 2k-1 -iE 2k ) are one dimensional. Thus, there exist a nonzero complex numbers z 1 , . . . , z s such that :

g(E 1 + iE 2 ) = z 1 (E 1 -iE 2 ), and g(E 2k-1 + iE 2k ) = z k (E 2k-1 + iE 2k ), k > 1.
The matrix of g is written in the basis of eigenvectors of the first matrix as follows :

QgQ -1 =           0 z 1 z 1 0 z 2 z 2 . . . z s z s           .
The determinant of the matrix QgQ -1 is negative or zero, which is impossible. Therefore, ξ = ξ 0 and Σ is a section for the action of SL(n, R) on Ω.

Lemma 2.3. Denote Ω r,s = G • Σ r,s . Let ξ 0 ∈ Ω r,s . 1. If r > 0, {ξ, such that C ξ = C ξ 0 } is exactly the adjoint orbit G • ξ 0 of ξ 0 . 2. If r = 0, {ξ, such that C ξ = C ξ 0 } is the union of two adjoint orbits G•ξ 0 ⊔G•ξ 1 .
Now, show that Ω is dense. Let ξ be an arbitrary matrix of sl(n, R). On C, we can transform this matrix in Jordan form:

1. for each Jordan block J j (c) associated to the real eigenvalue c of ξ, there exist vectors E 1 j , . . . , E t j in C n such that ξE 1 j = cE 1 j and, if t > 1, ξE t j = cE t j + E t-1 j . We can choose E t j real.

2. for each Jordan block J k (a + ib) associated to the non real eigenvalue a + ib, with b > 0, we can choose vectors

F 1 k , . . . , F t k in C n such that ξF 1 k = (a+ib)F 1 k and, if t > 1, ξF t k = (a + ib)F t k + F t-1 k .
The union of these families of vectors, for all Jordan blocks associated to a + ib, form a basis of the characteristic subspace V (a + ib) of ξ associated to a + ib. The combined vectors F t k form a basis of the characteristic subspace V (aib). In this basis, the matrix of ξ| V (a-ib) is also in Jordan form. As above, put

F t k = E t k + iE ′t k
, where E t k and E ′t k are real vectors.

We arrange the eigenvalues of ξ as above, then we obtain a real basis of R n . On this basis, ξ is written as follows :

ξ ′ = P ξP -1 =                    c 1 u 1 . . . . . . c r-1 u r-1 c r a 1 b 1 v 1 -b 1 a 1 0 v 1 . . . . . . a s-1 b s-1 v s-1 -b s-1 a s-1 0 v s-1 a s b s -b s a s                    = Diag(c 1 , . . . , c r , a 1 b 1 -b 1 a 1 , . . . , a s b s -b s a s )+ + Overdiag(u 1 , . . . , u r-1 , v 1 0 0 v 1 , . . . , v s-1 0 0 v s-1 ) = D + N.
Where P is a real matrix, Diag means that we place the cited sub matrices on the diagonal, Overdiag means that we place the cited sub matrices on the second diagonal, u j and v k are either 0 or 1. Let now the real numbers x 1 , . . . , x r and y 1 , . . . , y s all distinct such that

x 1 + • • • + x r + 2y 1 + • • • + 2y s = 0. Put: A = Diag(x 1 , . . . , x r , y 1 , y 1 , . . . , y s , y s ),
and for all ε > 0, ξ ε = ξ + εP -1 AP . For almost every ε, the trace of ξ ε is zero and ξ ε has n distinct eigenvalues. Then, ξ ε ∈ Ω and for any norm on sl(n, R), ξξ ε = ε P -1 AP . This proves :

Lemma 2.4. The set Ω is dense in sl(n, R).

Show that the set Ω is an open :

We use the implicit function theorem. Let ξ 0 a matrix in Ω. The characteristic polynomial C ξ 0 of ξ 0 has n simple roots. If C ξ 0 (α) = 0, then C ′ ξ 0 (α) = 0. If c j is a real eigenvalue of ξ 0 , then we consider the map

F j : sl(n, R) × R -→ R defined by F j (ξ, x) = C ξ (x). If a k + ib k is a non real eigenvalue of ξ 0 , we note C ξ (z) = C ξ (x + iy) = A ξ (x, y) + iB ξ (x, y), where A ξ and B ξ are real. C ξ is a polynomial in z, then ∂ ∂z C ξ (z) = ∂ ∂x C ξ (z) + i ∂ ∂y C ξ (z) = 0, for all z. Since a k + ib k is a simple root of C ξ 0 , then ∂ ∂z C ξ 0 (a k + ib k ) = ∂ ∂x C ξ 0 (a k + ib k ) -i ∂ ∂y C ξ 0 (a k + ib k ) = 0.
Therefore, we have either

∂ ∂x A ξ 0 (a k +ib k ) = 0 and ∂ ∂y B ξ 0 (a k +ib k ) = 0 or ∂ ∂y A ξ 0 (a k + ib k ) = 0 and ∂ ∂x B ξ 0 (a k + ib k ) = 0. In all cases, D(A ξ 0 , B ξ 0 ) D(x, y) (a k , b k ) = ∂ x A ξ 0 ∂ y A ξ 0 ∂ x B ξ 0 ∂ y B ξ 0 (a k , b k ) = (∂ x A ξ 0 (a k , b k )) 2 +(∂ x B ξ 0 (a k , b k )) 2 = 0.
We define

F j : sl(n, R) × R 2 -→ R 2 by F k (ξ, x, y) = (A ξ (x + iy), B ξ (x + iy)), then Jac(F k )(ξ 0 , a k , b k ) = 0.
The functions F j , F k are differentiable, then F j (ξ 0 , c j ) = 0 and

∂F j ∂x (ξ 0 , c j ) = C ′ ξ 0 (c j ) = 0. Similarly, F k (ξ 0 , a k , b k ) = 0 and DF k D(x, y) (ξ 0 , a k , b k ) = 0.
So, there exists an open U j (resp. U k ) of sl(n, R), containing ξ 0 , and there is an open V j of R containing c j (resp. V k of R 2 , containing (a k , b k )) and there are maps

f j : U j -→ V j (resp. f k : U k -→ V k ) such that (ξ, x) ∈ U j × V j F j (ξ, x) = 0 ⇐⇒ (ξ, x) ∈ U j × V j x = f j (ξ) resp. (ξ, x, y) ∈ U k × V k F k (ξ, x, y) = 0 ⇐⇒ (ξ, x, y) ∈ U k × V k (x, y) = f k (ξ)
We replace as needed the open V r by another open small enough such that

V j ∩ j ′ =j V j ′ = ∅, V k ∩ (R × {0}) ∪ k ′ =k V k ′ = ∅.
And we put U = r U r . U is an open containing ξ 0 and, for all ξ in U, C ξ vanishes at n distinct points (real or complex), then, U ⊂ Ω.

Lemma 2.5.

The set Ω is an open in sl(n, R).

3. sl(n, R) admits an overalgebra almost separating of degree n 3.1. Separation of orbits of Ω by invariant functions. This is also well known. Let ξ a n × n real matrix and C ξ its characteristic polynomial. On C, we can put ξ in Jordan form. We note z 1 , . . . , z n the diagonal terms of this Jordan form. Then :

C ξ (X) = (-1) n det(ξ -XI) = (X -z 1 ) • • • (X -z n ) = X n -( i z i )X n-1 + ( i<j z i z j )X n-2 + • • • + (-1) n z 1 . . . z n = X n -α n-1 X n-1 + α n-2 X n-2 + • • • + (-1) n α 0 .
Therefore, using a formula due to Newton (cf. [W]), we have, for all k,

(-1) k+1 i 1 <•••<i k z i 1 z i 2 . . . z i k = j z k j -( i 1 z i 1 )( j z k-1 j ) + ( i 1 <i 2 z i 1 z i 2 )( j z k-2 j ) + . . . + • • • + (-1) k-1 ( i 1 <•••<i k-1 z i 1 . . . z i k-1 )( j z j ) or (-1) k+1 α n-k = T r(ξ k ) -α n-1 T r(ξ) + α n-2 T r(ξ k-1 ) + • • • + (-1) k-1 α k-1 T r(ξ).
This formula allows to express all α k as functions of the numbers T r(ξ j ), and conversely, to express all T r(ξ k ) as functions of the numbers α j .

Finally, we deduce that: two matrices ξ and ξ ′ satisfying

C ξ = C ξ ′ if and only if T r(ξ k ) = T r(ξ ′k ) for all k = 1, . . . , n. Proposition 3.1.
We keep all previous notations, in particular, Ω = ∪ r+2s=n Ω r,s is an open, dense and invariant subset of sl(n, R). The orbits of Ω will be called generic orbits. Let

ξ 0 ∈ Ω r,s . 1. If r > 0, {ξ, such that T k (ξ) = T k (ξ 0 ) for all k = 2, . . . , n } is exactly the adjoint orbit G • ξ 0 of ξ 0 , 2. If r = 0, {ξ, such that T k (ξ) = T k (ξ 0 ) for all k = 2, . . . , n } is the union of two adjoint orbits G • ξ 0 ⊔ G • ξ 1 .
We say that the invariant functions T k separate almost the (co)adjoint generic orbits of sl(n, R).

Convex hull of orbits of Ω.

For n = 2, the convex hull of the orbits of Ω are well known (cf. [ASZ]). We deduce that, for n = 2 :

Conv(G • D(-c, c)) = sl(2, R) (c > 0), and Conv(G • D + (ib) ∪ G • D -(ib)) = sl(2, R) (b > 0). For n = 3, we deduce that Ω ⊂ Conv(G • D(c 1 , c 2 , c 3 )). Indeed, if c ′ 1 < c ′ 2 < c ′ 3 such that c ′ 1 + c ′ 2 + c ′ 3 = 0, then either c ′ 1 = -2c 3 , or c ′ 2 = -2c 3 . Suppose c ′ 1 = -2c 3
, the other case is trained the same by exchanging the induces 1 and 2. Let

c ′′ 1 = c ′ 1 - c 1 + c 2 2 and c ′′ 2 = -c ′ 1 -c 3 .
We write:

c 1 c 2 =    1 2 (c 1 -c 2 ) 1 2 (c 2 -c 1 )    + c 1 + c 2 2 1 1 , then, there exist t in [0, 1] and g ∈ SL(2, R) such that : c ′ 1 c ′′ 2 = c ′′ 1 -c ′′ 1 + c 1 + c 2 2 1 1 = t c 1 c 2 + (1 -t)g c 1 c 2 g -1 .
We deduce that the convex hull of

G•D(c 1 , c 2 , c 3 ) contains   c ′ 1 c ′′ 2 c 3   with c ′′ 2 = c 3 .
By the same argument, but with induces 2 and 3, we show that this convex hull

contains D(c ′ 1 , c ′ 2 , c ′ 3 ). Let now a ′ = - 1 2 c ′ 1 , and b ′ > 0, then : c ′ 2 c ′ 3 =    1 2 (c ′ 2 -c ′ 3 ) 1 2 (c ′ 3 -c ′ 2 )    + a ′ 1 1 , the convex hull of G • D(c 1 , c 2 , c 3 ) contains also D(c ′ 1 , a ′ + ib ′ ) =   c ′ 1 0 b ′ -b ′ 0   + a ′   0 1 1   .
On the other hand, we saw that

  c a -b b a   belongs to G • D(c, a+ ib). Therefore, if a = 0 then Conv(G • D(c, a + ib)) contains the matrix   c a a   , with a = c. So, by our first argument, Conv(G • D(c, a + ib)) contains the matrix   c ′ 1 c ′ 2 a   with c ′ 1 = c ′ 2 = a = c ′ 1 .Therefore, by the above, Conv(G • D(c, a + ib)) contains all Ω. If a = 0, Conv(G • D(0, ib)) contains the matrices 0 D + (ib) and 0 D -(ib) . So, Conv(G • D(0, ib)) contains the matrix   0 -1 1   . Finally, Conv(G • D(0, ib)) contains all Ω.
We have proved:

Lemma 3.2. If n = 3 and ξ ∈ Ω, then Ω ⊂ Conv(G • ξ).
If n = 4, as above, Ω ⊂ Conv(G • D(c 1 , . . . , c 4 )). We deduce by using the lemma that for all c ′ 2 , . . . , c ′ 4 ,

D(c 1 , c ′ 2 , c ′ 3 , c ′ 4 ) ∈ Conv(G • D(c 1 , c 2 , a + ib))
and also

Ω ⊂ Conv(G • D(c 1 , c 2 , a + ib)). It remains the cases D(a 1 + ib 1 , a 2 + ib 2 ), a 1 = 0 and D(ib 1 , ib 2 ).
In the first case, we saw that

    a 1 -b 1 b 1 a 1 a 2 -b 2 b 2 a 2     ∈ G • D(a 1 + ib 1 , a 2 + ib 2 ), then     a 1 a 1 a 2 a 2     ∈ Conv(G • D(a 1 + ib 1 , a 2 + ib 2 ))
and a 1 = a 2 .

By applying the calculation for n = 2, we deduce that D(a 1 , x, y, a 4 ) belongs to Conv(G • D(a 1 + ib 1 , a 2 + ib 2 )), for all x and y such that

a 1 + x + y + a 4 = 0. Therefore, Ω ⊂ Conv(G • D(a 1 + ib 1 , a 2 + ib 2 )).
For the latter case, we saw that, insl(2, R), the adjoint orbit of D(ib) is the set of

matrices x y + z y -z -x with z 2 -x 2 -y 2 = b 2 and z > 0. Then, G • D(ib 1 , ib 2 )
contains a matrix as follows:

    x z -z -x 0 b 2 -b 2 0     , with 0 < b 1 < z.
Combining this matrix with

    0 1 1 0 0 1 1 0     , we obtain : ξ =     -x -z z x 0 -b 2 b 2 0     ∈ G • D(ib 1 , ib 2 ). If t = b 1 z + b 1 , the matrix tξ + (1 -t)D(ib 1 , ib 2 ) is D(-tx, tx, i(1 -2t)b 2 ) ∈ Conv(G • D(ib 1 , ib 2 )). Or Lemma 3.3. If n = 4 and ξ ∈ Ω, then Ω ⊂ Conv(G • ξ).
Proposition 3.4. For all n > 2, the convex hull of the adjoint orbit of a point ξ in Ω contains Ω:

Ω ⊂ Conv(G • ξ).
This convex hull is dense in sl(n, R).

Proof.

By induction on n > 4, suppose that, for all 2 < p < n, this property is true. We consider D(c j , a k + ib k ) ∈ Σ r,s , with r + 2s = n.

If r ≥ 2, then n -2 > 2, and we write:

D(c j , a k + ib k ) = D(c ′ 1 , c ′ 2 ) D(c ′ 3 , . . . , c ′ r , a ′ k + ib ′ k ) +   c 1 + c 2 2 I 2 - c 1 + c 2 n -2 I n-2   , Using the fact that sl(2, R) = Conv(G • D(c ′ 1 , c ′ 2 ))
and by the induction hypothesis for n -2, we get

Ω ⊂ Conv(G • D(c j , a k + ib k )). If r = 1, we decompose D(c 1 , a k + ib k ) as : D(c 1 , a k + ib k ) = D(c ′ 1 , a ′ 1 + ib 1 ) D(a ′ 2 + ib ′ 2 , . . . , a ′ n + ib ′ n ) +    c 1 + 2a 1 3 I 3 - c 1 + 2a 1 n -3 I n-3    . Then, a matrix D(c ′′ 1 , c ′′ 2 , c ′′ 3 , a 2 + ib 2 , . . . , a n + ib n ) belongs to Conv(G • D(c 1 , a k + ib k ))
. Therefore, the first case applies, and we still get the result.

If r = 0, then s > 2, we decompose D(a k + ib k ) as : D(a k + ib k ) = D(a ′ 1 + ib 1 , a ′ 2 + ib ′ 2 ) D(a ′ 3 + ib ′ 3 , . . . , a ′ n + ib ′ n ) +    2a 1 + 2a 2 4 I 4 - 2a 1 + 2a 2 n -4 I n-4    . Then a matrix D(c ′′ 1 , . . . , c ′′ 4 , a 3 + ib 3 , . . . , a n + ib n ) belongs to Conv(G • D(a k + ib k ))
. So, the first case applies, and this completes the proof of our proposition.

Corollary 3.5. sl(n, R) admits an overalgebra almost separating of degree n.

Proof.

g = sl(n, R) admits an overalgebra of degree n, given by :

g + = sl(n, R) × R n-1 Φ : g ⋆ -→ g +⋆ , Φ(X) = (X, φ(X)) = (X, T 2 (X), T 3 (X), . . . , T n (X)).
Indeed, φ is polynomial, with degree n. Moreover, we have for all ξ in Ω,

Conv (Φ(Coad(SL(n, R))ξ)) = Conv(Coad(SL(n, R))ξ) × (T 2 (ξ), . . . , T n (ξ)) = sl(n, R) ⋆ × (T 2 (ξ), . . . , T n (ξ)).
Then Φ(ξ ′ ) belongs to this set if and only if T k (ξ ′ ) = T k (ξ) for all k, if and only if

C ξ ′ = C ξ .
We saw that if n is odd, {ξ ′ , such that C ξ ′ = C ξ } is exactly the orbit Coad(SL(n, R))ξ and, if n is even, {ξ ′ , such that C ξ ′ = C ξ } is either the orbit Coad(SL(n, R))ξ, or, if C ξ has only non real roots, the set {ξ ′ , such that C ξ ′ = C ξ } is the union of two disjoint orbits. This proves that (g + , φ) is an overalgebra almost separating of degree n of sl(n, R). Let G be a real Lie group, V a finite dimensional vector space and (π, V ) a linear representation of G. Denote by G + = G ′ ⋊ V the Lie group whose set G × V and low:

(g, v).(g ′ , v ′ ) = (gg ′ , v + π(g)v ′ ).
Its Lie algebra is g + = g ′ ⋊ V , whose space g ⊕ V and bracket :

[(X, u), (X ′ , u ′ )] = ([X, X ′ ], π ′ (X)u ′ -π ′ (X ′ )u). ( π ′ is the derivative of π, π ′ is the representation of g in V ). The exponential map is exp(X, u) = (exp X, e π ′ (X) -I π ′ (X) u).
We also define the linear map ψ u : g -→ V , by ψ u (X) = π ′ (X)u, for all u ∈ V . Then, the coadjoint action is realized in g + ⋆ = g ⋆ × V ⋆ and defined by:

Coad ′ (X, u)(ξ, f ) = (Coad ′ (X)ξ + t ψ u (f ), -t π ′ (X)f ).
The group action is

Coad(g, v)(ξ, f ) = (Coad(g)ξ + t ψ v ( t π(g -1 )f ), t π(g -1 )f ).
Denote by π ⋆ (g) = t π(g -1 ).

Let Φ : g ⋆ -→ g + ⋆ be a map non necessarily linear. We assume that p • Φ = id, then Φ is written Φ(ξ) = (ξ, φ(ξ)). φ is not necessarily linear.

Assume that Φ(Coad(G)ξ) = Coad(G + )Φ(ξ), then : for all g in G and all v in V , there exists

g ′ ∈ G (g ′ = g ′ g,v,ξ ) such that π ⋆ (g)φ(ξ) = φ(Coad(g ′ )ξ), Coad(g)(ξ) + ( t ψ v • π ⋆ (g))φ(ξ) = Coad(g ′ )ξ = Coad(g)(ξ) + t ψ v • φ(Coad(g ′ )ξ). In particular, if X is in g, then π ⋆ (exp(tX))(φ(ξ)) = φ(Coad(g ′ t )ξ). The continuous curve t → π ⋆ (exp(tX))(φ(ξ)) is drawn on the surface C = φ(Coad(G)ξ)
, its derivative at 0 is the vector π ⋆′ (X)φ(ξ). This vector belongs to the tangent space

T φ(ξ) (C) = φ ′ (φ(ξ))(T ξ (Coad(G)ξ)) = φ ′ (φ(ξ))(Coad(g)ξ).
We have also, for the same g in G, v in V , and

g ′ = g ′ g,v,ξ ∈ G, Coad(g)(ξ) = (I -t ψ v • φ)(Coad(g ′ )ξ).
We deduce that, if v = 0, then Coad(g)(ξ) = Coad(g ′ g,0,ξ )(ξ) and therefore π ⋆ (g)φ(ξ) = φ(Coad(g)ξ). So:

Lemma 4.2.
φ is an intertwining (non linear) between the coadjoint representation and the representation π ⋆ .

If φ is polynomial of degree p, then φ is written :

φ(ξ) = φ 1 (ξ) + φ 2 (ξ) + • • • + φ p (ξ),
with φ k homogeneous of degree k.

Since φ is an intertwining, then φ • Ad g = π ⋆ (g) • φ, and for all k, φ k • Ad g = π ⋆ (g) • φ k , i.e each φ k is an intertwining.

On the other hand, for each k, φ k (ξ) can be written

φ k (ξ) = b k (ξ • . . . • ξ k ),
where b k is a linear map from S k (g ⋆ ) in V ⋆ . The map b k is also an intertwining, since the action Coad k of G on S k (g ⋆ ) is such that :

φ k (Coad(g)ξ) = b k (Coad(g)ξ • . . . • Coad(g)ξ) = (b k • Coad k (g))(ξ • . . . • ξ). Put then: S p (g ⋆ ) = g ⋆ ⊕ S 2 (g ⋆ ) ⊕ • • • ⊕ S p (g ⋆ ), and b : S p (g ⋆ ) -→ V ⋆ , b(v 1 + v 2 + • • • + v p ) = b 1 (v 1 ) + • • • + b p (v p ). Let U = b(S p (g ⋆ )). U is a submodule of V ⋆ , isomorphic to the quotient module S p (g ⋆ )/ ker(b). Put then W = V /U ⊥ . W is a quotient module of the module V such that W ⋆ ≃ U ( and then W ≃ U ⋆ ). Lemma 4.3. If (g ⋊ V, φ) is an overalgebra almost separating of g, then (g ⋊ W, φ), where φ(ξ) = b(ξ + ξ • ξ + • • • + ξ • . . . • ξ)
is also an overalgebra almost separating of g.

Proof.

In the statement of this lemma, we identify

W ⋆ with the submodule U of V ⋆ . With this identification, if ι is the canonical injection of U in V ⋆ , then φ(ξ) = ι • φ(ξ). The application Φ becomes Φ(ξ) = (ξ, ι • φ(ξ)) = (j • Φ)(ξ) if j(ξ, v) = (ξ, ι(v)). Therefore Conv Φ(CoadG ξ) = j Conv (Φ(CoadG ξ)) , and Conv Φ(CoadG ξ) = Conv Φ(CoadG ξ ′ ) if and only if Conv (Φ(CoadG ξ)) = Conv (Φ(CoadG ξ ′ )).
We deduce that (g⋊W, φ) or, if we prefer, (g⋊(S p (g ⋆ )/ ker b) ⋆ , φ) is an overalgebra almost separating of g.

If g is semi-simple and deployed, then all its representations are completely reducible. Therefore W ⋆ = S p (g ⋆ )/ ker b is isomorphic to a submodule of S p (g ⋆ ) = S p (g). In this case, W is isomorphic to a submodule of (S p (g)) ⋆ . So, we consider the application φ with values in S p (g), and φ becomes :

φ(ξ) = b 1 (ξ) + • • • + b p (ξ • . . . • ξ).
The application b becomes an intertwining of modules S p (g).

Corollary 4.4.

If g is a deployed and semi-simple Lie algebra, admitting an overalgebra almost separating of degree p, and τ a natural application from g = g ⋆ to S p (g) defined by : τ

(ξ) = ξ + ξ • ξ + • • • + ξ • . . . • ξ,
then there exists an intertwining b of S p (g) such that (g ⋊ (S p (g)) ⋆ , b • τ ) is an overalgebra almost separating of g.

5.

The case g = sl(n, R) and p = 2 5.1. The case g = sl(n, R).

We suppose now g = sl(n, R). Recall the usual notations (cf. [FH]). sl(n, R) is a real simple algebra. A Cartan subalgebra h of sl(n, R), of dimension n -1, is given by the set of diagonal matrices ξ = D(c 1 , . . . , c n ). With this Cartan algebra, sl(n, R) is deployed. For H ∈ h, we note

L i (H) = c i , with L 1 + • • • + L n = 0.
We choose the usual system of simple roots, i.e the forms α i = L i -L i+1 (1 ≤ i ≤ n -1). The system of positive roots is the set of forms L i -L j , with i < j. If e ij = (x rs ) is the n × n matrix such that x rs = δ ri δ sj , then for all H in h,

ad(H)e ij = (α i + • • • + α j-1 )(H)e ij , if i < j -(α j + • • • + α i-1 )(H)e ij , if i > j.
The fundamental weights are

ω k = L 1 + • • •+ L k (1 ≤ k ≤ n -1
) and the simple modules are exactly the modules noted Γ a 1 ...a n-1 of highest weight

a 1 ω 1 + • • • + a n-1 ω n-1 ,
with a k integer. Moreover, the dual of Γ a 1 ,...,a n-1 is the module Γ a n-1 ,...,a 1 . (cf. [FH]).

Let X → X s be the symmetry operation relative to the second diagonal given by: if X is the matrix (x ij ), then X s is the matrix (x s ij ) with :

x s ij = x (n+1-j)(n+1-i) ,
The operation s leaves the Cartan subalgebra invariant. For all weight ω, put ω s (H) = ω(H s ). In particular, L s i = L n+1-i and ω s j = -ω n-j . Moreover, s permutes the radiciel spaces, since e s ij = e (n+1-j)(n+1-i) , or, if H belongs to h and i < j,

[H, e s ij ] = -(L s i -L s j )(H)e s ij . We consider now the module S k (sl(n, R)) i.e the space of the sums

i 1 <•••<i k λ i 1 ,...,i k X i 1 • . . . • X i k on
which sl(n, R) acts by the adjoint action ad defined by:

ad X (X i 1 • . . . • X i k ) = k r=1 X i 1 • . . . • [X, X ir ] • . . . • X i k . Lemma 5.1. The space S k (sl(n, R)) is self-dual i.e S k (sl(n, R)) ⋆ = S k (sl(n, R)).
Proof. Suppose that the module Γ a 1 ,...,a n-1 appears in S k (sl(n, R)). Then, there is a non zero vector v a 1 ,...,a n-1 such that , for all H in h, and for all i < j,

ad H (v a 1 ...a n-1 ) = (a 1 ω 1 + • • • + a n-1 ω n-1 )(H)v a 1 ...a n-1 , ad e ij (v a 1 ...a n-1 ) = 0. If v = i 1 <•••<i k λ i 1 ,...,i k X i 1 •. . .•X i k is a vector of S k (sl(n, R)), then v s = i 1 <•••<i k λ i 1 ,...,i k X s i 1 • . . . • X s i k . Moreover, the map v → v s is an involutive bijection : (v s ) s = v.
The vector v s a 1 ...a n-1 is not zero and, for all H in h, and all i < j, ad

H (v s a 1 ...a n-1 ) = -(a 1 ω 1 + • • • + a n-1 ω n-1 ) s (H)v s a 1 ...a n-1 = (a n-1 ω 1 + • • • + a 1 ω n-1 )(H)v s a 1 ...a n-1 , ad e ij (v s a 1 ...a n-1 ) = 0. In other words, Γ a 1 ,...,a n-1 s = Γ a n-1 ,...,a 1 ≃ Γ a 1 ,...,a n-1 ⋆ .
Corollary 5.2.

If sl(n, R) admits an overalgebra almost separating of degree p, if τ is the natural application of sl(n, R) ⋆ in S p (sl(n, R)) = (S p (sl(n, R))) ⋆ given by : τ

(ξ) = ξ +ξ •ξ +• • •+ξ •. . .•ξ, then there exist an intertwining b k of S k (sl(n, R)) (k = 1, . . . , p) such that (sl(n, R) ⋊ S p (sl(n, R)), k b k • τ ) is an overalgebra almost separating of the Lie algebra sl(n, R).

The case p = 2.

For k = 1 and k = 2, looking for the intertwining between S k (sl(n, R) ⋆ ) and S k (sl(n, R)) ⋆ . For k = 1, the space of these intertwining is one dimensional and generated by P 0 defined by : P 0 (ξ), X = T r(ξX).

Therefore, any intertwining b 1 is written b 1 = a 0 P 0 , with a 0 real. For k=2: 5.2.1. Decomposition of S 2 (g).

The module S 2 (g) is the sum of three or four irreducible modules, all of different types. Recall the usual notations (cf. [FH]).

• The highest weight vector in S 2 (sl(n, R)) is v 20...02 = e 1n .e 1n .

The weight of this vector is 2ω 1 + 2ω n = 2L 1 -2L n . Then, we deduce the existence of a simple module Γ 20...02 of dimension (cf. [FH]):

dim Γ 20...02 = n-1 i=2 2 + n -i n -i . n-1 j=2 2 + j -1 j -1 . 4 + n -1 n -1 = n 2 (n -1)(n + 3) 4 .
• Among the weight vectors of weight

ω 2 + ω n-2 = L 1 -L n + L 2 -L n-1
, and if n > 3, there is one that is annulled by the action of e i(i+1) , 1 ≤ i ≤ (n -1). This weight vector is : v 010...010 = e 2n .e 1(n-1)e 2(n-1) .e 1n .

We deduce then the existence of a simple module Γ 010...010 of dimension: 3), and this dimension is 0. This sub module does not appear.

dim Γ 010...010 = n-2 j=3 1 + (j -1) j -1 . n-2 j=3 1 + (j -2) j -2 . n-2 i=3 1 + (n -1) -i n -1 -i . n-2 i=3 1 + n -i n -i . n 2 (n + 1) 4(n -2) 2 (n -3) = n 2 (n + 1)(n -3) 4 If n = 3, e 22 is not in sl(
• Among the weight vectors of weight ω 1 + ω n-1 = L 1 -L n , there is one that is annulled by the action of e i(i+1) , 1 ≤ i ≤ (n -1). This weight vector is:

v 10...01 = n i=1 e 1i .e in - 2 n n j=1
e jj .e 1n .

Then, we deduce the existence of a simple module Γ 10...01 of dimension:

dim Γ 10...01 = n-1 i=2 1 + n -i n -i . n-1 j=2 1 + j -1 j -1 . 2 + n -1 n -1 = n 2 -1.
• Among the weight vectors of weight 0, there is one that is annulled by the action of e i(i+1) , 1 ≤ i ≤ (n -1). This weight vector is: We deduce the existence of a trivial simple module Γ 00...00 of dimension 1. Therefore:

S 2 (sl(n, R)) ∼ =      Γ 20...02 ⊕ Γ 10...01 ⊕ Γ 010...010 ⊕ Γ 0...0 , if n > 3 Γ 22 ⊕ Γ 11 ⊕ Γ 00 , if n = 3. since the dimensions, n 2 (n 2 -1) 2 = n 2 (n -1)(n + 3) 4 +n 2 -1+ n 2 (n + 1)(n -3) 4 +1.

Intertwining of S 2 (sl(n, R)).

Let P 1 , P 2 , P 3 and P 4 the intertwining defined from S 2 (sl(n, R)) in (S 2 (sl(n, R))) ⋆ , such that, for all ξ, η ∈ sl(n, R) and X, Y ∈ sl(n, R) :

• P 1 (ξ.η), X.Y = T r(ξXηY ) + T r(ξY ηX),

• P 2 (ξ.η), X.Y = T r(ξX)T r(ηY ) + T r(ξY )T r(ηX),

• P 3 (ξ.η), X.Y = T r(ξηXY ) + T r(ξηY X) + T r(ηξXY ) + T r(ηξY X),

• P 4 (ξ.η), X.Y = T r(ξη)T r(XY ). In particular, we have :

• P 2 (v 20...02 ) = P 3 (v 20...02 ) = P 4 (v 20...02 ) = 0, and P 1 (v 20...02 ), e n1 .e n1 = 1 = 0,

• P 3 (v 010...010 ) = P 4 (v 010...010 ) = 0, and P 2 (v 010...010 ), e n2 .e (n-1)1 = 4 = 0,

• P 4 (v 10...01 ) = 0, and P 3 (v 10...01 ), e n2 .e 21 = 0,

• P 4 (v 00...00 ) = 0.

Thus, if n > 3, P 1 , P 2 , P 3 and P 4 are independent and, since the dimension of the space of intertwining of S 2 (sl(n, R)) is 4, then any intertwining b 2 is written : b 2 = a 1 P 1 + a 2 P 2 + a 3 P 3 + a 4 P 4 , where a i are real constants.

If n = 3, P 1 , P 3 and P 4 are independent and, since the dimension of the space of intertwining is three, then we can write : b 2 = a 1 P 1 + a 3 P 3 + a 4 P 4 , where a i are real constants.

Remark 5.1. First, recall that for gl(n, R), the forms

(A 1 , . . . , A m ) → T r(A i 1 . . . A i k ) are the only invariant functions which generate K[End(V ) m ] GL(V ) (see [H-C]).
Remark that there are 24 possible products of 4 matrices, depending on the position of the matrix in the product. If we take the trace of these products, then there are only 6 distinct forms, since, for all A 1 , A 2 , A 3 , A 4 ∈ sl(n, R):

T r(A 1 A 2 A 3 A 4 ) = T r(A 2 A 3 A 4 A 1 ) = T r(A 3 A 4 A 1 A 2 ) = T r(A 4 A 1 A 2 A 3 ).
Since we are looking here to build symmetric forms in ξ, η and X, Y , there are only 4 symmetric forms obtained as product of traces of product matrices. These forms are the 4 forms described above. 5.3. sl(n, R) does not admit an overalgebra almost separating of degree 2.

We have seen if sl(n, R) admits an overalgebra almost separating of degree 2, then sl(n, R) admits an overalgebra of the form

G = (sl(n, R) ⋊ S 2 (sl(n, R)), (φ : ξ → b 1 (ξ) + b 2 (ξ • ξ))), with b 1 = a 0 P 0 and b 2 = a 1 P 1 + • • • + a 4 P 4 .
We assume that a such overalgebra almost separating G exists.

The generic orbits SL(n, R) • ξ are the orbits of the points ξ of Ω. Recall that :

SL(n, R) • ξ ⊂ {ξ ′ ∈ sl(n, R), C ξ ′ = C ξ }.
Thus, for all ξ in Ω and all v ∈ S 2 (sl(n, R)), we put

ζ = ξ + t ψ v (φ(ξ)) such that C ξ ′ = C ξ . Lemma 5.3.
If G is an overalgebra almost separating for sl(n, R), then for all ξ of sl(n, R) and all v of S 2 (sl(n, R)), ζ = ξ + t ψ v (φ(ξ)) has the same caracteristic polynomial as ξ and the same eigenvalues.

Proof. For any matrix ξ of sl(n, R), and all ε > 0, there exists ξ ε in Ω such that :

ξ -ξ ε < ε. Since ξ ε is in Ω, det(ξ ε + t ψ v (φ(ξ ε )) -λI) = det(ξ ε -λI), ∀λ, ∀v
If ε tends to 0, then, for all λ, det(ξ + t ψ v (φ(ξ)) -λI) = det(ξ -λI).

Theorem 5.4.

For n > 2, sl(n, R) does not admit an overalgebra almost separating of degree 2.

Proof.

We have seen if sl(n, R) has an overalgebra almost separating of degree 2, there exists an overalgebra G, with

φ(ξ) = a 0 P 0 (ξ) + (a 1 P 1 + • • • + a 4 P 4 )(ξ • ξ).
We will show that, if for all ξ in Ω, and all v in S 2 (sl(n, R)), ξ and ζ = ξ + t ψ v (φ(ξ)) have the same eigenvalues, then a 0 = a 1 = • • • = a 3 = 0, and that the function φ(ξ) = a 4 P 4 (ξ • ξ) does not separate the coadjoint orbits of sl(n, R), if n > 2.

Taking first v = U ∈ sl(n, R). Then t ψ U (φ(ξ)), X = a 0 T r(ξ[X, U]), and ζ = ξ + a 0 [U, ξ].
Let U = e n1 + e (n-1)2 and ξ = e 1n + e 2(n-1) , thus ζ = a 0 (-e 11e 22 + e (n-1)(n-1) + e nn ) + e 1n + e 2(n-1) and det(ζ -λI) = (-λ) n-4 (λ 2a 2 0 ) 2 . Therefore, ζ has the same spectrum as ξ implies a 0 = 0.

Put now v = X.X, then a direct calculation gives :

t ψ X.X (φ(ξ)) = 4a 1 [X, ξXξ] + 4a 2 T r(ξX)[X, ξ] + 4a 3 [X 2 , ξ 2 ], if n > 3, 4a 1 [X, ξXξ] + 4a 3 [X 2 , ξ 2 ], if n = 3.
Choose ξ = e 1n and X = e n1 . ξ and X are nilpotent matrices : X 2 = ξ 2 = 0 and we obtain :

ξX = e 11 , [X, ξXξ] = e nn -e 11 , T r(ξX) = 1, [X, ξ] = e nn -e 11 , thus t ψ X.X (φ(ξ)) = (4a 1 + 4a 2 )(-e 11 -e 22 + e (n-1)(n-1) + e nn ), if n > 3, 4a 1 (e 33 -e 22 ), if n = 3, and, if we note ζ = ξ + t ψ X.X (φ(ξ)), then det(ζ -λI) = (-λ) n-2 (λ 2 -(4a 1 + 4a 2 ) 2 ), if n > 3, -λ(λ 2 -(4a 1 ) 2 ), if n = 3.
Since det(ξ -λI) = (-λ) n , then we deduce that 4a 1 + 4a 2 = 0 if n > 3 and a 1 = 0 if n = 3.

Suppose now n > 3. We choose ξ = e 1n + e 2(n-1) and X = t ξ = e n1 + e (n-1)2 . These matrices are nilpotent and we obtain and λ) n , we deduce that 4a 1 + 8a 2 = 0. Thus, in all cases, a 1 = a 2 = 0.

det(ζ -λI) = (-λ) (n-4) (λ 2 -(4a 1 + 8a 2 ) 2 ) 2 . Since det(ξ -λI) = (-
Choose now ξ = e 1(n-1) + e (n-1)n and X = t ξ = e (n-1)1 + e n(n-1) , then

X 2 = e n1 , ξ 2 = e 1n , [X 2 , ξ 2 ] = -e 11 + e nn . Therefore t ψ X 2 (φ(ξ)) = 4a 3 (-e 11 + e nn ) and det(ζ -λI) = (-λ) (n-2) (λ 2 -(4a 3 ) 2 ). Hence, since det(ξ -λI) = (-λ) n , then a 3 = 0.
Thus, we deduce that :

φ(ξ) = b 2 (ξ.ξ) = a 4 P 4 (ξ.ξ) or φ(ξ), U + X.Y = a 4 T r(ξ 2 )T r(XY ).
But the overalgebra G is not separating, since, for all t in [0, 1], and all matrix M = D(c 4 , . . . , c n ) ∈ sl(n -3, R), with |c k | > 2, we define the matrix

ξ t =       1 2 (t + √ 4 -3t 2 ) 1 2 (t - √ 4 -3t 2 ) -t M       . For all t, ξ t ∈ Ω, det(ξ t ) = t(1 -t 2 ) k c k and T r(ξ 2 t ) = 2 + k c 2 k .
i.e, for all t,

Conv (Φ(CoadSL(n, R)ξ t )) = sl(n, R) ⋆ × {U + X • Y → a 4 (2 + k c 2 k )T r(XY )}, therefore if t = 1 √ 3 , Coad SL(n, R)(ξ t ) = Coad SL(n, R)(ξ 1 √ 3 ). Since t(1 -t 2 ) < 1 √ 3 (1 - 1 3 ) = 2 3 √ 3 , det(ξ t ) = det(ξ 1 √ 3
), thus ξ t is not in the orbit

Coad SL(n, R)ξ 1 √ 3 . Remark 5.2. Recall that, if n = 2, the overalgebra (sl(2, R) ⋊ R, [ξ → T r(ξ 2 )]
) is an overalgebra almost separating of degree 2 of sl(2, R) (cf. [ASZ] where we use the function

det(ξ) = - 1 2 T r(ξ 2 )).
Similarly, sl(3, R) does not admit an overalgebra almost separating of degree 2 but sl(3, R) admits an overalgebra almost separating of degree 3.

In this following section, we will show that sl(4, R) does not admit an overalgebra almost separating of degree 2 or 3 but it admits one overalgebra almost separating of degree 4.

6. The case n = 4 and p = 3

As above, we shall first find the explicit decomposition of S 3 (sl(4, R)).

6.1. Decomposition of S 3 (sl(4, R)).

We have seen that the module S 3 (sl(4, R)) is self dual. Then, if the submodule Γ a 1 a 2 a 3 appears in the decomposition of S 3 (sl(4, R)), the submodule Γ a 3 a 2 a 1 ≃ (Γ a 1 a 2 a 3 ) s appears also.

The module S 3 (sl(4, R)) is a submodule of S 2 (sl(4, R)) ⊗ sl(4, R). The decomposition of S 2 (sl(4, R)) ⊗ sl(4, R) is given by Littlewood-Richardson's rule (cf. [FH]), as follows :

S 2 (sl(4, R)) ⊗ sl(4, R) = (Γ 303 + Γ 212 + Γ 202 + Γ 101 ) + (Γ 121 + Γ 202 + Γ 101 + Γ 311 + Γ 113 ) + 3(Γ 210 + Γ 012 ) + 2Γ 020 + 3Γ 101 + Γ 000 .
The highest weight vectors which appear in S 2 (sl(4, R)) are v 202 , v 020 , v 101 and v 000 . We deduce that there are 4 highest weight vectors in S 3 (sl(4, R)) which are w 303 = v 202 .e 14 , w 121 = v 020 .e 14 , w 202 = v 101 .e 14 and w 101 = v 000 .e 14 . These vectors are the highest weight vectors for the simple modules Γ 303 , Γ 121 , Γ 202 and Γ 101 .

In S 2 (sl(4, R)) ⊗ sl(4, R), the highest weight vectors v 020 ⊗ e 14v 020 .e 14 , v 101 ⊗ e 14v 101 .e 14 and v 000 ⊗ e 14v 000 .e 14 appear also. The corresponding simple modules of these vectors are, respectively, Γ 121 , Γ 202 and Γ 101 . Since these vectors are not symmetric, then their corresponding modules are not submodules of S 3 (sl(4, R)).

The highest weight vector of Γ 311 is e 14 ⊗ e 13 ⊗ e 14e 14 .e 13 .e 14 which is not symmetric, then Γ 311 does not appear in S 3 (sl(4, R)), and Γ 113 does not appear also.

We conclude:

Γ 303 + Γ 121 + Γ 202 + Γ 101 ⊂ S 3 (sl(4, R)).
The additional invariant space of (Γ 303 + Γ 212 + Γ 202 + Γ 101 ) in S 3 (sl(4, R)) has the following decomposition, by using the dimensions :

S 3 (sl(4, R))/(Γ 303 + Γ 212 + Γ 202 + Γ 101 ) = (Γ 210 + Γ 012 ) + Γ 101 + Γ 000 .
Therefore :

S 3 (sl(4, R)) = (Γ 303 + Γ 212 + Γ 202 + Γ 101 ) + (Γ 210 + Γ 012 + Γ 101 + Γ 000 ).
The Now looking for the highest weight vectors of the four remaining simple modules.

By Littlewood-Richardson's rule, (Γ 210 + Γ 012 ) appears in the tensorial product Γ 020 ⊗ Γ 101 where Γ 020 is in S 2 (sl(4, R)), and Γ 101 is in sl(4, R).

The highest weight vector of the module Γ 020 is : v 020 = e 24 .e 13e 23 .e 14 .

We deduce also two other vectors of Γ 020 given by : ad e 42 v 020 = ((e 44e 22 ).e 13e 43 .e 14 + e 23 e 12 ), ad e 32 v 020 = (e 34 .e 13e 24 .e 12 -(e 33e 22 ).e 14 ).

Thus, there is a highest weight vector of Γ 210 , defined by : w 210 = e 12 .e 24 .e 13e 12 .e 23 .e 14e 14 .e 43 .e 14 + e 13 .e 34 .e 13 + (e 44e 33 ).e 13 .e 14 .

w 210 is a non zero vector and its weight is 4L 1 + 2L 2 + 2L 3 = 2ω 1 + 2ω 3 . Indeed : ad e 12 w 210 = 0, ad e 23 w 210 = 0 and ad e 34 w 210 = 0. Using the application s, the highest weight vector of the module Γ 012 is v s 210 or : w 012 = e 34 .e 13 .e 24e 34 .e 23 .e 14e 14 .e 21 .e 14 + e 24 .e 12 .e 24 + (e 11e 22 ).e 24 .e 14 .

It remains the modules Γ 101 and Γ 000 which appear in the tensorial product Γ 101 ⊗ Γ 101 . The first factor is in S 2 (sl(4, R)), the second is in sl(4, R).

There is a basis for the first factor defined by the following vectors : Recall that, in the previous section, we calculated the 8 highest weight vectors of the decomposition of S 3 (sl(4, R)), i.e the free system (w 1 , . . . , w 8 ) = (w 303 , w 121 , w 202 , w 210 , w 012 , w 101 , w ′ 101 , w 000 ).

e ′ ij =
Let M the matrix with 8 rows and 12 columns whose entries are the numbers T i (w k ), (w k ) t (i = 1, . . . , 12, k = 1, . . . , 8) where the vector e j 1 i 1 .e j 2 i 2 .e j 3 i 3 of S 3 (sl(4, R)) is noted (e i 1 j 1 .e i 2 j 2 .e i 3 j 3 ) t . We obtain, by using a symbolic computation program, the following matrix: 0 0 0 36 0 0 0 36 0 0 0 36 0 0 0 0 0 0 0 4 0 0 0 12 0 1 1 3 0 1 0 4 0 1 0 6 0 0 4 0 0 4 0 4 0 0 0 6 0 1 0 0 0 1 0 2 0 0 0 6 1 1 2 0 2 3 2 2 0 0 4 6 1 0 0 0 0 2 0 0 0 0 0 6 3 0 0 0 0 3 0 0 9 0 0 6

M =           
          
The rank of this matrix is 8.

We extract the columns 1, 2, 3, 4, 5, 8, 10, 9, so we obtain the following intertwining. The notation 'Sym' means that the expression is symmetrical in ξ, η, ζ.

If N is the sub-matrix of M, with 8 rows and 8 columns whose entries are P i (w k ), (w k ) t , i = 1, . . . , 8, then

N =           
0 0 0 36 0 36 0 0 0 0 0 0 0 4 0 0 0 1 1 3 0 4 1 0 0 0 4 0 0 4 0 0 0 1 0 0 0 2 0 0 1 1 2 0 2 2 0 0 1 0 0 0 0 0 0 0 3 0 0 0 0 0 0 9

          
The rank of this matrix is also 8. Thus (P 1 , P 2 , P 3 , P 4 , P 5 , P 6 , P 7 , P 8 ) are independent. Therefore: Lemma 6.1.

The applications P i : S 3 (sl(4, R) ⋆ ) -→ S 3 (sl(4, R)) ⋆ defined above, form a basis of the space of intertwining of the module S 3 (sl(4, R)).

But we consider, for 0 < t < 1, the matrices

ξ t =     √ 1 + t - √ 1 + t √ 1 -t - √ 1 -t     .
ξ t is an element of Ω for all t, T r(ξ 2 t ) = 4 and T r(ξ 3 t ) = 0 for all t. Although, det(ξ t ) = (1t 2 ) 2 . Therefore, with the same argument as in a previous section, we have, for all t, Conv (Φ(Coad SL(4, R)ξ t )) = (sl(4, R)) ⋆ × {U + X.Y + X ′ .Y ′ .Z ′ → 4a 4 T r(XY )}.

But, if t = 1 2 , ξ t is not in the orbit Coad SL(4, R)ξ 1 2 .

Thus, sl(4, R) does not admit an overalgebra almost separating of degree 3.

In fact, we think that the following conjecture is always true : Conjecture 6.3. For all n, sl(n, R) does not admit an overalgebra almost separating of degree n -1, but it admits an overalgebra almost separating of degree n.

More generally, if g is a real and deployed semi simple Lie algebra and if k is the greatest degree of the generators of the algebra of invariant functions on g, then g admits an overalgebra almost separating of degree k. But g does not admit an overalgebra almost separating of degree k -1.

The hypothesis 'g deployed' is necessary. Indeed, we remark that sl(2, R) does not admit an overalgebra almost separating of degree 1, but the Lie algebra su(2) admits an overalgebra almost separating of degree 1 since its adjoint orbits are spheres which are characterized by the closure of their convex hull.

4.

  Overalgebra almost separating of degree p of a Lie algebra g Definition 4.1. (Semi direct product)

v

  00...00 = 2n 1≤i<j≤n e ij .e ji + 1≤i<j≤n (e iie jj ).(e iie jj )

ξ 2

 2 = 0, ξX = e 11 + e 22 , ξXξ = e 1n + e 2(n-1) , [X, ξXξ] = -e 11e 22 + e (n-1)(n-1) + e nn , T r(ξX) = 2, [X, ξ] = -e 11e 22 + e (n-1)(n-1) + e nn .Therefore t ψ X.X (φ(ξ)) = (4a 1 + 8a 2 )(-e 11e 22 + e (n-1)(n-1) + e nn )

  (sl(4, R)) ⋆ = sl(4, R), and X, Y , Z elements in sl(4, R). The trace forms are the following :T 1 = T r(ξηζXY Z), T 2 = T r(ξηXζY Z), T 3 = T r(ξηXY ζZ), T 4 = T r(ξXηY ζZ), T 5 = T r(ξηζX)T r(Y Z), T 6 = T r(ξηXY )T r(ζZ), T 7 = T r(ξXY Z)T r(ηζ), T 8 = T r(ξXηY )T r(ζZ),T 9 = T r(ξηζ)T r(XY Z), T 10 = T r(ξηX)T r(ζY Z), T 11 = T r(ξη)T r(ζX)T r(Y Z), T 12 = T r(ξX)T r(ηY )T r(ζZ).

  Explicitly : P 1 (ξηζ), XY Z = Sym(T r(ξηζXY Z)), P 2 (ξηζ), XY Z = Sym(T r(ξηXζY Z)), P 3 (ξηζ), XY Z = Sym(T r(ξηXY ζZ)), P 4 (ξηζ), XY Z = Sym(T r(ξXηY ζZ)), P 5 (ξηζ), XY Z = Sym(T r(ξηζX)T r(Y Z)), P 6 (ξηζ), XY Z = Sym(T r(ξXηY )T r(ζZ)), P 7 (ξηζ), XY Z = Sym(T r(ξηX)T r(ζY Z)), P 8 (ξηζ), XY Z = Sym(T r(ξηζ)T r(XY Z)).

  highest weight vectors w 303 , w 121 , w 202 and w 101 are: w 303 = e 14 .e 14 .e 14 , w 121 = e 24 .e 13 .e 14e 23 .e 14 .e 14 , w 202 = e 12 .e 24 .e 14 + e 13 .e 34 .e 14 + 1 2 ((e 11e 22 ) -(e 33e 44 )).e 14 .e 14 , w 101 = 8(e 12 .e 21 .e 14 + e 13 .e 31 .e 14 + e 14 .e 41 .e 14 + e 23 .e 32 .e 14 + e 34 .e 43 .e 14 )+ + 3(e 11 .e 11 .e 14 + e 22 .e 22 .e 14 + e 33 .e 33 .e 14 + e 44 .e 44 .e 14 )--2(e 11 .e 22 .e 14 + e 11 .e 33 .e 14 + e 11 .e 44 .e 14 + e 22 .e 33 .e 14 + e 22 .e 44 .e 14 + e 33 .e 44 .e 14 ).

  e i1 .e 1j + e i2 .e 2j + e i3 .e 3j + e i4 .e 4j -1 2 (e 11 + e 22 + e 33 + e 44 ).e ij . In S 2 (sl(4, R)) ⊂ Γ 101 ⊗ Γ 101 , we have seen that the corresponding highest weight vectors are: v 101 = e 12 .e 24 + e 13 .e 34 + 1 2 ((e 11e 22 ) -(e 33e 44 )).e 14 , iie jj ).(e iie jj ). replacing the first factor e ij by the factor e ′ ij , we obtain the highest weight vectors w ′ 101 and w 000 ( w 000 is not developed) : w ′ 101 = 2e 12 (2e 23 .e 34 + 2e 21 .e 14 + (e 22e 11 ).e 24 -(e 33e 44 ).e 24 )+ + 2e 13 (2e 32 .e 24 + 2e 31 .e 14 + (e 33e 11 ).e 34 + (e 44e 22 ).e 34 )+ + (e 11e 22 )(2e 12 .e 24 + 2e 13 .e 34 + (e 11e 22 ).e 14 --(e 33e 44 ).e 14 ) -(e 33e 44 )(2e 12 .e 24 + 2e 13 .e 34 + (e 11e 22 ).e 14 -(e 33e 44 ).e 14 ), w 000 = 4(e 12 .e ′ 21 + e ′ 12 .e 21 + e 13 .e ′ 31 + e ′ 13 .e 31 + e 14 .e ′ 41 + e ′ 14 .e 41 + + e 23 .e ′ 32 + e ′ 23 .e 32 + e 24 .e ′ 42 + e ′ 24 .e 42 + e 34 .e ′

	v 000 = 8	e ij .e ji +
	1≤i<j≤4
	By 43 + e ′ 34 .e 43 )+
	+ (e 11 -e 22 )(e ′ 11 -e ′ 22 ) + (e 11 -e 33 )(e ′ 11 -e ′ 33 ) + (e 11 -e 44 )(e ′ 11 -e ′ 44 )+ + (e 22 -e 33 )(e ′ 22 -e ′ 33 ) + (e 22 -e 44 )(e ′ 22 -e ′ 44 ) + (e 33 -e 44 )(e ′ 33 -e ′ 44 ).

1≤i<j≤4 (e 6.2. Trace forms and intertwining of S 3 (sl(4, R)).

As for S 2 (sl(n, R), we know 12 trace forms. Denote by ξ, η and ζ elements in

This work was supported by The Hubert Curien-Utique contracts 06/S1502 and 09/G 1502. I thank my professor Didier Arnal for his aid an i thank the University of Bourgogne for its hospitality during my stay in France.

6.3. sl(4, R) does not admit an overalgebra almost separating of degree 3. Theorem 6.2.

The algebra sl(4, R) does not admit an overalgebra almost separating of degree 3.

Proof.

We have seen that if sl(4, R) admits an overalgebra of degree 3, then sl(4, R) admits an overalgebra of the form

Then, we choose v = X.X.X in S 3 (sl(4, R)) and we calculate t ψ v (P j (ξ.ξ.ξ)). Explicitly:

t ψ v (P 8 (ξ.ξ.ξ)) = 0.

Let ξ = e 14 , then ξ 2 = 0 and t ψ v (P j (ξ.ξ.ξ)) = 0, for j = 1, 2, 3, 5, 7.

Let now X = e 14 + e 41 , then ξX = e 11 and XξXξX = Xξ = e 41 .

So, we obtain t ψ v (P 4 (ξ.ξ.ξ)) = -3(e 11e 44 ) and t ψ v (P 6 (ξ.ξ.ξ)) = 3(e 11e 44 ). Thus, with same notations as above,

We deduce the relation c 6c 4 = 0.

On the other hand, let X = e 14e 41 , then : Thus, we get t ψ v (P 6 (ξ.ξ.ξ)) = 3(e 11e 44 ) and t ψ v (P 4 (ξ.ξ.ξ)) = 3(e 11e 44 ). Therefore

then c 6 + c 4 = 0. This shows that c 6 = c 4 = 0.

We choose now ξ = e 13 + e 34 , and X = t ξ = e 31 + e 43 . Then:

We deduce that t ψ v (P 2 (ξ.ξ.ξ)) = e 11 + e 33 -2e 44 and t ψ v (P 3 (ξ.ξ.ξ)) = 2e 11e 33e 44 . Therefore,

Hence, the spectrum of ζ is the same as ξ, i.e {0} implies c 2 + 2c 3 = 0, c 2c 3 = 0, and 2c 2 + c 3 = 0, so c 2 = c 3 = 0.

Therefore, the spectrum of ζ is the same as ξ, i.e {0} implies c 7 = 0.

Later, we choose ξ = e 12 + e 23 + e 34 and X = t ξ. Then, ξ 2 = e 13 + e 24 , ξ 3 = e 14 , X 3 = e 41 . Thus t ψ v (P 1 (ξ.ξ.ξ)) = e 11e 44 and the spectrum of

Finally, we choose another X = e 14 + e 41 and we allowed ξ = e 12 + e 23 + e 34 . Then X 2 = e 11 + e 44 and ξ 3 = e 11e 44 . Therefore, t ψ v (P 5 (ξ.ξ.ξ)) = 2(e 11e 44 ) and det(ζ -λI) = λ 4 implies c 5 = 0.

We finally get:

⋆ Laboratoire de Mathématique Physique, Fonctions Spéciales et Applications, Université de Sousse, Ecole Supérieure des Sciences et de Technologie de Hammam-Sousse, Rue Lamine Abassi 4011 H. Sousse, Tunisie E-mail address: amel.zergane@u-bourgogne.fr E-mail address: amel.zergan@yahoo.fr


Emmanuel Jeanvoine

Luc Sarzyniec

Lucas Nussbaum

Kadeploy3: Efficient and Scalable Operating System Provisioning for HPC Clusters

Keywords: HPC, cluster provisionning HPC, cluster provisionning

Operating system provisioning is a common and critical task in cluster computing environments. The required low-level operations involved in provisioning can drastically decrease the performance of a given solution, and maintaining a reasonable provisioning time on clusters of 1000+ nodes is a significant challenge. We present Kadeploy3, a tool built to efficiently and reliably deploy a large number of cluster nodes. Since it is a keystone of the Grid'5000 experimental testbed, it has been designed not only to help system administrators install and manage clusters but also to provide testbed users with a flexible way to deploy their own operating systems on nodes for their own experimentation needs, on a very frequent basis. In this paper we detail the design principles of Kadeploy3 and its main features, and evaluate its capabilities in several contexts. We also share the lessons we have learned during the design and deployment of Kadeploy3 in the hope that this will help system administrators and developers of similar solutions.

Introduction

Traditional users of computing resources do not often care about the way in which the operating system has been installed on the hardware as long as their applications can be compiled and executed.

However the task of installing an operating system can be very tedious on large scale clusters. Since it is not realistic to install the nodes independently, disk cloning or imaging [1,[START_REF]Open Source Cluster Application Resources[END_REF][START_REF]SystemImager[END_REF][START_REF]xCAT: Extreme Cloud Administration Toolkit[END_REF] is a common approach. In this case the administrator must keep updated only one node (sometime called golden node) that can be replicated to other nodes. Usually a small post-installation step has to be performed to customize certain node-specific parameters (e.g., identity details).

The work presented in this paper has emerged from quite specific requirements mandated by the Grid'5000 experimental testbed [6,[START_REF] Bolze | Grid'5000: a large scale and highly reconfigurable experimental Grid testbed[END_REF]. The goal of Grid'5000 is to provide the users with a fully customizable testbed in order to perform advanced experiments in all areas of computer science related to parallel, large-scale or distributed computing and networking. Thus, the testbed required a tool to allow users to deploy their own operating system (whatever flavor). In many cases, this capability is essential since users might need to gain root on the nodes in order to install specific packages or to tune kernel parameters, or simply to install a non-standard OS. The computing resources of Grid'5000 are distributed over several sites (10 in 2012), mostly in France. Each site can support several hundred nodes. The major constraints of OS provisioning on the Grid'5000 testbed include:

• the operating system on any grid node can be modified by any user at any time, potentially several times a day. To avoid any conflicts between users, the tool must interact with the batch scheduler to specify which user has the right to deploy a specified set of nodes during a time slice.

• the reconfiguration time of an entire cluster (100+ nodes) must be small enough (on the order of ten minutes) and the reconfiguration process reliable enough to let users quickly set up their experiments.

• several clusters of a given site (with different hardware characteristics) and even several grid sites can have to be reconfigured in one shot, in the case of a grid experiment for instance.

• even though Linux is the most widely used operating system on Grid'5000, non-Linux/*nix based operating systems must also be supported.

• some users do not need to deploy a specific environment; a standard production environment can be used instead. Whenever possible, the standard environment should be maintained between experiments so as to avoid total reconfiguration and longer setup times. This requires several technical restrictions, e.g., the new operating system must be installed on a separate partition and the master boot record must not be modified.

• since users can reconfigure the nodes as they see fit, nodes may be in almost any state after experiment completion. Thus no assumption must be made about the state of a node before a reconfiguration. Grid'5000 mechanisms allow to check if nodes have been altered after experiment completion in order to redeploy the standard environment.

• most users are accustomed to scripting their experiments, so the deployment tool must not only offer a command line interface, but also an API.

Macrostep 3

Final reboot Figure 1: Kadeploy deployment process, composed of three macro-steps Kadeploy3 has been designed to be used beyond the Grid'5000 testbed, so it is also possible to use it in a more common way (e.g., as an administration tool such as xCAT [START_REF]xCAT: Extreme Cloud Administration Toolkit[END_REF] or SystemImager [START_REF]SystemImager[END_REF]). Compared to its competitors, Kadeploy3 has better scalability properties, a property that is paramount since we would like to target petascale and future exascale clusters. The solution is relying on standard mechanisms (such as network boot), tunable (to be compliant with any technologies) and hardware independent. As a consequence Kadeploy3 is potentially usable with any kind of HPC cluster.

In this paper, we present an experiment in which we deploy 4,000 nodes in a single administrative cycle. Kadeploy3 is flexible enough to load or release dynamically certain features in order to fit a wide range of existing infrastructures and requirements.

The paper is organized as follows. Section 2 gives an overview of Kadeploy3 concerning the deployment process and its ecosystem. Section 3 describes the designs principles, in particular those related to the software architecture and to the scalability. Section 4 shows qualitative and quantitative evaluation elements that demonstrate the feasibility and the efficiency of our solution even in large scale environments. Section 5 details the lessons we have learned through the design, the development and the use of the tool. Section 6 compares Kadeploy3 to the state of the art. Finally, section 7 concludes the papers and presents the future directions we plan to investigate.

Overview

In this section we give an overview of Kadeploy3. First, we detail the steps that comprise the deployment process and how this process can be reliable. Then, we explain how Kadeploy3 interacts with the infrastructure ecosystem and in particular, the issue of node booting. Finally we present the suite of tools associated to Kadeploy3.

Deployment Process

Kadeploy3 belongs to the family of the disk imaging and cloning tools. Thus it takes as input an archive containing the operating system to deploy, called an environment, and copies it on Inria the target nodes. As a consequence, Kadeploy3 does not install an operating system following a classical installation procedure and the user has to provide an archive of the environment (as a tarball, for Linux environments).

As shown in figure 1, a typical deployment with Kadeploy3 is composed of three major steps, called macro steps.

1. Minimal environment setup: the nodes reboot into a trusted minimal environment that contains all the tools required for the deployment (partitioning tools, archive management, ...) and the required partitioning is performed.

2. Environment installation: the environment is broadcast to all the nodes and extracted on the disks. Some post-installations operations can also be performed.

3.

Reboot on the deployed environment.

Each macro step can be executed via several different mechanisms to optimize the deployment process depending upon required parameters and the specific infrastructure. For instance, the Reboot on the deployed environment step can perform a traditional reboot or it might instead rely on a call to kexec1 for a shorter reboot.

Reconfiguring a set of nodes involves several low-level operations that can lead to failures for various reasons, e.g., temporary loss of network connectivity, reboot longer than planned, etc. Kadeploy3 is designed to identify these failures as quickly as possible and improve deployment reliability by providing a macro step replay mechanism on the nodes of interest. To illustrate that, let's consider the last deployment macro step that aims at rebooting on the deployed environment. Kadeploy3 implements, among others, the following strategies:

1. directly load the kernel inside the deployed environment thanks to kexec; 2. perform a hard reboot using an out-of-band management hardware without checking the state of node.

Thus it is possible to describe strategies such as: try to launch the first strategy; then if some nodes fail, try to launch the second strategy two time if required.

Interaction with the Ecosystem

Kadeploy3 does not directly take control of the nodes since it would require some specific and uncommon hardware support. Instead, it uses common network boot capabilities based on the PXE protocol [START_REF]Preboot Execution Environment (PXE) Specification[END_REF]. This works as follows:

1. at boot time, the network device of the node makes a DHCP query;

2. a DHCP server responds to the node with the address of the server containing the PXE profile (i.e., the information describing how the node is supposed to boot);

3. the node fetches the PXE profile from the server and performs the required operations.

Depending upon the profile, some operations may require retrieval of more files, such as a kernel.

Using such a mechanism, combined to the capability to dynamically update the PXE profiles of the nodes and with the capability to reboot the nodes in a reliable way (thanks to BMC, RSA or PDU capabilities for instance), it is possible to take the control of the nodes and to specify what they are booting.

Kadeploy

DHCP TFTP/HTTP Compute nodes

(1) Kadeploy writes PXE profiles on the TFTP or HTTP server

(2) Kadeploy triggers the reboot of compute nodes using SSH, IPMI or a manageable PDU

(3) Nodes get their configuration using DHCP (4) Nodes retrieve their PXE profile using TFTP Figure 2: Interactions between Kadeploy and its ecosystem

Figure 2 shows the interaction between Kadeploy3, the infrastructure services and the cluster nodes.

The Kadeploy3 software suite

Kadeploy3 is packaged with a set of complementary tools that are briefly described in this section.

Management of images

the Kaenv tool enables users and administrators to manage a catalog of deployment images, either shared between users or private to one user.

Rights management

Karights is used to define deployment permissions for users. It also provides the glue to integrate Kadeploy with a batch scheduler, making it possible to allow a given user to deploy a set of nodes for the duration of his job on the cluster.

Statistics collection

deployment statistics (durations, success/failures) are collected continuously, and available through the Kastat tool. This data can be leveraged by system administrators to identify nodes with hardware issues.

Frontends to low-level tools Tools such as Kareboot, Kaconsole and Kapower act as frontends to lower-level tools (such as those based on IPMI [START_REF]Intelligent Platform Management Interface (IPMI) Specification[END_REF] and integrate with the Kadeploy rights management system, to allow users to reboot, power-off/on, and access the remote serial console of nodes.

Inria 3 Design Principles

Software Architecture

We detail here several aspects of the Kadeploy3 architecture and the reasons behind our choices.

Client/Server Architecture

Kadeploy3 implements a client/server architecture. The majority of the deployment code is located on a server that requires write access to the PXE profile repository. All tools presented in section 2.3 can be used either using a lightweight client or using an RPC API. A typical installation would use one Kadeploy server for a set of clusters that are reachable on the same local network. In our terminology, a cluster is a set of nodes with identical characteristics (for performance concerns) located in the same area (typically the same room where the latency between the nodes is very low). When using one Kadeploy server to manage several clusters (what we call a site), the latency between the server and the nodes is supposed to be quite low also since several infrastructure services are shared (e.g., TFTP server for PXE boot, database, etc). In this case the clusters are supposed to be inside the same building. This design has several benefits:

• Support for concurrent deployments is one objective of Kadeploy3. Indeed, in the Grid'5000 context, several users can easily deploy nodes at the same time. Having a global view of all deployments allows certain optimizations such as simplified database access (required for rights management, environment management and some logging operations), support for an environment cache on the server, and support for mastering some concurrent operations that would hurt the infrastructure in case of massive execution (e.g., reboots, power operations, etc);

• It is possible, from a single client, to control deployments from multiple servers (typically located at different grid sites) with a single client. This feature is currently used on the Grid'5000 testbed to perform concurrent deployments on several grid sites in a single administrative cycle;

• Since the PXE repository requires root access, the server needs to run Kadeploy tasks as root, but the clients can run as a normal user. This limits potential security issues.

Deployment Process Management

As stated in section 2.1, several mechanisms may be available to carry out each macro step. Kadeploy3 implements a minimal workflow engine that manages the lifecycle of the deployment process.

First, it is possible to specify a predefined mechanism for each macro step in the configuration. Robustness is also supported by telling the system to perform several rounds of a given macro step in the case of failures in a subset of nodes. Furthermore, macro step mechanisms may be combined in different permutations across multiple attempts. This may increase reliability by, e.g., using an optimized but unreliable mechanism in a first round and then using safer but less optimal mechanisms in subsequent rounds to ensure eventual success. The last macro-step of rebooting nodes in a deployed environment illustrates this approach.

In order to accommodate special requirements, complex deployment processes can be altered or completely redefined by users on the command line. Furthermore, the deployment process can be enhanced at any time. This enables users to act like administrators and perform specific operations that are not necessary for a majority of users.

Finally, the Environment installation macro step has the capability to execute post-configuration operations once the environment is copied to node disks. This allows customization of the environment and is often required to assign some specific configuration parameters. Kadeploy3 defines two levels of post-configuration. The first is specified by administrators and is applied in every deployment and the second can be defined by users to tailor their own deployment. More specifically, the deployment process can be augmented at any time by allowing users to add hooks in the workflow engine.

Booting into the deployed environment

Once the environment is copied on the nodes and the post-installation operations are performed, the environment has to be launched. This is done by updating the PXE profile of the nodes followed by a reboot. Since the Grid'5000 context adds the constraint of keeping the master boot record of the nodes unmodified, it is not possible to leverage on a classical boot method.

Kadeploy3 offers two methods to launch an environment, both based on network boot. The first method, called pure PXE boot, consists in fetching the kernel files (vmlinuz, initrd, and possibly an hypervisor) over the network in order to directly boot a node (the environment files are written on the disk). This methods only works with environments based on Linux. Because the deployed environment can vary, the kernel files must be extracted from the environment on the Kadeploy server before being placed in the PXE repository for a future fetch. To help the extraction, the environment creator must specify in the environment description, the paths to the necessary kernel files. Although a cache mechanism can be used to reduce the burden of repetitive extraction when the same environment is deployed, PXE boot remains heavy-handed. Furthermore, the kernel files (several MBs) have to be fetched, over TFTP or HTTP (in the best case), by all deployed nodes, which contributes to network congestion. These limitations make this method suitable only for uncommon situations, e.g., when the hardware is not compliant with the advanced Syslinux [START_REF]The Syslinux Project[END_REF] features detailed in the rest of this section.

The second method, called chainload boot, uses the Syslinux chain.c32 comboot to boot a partition directly on a node. In this case, the PXE profile contains a reference to chain.c32 and the number of the partition from which to chainload. At boot time, after the PXE profile fetch, the node fetches chain.c32 and boots directly off the specified partition. This method assumes that a bootloader is installed in the given partition. Here, we have two situations:

• the deployed environment is based on Linux. According to the paths specified in the environment description, Kadeploy3 generates a Grub2 configuration and installs it on the target partition;

• the deployed environment is not based on Linux. In this case, the environment is contained within a raw partition image that already embeds a bootloader. The image is written directly to the target partition on the node.

Reliability of Reboot and Power Operations

Since reboot and power operations are essential to control of cluster nodes, and ultimately the entire deployment process itself, they must behave correctly and reliably. Several methods can be used to reboot a nodes:

1. soft reboot: direct execution of the reboot command;

2. hard reboot: via the reboot capability of out-of-band management hardware with protocols such as IPMI. Various kinds of reboot can be executed: reset, power cycle, etc; Inria 3. very hard reboot: use the power management capability of the power distribution unit (PDU).

Obviously it is better to use a method that leverages available hardware parts. Performing a reboot is the best solution with regards to speed and cleanliness. But it may not be an option if the target node is unreachable via in-band methods such as ssh (e.g., the node is already down, the OS has crashed, an unfriendly operating system is installed, etc). In this scenario, we would use IPMI-like features if available. Also, it might be better for speed to perform a reset rather than a power cycle since it bypasses the power on self test, but sometimes this is not sufficient. Finally, if onboard management hardware is unreachable, we may be required to use the capabilities of a remotely manageable PDU. Kadeploy3 provides administrators with a way to specify several levels of commands in order to perform escalation if required. This allows them to perform highly reliable deployments if the clusters have the appropriate hardware. Advanced scripts that deal with multiple reboot methods can also be used to improve flexibility and reliability. Unfortunately, depending on the methods chosen, reboot escalation comes at a cost. Thus a balance must be struck between desired reliability and the time to deployment. Typically escalation operates by first performing a soft reboot. In case of failure on some nodes, a hard reboot is performed and a very hard reboot if necessary.

Implementing a generic command escalation feature can be a bit difficult. Actually, some commands might involve several nodes, e.g. those attached to the same PDU. In this case, performing a PDU power-off can shutdown several nodes. Kadeploy3 allows one to specify groups of nodes in relation to a given command level. These groups can be used for instance to describe the nodes plugged into the same PDU. When a deployment involves some nodes that require such an operation, it is only performed on the nodes that do not belong to any group or on the nodes whose entire group is involved in the deployment.

Configuration

A Kadeploy server is supposed to manage several clusters in the same LAN. Because different clusters have different hardware specifications (e.g. NICs, hard-drives, out-of-band management hardware, etc), they have to be managed independently from the deployment point of view.

Configuring Kadeploy3 on the server side consists in filling four kinds of YAML files:

1. a common configuration file defines general parameters of a Kadeploy server (e.g., the access to the database for rights and environments management, the windows sizes for the reboot commands, etc).

2. a global file defines the different clusters managed by a server as well as the nodes (hostnames and IPs) included in each cluster.

3. as much specific configuration files as the number of defined clusters. Each cluster configuration file defines the specific configuration elements peculiar to a cluster (e.g., the minimal environment and its parameters, the reboot/power commands, the reboot timeouts, or the definition of the deployment workflow composed of the different macro steps).

4. for specific requirements, it is possible to define specific reboot or power commands for some nodes. This specific configuration overloads the commands defined into the cluster configuration files and avoid the creation of unnecessary Kadeploy clusters for some exceptions.

On the client side, it is only necessary to specify the location of the server. If multiple servers are defined into the client configuration file, Kadeploy3 also offers a facility to perform deployment on multiple servers in a single administrative cycle.

Key Features for Scalability

Parallel commands

The deployment workflow contains several operations that reduce to executing a command on a large set of nodes. The exit status of the command returns to the deployment process the subset of nodes for which the command was executed correctly.

Thanks to SSH, one can execute commands remotely and retrieve their outputs (stdout, stderr, exit status, etc). Launching SSH commands on a large number of nodes in sequence does not scale at all. Furthermore, launching all commands simultaneously can impose an extreme load on the client and saturate all of its file descriptors.

Several tools have been built to overcome these limitations. For instance, Pdsh [START_REF]Parallel Distributed Shell[END_REF] and ClusterShell [2] are designed to execute SSH commands on many nodes in parallel. Both tools use windowed execution to limit the number of concurrent SSH commands and both also allow retrieval of command outputs on each node.

We choose to leverage TakTuk [START_REF] Claudel | adaptive deployment of remote executions[END_REF] as our mechanism for parallel command execution and reporting. TakTuk is based upon a model of hierarchical connection. This allows it to distribute the execution load on all the nodes in a tree and to perform commands with low latency. Using such a hierarchical mechanism would normally require the tool to be installed on all nodes. Fortunately, TakTuk includes a convenient auto-propagation feature that assures the tool's existence on all necessary nodes. The tool also uses an adaptive work-stealing algorithm to improve performance, even on heterogeneous infrastructures.

File broadcast

The broadcast of the system image to all nodes is a critical part of the deployment. In cluster environments where the most important network for applications is using Infiniband or Myrinet, the Ethernet network is often composed of a hierarchy of switches (e.g.; one switch per rack) that is hard to leverage for a high-performance broadcast. File distribution to a large number of nodes via any sequential push or pull method is not scalable. Kadeploy3 provides system administrators with three scalable file distribution approaches during the Environment installation macro step to minimize deployment time.

With tree-based broadcast, a file is sent from the server to a subset of nodes, which in turn send the file to other subsets until all the nodes have received. The size of the subsets, called tree arity, can be specified in the configuration. A large arity can reduce the latency to reach all nodes but transfer times might increase because global bandwidth is equal to the bandwidth of a network link divided by the tree arity. The opposite effect occurs when the arity is small. In general, this broadcast method does not maximize bandwidth and should be used primarily for the distribution of small files. This method is also inefficient when used in hierarchical networks. We implement tree-based broadcast using TakTuk.

Chain-based broadcast facilitates the transfer of files with high bandwidth. In practice, this broadcast method is a special case of tree-based broadcast with an arity of 1. A classical chainbased broadcast suffers from the establishment time of the chain in large scale clusters. Indeed, since each node must connect to the next node in the chain (usually via SSH), a sequential initialization would drastically increase the entire broadcast period. Thus we perform the initialization of the chain with a tree-based parallel command. This kind of broadcast is near-optimal in a Inria images server Figure 3: Topology-aware chained broadcast. Data is pipelined between all nodes. When correctly ordered, this ensures that inter-switches links are only used once in both directions. hierarchical network if the chain is well ordered since, as shown in Figure 3, all the full-duplex network links can be saturated in both directions, and the performance bottleneck becomes the backplane bandwidth of the network switches. For this method, we implement chain initialization using TakTuk and perform transfers using other custom mechanisms.

BitTorrent-based broadcast allows us to send files at large scale without making any assumptions about the quality of the network. Furthermore, BitTorrent is able to efficiently handle churn, an important property in large scale systems like petascale and future exascale clusters. Currently, our experiments show that there are two scenarios in which the performance of this broadcast method is inferior to the other methods. The first pathological case is one in which we are broadcasting on a small-scale cluster with a high-speed network, and the second is one in which we are broadcasting small files. In both cases, BitTorrent exhibits high latency and the overhead of the protocol dominates the time to broadcast. Also, as shown in Figure 4, the large number of established connections between nodes induced by the protocol can lead to bottlenecks (in red) depending on the network topology.

Windowed operations

Our experience in the development of a cluster deployment tool shows that several low-level operations must be performed carefully. For instance, it can be disastrous to reboot a huge number of nodes at the same time in the same technical room since it can generate electric hazard. It can also flood the network with DHCP requests and accidentally lead to multiple boot failures.

Kadeploy3 addresses this problem by supporting the definition of windows for multiple operations like reboots, power operations or nodes check (this leads to scan some ports).

Let's take the reboot example to illustrate that. According to the infrastructure capabilities (e.g., network, service nodes, etc) the administrator of a cluster estimates that no more than 100 nodes should be rebooted at once, and a grace period of 10 seconds should be observed after having rebooted 100 nodes to reboot more nodes. Imagine that you have 400 nodes to reboot. In this configuration, Kadeploy3 reboots 100 nodes, waits 10 seconds, reboots 100 nodes, and so images server on until all the nodes have been rebooted.

To be effective in a context where concurrent deployments can occur, windows are applied globally on a Kadeploy3 server.

Evaluation

In this section, we describe and evaluate Kadeploy3 along several axes: its source code, its current usage, some benchmarks on physical infrastructures, and scalability benchmarks on virtualized infrastructures.

Software

Kadeploy3 is developed in Ruby and has about 10,000 SLOC. Source code is available under a free license, as well as Debian and Red Hat packages. As other tool developers have discovered (e.g. Puppet, Chef, etc), Ruby is well-suited to the objectives of this type of project thanks to its high expressiveness and its meta-programming features. Furthermore, the core functionality of Kadeploy3 has no special performance requirements except for parallel command execution and file broadcast, which are easily delegated to other tools. Thus we favor the simplicity of development and a high maintenance potential.

Qualitative Elements

Kadeploy3 has been used intensively on the Grid'5000 testbed since the end of 2009. In that time, approximately 620 different users have performed 117,000 deployments. On average each deployment has involved 10.3 nodes. The largest deployment involved 496 nodes (in multisite mode). To our knowledge, the deployed operating systems are mostly based on Linux (all flavors) with a sprinkling of FreeBSD. Although the Grid'5000 use case does not exercise all the goals targeted by Kadeploy3 (e.g., scalability), it shows the tool's adequacy with regard to most characteristics, such as reliability. Kadeploy3 is also used in more straightforward contexts, for administration tasks on production clusters in several french research institutes at least. In this case, several features are not used but scalability and reliability contributes to ease some administration tasks and to minimize the downtime.

Validation in Real Infrastructure

Deployment of a Regular Cluster

In this section, we provide the reader with an idea of the time required to deploy regular clusters. We perform a set of deployments on 130 nodes of the graphene cluster from the Nancy Grid'5000 site. We have launched 5 deployments with a 137 MB environment (called min deployments) and 5 deployments with a 1429 MB environment (called big deployments).

In those deployments, all the nodes were deployed correctly. Actually some temporary failures occurs (between 0 to 4 nodes each time), but the robustness mechanisms of Kadeploy3 where used to ensure the full deployment success. In particular, we add a possible retry on the first macro step.

Figure 5 details some measures made during the deployments. We can see that deploying 130 nodes in one shot takes between 9 to 12 minutes, depending on the environment size. The deployment time is mainly spent in two steps: the wait of rebooted nodes (in the 1st and in the 3rd macro step and the broadcast file (in the 2nd macro step). The 1st and the 3rd macro steps are of the same kind for min and big deployments, the difference is due to the small sampling. Indeed rebooting 130 nodes can take a variable time according to several uncontrolled parameters in the infrastructure.

To ensure reliability of the deployments we chose to use a non-aggressive configuration where large timeouts have been set in order to give slow nodes a chance to appear after a reboot and also to enable retries. Faster deployment times would have been reached with a more aggressive configuration, at the price of a few node loss. To be rigorous, we have to precise that the results shown in figure 5, excepted for the average deployment time, do not take into account the time spent for nodes that had needed a second try. Actually, the time spent in the retry is partially covered by the main deployment because rebooting just a few nodes is faster than rebooting a large set and other operations like file broadcast are also faster on a small node set. That is why adding the average time spent in the 3 macro steps give a smaller value than the average deployment time.

Scalability Validation in Virtualized Infrastructure

Validating scalability on large physical infrastructures can become complex because it requires privileged rights on many components (e.g., access to management cards, modification of PXE profiles, etc). Thus we chose to build our own large-scale virtual testbed on Grid'5000, leveraging important features such as link-layer isolation, and Kadeploy3 of course.

Bordeaux Grenoble

Figure 6 shows the network topology of the Grid'5000 platform. Our testbed comprised four network-isolated sites (red nodes and associated links). We had access to 635 nodes upon which we launched a variable number of KVM virtual machines, depending on the node's capabilities. In total, 3,999 virtual machines were launched and participated in a single virtual network. Building the testbed was tricky for several reasons like the high latency between two sites that affects the infrastructure services. Those reasons are more deeply explained in section 5.3. Thanks to the versatility of the Grid'5000 platform, we were able to construct the testbed without any privileged user rights and without suspending access to the platform by other legitimate users.

Once the testbed was launched, we were able to perform deployments within a single cluster of 3,999 nodes. During the largest run, a 430 MB environment was installed on 3,838 virtual machines in less than an hour. 161 virtual nodes were lost due to network or KVM issues. A significant amount of time was also wasted because of the high latency between sites (10-20 ms), which affected some infrastructure services like DHCP and the PXE protocol.

Here are few statistics of the time spent in the time-greediest steps: the first reboot took 11

Inria minutes, the broadcast of the image archive took 15 minutes, the second reboot took 7 minutes. We should also highlight the fact that this experiment was designed a non-friendly way for Kadeploy. Indeed, Kadeploy is designed as a cluster oriented tool and in this experiment, we described our resources as resources of the same cluster while in reality the physical machines were distributed over four sites separated by hundreds of kilometers. This was unfavorable to the parallel commands execution mechanism that works effectively with small latency differences between the nodes involved in a deployment. This experiment demonstrates the effectiveness of the Kadeploy3 design in terms of scalability and reliability. In particular, hierarchical parallel commands and chain-based broadcast are wellsuited to deployments at this scale. With regard to reliability, roughly 96% of the nodes were deployed successfully. Deployment to other nodes failed due to infrastructure issues but a large number of those (e.g., the ones not affected by KVM problems) could have been recovered using a fallback approach, at the cost of a longer deployment time.

We are confident that Kadeploy3 will scale to larger infrastructures and will be a good choice for node reconfiguration on a variety of current and future clusters.

Lessons Learned

In this section we highlight three technical points that gave us a bit of trouble in the design and testing of Kadeploy3. The goal is to allow other administrators to save time with the lessons we have learned.

Dealing with Unreliable Reboot Mechanisms

Since our node control mechanism relies heavily on remote reboot, it is essential to ensure that it is performed correctly. Unfortunately, we learned that some of these mechanisms are not reliable. Much of the problem can be attributed to varying and sometimes incorrect vendor implementations of IPMI and other protocols. This leads to situations in which the management card is not able to reboot a node that is in an unexpected state or otherwise unreachable. Furthermore, IPMI is sometimes implemented on the same Ethernet port that the node uses for its own traffic. Traffic competition can lead to unresponsive management cards.

In section 3.1.4, we presented the escalation command mechanism to increase the reliability of the reboot and power control operations. This mechanism depends upon the return status of the executed commands to decide if escalation is required on some nodes. If the return status of the executed commands is not correctly reported, it can lead to unreliable reboots. We found that instead of using raw IPMI commands (or their equivalent for other protocols) we could improve reliability by wrapping the commands in ad-hoc scripts that test several preconditions and postconditions.

First Steps of the Boot

Still related to the node control mechanism, we address the first steps of the boot. As stated in section 2.2, just after the DHCP step, nodes must retrieve their PXE profile and possibly some associated files. To achieve this, a typical DHCP configuration would instruct the nodes to retrieve pxelinux.0 (from the Syslinux project [START_REF]The Syslinux Project[END_REF]). Then the nodes are able to continue retrieving other necessary files. All transfers are performed over TFTP, which is not reliable and not scalable, and which can lead to boot issues.

We found that one way in which to increase reliability and speed is to use gpxelinux.0 (also from the Syslinux project) instead of pxelinux.0. Even though the retrieval of gpxelinux.0 still has to be done over TFTP, other retrievals can be made over higher level protocols such as HTTP. This greatly improves scalability and reliability since, e.g., HTTP servers can deal with high numbers of static requests, as opposed to the horrible performance exhibited by TFTP servers under high load.

We also found that PXE implementations in many BIOSes are often poor. When possible, we highly recommend that network card firmware be updated to use something such as iPXE [START_REF]iPXE -Open source boot firmware[END_REF]. This is an open-source boot firmware that enhances a classical PXE implementation with features such as booting directly from an HTTP server, from iSCSI, or from an Infiniband network. This approach completely bypasses retrievals via TFTP and highly increases the speed and reliability of the boot stage.

Scalability Testing

Building scalable tools always brings the question of the scalability evaluation. Tools like Kade-ploy3 require a complex infrastructure to be tested and cannot use methods like simulation. As said in section 4.4, we have built a tool that allows the deployment of a large-scale infrastructure thanks to virtualization and to advanced features of Grid'5000. We would like to underline some issues we encountered.

The first problem when dealing with a large number of nodes was related to the poor reliability and scalability properties of the TFTP protocol. From dozen of simultaneous requests, TFTP server was quickly overloaded, resulting in a denial-of-service (DoS) that leads to multiple boot failures. To solve this problem, we have configured virtual machines with an iPXE compliant NIC in order to be able to use HTTP protocol instead of TFTP for PXE profiles and kernel files fetching. Using HTTP allows to boot hundreds of nodes at the same time. Furthermore, thanks to some HTTP server tunings, we were able to serve twice as much requests, with an increased bandwidth.

Relying on a more scalable protocol was useful to improve the performance but it was not enough to get rid of DoS issues. A service accessed from thousands of nodes at the same time can quickly become overloaded, especially if communication sockets are not quickly closed (e.g., when broadcasting large files). Thus we had to replicate the infrastructure services. To enable PXE profiles and kernel files distribution from multiple HTTP servers, we tuned the DNS server to split the requests over several HTTP servers. Because the testbed is distributed over several Grid'5000 sites, the iPXE HTTP implementation also suffers from the high latency between the grid sites. Thus we had to replicate the HTTP servers on every site, and thanks to another DNS tuning, the nodes of a given site were only served by local HTTP servers.

We also had to deal with ARP tables overflow. Since some services (e.g., DHCP) were accessed by every nodes, the ARP tables of those servers were quickly saturated. This issue has been solved by increasing the ARP tables on the servers thanks to on-the-fly Linux kernel tuning facilities.

Related Works

This section present some tools that can be compared to Kadeploy3. We only present open-source solutions since we are not able to freely study the commercial ones.

xCAT [START_REF]xCAT: Extreme Cloud Administration Toolkit[END_REF] aims at doing operating system provisioning on physical or virtual machines. It supports scripted install, stateless deployment and cloning deployment. Concerning physical machines, it targets RPM based Linux distributions (RHEL, CentOS, Fedora), IBM AIX and some Windows versions. Even if it can be used more or less easily on any hardware, xCAT is strongly designed to run on IBM one. In this case, it offers a set of features to quickly set Inria up and control the management node services (DNS, DHCP, TFTP, HTTP). According to the developers, a single xCAT instance can scale up to 128 nodes clusters. Beyond this, several xCAT instances can be deployed hierarchically to scale far away. To perform broadcast operations, xCAT relies on hierarchical HTTP transfers or iSCSI. Comparing to Kadeploy3, it offers extra services like scripted install and stateless deployment. However it is less versatile concerning the operating systems and the supported hardware. It also does not allow to perform large scale deployments in a single shot since it does not leverage on scalable tools for parallel commands and file broadcast like Kadeploy3 does. Finally, xCAT only targets administration tasks and does not allow user deployments.

Clonezilla [1] is a cloning tool that supports almost any operating system since it is compliant with a lot of file systems. For unsupported file system, Clonezilla can do sector-to-sector copy using dd, like Kadeploy3. Clonezilla is proposed in two versions: Clonezilla Live and Clonezilla Server Edition. Since Clonezilla Live is dedicated to single machine backup, we focus on Clonezilla Server Edition. It relies on DRBL [START_REF]Diskless Remote Boot in Linux[END_REF] that provides a diskless environment for cluster nodes. Clonezilla has no dependency to any specific hardware and can use either unicast or multicast transfer for environment broadcast. However, it is not designed for large scale clusters but instead infrastructures like classrooms.

SystemImager [START_REF]SystemImager[END_REF] aims at replicating a golden node on a cluster. It can either perform bare metal installation of cluster nodes or propagate updates from the golden node to the cluster nodes using rsync. In the case of bare metal installation, the environment broadcast can use rsync, multicast, and BitTorrent for a better scalability. Only file broadcast takes scalability concerns into account, thus only a few hundred of nodes can be deployed in one shot. Compared to Kadeploy3, SystemImager is less versatile since it targets only the administration purpose and only supports Linux based operating systems. SystemImager is widely used and is a keystone for higher level tools like Oscar [START_REF]Open Source Cluster Application Resources[END_REF].

Other tools like Cobbler [3] or FAI [START_REF]Fully Automatic Installation (FAI)[END_REF] aims at installing a Linux operating system on a cluster following the regular system installation process. These tools are not suitable for large scale clusters and only focus on Linux.

Conclusion and Future Works

This paper presents Kadeploy3, an efficient, reliable and scalable tool that aims at performing operating system provisioning on HPC clusters.

Kadeploy3 has been designed in the context of the Grid'5000 experimental testbed where the goal was to provide grid users with a way to fully reconfigure the grid nodes as they see fit during their experiments.

Kadeploy3 is also well suited for classical administration tasks. Indeed, the reliability and the scalability properties of Kadeploy3 allow to safely perform operating system provisioning on large scale clusters without inducing long downtimes like it is the case with some unreliable and poorly scalable tools of the state of the art.

Because it is used since 2009 on the Grid'5000 context by several hundreds of users and because it is also used for administrative tasks on production clusters, Kadeploy3 has proven to be useable, efficient, and reliable for day-to-day use.

We have also demonstrated the scalability of Kadeploy3 by presenting experiments where we have performed successfully a deployment on a petascale cluster comprising 2000 nodes, and where we also have performed deployments into a virtualized testbed comprising about 4000 nodes.

Future works will be dedicated to the improvement of the file broadcast techniques, in partic-ular when the network topology is complex, and to the improvement of the hierarchical parallel command tool in the situation where the tree must not be randomly created, for instance when latency between the nodes is heterogeneous.

Figure 4 :

 4 Figure 4: Bittorrent broadcast. The random selection of peers leads to saturation of the interswitches links.

Figure 5 :

 5 Figure 5: Deployment times (seconds)

Figure 6 :

 6 Figure 6: Grid'5000 network topology

RR n°8002

http://www.ibm.com/developerworks/linux/library/l-kexec/index.html RR n°8002

rue du Jardin Botanique CS20101 54603 Villers-lès-Nancy Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgements

Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the Inria ALADDIN development action with support from CNRS, RE-NATER and several Universities as well as other funding bodies (see https://www.grid5000. fr). Special acknowledgements to Olivier Richard for his contribution to the previous versions of Kadeploy and to several ideas presented in this paper, and to Marc Chiarini for his help at improving the paper.

Availability

Kadeploy3 is freely available under the Open Source CeCILL v2 license on http://kadeploy3.gforge.inria.fr