P Bianchi
email: pascal.bianchi@supelec.fr

M Debbah

J Najim
email: najim@enst.fr

Asymptotic Independence in the Spectrum of the Gaussian Unitary Ensemble

Consider a n × n matrix from the Gaussian Unitary Ensemble (GUE). Given a finite collection of bounded disjoint real Borel sets (∆ i,n , 1 ≤ i ≤ p), properly rescaled, and eventually included in any neighbourhood of the support of Wigner's semi-circle law, we prove that the related counting measures (N n (∆ i,n ), 1 ≤ i ≤ p), where N n (∆) represents the number of eigenvalues within ∆, are asymptotically independent as the size n goes to infinity, p being fixed.

As a consequence, we prove that the largest and smallest eigenvalues, properly centered and rescaled, are asymptotically independent ; we finally describe the fluctuations of the condition number of a matrix from the GUE.

I. INTRODUCTION AND MAIN RESULT

Denote by H n the set of n × n random Hermitian matrices endowed with the probability measure

P n (d M) := Z -1 n exp - n 2 Tr M 2 d M ,
where Z n is the normalization constant and where

d M = n i=1 d M ii 1≤i<j≤n R [d M ij ] 1≤i<j≤n I [d M ij ]
for every M = (M ij ) 1≤i,j≤n in H n (R [z] being the real part of z ∈ C and I [z] its imaginary part). This set is known as the Gaussian Unitary Ensemble (GUE) and corresponds to the case where a n × n hermitian matrix M has independent, complex, zero mean, Gaussian distributed entries with variance E|M ij | 2 = 1 n above the diagonal while the diagonal entries are independent real Gaussian with the same variance. Much is known about the spectrum of M. Denote by λ

(n) 1 , λ (n) 2 , • • • , λ (n)
n the eigenvalues of M (all distinct with probability one), then : -The joint probability density function of the (unordered) eigenvalues (λ

(n) 1 , • • • , λ (n)
n ) is given by :

p n (x 1 , • • • , x n ) = C n e - P x 2 i 2 j<k |x j -x k | 2 ,
where C n is the normalization constant.

- [START_REF] Wigner | On the distribution of the roots of certain symmetric matrices[END_REF] The empirical distribution of the eigenvalues 1 n n i=1 δ λ (n) i (δ x stands for the Dirac measure at point x) converges toward Wigner's semi-circle law whose density is :

1 2π 1 (-2,2) (x) 4 -x 2 .
- [START_REF] Bai | Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix[END_REF] The largest eigenvalue λ -2), the right-end (resp. left-end) point of the support of the semi-circle law as n → ∞.

F + GU E (s) = exp - ∞ s (x -s)q 2 (x) dx ,
where q solves the Painlevé II differential equation :

q ′′ (x) = xq(x) + 2q 3 (x) , q(x) ∼ Ai(x) as x → ∞

and Ai(x) denotes the Airy function. In particular, F + GU E is continuous. Similarly, n

2 3 λ (n) min + 2 D -→ F - GU E
where F - GU E (s) = 1 -F + GU E (-s) . If ∆ is a Borel set in R, denote by :

N n (∆) = # λ (n) i ∈ ∆ ,
i.e. the number of eigenvalues in the set ∆. The following theorem is the main result of the article.

Theorem 1: Let M be a n × n matrix from the GUE with eigenvalues (λ

(n) 1 , • • • , λ (n)
n ). Let p ≥ 2 be an integer and let (µ 1 , • • • , µ p ) ∈ R p be such that -2 = µ 1 < µ 2 < • • • < µ p = 2. Denote by ∆ = (∆ 1 , • • • , ∆ p ) a collection of p bounded Borel sets in R and consider ∆ n = (∆ 1,n , • • • , ∆ p,n ) defined by the following scalings :

(edge) ∆ 1,n := -2 + ∆ 1 n 2/3 , ∆ p,n := 2 + ∆ p n 2/3 , (bulke) ∆ i,n := µ i + ∆ i n , 2 ≤ i ≤ p -1 .
Let (ℓ 1 , • • • , ℓ p ) ∈ N p , then :

lim n→∞ P (N n (∆ 1,n ) = ℓ 1 , • • • , N n (∆ p,n ) = ℓ p ) - p k=1 P (N n (∆ k,n ) = ℓ k ) = 0 .
Proof of Theorem 1 is postponed to Sections III. In Section II, we state and prove the asymptotic independence of the random variables n

Acknowlegment

The authors are grateful to Walid Hachem for fruitful discussions and many helpful remarks ; the authors wish also to thank Eric Amar for useful references related to complex analysis.

II. ASYMPTOTIC INDEPENDENCE OF EXTREME EIGENVALUES

In this section, we prove that the random variables n

2 3 λ (n) max -2 and n 2 3 λ (n)
min + 2 are asymptotically independent as the size of matrix M goes to infinity. We then apply this result to describe the fluctuations of

λ (n) max λ (n) min
. In the sequel, we drop the upperscript (n) to lighten the notations.

A. Asymptotic independence

Specifying p = 2, µ 1 = -2, µ 2 = 2 and getting rid of the boundedness condition over ∆ 1 and ∆ 2 in Theorem 1 yields the following :

Corollary 1: Let M be a n × n matrix from the GUE. Denote by λ min and λ max its smallest and largest eigenvalues, then the following holds true :

P n 2 3 (λ min + 2) < x , n 2 3 (λ max -2) < y -P n 2 3 (λ min + 2) < x P n 2 3 (λ max -2) < y ---→ n→∞ 0 . Otherwise stated, n 2 3 (λ min + 2), n 2 3 (λ max -2) D ---→ n→∞ (λ -, λ + ),
where λ -and λ + are independent random variables with distribution functions F - GU E and F + GU E . Proof: Denote by (λ (i) ) the ordered eigenvalues of M :

λ min = λ (1) ≤ λ (2) ≤ • • • ≤ λ (n) = λ max . Let (x, y) ∈ R 2 and take α ≥ max(|x|, |y|). Let ∆ 1 = (-α, x) and ∆ 2 = (y, α) so that ∆ 1,n = -2 - α n 2 3 , -2 + x n 2 3
and

∆ 2,n = 2 + y n 2 3 , 2 + α n 2 3
.

We have :

{N (∆ 1,n ) = 0} = n 2 3 (λ min + 2) > x ∪ ∃i ∈ {1, • • • , n}; λ (i) ≤ -2 - α n 2 3 , λ (i+1) ≥ -2 + x n 2 3 := n 2 3 (λ min + 2) > x ∪ { Π(-α, x) } , (1)
with the convention that if i = n, the condition simply becomes λ max ≤ -2αn -2 3 . Note that both sets in the right-hand side of the equation are disjoint. Similarly :

{N (∆ 2,n ) = 0} = n 2 3 (λ max -2) < y ∪ ∃i ∈ {1, • • • , n}; λ (i-1) ≤ 2 + y n 2 3 , λ (i) ≥ 2 + α n 2 3 , := n 2 3 (λ max -2) < y ∪ { Π(y, α) } , (2)
with the convention that if i = 1, the condition simply becomes λ min ≥ 2 + αn -2 3 . Gathering the two previous equalities enables to write {N (∆ 1,n ) = 0, N (∆ 2,n ) = 0} as the following union of disjoint events :

{N (∆ 1,n ) = 0 , N (∆ 2,n ) = 0} = Π(-α, x) , n 2 3 (λ max -2) < y ∪ Π(-α, x) , Π(y, α) ∪ n 2 3 (λ min + 2) > x , Π(y, α) ∪ n 2 3 (λ min + 2) > x , n 2 3 (λ max -2) < y . (3)
Define :

u n := P n 2 3 (λ min + 2) > x , n 2 3 (λ max -2) < y -P n 2 3 (λ min + 2) > x P n 2 3 (λ max -2) < y = P {N (∆ 1,n ) = 0 , N (∆ 2,n ) = 0} -P {N (∆ 1,n ) = 0} P {N (∆ 2,n ) = 0} + ǫ n (α) , (4)
where, by equations (1), ( 2) and (3),

ǫ n (α) := -P Π(-α, x) , n 2 3 (λ max -2) < y -P Π(-α, x) , Π(y, α) -P n 2 3 (λ min + 2) > x , Π(y, α) + P {N (∆ 1,n ) = 0} P Π(y, α) + P {Π(-α, x)} P {N (∆ 2,n ) = 0} -P {Π(-α, x)} P Π(y, α) .
Using the triangular inequality, we obtain :

|ǫ n (α)| ≤ 6 max P {Π(-α, x)} , P Π(y, α) As { Π(-α, x) } ⊂ {n 2 3 (λ min + 2) < -α}, we have P{Π(-α, x) } ≤ P{n 2 3 (λ min + 2) < -α} ---→ n→∞ F - GU E (-α) ---→ α→∞ 0 .
We can apply the same arguments to { Π(y, α) } ⊂ {n 2 3 (λ max -2) > α}. We thus obtain :

lim α→∞ lim sup n→∞ |ǫ n (α)| = 0 . (5)
The difference

P {N (∆ 1,n ) = 0 , N (∆ 2,n ) = 0}-P {N (∆ 1,n ) = 0} P {N (∆ 2,n ) = 0}
in the righthand side of (4) converges to zero as n → ∞ by Theorem 1. We therefore obtain :

lim sup n→∞ |u n | = lim sup n→∞ |ǫ n (α)| .
The lefthand side of the above equation is a constant w.r.t. α while the second term (whose behaviour for small α is unknown) converges to zero as α → ∞ by [START_REF] Smithies | Integral equations[END_REF]. Thus, lim n→∞ u n = 0. The mere definition of u n together with Tracy and Widom fluctuation results yields :

lim n→∞ P n 2 3 (λ min + 2) > x , n 2 3 (λ max -2) < y = 1 -F - GU E (x) × F + GU E (y) .
This completes the proof of Corollary 1.

B. Application : Fluctuations of the condition number in the GUE

As a simple consequence of Corollary 1, we can easily describe the fluctuations of the condition number λmax λmin . Corollary 2: Let M be a n × n matrix from the GUE. Denote by λ min and λ max its smallest and largest eigenvalues, then :

n 2 3 λ max λ min + 1 D ---→ n→∞ - 1 2 (λ -+ λ + ) ,
where D -→ denotes convergence in distribution, λ -and λ + are independent random variable with respective distribution F - GU E and F + GU E . Proof: The proof is a mere application of Slutsky's lemma (see for instance [START_REF] Van Der | Asymptotic statistics, volume 3 of Cambridge Series in Statistical and Probabilistic Mathematics[END_REF]Lemma 2.8]). Write : Another application of Slutsky's lemma yields the convergence (in distribution) of the right-hand side of (6) to the limit of

n 2 3 λ max λ min + 1 = - 1 2 n 2 3 (λ max -2) + n 2
-1 2 n 2 3 (λ max -2) + n 2 3 (λ min + 2) , that is -1 2 (X + Y
) with X and Y independent and distributed according to F - GU E and F + GU E . Proof of Corollary 2 is completed.

III. PROOF OF THEOREM 1

A. Useful results 1) Kernels:

Let {H k (x)} k≥0 be the classical Hermite polynomials H k (x) := e x 2 -d dx k e -x 2 and consider the function ψ (n) k (x) defined for 0 ≤ k ≤ n -1 by : ψ (n) k (x) := n 2 1 4 e -nx 2 4 (2 k k! √ π) 1 2 H k n 2 x .
Denote by K n (x, y) the following Kernel on R 2 :

K n (x, y) := n-1 k=0 ψ (n) k (x)ψ (n) k (y) (7) = ψ (n) n (x)ψ (n) n-1 (y) -ψ (n) n (y)ψ (n) n-1 (x) x -y (8)
Equation ( 8) is obtained from ( 7) by the Christoffel-Darboux formula. We recall the two well-known asymptotic results Proposition 1: a) Bulk of the spectrum. Let µ ∈ (-2, 2).

∀(x, y) ∈ R 2 , lim n→∞ 1 n K n µ + x n , µ + y n = sin πρ(µ)(x -y) π(x -y) , (9)
where

ρ(µ) = √ 4-µ 2
2π . Furthermore, the convergence ( 9) is uniform on every compact set of R 2 . b) Edge of the spectrum.

∀(x, y) ∈ R 2 , lim n→∞ 1 n 2/3 K n 2 + x n 2/3 , 2 + y n 2/3 = Ai(x)Ai ′ (y) -Ai(y)Ai ′ (x) x -y , (10)
where Ai(x) is the Airy function. Furthermore, the convergence (10) is uniform on every compact set of R 2 . We will need as well the following result on the asymptotic behavior of functions ψ

(n) k . Proposition 2: Let µ ∈ (-2, 2), let k = 0 or k = 1 and denote by K a compact set of R.
a) Bulk of the spectrum. There exists a constant C such that for large n,

sup x∈K ψ (n) n-k µ + x n ≤ C . (11)
b) Edge of the spectrum. There exists a constant C such that for large n,

sup x∈K ψ (n) n-k ±2 ± x n 2/3 ≤ n 1/6 C . ( 12
)
The proof of these results can be found in [START_REF] Pastur | Eigenvalue distribution of random matrices[END_REF]Chapter 7].

2) Determinantal representations, Fredholm determinants:

There are determinantal representations using kernel K n (x, y) for the joint density p n of the eigenvalues (λ

(n) i ; 1 ≤ i ≤ n),
and for its marginals (see for instance [2, Chapter 6] :

p n (x 1 , • • • , x n ) = 1 n! det {K n (x i , x j )} 1≤i,j≤n , (13)
R n-m p n (x 1 , • • • , x n )dx m+1 • • • dx n = (n -m)! n! det {K n (x i , x j )} 1≤i,j≤m (m ≤ n) . ( 14
)
Definition 1: Consider a linear operator S defined for any bounded integrable function f : R → R by

Sf : x → R S(x, y)f (y)dy ,
where S(x, y) is a bounded integrable Kernel on R 2 → R with compact support. The Fredholm determinant D(z) associated with operator S is defined as follows :

det(1 -zS) := 1 + ∞ k=1 (-z) k k! R k det {S(x i , x j )} 1≤i,j≤k dx 1 • • • dx k , (15)
for each z ∈ C, i.e. it is an entire function. Its logarithmic derivative has the simple expression :

D ′ (z) D(z) = - ∞ k=0 T (k + 1)z k , (16)
where

T (k) = R k S(x 1 , x 2 )S(x 2 , x 3 ) • • • S(x k , x 1 ) dx 1 • • • dx k . ( 17
)
For details related to Fredholm determinants, see for instance [START_REF] Smithies | Integral equations[END_REF], [START_REF] Tricomi | Integral equations[END_REF].

The following kernel will be of constant use in the sequel :

S n (x, y; λ, ∆) = p i=1 λ i 1 ∆i (x)K n (x, y), (18)
where

λ = (λ 1 , • • • , λ p ) ∈ R p or λ ∈ C p , depending on the need.
Remark 1: Kernel K n (x, y) is unbounded and one cannot consider its Fredholm determinant without caution. Kernel S n (x, y) is bounded in x since the kernel is zero if x is outside the compact set ∪ p i=1 ∆ i , but a priori unbounded in y. In all the forthcoming computations, one may replace S n with the bounded kernel Sn (x, y) = p i,ℓ=1 λ i 1 ∆i (x)1 ∆ℓ (y)K n (x, y) and get exactly the same results. For notational convenience, we keep on working with S n .

Proposition 3: Let p ≥ 1 be a fixed integer ; let ℓ

= (ℓ 1 , • • • , ℓ p ) ∈ N p and denote by ∆ = (∆ 1 , • • • , ∆ p )
, where every ∆ i is a bounded Borel set. Assume that the ∆ i 's are pairwise disjoint. Then the following identity holds true :

P {N (∆ 1 ) = ℓ 1 , • • • , N (∆ p ) = ℓ p } = 1 ℓ 1 ! • • • ℓ p ! - ∂ ∂λ 1 ℓ1 • • • - ∂ ∂λ p ℓp det (1 -S n (λ, ∆)) λ1=•••=λp=1 , (19)
where S n (λ, ∆) is the operator associated to the kernel defined in (18).

Proof of Proposition 3 is postponed to Appendix A.

3) Useful estimates for kernel S n (x, y; λ, ∆) and its iterations: Consider µ, ∆ and ∆ n as in Theorem 1. Assume moreover that n is large enough so that the Borel sets

(∆ i,n ; 1 ≤ i ≤ p) are pairwise disjoint. For i ∈ {1, • • • , p}, define κ i as κ i = 1 if -2 < µ i < 2 2 3 if µ i = ±2 , (20)
i.e. κ 1 = κ p = 2 3 and κ i = 1 for 1 < i < p. Let λ ∈ C p . With a slight abuse of notation, denote by S n (x, y; λ) the kernel :

S n (x, y; λ) := S n (x, y; λ, ∆ n ) . (21)
For 1 ≤ m, ℓ ≤ p, define :

M m×ℓ,n (Λ) := sup λ∈Λ sup (x,y)∈∆m,n×∆ℓ,n |S n (x, y; λ)| , (22)
where S n (x, y; λ) is given by (21). Proposition 4: Let Λ ⊂ C p be a compact set. There exist two constants R = R(Λ) > 0 and C = C(Λ) > 0, independent from n, such that for n large enough,

M m×m,n (Λ) ≤ R -1 n κm , 1 ≤ m ≤ p M m×ℓ,n (Λ) ≤ Cn 1-κm +κ ℓ 2 , 1 ≤ m, ℓ ≤ p, m = ℓ . ( 23
)
Proposition 4 is proved in Appendix B. Consider the iterated kernel |S n | (k) (x, y; λ) defined by :

|S n | (1) (x, y; λ) = |S n (x, y; λ)| |S n | (k) (x, y; λ) = R k-1 |S n (x, u; λ)| × |S n | (k-1) (u, y; λ) du k ≥ 2 , ( 24
)
where S n (x, y; λ) is given by (21). The next estimates will be stated with λ ∈ C p fixed. Note that |S n | (k) is nonnegative and writes :

R k-1 |S n (x, u 1 ; λ)S n (u 1 , u 2 ; λ) • • • S n (u k-1 , y; λ)|du 1 • • • du k-1 .
As previously, define for 1 ≤ m, ℓ ≤ p :

M (k) m×ℓ,n (λ) := sup (x,y)∈∆m,n×∆ℓ,n |S n | (k) (x, y; λ)
The following estimates hold true : Proposition 5: Consider the compact set Λ = {λ} and the associated constants R = R(λ) and C = C(λ) as given by Prop. 4. Let β > 0 be such that β > R -1 and consider ǫ ∈ (0, 1 3 ). There exists an integer N 0 = N 0 (β, ǫ) such that for every n ≥ N 0 and for every k ≥ 1,

M (k) m×m,n (λ) ≤ β k n κm , 1 ≤ m ≤ p M (k) m×ℓ,n (λ) ≤ Cβ k-1 n (1+ǫ-κm +κ ℓ 2 ) , 1 ≤ m, ℓ ≤ p, m = ℓ . ( 25
)
Proposition 5 is proved in Appendix C.

B. End of proof

Consider µ, ∆ and ∆ n as in Theorem 1. Assume moreover that n is large enough so that the Borel sets (∆ i,n ; 1 ≤ i ≤ p) are pairwise disjoint. As previously, denote S n (x, y; λ) = S n (x, y; λ, ∆ n ) ; denote also S i,n (x, y; λ

i ) = S n (x, y; λ i , ∆ i,n ) = λ i 1 ∆i (x)K n (x, y), for 1 ≤ i ≤ p. Note that S n (x, y; λ) = S i,n (x, y; λ i ) if x ∈ ∆ i,n .
For every z ∈ C and λ ∈ C p , we use the following notations :

D n (z, λ) := det(1 -zS n (λ, ∆ n )) and D n,i (z, λ i ) := det(1 -zS n (λ i , ∆ i,n )) (26)
The following controls will be of constant use in the sequel. Proposition 6: 1) Let λ ∈ C p be fixed. The sequences of functions :

z → D n (z, λ) and z → D i,n (z, λ i ), 1 ≤ i ≤ p
are uniformly bounded on every compact subset of C. 2) Let z = 1. The sequences of functions :

λ → D n (1, λ) and λ → D 1,n (1, λ i ), 1 ≤ i ≤ p
are uniformly bounded on every compact subset of C p . 3) Let λ ∈ C p be fixed. For every δ > 0, there exists r > 0 such that

sup n sup z∈B(0,r) |D n (z, λ) -1| < δ , sup n sup z∈B(0,r) |D i,n (z, λ i ) -1| < δ , 1 ≤ i ≤ p .
Proof of Proposition 6 is provided in Appendix D.

We introduce the following functions :

d n : (z, λ) → det (1 -zS n (λ, ∆ n )) - p i=1 det (1 -zS n (λ i , ∆ i,n )) , (27)
f n : (z, λ) → D ′ n (z, λ) D n (z, λ) - p i=1 D ′ i,n (z, λ i ) D i,n (z, λ i ) , ( 28
)
where ′ denotes the derivative with respect to z ∈ C. We first prove that f n goes to zero as z → 0.

1) Asymptotic study of f n in a neighbourhood of z = 0: In this section, we mainly consider the dependence of f n in z ∈ C while λ ∈ C p is kept fixed. We therefore drop the dependence in λ to lighten the notations. Equality (16) yields :

D ′ n (z) D n (z) = - ∞ k=0 T n (k + 1)z k and D ′ i,n (z) D i,n (z) = - ∞ k=0 T i,n (k + 1)z k (1 ≤ i ≤ p) (29)
where ′ denotes the derivative with respect to z ∈ C and T n (k) and T i,n (k) are as in (17), respectively defined by :

T n (k) := R k S n (x 1 , x 2 )S n (x 2 , x 3 ) • • • S n (x k , x 1 )dx 1 • • • dx k , (30)
T i,n (k) := R k S i,n (x 1 , x 2 )S i,n (x 2 , x 3 ) • • • S i,n (x k , x 1 )dx 1 • • • dx k . (31)
Recall that D n and D i,n are entire functions (of z ∈ C). The functions

D ′ n D n and D ′ i,n D i,n
admit a power series expansion around zero given by (29). Therefore, the same holds true for f n (z), moreover : Lemma 1: Define R as in Proposition 4. For n large enough, f n (z) defined by ( 28) is holomorphic on B(0, R) := {z ∈ C, |z| < R}, and converges uniformly to zero as n → ∞ on each compact subset of B(0, R).

Proof: Denote by ξ (n) i (x) := λ i 1 ∆i,n (x) and recall that T n (k) is defined by (30). Using the identity

k m=1 p i=1 a im = σ∈{1,•••,p} k k m=1 a σ(m)m , (32)
where a im are complex numbers, T n (k) writes (k ≥ 2) :

T n (k) = R k k m=1 p i=1 ξ (n) i (x m ) K n (x 1 , x 2 ) • • • K n (x k , x 1 )dx 1 • • • dx k , = σ∈{1,••• ,p} k j n,k (σ) , (33)
where we defined

j n,k (σ) := R k k m=1 ξ (n) σ(m) (x m ) K n (x 1 , x 2 ) • • • K n (x k , x 1 )dx 1 • • • dx k . ( 34
)
We split the sum in the right-hand side into two subsums. The first is obtained by gathering the terms with k-uples σ = (i, i, • • • , i) for 1 ≤ i ≤ p and writes :

p i=1 R k k m=1 λ i 1 ∆i,n (x m ) K n (x 1 , x 2 ) • • • K n (x k , x 1 )dx 1 • • • dx k = p i=1 T i,n (k) ,
where T i,n (k) is defined by (31). The remaining sum consists of those terms for which there exists at least one couple

(m, ℓ) ∈ {1, • • • , k} 2 such that σ(m) = σ(ℓ). Let S = σ ∈ {1, • • • , p} k : ∃(m, ℓ) ∈ {1, • • • , k} 2 , σ(m) = σ(ℓ) , we obtain T n (k) = p i=1 T i,n (k) + s n (k) where s n (k) := σ∈S j n,k (σ) ,
for each k ≥ 2. For each q ∈ {1, . . . , k -1}, denote by π q the following permutation for any k-uplet (a 1 , . . . , a k ) :

π q (a 1 , . . . , a k ) = (a q , a q+1 , . . . , a k , a 1 , . . . , a q-1 ) .

In other words, π q operates a circular shift of q -1 elements to the left. Clearly, any k-uple σ ∈ S can be written as σ = π q (m, ℓ, σ) for some q ∈ {1, . . . , k -1}, (m, ℓ) ∈ {1, . . . , p} such that m = ℓ, and σ ∈ {1, . . . , p} k-2 . Thus,

|s n (k)| ≤ k-1 q=1 (m,ℓ)∈{1•••p} 2 m =ℓ σ∈{1•••p} k-2 |j n,k (π q (m, ℓ, σ))| .
From (34), function j n,k is invariant up to any circular shift π q , so that j n,k (σ) coincides with j n (m, ℓ, σ) for any σ = π q (m, ℓ, σ) as above. Therefore,

|s n (k)| ≤ k-1 q=1 (m,ℓ)∈{1•••p} 2 m =ℓ σ∈{1•••p} k-2 |j n,k (m, ℓ, σ)| ≤ k (m,ℓ)∈{1•••p} 2 m =ℓ σ∈{1•••p} k-2 R k |ξ (n) m (x 1 )ξ (n) ℓ (x 2 )ξ (n) σ(1) (x 3 ) • • • ξ (n) σ(k-2) (x k )| ×|K n (x 1 , x 2 ) • • • K n (x k , x 1 )|dx 1 • • • dx k
The latter writes

|s n (k)| = k 1≤m,ℓ≤p m =ℓ ∆m,n×∆ℓ,n K n (x 1 , x 2 )ξ (n) m (x 1 )ξ (n) ℓ (x 2 ) ×   R k-2 σ∈{1•••p} k-2 ξ (n) σ(1) (x 3 ) • • • ξ (n) σ(k-2) (x k ) |K n (x 2 , x 3 ) • • • K n (x k , x 1 )| dx 3 • • • dx k   dx 1 dx 2 = k 1≤m,ℓ≤p m =ℓ ∆m,n×∆ℓ,n K n (x 1 , x 2 ) × p i=1 ξ (n) i (x 1 ) × p i=1 ξ (n) i (x 2 ) ×   R k-2 σ∈{1•••p} k-2 ξ (n) σ(1) (x 3 ) • • • ξ (n) σ(k-2) (x k ) |K n (x 2 , x 3 ) • • • K n (x k , x 1 )| dx 3 • • • dx k   dx 1 dx 2 .
It remains to notice that

p i=1 ξ (n) i (x 2 ) R k-2 σ∈{1•••p} k-2 k m=3 ξ (n) σ(m-2) (x m ) |K n (x 2 , x 3 ) • • • K n (x k , x 1 )| dx 3 • • • dx k (a) = p i=1 ξ (n) i (x 2 ) R k-2 k m=3 p i=1 ξ (n) i (x m ) |K n (x 2 , x 3 ) • • • K n (x k , x 1 )| dx 3 • • • dx k = R k-2 |S n (x 2 , x 3 )S n (x 3 , x 4 ) • • • S n (x k , x 1 )|dx 3 • • • dx k (b) = |S n | (k-1) (x 2 , x 1 ) ,
where (a) follows from (32), and (b) from the mere definition of the iterated kernel (24). Thus, for k ≥ 2, the following inequality holds true :

|s n (k)| ≤ k 1≤m,ℓ≤p m =ℓ ∆m,n×∆ℓ,n |S n (x 1 , x 2 )| × |S n | (k-1) (x 2 , x 1 )dx 1 dx 2 . ( 35
)
For k = 1, let s n (1) = 0 so that equation T n (k) = i T i,n (k) + s n (k) holds for every k ≥ 1.

According to (28), f n (z) writes :

f n (z) = - ∞ k=1 s n (k + 1)z k .
Let us now prove that f n (z) is well-defined on the desired neighbourhood of zero and converges uniformly to zero as n → ∞. Let β > R -1 , then Propositions 4 and 5 yield :

|s n (k)| ≤ k 1≤m,ℓ≤p m =ℓ ∆m,n×∆ℓ,n |S n (x, y)||S n | (k-1) (y, x)dxdy , ≤ k 1≤m,ℓ≤p m =ℓ M m×ℓ,n M (k-1) ℓ×m,n |∆ m,n ||∆ ℓ,n | , ≤ k β k-2 1≤m,ℓ≤p m =ℓ C 2 n (1-κm +κ ℓ 2 ) n (1+ǫ-κm +κ ℓ 2 ) n -(κm+κℓ) × |∆ m ∆ ℓ | , ≤ k β k-2 1≤m,ℓ≤p m =ℓ C 2 |∆ m ∆ ℓ | n 2(κm+κℓ-1)-ǫ , (a) ≤ k β k-2 × max 1≤m≤p |∆ m | 2 × p(p -1)C 2 n 2 3 -ǫ
, where (a) follows from the fact that κ m + κ ℓ -1 ≥ 1 3 . Clearly, the power series ∞ k=1 (k + 1)β k-1 z k converges for |z| < β -1 . As β -1 is arbitrarily lower than R, this implies that f n (z) is holomorphic in B(0, R). Moreover, for each compact subset K included in the open disk B(0, β -1 ) and for each z ∈ K,

|f n (z)| ≤ ∞ k=1 (k + 1)β k-1 (sup z∈K |z|) k × max 1≤m≤p |∆ m | 2 × p(p -1)C 2 n 2 3 -ǫ .
The right-hand side of the above inequality converges to zero as n → ∞. Thus, the uniform convergence of f n (z) to zero on K is proved ; in particular, as β -1 < R, f n (z) converges uniformly to zero on B(0, R). Lemma 1 is proved.

2) Convergence of d n to zero as n → ∞: In this section, λ ∈ C p is fixed. We therefore drop the dependence in λ in the notations. Consider function F n defined by :

F n (z) := log D n (z) p i=1 D i,n (z) , ( 36
)
where log corresponds to the principal branch of the logarithm and D n and D i,n are defined in (29). As D n (0) = D i,n (0) = 1, there exists a neighbourhood of zero where F n is holomorphic. Moreover, using Proposition 6-3), one can prove that there exists a neighbourhood of zero, say B(0, ρ), where F n (z) is a normal family. Assume that this neighbourhood is included in B(0, R), where R is defined in Proposition 4 and notice that in this neighbourhood,

F ′ n (z) = f n (z)
as defined in (28). Consider a compactly converging subsequence F φ(n) → F φ in B(0, ρ) (by compactly, we mean that the convergence is uniform over any compact set Λ ⊂ B(0, ρ)), then one has in particular

F ′ φ(n) (z) → F ′ φ but F ′ φ(n) (z) = f φ(n) (z) → 0. Therefore, F φ is a constant over B(0, ρ), in particular, F φ (z) = F φ (0) = 0.
We have proved that every converging subsequence of F n converges to zero in B(0, ρ). This yields the convergence (uniform on every compact of B(0, ρ)) of F n to zero in B(0, ρ). This yields the existence of a neighbourhood of zero, say B(0, ρ ′ ) where :

D n (z) p i=1 D i,n (z) ---→ n→∞ 1 (37)
uniformly on every compact of B(0, ρ ′ ). Recall that d n (z) = D n (z) -p i=1 D i,n (z). Combining (37) with Proposition 6-3) yields the convergence of d n (z) to zero in a small neighbourhood of zero. Now, Proposition 6-1) implies that d n (z) is a normal family in C. In particular, every subsequence d φ(n) compactly converges to a holomorphic function which coincides with 0 in a small neighbourhood of the origin, and thus is equal to 0 over C. We have proved that

d n (z) ---→ n→∞ 0, ∀z ∈ C , with λ ∈ C p fixed.
3) Convergence of the partial derivatives of λ → d n (1, λ) to zero: In order to establish Theorem 1, we shall rely on Proposition 3 where the probabilities of interest are expressed in terms of partial derivatives of Fredholm determinants. We therefore need to establish that the partial derivatives of d n (1, λ) with respect to λ converge to zero as well. This is the aim of this section.

In the previous section, we have proved that ∀(z, λ) ∈ C p+1 , d n (z, λ) → 0 as n → ∞. In particular,

d n (1, λ) → 0, ∀λ ∈ C p .
We now prove the following facts (with a slight abuse of notation, denote

d n (λ) instead of d n (1, λ)) : 1) As a function of λ ∈ C p , d n (λ) is holomorphic.
2) The sequence (λ → d n (λ)) n≥1 is a normal family on C p .

3) The convergence d n (λ) → 0 is uniform over every compact set Λ ⊂ C p . Proof of Fact 1) is straightforward and is thus omitted. Proof of Fact 2) follows from Proposition 6-2). Let us now turn to the proof of Fact 3). As (d n ) is a normal family, one can extract from every subsequence a compactly converging one in C p (see for instance [4, Theorem 1.13]). But for every λ ∈ C p , d n (λ) → 0, therefore every compactly converging subsequence converges toward 0. In particular, d n itself compactly converges toward zero, which proves Fact 3).

In order to conclude the proof, it remains to apply standard results related to the convergence of partial derivatives of compactly converging holomorphic functions of several complex variables, as for instance [START_REF] Range | Holomorphic functions and integral representations in several complex variables[END_REF]Theorem 1.9]. As d n (λ) compactly converges to zero, the following convergence holds true :

Let (ℓ 1 , • • • , ℓ p ) ∈ N p , then ∀λ ∈ C p , ∂ ∂λ 1 ℓ1 • • • ∂ ∂λ p ℓp d n (λ) ---→ n→∞ 0 .
This, together with Proposition 3, completes the proof of Theorem 1.

APPENDIX

A. Proof of Proposition 3

Denote by E n (ℓ, ∆) the probability that for every i ∈ {1, • • • , p}, the set ∆ i contains exactly ℓ i eigenvalues :

E n (ℓ, ∆) = P {N (∆ 1 ) = ℓ 1 , • • • , N (∆ p ) = ℓ p } . ( 38
)
Let P n (m) be the set of subsets of {1, • • • , n} with exactly m elements. If A ∈ P n (m), then A c is its complementary subset in {1, • • • , n}. The mere definition of E n (ℓ, ∆) yields :

E n (ℓ, ∆) = R n (A1,••• ,Ap)∈ Pn(ℓ1)ו••×Pn(ℓp) p k=1    i∈Ak 1 ∆k (x i ) j∈A c k (1 -1 ∆k (x j ))    p n (x 1 • • • x n )dx 1 • • • dx n
Using the following formula :

1 ℓ! - d dλ ℓ n i=1 (1 -λα i ) = A∈Pn(ℓ) i∈A α i j∈A c
(1λα j ) , we obtain :

E n (ℓ, ∆) = 1 ℓ 1 ! • • • ℓ p ! - ∂ ∂λ 1 ℓ1 • • • - ∂ ∂λ p ℓp Γ(λ, ∆) λ1=•••=λp=1
where

Γ(λ, ∆) = R n n i=1 (1 -λ 1 1 ∆1 (x i )) • • • (1 -λ p 1 ∆p (x i )) p n (x 1 • • • x n ) dx 1 • • • dx n .
Expanding the inner product and using the fact that the ∆ k 's are pairwise disjoint yields :

(1 -λ 1 1 ∆1 (x)) • • • (1 -λ p 1 ∆p (x)) = 1 - p k=1 λ k 1 ∆k (x) . Thus Γ(λ, ∆) = R n n i=1 1 - p k=1 λ k 1 ∆k (x i ) p n (x 1 • • • x n ) dx 1 • • • dx n , (a) = 1 + R n n m=1 (-1) m A∈Pn(m) i∈A p k=1 λ k 1 ∆k (x i ) p n (x 1 • • • x n ) dx 1 • • • dx n , = 1 + n m=1 (-1) m A∈Pn(m) R n i∈A p k=1 λ k 1 ∆k (x i ) p n (x 1 • • • x n ) dx 1 • • • dx n , (b) = 1 + n m=1 (-1) m n m R n m i=1 p k=1 λ k 1 ∆k (x i ) p n (x 1 • • • x n ) dx 1 • • • dx n , (c) = 1 + n m=1 (-1) m m! R m m i=1 p k=1 λ k 1 ∆k (x i ) det {K n (x i , x j )} 1≤i,j≤m dx 1 • • • dx m ,
where (a) follows from the expansion of i (1 -k λ k 1 ∆k (x i )), (b) from the fact that the inner integral in the third line of the previous equation does not depend upon E due to the invariance of p n with respect to any permutation of the x i 's, and (c) follows from the determinantal representation (14). Therefore, Γ(λ, ∆) writes :

Γ(λ, ∆) = 1 + n m=1 (-1) m m! R m det {S n (x i , x j ; λ, ∆)} 1≤i,j≤m dx 1 • • • dx m (39)
where S n (x, y; λ, ∆) is the kernel defined in (18). As the operator S n (λ, ∆) has finite rank n, (39) coincides with the Fredholm determinant det(1 -S n (λ, ∆)) (see [START_REF] Tricomi | Integral equations[END_REF] for details). Proof of Proposition 3 is completed.

B. Proof of Proposition 4

In the sequel, C > 0 will be a constant independent from n, but whose value may change from line to line. First consider the case i = j. Denote by S µi (x, y) the following limiting kernel :

S µi (x, y) :=              sin πρ(µ i )(x -y) π(x -y) if -2 < µ i < 2 Ai(x)Ai ′ (y) -Ai(y)Ai ′ (x) x -y if µ i = 2, Ai(-x)Ai ′ (-y) -Ai(-y)Ai ′ (-x) -x + y if µ i = -2,
Proposition 1 implies that n -κi K n (µ i + x/n κi , µ i + y/n κi ) converges uniformly to S µi (x, y) on every compact subset of R 2 , where κ i is defined by (20). Moreover, S µi (x, y) being bounded on every compact subset of R 2 , there exists a constant C i such that :

M i×i,n (Λ) = sup λ∈Λ |λ i | sup (x,y)∈∆ 2 i,n |K n (x, y)| = sup λ∈Λ |λ i | sup (x,y)∈∆ 2 i K n µ i + x n κi , µ i + y n κi ≤ sup λ∈Λ |λ i | n κi sup (x,y)∈∆ 2 i 1 n κi K n µ i + x n κi , µ i + y n κi -S µi (x, y) + sup (x,y)∈∆ 2 i |S µi (x, y)| ≤ n κi C i , (40)
It remains to take R as R -1 = max(C 1 , • • • , C p ) to get the pointwise or uniform estimate.

Consider now the case where i = j. Using notation κ i , inequalities (11) and ( 12) can be conveniently merged as follows : There exists a constant C such that for

1 ≤ i ≤ p, sup x∈∆i,n ψ (n) n-k (x) ≤ n 1-κ i 2 C . (41)
For n large enough, we obtain, using (8) :

M i×j,n (Λ) (a) ≤ sup λ∈Λ |λ i | sup (x,y)∈∆i,n×∆j,n |ψ (n) n (x)||ψ (n) n-1 (y)| + |ψ (n) n (y)||ψ (n) n-1 (x)| |x -y| , (b)
≤ sup

λ∈Λ |λ i | n 1-κ i 2 + 1-κ j 2 2C 2 inf (x,y)∈∆i,n×∆j,n |x -y| , (c) ≤ C n 1-κ i +κ j 2 ,
where (a) follows from ( 8), (b) from ( 41) and (c) from the fact that

lim inf n→∞ inf (x,y)∈∆i,n×∆j,n |x -y| = |µ i -µ j | > 0.
Proposition 4 is proved.

C. Proof of Proposition 5

Let Λ = {λ} be fixed. We drop, in the rest of the proof, the dependence in λ in the notations. The mere definition of |S n | (k) yields :

0 ≤ |S n | (k) (x, y) ≤ R |S n (x, u)| × |S n | (k-1) (u, y)du = p i=1 ∆i,n |S n (x, u)| × |S n | (k-1) (u, y)du
From the above inequality, the following is straightforward :

∀(x, y) ∈ ∆ m,n × ∆ ℓ,n , |S n | (k) (x, y) ≤ p i=1 |∆ i,n |M m×i,n M (k-1) i×ℓ,n .
Using Proposition 4, we obtain :

M (k) m×ℓ,n ≤ R -1 M (k-1) m×ℓ,n + α i =m n (1-κm +3κ i 2 ) M (k-1) i×ℓ,n , (42)
where

α := max(C|∆ 1 |, • • • , C|∆ p |). Now take β > R -1 and ǫ ∈ (0, 1 3 ). Property (25) holds for k = 1 since M m×m,n ≤ R -1 n κm ≤ βn κm and M m×ℓ,n ≤ Cn (1-κm +κ ℓ 2 ) ≤ Cn (1+ǫ-κm +κ ℓ 2 )
for every m = ℓ by Proposition 4. Assume that the same holds at step k -1.

Consider first the case where m = ℓ. Eq. (42) becomes where the last inequality follows from the fact that 2 + ǫ -2κ m -2κ i < 0, which implies that n 2+ǫ-2κm-2κi → 0, which in turn implies that the term inside the parentheses is lower than one for n large enough. Now if m = ℓ, Eq. (42) becomes :

M (k) m×m,n ≤ R -1 β k-1 n κm + αCβ k-2 i =m n (1-κm 2 - 3κ i 2 ) n (1+ǫ-κ i 2 -κm 2 ) ≤ β k n κm   R -1 β + i =m
M (k) m×ℓ,n ≤ R -1 Cβ k-2 n (1+ǫ-κ ℓ +κm 2 ) + αβ k-1 n (1-κ ℓ +κm 2 ) + i =m,ℓ Cαβ k-2 n (1-κm +3κ i 2 ) n (1+ǫ-κ i +κ ℓ 2 ) = Cβ k-1 n (1+ǫ-κ ℓ +κm 2 )   R -1 β + α Cn ǫ + α β i =m,ℓ n 1-2κi   ≤ Cβ k-1 n (1+ǫ-κ ℓ +κm 2 ) R -1 β + α Cn ǫ + αp 2 βn 1 3 ≤ Cβ k-1 n (1+ǫ-κ ℓ +κm 2 ) ,
where the last inequality follows from the fact that the term inside the parentheses is lower than one for n large enough. Therefore, (25) holds for each k ≥ 1 and for n large enough.

D. Proof of Proposition 6

Define U n (k, λ) := R k det {S n (x i , x j ; λ)} i,j=1•••k dx 1 • • • dx k . Using Hadamard's inequality,

U n (k, λ) ≤ R k k i=1 k j=1 |S n (x i , x j ; λ)| 2 dx 1 • • • dx k ≤ R k k i=1 k j=1 p m=1 λ m 1 ∆m,n (x i ) 2 |K n (x i , x j )| 2 dx 1 • • • dx k Therefore, U n (k, λ) ≤ R k k i=1 p m=1 λ m 1 ∆m,n (x i ) k j=1 |K n (x i , x j )| 2 dx 1 • • • dx k = R k σ∈{1•••p} k k i=1 λ σ(i) 1 ∆σ(i),n (x i ) k j=1 |K n (x i , x j )| 2 dx 1 • • • dx k = σ∈{1•••p} k R k k i=1 k j=1 |λ σ(i) 1 ∆σ(i),n (x i )K n (x i , x j )| 2 dx 1 • • • dx k .
In the above equation, integral We now use Proposition 4 to bound the right-hand side. Clearly, when σ(i) = σ(j), Proposition 4 implies that |∆ σ(i),n |M σ(i)×σ(i),n (Λ) ≤ R -1 Λ ∆ max , where ∆ max = max 1≤i≤p |∆ i |. This inequality still holds when σ(i) = σ(j) as a simple application of Proposition 4. Therefore,

sup λ∈Λ U n (k, λ) ≤ σ∈{1,••• ,p} k k k 2 ∆ k max R -k Λ = p ∆ max √ k R Λ k .
Using this inequality, it is straightforward to show that the serie k sup λ∈Λ Un(k,λ) k! z k converges for every z ∈ C and every compact set Λ. Parts 1) and 2) of the proposition are proved. Based on the definition of D n (z, λ) and D i,n (z, λ i ), we obtain :

max (|D n (z, λ) -1|, |D i,n (z, λ i ) -1|, 1 ≤ i ≤ p) ≤ |z| ∞ k=1 |z| k-1 k! U n (k, λ) ,
which completes the proof of Proposition 6.

  surely converges to 2 (resp.

  are the smallest and largest eigenvalues of M . We then describe the asymptotic fluctuations of the ratio λ (n) max λ (n) min .

αC β 2 n

 2 (2+ǫ-2κm-2κi)   ≤ β k n κmfor n large enough ,

  R k clearly reduces to an integral on the set∆ σ(1),n × • • • × ∆ σ(p),n . Thus, sup λ∈Λ U n (k, λ) ≤ σ∈{1•••p} k ∆σ(1),nו••×∆σ(p),n ×σ(j) (Λ)dx 1 • • • dx k i),n |M σ(i)×σ(j)

This work was partially supported by the "Agence Nationale de la Recherche" via the program "Masses de données et connaissances", project SESAME and by the "GDR ISIS" via the program "jeunes chercheurs". P. Bianchi and M. Debbah are with SUPELEC, France.


Walid Saad
email: saad@unik.no

Zhu Han

Merouane Debbah
email: merouane.debbah@supelec.fr

Are Hjørungnes

A Coalition Formation Game in Partition Form for Peer-to-Peer File Sharing Networks

In current peer-to-peer file sharing networks, a large number of peers with heterogeneous connections simultaneously seek to download resources, e.g., files or file fragments, from a common seed at the time these resources become available, which incurs high download delays on the different peers. Unlike existing literature which mainly focused on cooperative strategies for data exchange between different peers after all the peers have already acquired their resources, in this paper, we study the cooperation possibilities among a number of peers seeking to download, concurrently, a number of resources at the time the availability of the resources is initially announced at a common seed. We model the problem as a coalitional game in partition form and we propose an algorithm for coalition formation among the peers. The proposed algorithm enables the peers to take autonomous decisions to join or leave a coalition while minimizing their average download delay. We show that, by using the proposed algorithm, a Nash-stable partition composed of coalitions of peers is formed. Within every coalition, the peers distribute their download requests between the seed and the cooperating partners in a way to minimize the total average delay incurred on the coalition. Analytically, we study the 2-peer scenario and derive the optimal download request distribution policies. Simulation results show that, using the proposed coalition formation game, the peers can improve their average download delay per peer of up to 99.6% compared to the non-cooperative approach for the case with N = 15 peers.

I. INTRODUCTION

Peer-to-peer (P2P) file sharing services such as BitTorrent [1] have recently become one of the most popular resource sharing medium among users. Using a combination of advanced search and communication techniques as well as large-scale distributed file storage systems, P2P file sharing systems allow a number of users to download and share content among each other in a decentralized, scalable, and fault tolerant manner.

Due to the heterogeneous capabilities of the peers as well as the decentralized nature of P2P file sharing, current P2P systems face many challenges at different perspectives [START_REF] Lua | A survey and comparison of peer-to-peer overlay network schemes[END_REF]. For instance, in [START_REF] Qiu | Modeling and performance analysis of BitTorrentlike peer-to-peer networks[END_REF], the authors proposed incentives, using tit-for-tat strategies, for allowing the peers in a P2P system to efficiently exchange their data. The work in [START_REF] Park | A framework for foresighted resource reciprocation in P2P networks[END_REF] studied the problem of resource reciprocation of multimedia content among peers using a stochastic game. Further, in [START_REF] Lien | Performance issues of P2P file sharing over asymmetric and wireless networks[END_REF], mesh-based architectures for content dissemination are studied in P2P networks.

Most of the aforementioned work in P2P networks focuses on the P2P sharing of resources after these resources were entirely acquired by the peers, independently, from different seeds. However, a prominent challenge of P2P systems that remains relatively unexplored is the study of the scenario where a number of peers compete for downloading, concurrently, a number of resources, e.g., files or file fragments that complement their already owned resources, from the same seed at the time the availability of the resources is announced. For instance, whenever a new file, fragment, or group of files/file fragments, become available at a certain seed, i.e., a server or another peer, a large number of interested peers, e.g., a flash crowd of nodes interested in these resources, will, concurrently, attempt to download these resources from the seed. Eventually, due to the limited upload capabilities of the seed and the heterogeneous characteristics of the peers, this scenario yields increased download delays on the competing peers (this issue is highlighted in [START_REF] Lien | Performance issues of P2P file sharing over asymmetric and wireless networks[END_REF]). Hence, one important challenge is to propose cooperative schemes for P2P networks that can alleviate the download delays of the peers during this phase of simultaneous download of resources at the time they become available.

The main contribution of this paper is to propose cooperative strategies, using the framework of coalition formation games in partition form, for enabling the peers to improve their download delays during the concurrent download of resources from a common seed. Another contribution of this paper is to discuss the optimal division of the peers' download request between the main seed and other cooperative peers. For this purpose, we formulate a coalition formation game in partition form among a number of peers that seek to cooperatively improve their download delay while downloading resources from a common seed at the time the resources become available. For the devised game model, we propose a coalition formation algorithm through which each peer can take an individual decision to join or leave a coalition while minimizing its average download delay. We show that the proposed coalition formation algorithm enables the peers to self-organize into a Nash-stable partition composed of coalitions of peers. Analytically and through simulations, we assess different aspects of the proposed scheme.

II. SYSTEM MODEL Consider a P2P network consisting of N peers and let N denote the set of all peers. We consider that each peer already owns a small number of resources, e.g., files or fragments, related to a particular content and is seeking to download the remainder of this content. Whenever a seed, e.g., a server or another independent peer (not in the set N ) that owns the entire content of interest to the peers, announces the availability of a number of resources, all N peers will concurrently attempt to download these resources from the seed. In this model, it is considered that the seed owns all the data related to the content of common interest to the peers while each peer in N owns different chunks of this data.

Each peer i ∈ N has an upload rate µ i , and, in a noncooperative manner, attempts to download the remainder of its data from the common seed with a download rate λ i . With no loss of generality, we assume that, for any peer i, the arrival process for the download requests is exponentially distributed with parameter λ -1 i . In such a scenario, given that the seed has an upload rate of µ s and considering that the file service process is an M/D/1 queue, the average delay τ nc for any peer i ∈ N non-cooperatively downloading data from the seed is

τ nc = λ s 2µ s (µ s -λ s ) , ( 1
)
where λ s = ∑ i∈N λ i is the total request rates at the seed.

As the seed has a limited upload rate µ s , one can see from (1) that, whenever the number of peers interested in the seed's content is large, the download delay increases significantly. In particular, the total download requests that the seed can handle must satisfy the stability condition of the queueing system in (1), i.e., λ s < µ s . As a direct result of this condition, the number of peers that can concurrently download the data from the seed, non-cooperatively, is limited and strongly depends on the heterogeneous download rates of the peers. For example, a single peer with large download rate can congest the seed and forbid other peers from utilizing the resource.

To reduce their performance, instead of solely downloading the remaining content from the seed directly, the peers can download the content of interest from the seed as well as from a subset of other peers. By doing so, the peers can potentially reduce the load on the seed and possibly improve their delay. Within each group of cooperating peers, i.e., a coalition S ⊆ N , every peer i ∈ S can direct its download requests to the seed as well as to other cooperative peers j ∈ S \ {i} with a certain fraction p ij such that

0 ≤ p ij ≤ µ j λ i , ∀j ∈ S \ {i} and ∑ j∈S\{i} p ij + p i0 = 1 (2)
where the upper bound in the first condition ensures that no peer i ∈ S will download data from another peer j ∈ S with a rate that exceeds the upload rate µ j of peer j and 0 ≤ p i0 ≤ µ s λi is the fraction of requests directed to the seed from peer i. For every peer i ∈ S, we define the (|S| + 1) × 1 (| • | is the set cardinality operator) column vector p i = [p i0 , . . . , p i|S| ] T of all the fractions of requests directed by by peer i to its partners in S and the seed. Note that, p ii = 0, ∀i ∈ S. Further, we let P S = [p 1 , . . . , p |S| ] be the (|S| + 1) × |S| matrix of all the fractions of the peers in coalition S. Note that, we assume that any peer outside a coalition S, i.e., in N \S, will not allow peers inside S to use its upload bandwidth. Subsequently, for any cooperative peer i member of a coalition S ⊆ N which is downloading data from the seed and the peers in K ⊆ S with |K| = K, given that each of the K queues are independent and by using Little's Law [START_REF] Bertsekas | Data Networks[END_REF] the average download delay will be

τ i (P S ) = 1 K + 1   ∑ j∈S,j̸ =i Λ j 2µ j (µ j -Λ j ) + τ s   , (3)
where the first term is the delay from the data downloaded by peer i from K partners in coalition S with µ j the service rate of peer j ∈ S, and τ s the delay from the data downloaded by i from the seed which is the same for all i ∈ S and is given using the same expression as (1) with λ s = ∑ i∈S p i0 λ i . Further, Λ j = (P S ) j λ in (3) represents the total load at peer j ∈ S with (P S ) j the jth line of P S and λ an |S| × 1 vector with each element λ k corresponding to the download rate of a peer k ∈ S. Note that, we assume that, for any coalition S that forms, ∃i ∈ S such that p i0 ̸ = 0, i.e., at least one peer downloads from the seed, otherwise, the download delay in (3) is considered to be infinite. By adequately selecting the distribution of their download requests, i.e., the matrix P S , the cooperative peers might be able to improve their average.

Although the peers can divide their download requests in any way between the cooperative peers and the seed, one scheme that the peers can adopt is to distribute their requests in a way to minimize the total average delay experienced by the coalition as a whole. Such an optimization is quite popular both in game theory and networking whereby a group of nodes can act so as to minimize the total social cost (or alternatively maximize the overall social welfare) on the network as a whole [START_REF] Shakkottai | Network optimization and control[END_REF], [START_REF] Saad | Coalitional game theory for communication networks[END_REF].

In this context, given a coalition S ⊆ N of cooperative peers, the peers in the coalition distribute their download requests, i.e., compute the vectors p i , ∀i ∈ S such that the total social cost, i.e., the total average delay of the coalition, is minimized. In other words, each coalition jointly solves the following optimization min

P S ∑ i∈S τ i (P S ), (4)
s.t. 0 ≤ p i0 < µ s λ i and 0 ≤ p ij < µ j λ i , ∀j ∈ S \ {i}, i = 1 . . . |S|, ∑ j∈S\{i} p ij + p i0 = 1, i = 1 . . . |S|,
where τ i is given by ( 3) and the two constraint describe previously mentioned properties of the download request fractions. Note that, as previously mentioned, at least one peer in the coalition must be connected to the seed, i.e., ∃i ∈ S with p i0 ̸ = 0, otherwise the delay is infinite. Subsequently, whenever a group of peers cooperate within a coalition S, they can compute the download request distribution which minimizes the total average delay of their coalition as per (4) which is a standard constrained optimization problem that can be solved using several known optimization methods [START_REF] Boyd | Convex Optimization[END_REF]. As a result of this optimization, the delay of every peer i in coalition S will be given by τ i (P * S ) as per (3) with P * S denoting the solution of (4). Nonetheless, although minimizing the social cost is an attractive approach, in several scenarios, the social optimum and the individual incentives of the peers might not be aligned, i.e., optimizing the social cost of a coalition does not guarantee a better individual delay for every peer involved in the coalition [START_REF] Shakkottai | Network optimization and control[END_REF]. Hence, there is a need to devise cooperative strategies which allow each peer to autonomously form coalitions while taking into account two conflicting objectives: (i)-Improving its individual delay through cooperation and (ii)-Distributing its download requests inside the coalition in a way to minimize the overall social cost on the network as per (4).

III. PEERS COOPERATION AS A COALITIONAL GAME IN

PARTITION FORM We use the framework of coalitional game theory [START_REF] Saad | Coalitional game theory for communication networks[END_REF] to study the proposed cooperative P2P model. Denoting by B as the set of all partitions of N , the proposed P2P cooperation problem is modeled as a coalitional game in partition form with nontransferable utility defined as follows [START_REF] Saad | Coalitional game theory for communication networks[END_REF]:

Definition 1: A coalitional game in partition form with nontransferable utility (NTU) is defined by a pair (N , V ) where N is the set of players and V is a mapping such that for every partition Π ∈ B , and every coalition S ⊆ N , S ∈ Π, V (S, Π) is a closed convex subset of R S that contains the payoff vectors that players in S can achieve.

Denoting by ϕ i (S, Π) the payoff of any peer i in coalition S ∈ Π within a partition Π ∈ B of N , we define the coalitional value set, i.e., the mapping V in partition form, as follows

V (S, Π) = {ϕ(S, Π) ∈ R S |∀i ∈ S, ϕ i (S, Π) = -τ i (P * S )}, (5)
where τ i (P * S ) is given by (3) with P * S the solution of (4) for coalition S and the minus sign is inserted for convenience, in order to turn the problem into a maximization problem. Note that, the delay τ i (P S ) in (3) depends, through it second term, not only on the download request distribution inside S but also on the distribution outside S through the seed, and, thus, it depends on the partition Π (for notational convenience this dependence is dropped from τ i (P * S )). Thus, the proposed P2P cooperative approach is formulated as an (N , V ) coalitional game in partition form with NTU where the mapping V is a closed and convex subset of R S as given by (5) (singleton set).

The main challenge of a coalitional game in partition form is to construct algorithms for forming the coalitions. First, we define the following concept:

Definition 2: Given any peer i ∈ N , a preference relation denoted by ≽ i is defined as a complete, reflexive, and transitive binary relation over the set of all coalition/partition pairs that peer i can be a member of, i.e., the set

{(S k , Π)|S k ⊆ N , i ∈ S k , S k ∈ Π, Π ∈ B}.
As a result, for any peer i ∈ N that can provide a quantification of its benefit for every potential coalition that it can form, the preference relation ≽ i can be used to compare the peer's preference between any two coalitions S 1 ⊆ N , S 1 ∈ Π and, S 2 ⊆ N , S 2 ∈ Π ′ such that i ∈ S 1 and i ∈ S 2 and their respective partitions. Hence, (S 1 , Π) ≽ i (S 2 , Π ′ ) implies that peer i is better off working cooperatively in coalition S 1 when Π is in place, over being member of coalition S 2 when Π ′ is in place, or at least, i prefers both coalition/partition pairs equally (when the preference is strict, it is denoted by ≻ i ). Note that a preference relation can be used to compare two coalitions in the same partition, or the same coalition in two different partitions. For the peer-to-peer cooperation game, we propose the following preference relation for any peer i ∈ N :

(S 1 , Π) ≽ i (S 2 , Π ′ ) ⇔ w i (S 1 , Π) ≥ w i (S 2 , Π ′ ), (6)
where S 1 ∈ Π, S 2 ∈ Π ′ , with Π, Π ′ ∈ B, are any two coalitions that contain peer i, i.e., i ∈ S 1 and i ∈ S 2 and w i is a preference function defined for a peer i ∈ N as follows:

w i (S, Π) =      ϕ i (S, Π), if ϕ j (S, Π) ≥ ϕ j (S \ {i}, Π), ∀j ∈ S \ {i}& S / ∈ h(i) or (|S| = 1), 0, otherwise, (7)
where ϕ i (S, Π) is given by (3) through [START_REF] Lien | Performance issues of P2P file sharing over asymmetric and wireless networks[END_REF] and it represents the delay perceived by peer i ∈ S when partition Π is in place and h(i) is the history set of peer i which holds the coalitions of size larger than 1 that i was member of in the past, and had parted.

The main idea behind the function w i is that a peer i assigns a preference equal to its achieved payoff for any coalition/partition pair (S, Π) as long as coalition S is either a singleton coalition (i.e., i is acting non-cooperatively) or S is a coalition of size larger than 1, which was not previously visited by i (not in h(i)), and where the joining of peer i to coalition S is not detrimental to any of the peers already in S \{i}. Otherwise, the peer assigns a zero preference value to any coalition whose members' payoffs decrease due to the presence of i, since the members of such a coalition will refuse to have i join the coalition. Also, peer i assigns a zero preference to any coalition it already visited and left since i has no incentive to revisit such a coalition.

IV. PROPOSED COALITION FORMATION ALGORITHM For forming coalitions, we propose the following rule that can be followed individually by each peer in the network: Definition 3: Change Rule -For a given partition Π = {S 1 , . . . , S M } of the set of peers N , a peer i can decide to change its coalition, i.e., leave its current coalition S m , for some m ∈ {1, . . . , M } and join another coalition Using the change rule, any peer can decide to leave its present coalition S m ∈ Π and join a new coalition S k ∈ Π, forming a new partition Π ′ , as long as the new pair (S k ∪{i}, Π ′ ) is strictly preferred over (S m , Π) through the preference relation defined by ( 6) and [START_REF] Shakkottai | Network optimization and control[END_REF]. That is, a peer can move to a new coalition if it can strictly improve its payoff, without decreasing the payoff of any member of the new coalition, i.e., given the consent of the new members as per [START_REF] Bertsekas | Data Networks[END_REF]. Further, each time a peer executes a change rule from its current coalition S m ∈ Π, coalition S m is stored in its history set

S k ∈ Π ∪ {∅}, with S k ̸ = S m , if and only if (S k ∪ {i}, Π ′ ) ≻ i (S m , Π) where Π ′ = {Π \ {S m , S k }} ∪ {S m \ {i}, S k ∪ {i}}
h(i) (if |S m | > 1).
Consequently, we propose a coalition formation algorithm composed of three main stages: Peer discovery, coalition formation, and cooperative download. During the first stage, as the seed announces the availability of the resources, all interested peers attempt to download the content from the seed. Meanwhile, the peers can use a tracker or other well known peer-discovery algorithms such as in [1], [START_REF] Lua | A survey and comparison of peer-to-peer overlay network schemes[END_REF] to learn of the presence of other peers downloading from the seed. Once peer discovery is done, the peers engage in the coalition formation stage. In this stage, each peer attempts to estimate its payoff from changing its current coalition and joining another coalition (or peer). Once a peer finds a potential change possibility (satisfying ( 6) and ( 7)), it can make a distributed decision to break from its current coalition and join a new coalition. In this stage, we consider that the peers make decisions in a certain random order (dictated by who requests first to cooperate). The peers take their change decisions based on an assessment, using (3) and (4), of the payoff given the current partition and not on the long term payoff. Such a strategy is a quite common approach for decision making, referred to as myopic strategy [START_REF] Saad | Coalitional game theory for communication networks[END_REF]. Following the convergence of the coalition formation process, a partition Π f is in place in the network for downloading the resources from the seed which occurs in the last stage of the algorithm using the model described in Section II. A summary of the proposed algorithm is given in Algorithm 1.

The stability of the partition Π f can be studied using the following stability concept:

Definition 4: A partition Π = {S 1 , . . . , S M } is Nash-stable if ∀i ∈ N s. t. i ∈ S m , S m ∈ Π, (S m , Π) ≽ i (S k ∪ {i}, Π ′ ) for all S k ∈ Π∪{∅} with Π ′ = (Π\{S m , S k }∪{S m \{i}, S k ∪{i}}).
Hence, a partition Π is Nash-stable, if no peer has an incentive to move from its current coalition to another coalition in Π or to deviate and act alone. Given this notion, the convergence of the proposed algorithm during the coalition formation stage is guaranteed as follows:

Theorem 1: Starting from any initial network partition Π 0 , the coalition formation stage of the proposed algorithm always converges to a final Nash-stable network partition Π f ∈ B.

Proof: This is a result of the finite number of partitions of the set N (given by the Bell number [START_REF] Saad | Coalitional game theory for communication networks[END_REF]) and of the definition of the change rule.

Algorithm 1 Proposed peer-to-peer coalition formation algorithm.

Initial State

The network is partitioned by Π0 = {S1, . . . , SM }. At the beginning of all time, the network is non-cooperative, hence, Π0 = N .

Stage 1 -Peer Discovery:

The seed announces the availability of resources sought by all peers. Each peer in N attempts to download the content from the seed. Using peer discovery algorithms such as trackers or others [1], [START_REF] Lua | A survey and comparison of peer-to-peer overlay network schemes[END_REF], the peers discover the presence of other peers at the seed.

Stage 2 -Coalition Formation: repeat

Each peer i ∈ N investigates potential change operations using the preference in ( 6) by engaging in pairwise negotiations with existing coalitions in partition Π.

Once a change operation is found: a) Peer i leaves its current coalition. b) Peer i updates its history h(i), if needed. c) Peer i joins the new coalition with the consent of its members. until convergence to a Nash-stable partition Stage 3 -Cooperative Download:

The formed coalitions perform cooperative download from the seed and their partners as per Section II.

V. SIMULATION RESULTS AND ANALYSIS A. Analysis of a network with 2 peers

In the scenario of a network with 2 peers, under certain conditions on the upload rate of the seed µ s , the optimal social cost minimizing solution for the coalition S = {1, 2}, if this coalition forms, can be given by the following theorem:

Theorem 2: Consider two peers seeking to download data from a common seed and having, respectively, the download and upload rates λ 1 , λ 2 , µ 1 , and µ 2 . In this scenario, given λ T = λ 1 +λ 2 , whenever the seed's upload rate µ s > λ T satisfies

µ s ≤ { ( √ 2 + 1)µ1 -µ2 + λT if µ1 ≤ µ2 < ( √ 2 + 1)µ1 ( √ 2 + 1)µ2 -µ1 + λT if µ2 < µ1 ≤ ( √ 2 + 1)µ2 (8)
The optimal solution that minimizes the social cost of coalition

S = {1, 2}, if S forms, is P * S = [ p * 10 p * 20 p * 12 p * 21 ] with p * 12 = 1 -p * 10 = ( √ 2 -2)(µ 1 + µ s -λ T ) + √ 2µ 2 2λ 1 , (9)
p * 21 = 1 -p * 20 = ( √ 2 -2)(µ 2 + µ s -λ T ) + √ 2µ 1 2λ 2 . ( 10
)
Proof: Consider the scenario where 2 peers, with respective upload and download rates λ 1 , λ 2 , µ 1 , and µ 2 wish to download resources from a common seed having an upload rate µ s > λ T , λ T = λ 1 + λ 2 . For analyzing whether it is of their benefit to form coalition S = {1, 2}, the peers need to find the social cost minimizing request rate distribution matrix P * S , as per (4). Denote by x 12 = p 12 λ 1 as the amount of download requests directed by peer 1 to peer 2 and x 21 = p 21 λ 2 its counterpart from peer 2 on peer 1. Thus, given the download delays τ 1 (P S ) and τ 2 (P S ) of peers 1 and 2, respectively, as per (3), the total delay of the coalition S is (the dependence on P S is dropped for simplicity)

τ S total (P S ) = τ 1 + τ 2 = x 12 4µ 2 (µ 2 -x 12 ) + x 21 4µ 1 (µ 1 -x 21 ) + τ s (11) with τ s = λT -x12-x21 2µ s (µ s -(λT -x12-x21)) as per (1) with λ s = (λ 1 - x 12 ) + (λ 2 -x 21 ).
For finding the optimal P * S using (4), the peers need to minimize τ S total (P S ) given the constraints

0 ≤ p 12 < µ 2 λ 1 , 0 ≤ p 21 < µ 1 λ 2 , ( 12
)
p 12 + p 10 = 1, p 21 + p 20 = 1.
Note that since µ s > λ T then p 10 and p 20 always satisfy the constraints of (4). By solving ∂τ S total (P S ) ∂x12

= 0 and manipulating the resulting quadratic equation, we obtain, using µ s > λ T , two roots for the equation (details are omitted due to page limits)

x ′ 12 = (α + 1)x 21 + (α + 1)(µ s -λ T ) + (α + 2)µ 2 , (13) where α = ± √ 2. By inspecting (13), one can verify that having α = √ 2 and given µ s > λ T yields x ′ 12 > µ 2 which is an infeasible solution since we must have x 12 ≤ µ 2 . Hence, the only possible solution is

x 12 = (1 - √ 2)x 21 + (1 - √ 2)(µ s -λ T ) + (2 - √ 2)µ 2 (14)
In a symmetric manner, by setting ∂τ S total (P S ) ∂x21

= 0, we find

x 21 = (1 - √ 2)x 12 + (1 - √ 2)(µ s -λ T ) + (2 - √ 2)µ 1 (15)
and, thus, the optimal solution is the solution of the system ( 14) and ( 15) which satisfies the constraints, and is given by

x * 12 = ( √ 2 -2) 2 µ 1 + √ 2 2 µ 2 + ( √ 2 -2) 2 (µ s -λ T ) (16)
x * 21 = ( √ 2 -2) 2 µ 2 + √ 2 2 µ 1 + ( √ 2 -2) 2 (µ s -λ T ) (17)
By substituting ( 16) and ( 17) in the constraints of (12) and through algebraic manipulations while maintaining µ s > λ T , we find that the derived solution is feasible whenever [START_REF] Saad | Coalitional game theory for communication networks[END_REF] , the optimal matrix P * S can be computed. In summary, Theorem 2 provides an analytical closed form solution that the peers can use to compute their optimal policy for download request distribution, given that the seed's upload rate satisfies (8) 1 . Moreover, once the two peers compute the optimal divisions for the coalition S = {1, 2}, using ( 6) and ( 7) (as per the change rule), the peers would agree to join into a single coalition S if at least one peer is better off in the cooperative case without decreasing the payoff of the other peer, i.e., τ 1 (P * S ) ≥ τ nc with τ 2 (P * S ) > τ nc or τ 1 (P * S ) > τ nc with τ 2 (P * S ) ≥ τ nc where τ nc is the non-cooperative delay as per (1).

As seen by ( 3), [START_REF] Boyd | Convex Optimization[END_REF], and (10), for a given seed load µ s > λ 1 + λ 2 , the decision of the two peers to join inherently depends on the characteristics of the peers, i.e., their download and upload rates. For instance, from Theorem 2, it is interesting to note that the optimal divisions p * 12 and p * 21 are linear functions of the upload rates µ 1 , µ 2 , and µ s . Further, given a fixed upload rate for a peer, e.g., µ 1 , as the upload rate µ 2 of the other peer increases, the social cost minimizing solution dictates that peer 1 leeches less and less on peer 2. In order to emphasize this aspect and show how the upload rate of the peers affects their cooperative policies ( 9) and (10), we consider the following example.

Example 1: Consider 2 peers with, respectively, the download and upload rates λ 1 = 1.4 Mbps, λ 2 = 1 Mbps, µ 1 = 512 kbps, and µ 2 ∈ [256, 850] kbps. We consider the case when a server, acting as a seed, with an upload rate µ s = 2.5 Mbps announces the availability of resources that peers 1 and 2 seek to download. These parameters are chosen such that, at all µ 2 , (8) is verified and both peers find it always beneficial to form a single coalition as per the change rule and [START_REF] Bertsekas | Data Networks[END_REF]. For this scenario, we are interested in the variation of the optimal policies of the peers, as per ( 9) and (10), when coalition S = {1, 2} forms and 1 Alternatively, in the case when [START_REF] Saad | Coalitional game theory for communication networks[END_REF] is not satisfied, the peers can always find their optimal download distributions using classical optimization techniques [START_REF] Boyd | Convex Optimization[END_REF]. as µ 2 changes. By inspecting (9), we can see that, as the upload capability of peer 2 increases, peer 1 tends to put more download requests on peer 2, while peer 2 decreases its download requests on peer 1. For instance, while at µ 2 = 256 kbps, peer 1 does not download any data from peer 2 as p * 12 ≈ 0 as per (9) (but still benefits from cooperation due to the reduced load on the server from the cooperation of peer 2), at µ 2 = 850 kbps, peer 1 download up to p * 12 = 30% of its data from peer 2. In contrast, the fraction of download of peer 2 from peer 1 decreases around p * 21 = 25.8% at µ 2 = 256 kbps down to p * 21 = 8.4% at µ 2 = 850 kbps. Hence, as one of the peers leeches more on the other, the optimal policy of the other peer dictates to download more from the server (which is less congested due to the cooperative behavior of the other peer) and less from the other peer. Finally, by solving the system of equalities constituted by ( 9) and (10), we can find that, at µ 2 = 577.5 kbps, the optimal policy of both peers is to equally download from each other, i.e., p * 12 = p * 21 = 16.3%.

B. Simulation results for a network with N ≥ 2 peers

For simulations, we consider a server as a seed with a robust connection having, unless stated otherwise, an upload rate of µ s = 15 Mbps. At the time the server announces the availability of resources for download, N ≥ 2 peers in the set N with download rates λ i , ∀i ∈ N , attempt to concurrently download the content from the server. For all simulations, the download rates λ i , ∀i ∈ N are randomly generated from a uniform distribution over [256, 3000] kbps while maintaining the queueing stability condition µ s > ∑ i∈N λ i . Further, all the peers' connections are considered asymmetric with upload rates uniformly distributed in the interval µ i ∈ [256, min (λ i , 1024)] kbps, ∀i ∈ N . All results are averaged, through a large number of runs, over all possible random choices of the peers' download and upload rates.

In Fig. 1, we show the average download delay per peer as the number of peers downloading from the server N increases. Fig. 1 shows that, as N increases, the average delay for the non-cooperative scheme increases due to the increased load on the server. In contrast, for the proposed algorithm, although the average delay starts by increasing slowly, at N = 10 peers, this average delay starts to slightly decrease with N since the benefit from cooperation grows due to: (i)-The presence of more peers to cooperate with and (ii)-The growing need for cooperation with the increasing server load. Fig. 1 demonstrates that the proposed algorithm presents a significant performance advantage, in terms of average download delay per peer, increasing with the numbers of peers N (due to the presence of more cooperation possibilities) and reaching up to 99.6% (two orders of magnitude) improvement relative to the non-cooperative case at N = 15 peers. In Fig. 2, we show the average download delay per peer for a scenario with N = 10 peers as the upload rate of the server µ s , increases. In this figure, we can see that, for both the proposed scheme and the non-cooperative approach, as µ s increases, the average download delay decreases, as the server becomes less congested. Further, Fig. 2 shows that the increase of µ s decreases the performance advantage of the proposed algorithm as the peers would have less incentive to cooperate due to being somehow satisfied with their non-cooperative download delays (which becomes smaller as µ s grows). Nonetheless, Fig. 2 demonstrates that, at all µ s , the proposed coalition formation algorithm yields a performance advantage of at least 29.3% (at µ s = 40 Mbps) relative to the non-cooperative case.

VI. CONCLUSIONS In this paper, we studied the problem of cooperation among a number of peers seeking to download a content of interest from a common seed at the time this seed announces the availability of the resources. We modeled the problem as a coalition formation game in partition form and we proposed an algorithm for forming coalitions. By engaging in the proposed algorithm, the peers can take individual decisions to join or break from a coalition while minimizing their average download delay. We demonstrated that the coalition formation process allows the peers to self-organize into a Nash-stable partition. For the 2-peer case, we derived analytical results for the optimal download request divisions. Through simulations, we showed that the proposed algorithm yields significant performance gains.

  is the partition resulting of the change. This change rule is represented by {S m , S k } → {S m \ {i}, S k ∪ {i}} and Π → Π ′ .

Fig. 1 .

 1 Fig. 1. Average download delay per peer achieved by the proposed algorithm and the non-cooperative case as the number of peers N increases.

Fig. 2 .

 2 Fig.2. Average download delay per peer for a scenario with N = 10 peers as the server upload rate µ s varies.

This work was supported by NFR through the project 183311/S10, and US NSF CNS-0910461, CNS-0953377, and CNS-0905556.


Michael Haupt

Robert Hirschfeld
email: hirschfeld@hpi.uni-potsdam.de

Marcus Denker
email: denker@iam.unibe.ch

Type Feedback for Bytecode Interpreters ⋆ Position Paper ICOOOLPS 2007

This position paper proposes the exploitation of type feedback mechanisms, or more precisely, polymorphic inline caches, for purely interpreting implementations of object-oriented programming languages. Using Squeak's virtual machine as an example, polymorphic inline caches are discussed as an alternative to global caching. An implementation proposal for polymorphic inline caches in the Squeak virtual machine is presented, and possible future applications for online optimization are outlined.

Introduction

Bytecode interpreters are small in size and comparatively easy to implement, but generally execute programs much less efficiently than just-in-time (JIT) compilers. Techniques like threaded interpretation [START_REF] Klint | Interpretation Techniques[END_REF][START_REF] Piumarta | Optimizing Direct Threaded Code by Selective Inlining[END_REF][START_REF] Berndl | Context Threading: A Flexible and Efficient Dispatch Technique for Virtual Machine Interpreters[END_REF] focus on speeding up bytecode interpretation itself, and caching [START_REF] Deutsch | Efficient Implementation of the Smalltalk-80 System[END_REF][START_REF] Hölzle | Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches[END_REF][START_REF] Arnold | A Survey of Adaptive Optimization in Virtual Machines[END_REF] improves the performance of message sends-the most common operation in object-oriented software [START_REF] Hölzle | Do Object-Oriented Languages Need Special Hardware Support?[END_REF].

It is interesting to observe that, while threading mechanisms are used naturally to a varying degree in bytecode interpreter implementations, such systems usually employ only global caching to speed up dynamic method dispatch. A global cache is clearly beneficial with respect to overall performance. Still, it does not provide optimal support for polymorphic message send sites, and it does not allow for exploiting type information (we provide details on these issues in the following section). In our opinion, the employment of polymorphic inline caches (PICs) [START_REF] Hölzle | Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches[END_REF] instead can provide means for achieving significant speedups in bytecode interpreters while exhibiting only a moderate increase in memory footprint and implementation complexity.

In the next section, we briefly discuss global caches. The bytecode interpreter we use as a case study throughout this paper is that of the Squeak [START_REF] Ingalls | Back to the Future: the Story of Squeak, a Practical Smalltalk Written in Itself[END_REF][START_REF]Squeak Home Page[END_REF] virtual machine (VM) [START_REF]Squeak Virtual Machine Home Page[END_REF]. Section 3 proposes an approach to the implementation of PICs in the Squeak bytecode interpreter. Finally, section 4 gives a summary of the paper and an outlook on possible future optimizations in bytecode interpreters that are encouraged by the introduction of type feedback mechanisms.

Global Caching: Discussion

The Squeak VM bytecode interpreter uses a global cache for improving method lookup performance. This cache has a fixed size and maps <target class, selector> pairs to concrete method implementations (compiled methods). It significantly contributes to the overall performance of the Squeak interpreter.

However, such a cache has several shortcomings. Since it is global, collisions are relatively frequent and lead to longer method lookup times. The cache has to be flushed as soon as changes in the class hierarchy or in method implementations occur. For changes in method implementations, the cache is not entirely flushed, but only for the entries that refer to implementations of the selector in question.

Moreover, flushing is required whenever the garbage collector performs heap compaction, as hashing is done based on target class and selector object addresses. After a flush, the cache needs to be repopulated, during which and overall performance is lower.

The global cache suffers from being global. It cannot react to local changes in an adequate way-i. e., by an update operation that is quasi-local in its effect on cache contents. A local change, such as a class overwriting an inherited method, actually affects only a small part of the entire class hierarchy. Nevertheless, method lookup data for large parts of the class hierarchy needs to be restored.

Also, the global cache is, due to its mapping scheme, generally not able to provide local information, that is information per send site. Such information typically comprises of the concrete receiver types (classes) of a message at a given polymorphic send site. It is called type feedback information [START_REF] Hölzle | Optimizing Dynamically-Dispatched Calls With Run-Time Type Feedback[END_REF] and is very interesting with regard to optimizations (cf. Sec. 4).

The performance of the Squeak bytecode interpreter is good. Still, we believe that it can benefit from a caching mechanism that supports local type feedback. These so-called inline caches [START_REF] Deutsch | Efficient Implementation of the Smalltalk-80 System[END_REF] are usually used in environments that employ JIT compilation and bring great benefit in terms of dynamic message dispatch performance.

Inline caches store the most recently looked-up method address at each given send site. The address is cached at the send site, replacing the call instruction to the lookup method with a direct jump to the code of the method. Since there is a jump to the cached method, no lookup needs to be done at all. There is only a slight overhead resulting from a check at the beginning of the method verifying that the class of the receiver is the correct one. In case the receiver class has changed, the standard lookup is used instead. Obviously, simple inline caches are not an ideal solution for supporting polymorphic send sites since they already fail if the same message is sent to an alternating list of objects.

PICs [START_REF] Hölzle | Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches[END_REF] store, for a given send site, the method addresses of N past message sends, where N is the cache size. A PIC stores <receiver class, method address> key-value pairs. The Strongtalk [START_REF]Strongtalk Home Page[END_REF] VM is a prominent example of such an environment. It is comprised of a bytecode interpreter and a JIT compiler; the interpreter already stores type feedback information in PICs to speed up message sending. Information stored in these PICs is later exploited by JIT-compiled native code.

Polymorphic Inline Caching in Bytecode Interpreters

We believe that PICs can be beneficial also in solely interpreting VM implementations, such as the Squeak VM [START_REF]Squeak Virtual Machine Home Page[END_REF]. In this section, we outline an implementation proposal for PICs in that environment.

An interpreter does not generate binary code for methods, thus PICs cannot store memory addresses of code. In Squeak, the bytecode is stored in compiled method objects. Here, PICs can store a reference to the compiled method object instead.

The implementation affects both the Squeak VM and reflectively the Smalltalk image. At the image level, each Smalltalk method is represented as an instance of the CompiledMethod class. The format of CompiledMethod instances needs to be modified to store send site type feedback information. In the VM, the interpreter logic must be augmented to support storing and updating of said information.

Squeak CompiledMethods have the layout shown in Fig. 1. The standard object header provides information about the object itself, its class, hash value, etc. The subsequent method header contains information on the method in question, such as the number of arguments, local variables and literals. After that, there are several pointers to the method's literals, each referencing a given constant occurring in the method. For example, all send bytecodes reference their selector (the name of the method to call) as an offset in the literal frame. The bytecode represents the method code, and the trailer carries additional information about the method's source code location. For the PIC implementation in Squeak, the literals region in CompiledMethod instances is of special interest. In the current Squeak system, the compiler gen-erates one slot in the literal frame for any unique selector. This means that send bytecodes sending the same selector reference the same slot in the the literal array (cf. Fig. 1). The Smalltalk compiler needs to be modified to generate one entry in the literal array for each send, without the sharing property mentioned above.

Thus we have as many literal slots storing selectors as there are send bytecodes in the CompiledMethod (cf. Fig. 2). Each of these slots can hold a reference to an object carrying feedback information. To this end, several dedicated classes (described below) to be introduced into the image. Initially, all selector slots contain selectors. Once a send site is visited by the bytecode interpreter and the corresponding message is sent, the selector is replaced by a reference to an inline cache (IC) object (cf. Fig. 3), an instance of the InlineCache class. An IC object contains five values: the selector, the most recent target class of the send, the address of the most recently looked-up method for the selector, a hotness counter, and a trip counter. The bytecode interpreter increases the hotness counter each time it executes the corresponding message send. It then also checks whether the target class is the same as it was when the send was executed the last time. If so, the stored method address is used to retrieve the method implementation to be executed. If the receiver class check fails, the trip counter is increased, and the correct class and implementation are looked up and stored.

If such a send site causes actual lookups too often, its IC object reference can be replaced with a PIC object reference (cf. Fig. 4). A PIC object is organized much like an IC object: it also carries the selector in question and type feedback information. The notable difference is that a PIC object carries up to 8 triples of receiver class, method address, and hotness counter. The bytecode interpreter, when executing the corresponding send, iterates over the PIC and checks for the correct receiver class. Once it finds one already stored, the respective stored method is executed and the pertaining hotness counter is increased. If no matching receiver class is found, lookup proceeds as usual and the result is stored in a free slot of the PIC object if available. It is not necessary to store a hotness counter alongside with each PIC object entry, but future optimizations can benefit from this information (see below).

Summary and Future Optimizations

In the previous sections, we have discussed caching optimization mechanisms for bytecode interpreters. In our opinion, global caches are, although helpful with regard to performance, not fully supportive of dynamic optimizations possible in interpreters. For that we propose the introduction of PICs based on local type feedback.

The locality of type feedback information is a feature of PICs that can be exploited beyond performance improvements in the VM. Type feedback information made available at the image level facilitates optimizations above the abstraction barrier imposed by the Squeak VM.

The AOStA (Adaptively Optimizing Smalltalk Architecture) project [START_REF] Miranda | A Sketch for an Adaptive Optimizer for Smalltalk written in Smalltalk[END_REF] relies on type feedback from the VM to dynamically and adaptively optimize Smalltalk bytecodes in the image using bytecode manipulation. An example of such an optimization is method inlining: based on type feedback information and hotness counter data, methods frequently invoked from a given send site can be inlined directly at the image level, without the need to create stack frames and method context objects.

Originally, AOStA has been conceived for the VisualWorks VM [START_REF]Cincom Home Page[END_REF]. The VisualWorks JIT compiler generates PICs at send sites. A system like AOStA can be beneficial also to purely interpreted systems like Squeak Smalltalk if the underlying interpreter supports type feedback using PICs, as proposed in this paper.

Fig. 1 .

 1 Fig. 1. Object layout of a Squeak CompiledMethod instance.

Fig. 2 .

 2 Fig. 2. A CompiledMethod instance without selector sharing.

Fig. 3 .

 3 Fig. 3. A former literal slot referencing an IC object.

Fig. 4 .

 4 Fig. 4. A PIC object referenced from a CompiledMethod instance.

⋆ Proceedings of the Second Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS'2007), July 2007, ISSN 1436-9915, pp. 17-22.

Acknowledgments. We gratefully acknowledge the financial support of the Swiss National Science Foundation for the project "Analyzing, capturing and taming software change" (SNF Project No. 200020-113342, Oct. 2006 -Sept. 2008).