Franck Maunoury
email: franck.maunoury@upmc.fr

Necessary and sufficient conditions for the existence of α-determinantal processes

Keywords: determinantal process, permanental process, α-determinantal process, αpermanental process, infinitely divisible, complete monotonicity, fermion process, boson process AMS 2010 subject classifications: 60G55, 60E07

We give necessary and sufficient conditions for existence and infinite divisibility of α-determinantal processes. For that purpose we use results on negative binomial and ordinary binomial multivariate distributions.

Introduction

Several authors have already established necessary and sufficient conditions for existence of α-determinantal processes. Macchi in [START_REF] Macchi | The coincidence approach to stochastic point processes[END_REF] and Soshnikov in its survey paper [START_REF] Soshnikov | Determinantal random point fields[END_REF] gave a necessary and sufficient condition for determinantal processes with self-adjoint kernels, which corresponds to the case α = -1. The same condition has also been established in a different way by Hough, Krishnapur, Peres and Virág in [START_REF] Hough | Determinantal processes and independence[END_REF] in the case α = -1. They have also given a sufficient condition of existence in the case α = 1 and self-adjoint kernel. In the special case when the configurations are on a finite space, the paper of Vere-Jones [START_REF] Vere-Jones | Alpha-permanents and their applications to multivariate gamma, negative binomial and ordinary binomial distributions[END_REF] provides necessary and sufficient conditions for any value of α. Finally, Shirai and Takahashi have given sufficient conditions for the existence of an αdeterminantal process for any values of α. However, in the case α > 0, their sufficient condition (Condition B) in [START_REF] Shirai | Random point fields associated with certain Fredholm determinants. I: fermion, Poisson and boson point processes[END_REF] does not work for the following example: the space is reduced to a single point space and the reference measure λ is a unit point mass. With their notations, the two kernels K and J α are respectively reduced to two real numbers k and j α , with

j α = k 1 + αk
We can choose α > 0 and k < 0 such that j α > 0. Under these assumptions, Condition B is fulfilled but the obtained point process has a negative correlation function (ρ 1 (x) = k), which has to be excluded, since a correlation function is an almost everywhere nonnegative function. We are going to strengthen Condition B of Shirai and Takahashi and obtain a necessary and sufficient condition in the case α > 0. This is presented in Theorem 1. Besides, in the case α < 0, we extend the result of Shirai and Takahashi to the case of non self-adjoint kernels and show that the obtained condition is also necessary (Theorems 4 and 5). Moreover, we show that -1/α is necesserely an integer. This has been noticed by Vere-Jones in [START_REF] Vere-Jones | A generalization of permanents and determinants[END_REF] in the case of configurations on a finite space. We also give a necessary and sufficient condition for the infinite divisibility of an αdeterminantal process for all values of α. The main results are presented in Section 3. Section 2 introduces the needed notation. In Section 4, we write a multivariate version of a Shirai and Takahashi formulae on Fredholm determinant expansion. Sections 5 and 6 present the proofs of the results concerning respectively the cases α > 0 and α < 0. The proofs concerning infinite divisibility are presented in Section 7.

Preliminaries

Let E be a locally compact Polish space. A locally finite configuration on E is an integervalued positive Radon measure on E. It can also be identified with a set {(M, α M ) : M ∈ F }, where F is a countable subset of E with no accumulation points (i.e. a discrete subset of E) and, for each point in F , α M is a non-null integer that corresponds to the multiplicity of the point M (M is a multiple point if α M ≥ 2). Let λ be a Radon measure on E. Let X be the space of the locally finite configurations of E. The space X is endowed with the vague topology of measures, i.e. the smallest topology such that, for every real continuous function f with compact support, defined on E , the mapping

X ∋ ξ → f, ξ = x∈ξ f (x) = f dξ is continuous.
Details on the topology of the configuration space can be found in [START_REF] Albeverio | Analysis and geometry on configuration spaces[END_REF]. We denote by B(X ) the corresponding σ-algebra. A point process on E is a random variable with values in X . We do not restrict ourselves to simple point processes, as the configurations in X can have multiple points.

For a n × n matrix A = (a [ij ) 1≤i,j≤n , set:

det α A = σ∈Σn α n-ν(σ) n i=1 a iσ(i)
where Σ n is the set of all permutations on {1, . . . , n} and ν(σ) is the number of cycles of the permutation σ.

For a relatively compact set Λ ⊂ E, the Janossy densities of a point process ξ w.r.t. a Radon measure λ are functions (when they exist) j Λ n :

E n → [0, ∞) for n ∈ N, such that j Λ n (x 1 , . . . , x n ) = n! P(ξ(Λ) = n) π Λ n (x 1 , . . . , x n ) j Λ 0 (∅) = P(ξ(Λ) = 0), where π Λ
n is the density with respect to λ ⊗n of the ordered set (x 1 , . . . , x n ), obtained by first sampling ξ, given that there are n points in Λ, then choosing uniformly an order between the points. For Λ 1 , . . . ,

Λ n disjoint subsets included in Λ, Λ 1 ו••×Λn j Λ n (x 1 , . . . , x n )λ(dx 1 ) . . . λ(dx n
) is the probability that there is exactly one point in each subset Λ i (1 ≤ i ≤ n), and no other point elsewhere.

We recall that we have the following formula, for a non-negative mesurable function f with support in a relatively compact set Λ ⊂ E:

E(f (ξ)) = f (∅) j Λ 0 (∅) + ∞ n=1 1 n! Λ n f (x 1 , . . . , x n ) j Λ n (x 1 , . . . , x n )λ(dx 1 ) . . . λ(dx n ).
For n ∈ N and a ∈ R, we denote a (n) = n-1 i=0 (ai). The correlation functions (also called joint intensities) of a point process ξ w.r.t. a Radon measure λ are functions (when they exist) ρ n : E n → [0, ∞) for n ≥ 1, such that for any family of mutually disjoint relatively compact subsets Λ 1 , . . . , Λ d of E and for any non-null integers n 1 , . . . , n d such that

n 1 + • • • + n d = n, we have E d i=1 ξ(Λ i ) (n i ) = Λ n 1 1 ו••×Λ n d d ρ n (x 1 , . . . , x n )λ(dx 1 ), . . . , λ(dx n ).
Intuitively, for a simple point process, ρ n (x 1 , . . . , x n )λ(dx 1 ) . . . λ(dx n ) is the infinitesimal probability that there is at least one point in the vicinity of each x i (each vicinity having an infinitesimal volume λ(dx i ) around

x i ), 1 ≤ i ≤ n.
Let α be a real number and K a kernel from E 2 to R or C. An α-determinantal point process, with kernel K with respect to λ (also called α-permanental point process) is defined, when it exists, as a point process with the following correlation functions ρ n , n ∈ N with respect to λ:

ρ n (x 1 , . . . , x n ) = det α (K(x i , x j )) 1≤i,j≤n .
We denote by µ α,K,λ the probability distribution of such a point process. We exclude the case of a point process almost surely reduced to the empty configuration.

The case α = -1 corresponds to a determinantal process and the case α = 1 to a permanental process. The case α = 0 corresponds to the Poisson point process. We suppose in the following that α = 0.

We will always assume that the kernel K defines a locally trace class integral operator K on L 2 (E, λ). Under this assumption, one obtains an equivalent definition for the αdeterminantal process, using the following Laplace functional formula:

E µ α,K,λ exp - E f dξ = Det I + αK[1 -e -f ] -1/α (1)
where f is a compactly-supported non-negative function on E, K[1e -f ] stands for √

1e -f K √ 1e -f , I is the identity operator on L 2 (E, λ) and Det is the Fredholm determinant. Details on the link between the correlation function and the Laplace functional of an α-determinantal process can be found in the chapter 4 of [START_REF] Shirai | Random point fields associated with certain Fredholm determinants. I: fermion, Poisson and boson point processes[END_REF]. Some explanations and useful formula on the Fredholm determinant are given in chapter 2.1 of [START_REF] Shirai | Random point fields associated with certain Fredholm determinants. I: fermion, Poisson and boson point processes[END_REF].

For a subset Λ ⊂ E, set: K Λ = p Λ Kp Λ , where p Λ is the orthogonal projection operator from L 2 (E, λ) to the subspace L 2 (Λ, λ).

For two subsets Λ, Λ ′ ⊂ E, set: K ΛΛ ′ = p Λ Kp Λ ′ , and denote by K ΛΛ ′ its kernel. We have for any x, y ∈ E, K ΛΛ ′ (x, y) = 1 Λ (x) 1 Λ ′ (y) K(x, y).

When I + αK (resp. I + αK Λ ) is invertible, J α (resp. J Λ α )
is the integral operator defined by:

J α = K(I + αK) -1 (resp. J Λ α = K Λ (I + αK Λ ) -1
) and we denote by J α (resp. J Λ α ) its kernel. Note that J Λ α is not the orthogonal projection of J α on L 2 (Λ, λ).

Main results

Theorem 1. For α > 0, there exists an α-permanental process with kernel K iff:

• Det(I + αK Λ ) ≥ 1, for any compact set Λ ⊂ E • det α (J Λ α (x i , x j ))
1≤i,j≤n ≥ 0, for any n ∈ N, any compact set Λ ⊂ E and any λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n .

Remark 2.

Even when E is a finite set, note that the second condition of Theorem 1 consists in an infinite number of computations. Finding a simpler condition, that could be checked in a finite number of steps is still an open problem. Theorem 3. For α > 0, if an α-permanental process with kernel K exists, then:

Spec K Λ ⊂ {z ∈ C : Re z > - 1 2α } , for any compact set Λ ⊂ E.
We remark that this condition is equivalent to

Spec J Λ α ⊂ {z ∈ C : |z| < 1 α } , for any compact set Λ ⊂ E Theorem 4.
For α < 0 and K an integral operator such that I + αK Λ is invertible, for any compact set Λ ⊂ E, an α-determinantal process with kernel K exists iff the two following conditions are fulfilled:

(i) -1/α ∈ N (ii) det(J Λ α (x i , x j ))
) ∈ Λ n .
The arguments developed in the proof of Theorem 4 shows that actually (ii) =⇒ (i). Consequently, Condition (ii) is itself a necessary and sufficient condition. It also implies that Det(I + βK Λ ) > 0 for any β ∈ [α, 0] and any compact Λ ⊂ E. Theorem 5. For α < 0 and K an integral operator such that for some compact set Λ 0 ⊂ E, I + αK Λ 0 is not invertible, an α-determinantal process with kernel K exists iff:

(i') -1/α ∈ N (ii') det(J Λ β (x i , x j )) 1≤i,j≤n ≥ 0, for any n ∈ N, any β ∈ (α, 0), any compact set Λ ⊂ E and any λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n .
As in Theorem 4, we also have (ii ′ ) =⇒ (i ′ ) and Condition (ii ′ ) is itself a necessary and sufficient condition.

Note that I + αK Λ 0 is not invertible if and only if there is almost surely at least one point in Λ 0 . Corollary 6. For m a positive integer, the existence of a (-1/m)-determinantal process with kernel K is equivalent to the existence of a determinantal process with the kernel K m .

Corollary 7. For α < 0 and K a self-adjoint operator, an α-determinantal process with kernel K exists iff:

• -1/α ∈ N • Spec K ⊂ [0, -1/α]
This result is well known in the case α = -1 (see for example Hough, Krishnapur, Peres and Virág in [START_REF] Hough | Determinantal processes and independence[END_REF]).

The sufficient part of this necessary and sufficient condition corresponds to condition A in [START_REF] Shirai | Random point fields associated with certain Fredholm determinants. I: fermion, Poisson and boson point processes[END_REF] of Shirai and Takahashi.

Theorem 8. For α < 0, an α-determinantal process in never infinitely divisible.

Theorem 9. For α > 0, an α-determinantal process is infinitely divisible iff

• Det(I + αK Λ ) ≥ 1, for any compact set Λ ⊂ E • σ∈Σn:ν(σ)=1 n i=1 J Λ α (x i , x σ(i) ) ≥ 0, for any n ∈ N, any compact set Λ ⊂ E and λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n .
This theorem gives a more general condition for infinite-divisibility of an α-permanental process than the condition given by Shirai and Takahashi in [START_REF] Shirai | Random point fields associated with certain Fredholm determinants. I: fermion, Poisson and boson point processes[END_REF]. Theorem 10. For K a a real symmetric locally trace class operator and α > 0, an α-permanental process is infinitely divisible iff

• Det(I + αK Λ ) ≥ 1, for any compact set Λ ⊂ E • J Λ α (x 1 , x 2 ) . . . J Λ α (x n-1 , x n )J Λ α (x n , x 1 ) ≥ 0, for any n ∈ N, any compact set Λ ⊂ E and λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n .
Following Griffith and Milne's remark in [START_REF] Griffiths | A class of infinitely divisible multivariate negative binomial distributions[END_REF], when an α-permanental process with kernel K exists and is infinitely divisible, we can replace J α Λ by |J α Λ | and obtain an α-permanental process with the same probability distribution.

Fredholm determinant expansion

In [START_REF] Shirai | Random point fields associated with certain Fredholm determinants. I: fermion, Poisson and boson point processes[END_REF], Shirai and Takahashi have proved the following formula

Det(I -αzK) -1/α = ∞ n=0 z n n! E n det α (K(x i , x j )) 1≤i,j≤n λ(dx 1 ) . . . λ(dx n ) (2)
for a trace class integral operator K with kernel K and for z ∈ C such that αzK < 1.

In the case where the space E is finite, this formula is also given by Shirai in [START_REF] Shirai | Remarks on the positivity of α-determinants[END_REF].

As z → Det(I -αzK) is analytic on C and z → z -1/α is analytic on C * , we obtain that z → Det(I -αzK Λ,α ) -1/α is analytic on {z ∈ C : I -αzK Λ,α invertible}. Therefore, the formula can be extended to the open disc D, centered in 0 with radius

R = sup{r ∈ R + : ∀z ∈ C, |z| < r ⇒ I -αzK is invertible}.
D is the open disc of center 0 and radius 1/ αK , if the operator K is self-adjoint, but it can be larger if K is not self-adjoint.

As remarked by Shirai and Takahashi, the formula ( 2) is valid for any z

∈ C if -1/α ∈ N.
The following proposition extends (2) to a multivariate case.

Proposition 12. Let Λ ⊂ E be a relatively compact set, Λ 1 , . . . Λ d mutually disjoint subsets of Λ and K a locally trace class integral operator with kernel K.

We have the following formula

Det I -α d k=1 z k K Λ k Λ -1/α = ∞ n 1 ,...,n d =0 d k=1 z n k k n k ! Λ n 1 1 ו••×Λ n d d det α (K(x i , x j )) 1≤i,j≤n λ(dx 1 ) . . . λ(dx n ) (3) for any z 1 , . . . , z d ∈ C, such that I -αγ d k=1 z k K Λ k Λ is invertible for any complex number γ satisfying |γ| < 1 (n denotes n 1 + • • • + n d ).
Proof. We apply the formula (2) to the class trace operator d k=1 z k K Λ k Λ and we use the multilinearity property of the α-determinant of a matrix with respect to its rows.

We obtain

Det I -α d k=1 z k K Λ k Λ -1/α = ∞ n=0 1 n! E n det α d k=1 z k K Λ k Λ (x i , x j ) 1≤i,j≤n λ(dx 1 ) . . . λ(dx n ) = ∞ n=0 1 n! E n d k 1 ,...kn=1 det α z k i 1 Λ k i (x i )1 Λ (x j )K(x i , x j ) 1≤i,j≤n λ(dx 1 ) . . . λ(dx n ) = ∞ n=0 1 n! d k 1 ,...kn=1 Λ k 1 ו••×Λ kn det α (z k i K(x i , x j )) 1≤i,j≤n λ(dx 1 ) . . . λ(dx n ) = ∞ n=0 1 n! d k 1 ,...kn=1 n i=1 z k i Λ k 1 ו••×Λ kn det α (K(x i , x j )) 1≤i,j≤n λ(dx 1 ) . . . λ(dx n )
where we have used the fact that

K Λ k Λ (x i , x j ) = 1 Λ k (x i ) 1 Λ (x j )K(x i , x j )
for the equality between the first and the second line.

As the value of the α-determinant of a matrix is unchanged by simultaneous interchange of its rows and its columns, the product z n 1 1 . . . z n d d where n 1 + . . . n d = n, will be repeated n n 1 ...n d times. This gives the desired formula.

For a relatively compact set Λ ⊂ E and Λ 1 , . . . , Λ d mutually disjoint subsets of Λ, the computation of the Laplace functional of an α-determinantal process for the function

f : (z 1 , . . . , z d ) → -d k=1 (log z k )1 Λ k , with z 1 , . . . , z d ∈ (0, 1]
gives thanks to (1):

E µ α,K,λ d k=1 z ξ(Λ k ) k = Det I + α d k=1 (1 -z k ) K Λ k Λ -1/α (4)
which is the probability generating function (p.g.f.) of the finite-dimensional random vector (ξ(Λ 1 ), . . . , ξ(Λ d )).

For α < 0, the formula (4) reminds the multivariate binomial distribution p.g.f. and for α > 0, the multivariate negative binomial distribution p.g.f., given by Vere-Jones in [START_REF] Vere-Jones | Alpha-permanents and their applications to multivariate gamma, negative binomial and ordinary binomial distributions[END_REF], in the special case where the space E is finite.

αpermanental process (α > 0)

Proof of Theorem 1. We first prove that the conditions are necessary. We suppose that there exists an α-permanental process with α > 0, kernel K defining the locally trace class integral operator K.

By taking d = 1 in the formula (4), we have

E µ α,K,λ z ξ(Λ) = Det (I + α(1 -z) K Λ ) -1/α
for any compact set Λ ⊂ E and z ∈ (0, 1].

Thus, Det(I + α(1 -z)K Λ ) ≥ 1 for z ∈ (0, 1]. By continuity (as z → Det(I + (1 -z)K Λ )
is indeed analytic on C), we obtain that Det(I + αK Λ ) ≥ 1, which is the first condition. This implies that for any compact set Λ ⊂ E, I + αK Λ is invertible. Hence J Λ α exists and we have, for any non-negative function f , with compact support included in Λ

E µ α,K,λ   x∈ξ e -f (x)   = Det(I + αK[1 -e -f ]) -1/α = Det(I + αK Λ (1 -e -f )) -1/α = Det(I + αK Λ ) -1/α Det(I -αJ Λ α e -f ) -1/α = Det(I + αK Λ ) -1/α ∞ n=0 1 n! Λ n n i=1 e -f (x i ) det α (J Λ α (x i , x j )) 1≤i,j≤n λ(dx 1 ) . . . λ(dx n ) (5)
where we have used for the equality between the first and the second line the fact that Det(I + AB) = Det(I + BA), for any trace class operator A, and any bounded operator B.

As the Laplace functional defines a.e. uniquely the Janossy density of a point process, one obtains:

det α (J Λ α (x i , x j )) 1≤i,j≤n ≥ 0 λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ E n j Λ α,n (x 1 , . . . , x n ) = Det(I + αK Λ ) -1/α det α (J Λ α (x i , x j )) 1≤i
,j≤n is the Janossy density.

Conversely, if we assume Det(I + αK Λ ) -1/α > 0 and det α (J Λ α (x i , x j )) 1≤i,j≤n ≥ 0 for any n ∈ N, any compact set Λ ⊂ E and any λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n , the Janossy density will be correctly defined and, on any compact set Λ, we get the existence of a point process ξ Λ with kernel K Λ (see Proposition 5.3.II. in [START_REF] Daley | An introduction to the theory of point processes[END_REF] -here the normalization condition is automatic by chosing f = 0 in ( 5)). The restriction of a point process η, defined on Λ ′ ⊂ E, to a subspace Λ ⊂ Λ ′ is the point process denoted η| Λ , obtained by keeping the points in Λ and deleting the points in Λ ′ \Λ. For any compact sets Λ, Λ ′ ⊂ E, such that Λ ⊂ Λ ′ , ξ Λ and ξ Λ ′ | Λ have the same Laplace functional, because we have for any non-negative function f, with compact support included in Λ:

E exp - Λ f dξ Λ ′ | Λ = Det(I + αK Λ ′ [1 -e -f ]) -1/α = Det(I + αK Λ [1 -e -f ]) -1/α = E exp - Λ f dξ Λ .
Therefore, ξ Λ and ξ Λ ′ | Λ have the same probability distribution. We say that the family (L(ξ Λ )), Λ compact set included in E, is consistent.

Then we can obtain a point process on the complete space E by the Kolmogorov existence theorem for point processes (see Theorem 9.2.X in [START_REF] Daley | An introduction to the theory of point processes[END_REF] with

P k (A 1 , . . . , A k ; n 1 , . . . , n k ) = P ξ ∪ k i=1 A i (A 1 ) = n 1 , . . . , ξ ∪ k i=1 A i (A k ) = n k : as ξ ∪ k i=1
A i is a point process, it follows that the properties (i), (iii), (iv) are fulfilled ; (ii) is fulfilled because the family (L(ξ Λ )), Λ compact set included in E, is consistent). As we used, in this second part of the proof, only the fact that Det(I + αK Λ ) -1/α > 0 (instead of Det(I + αK Λ ) -1/α ≥ 1), the assertion in remark 11 is also proved.

Proof of Theorem 3. We suppose there exists an α-permanental process with α > 0, kernel K defining the locally trace class integral operator K.

Then, following the proof of the preceding theorem, we get that, for all z ∈ [0, 1]

Det(I + α(1 -z)K Λ ) = Det(I + αK Λ ) Det(I -αzJ Λ α ) > 0.
As the power series of Det(I -αzJ Λ α ) -1/α has all its terms non-negative,

|(Det(I -αzJ α Λ ) -1/α | ≤ (Det(I -α |z| J α Λ ) -1/α .
If z 0 is a complex number with minimum modulus such that (Det(I -

αz 0 J α Λ ) = 0, by analycity of z → Det(I -αzJ Λ α ) on C and z → z -1 on C * , Det(I -αzJ Λ α ) -1/α converges for |z| < |z 0 | and diverges for z = z 0 . Thus the series diverges in z = |z 0 | and |z 0 | > 1.
This means that the series converges for |z| ≤ 1 thus, in this case, Det(I -αzJ Λ α ) > 0.

This implies the necessary condition: Spec

J Λ α ⊂ {z ∈ C : |z| < 1 α }.
As ν eigenvalue of K is equivalent to ν 1 + αν eigenvalue of J , and as, K and J being compact operators, their non-null spectral values are their eigenvalues, we get the other equivalent necessary condition:

Spec K Λ ⊂ {z ∈ C : Re z > - 1 2α }.
6 αdeterminantal process (α < 0)

We recall the following remark, already made for example in [START_REF] Hough | Determinantal processes and independence[END_REF].

Remark 13. If we define kernels only λ ⊗2 -almost everywhere, there can be problems when we consider only the diagonal terms, as λ ⊗2 {(x, x) : x ∈ Λ} = 0. For example, in the formula

tr K Λ = Λ K(x, x)λ(dx),
tr K Λ is not uniquely defined. To avoid this problem, we write the kernel K Λ as follows:

K Λ (x, y) = ∞ k=0 a k ϕ k (x)ψ k (y)
where (ϕ k ) k∈N , (ψ k ) k∈N are orthonormal basis in L 2 (Λ, λ) and (a k ) k∈N is a sequence of non-negative real number, which are the singular values of the operator K Λ . The functions ϕ k and ψ k , k ∈ N, are defined λ-almost everywhere, but this gives then a unique value for the expression of type

Λ n F (K(x i , x j ) 1≤i,j≤n ) G(x 1 , . . . , x n )λ(dx 1 ) . . . λ(dx n )
where F is an arbitrary complex function from C n 2 and G is an arbitrary complex function from Λ n . With this remark, the quantities that appear with F = det α are well defined.

Lemma 14. Let K be a kernel defined as in Remark 13 and defining a trace class integral operator K on L 2 (Λ, λ), where Λ is a non-λ-null compact set included in the locally compact Polish space E, λ be a Radon measure, n an integer and α a real number. Let F be a continuous fonction from C n 2 to C. The three following assertions are equivalent

(i) F (K(x i , x j ) 1≤i,j≤n ) ≥ 0 λ ⊗n -a.e.(x 1 , . . . , x n ) ∈ Λ n (ii) there exists a set Λ ′ ⊂ Λ such that λ(Λ\Λ ′ ) = 0 and F ((K(x i , x j )) 1≤i,j≤n ) ≥ 0 for any (x 1 , . . . , x n ) ∈ (Λ ′ ) n (iii) there exists a version of K such that F ((K(x i , x j )) 1≤i,j≤n ) ≥ 0 for any (x 1 , . . . , x n ) ∈ Λ n
Proof. (i) is clearly a consequence of (ii). We assume now that (i) is satisfied and we denote by N the λ ⊗n -null set of n-tuples (x 1 , . . . , x n ) ∈ Λ n such that F ((K(x i , x j )) 1≤i,j≤n ) < 0. As in remark 13, we write the kernel K as follows

K(x, y) = ∞ k=0 a k ϕ k (x)ψ k (y) = ( √ a k ϕ k ) k∈N (x)|( √ a k ψ k ) k∈N (y)
where (ϕ k ) k∈N , (ψ k ) k∈N are orthonormal basis in L 2 (Λ, λ), (a k ) k∈N is a sequence of nonnegative real number, which are the singular values of the operator K and .|. denote the inner product in the Hilbert space l 2 (C).

As K is trace class, we have ∞ k=0 a k < ∞. Hence:

∞ k=0 a k |ϕ k (x)| 2 < ∞ and ∞ k=0 a k |ψ k (x)| 2 < ∞ λ-a.e. x
: (x, y) → ( √ a k ϕ k ) k∈N (x)|( √ a k ψ k ) k∈N (y) is continuous on A 2 p .
As E is a Polish space, it can be endowed with a distance that we denote by d. We consider the sets

A ′ p = {x ∈ A p : ∀r > 0, λ(B(x, r) ∩ A p ) > 0} B p,n = {x ∈ A p : λ(B(x, 1/n) ∩ A p ) = 0}
where B(x, r) is the open ball in E of radius r centered at x and n is an integer. Let (x k ) k∈N be a sequence in B p,n converging to x ∈ A p . Then we have, when

d(x, x k ) < 1/n, λ(B(x, 1/n -d(x, x k ) ∩ A p ) ≤ λ(B(x k , 1/n) ∩ A p ) = 0
Therefore λ(B(x, 1/n) ∩ A p ) = 0 and x ∈ B p,n : B p,n is closed, thus compact (as it is included in the compact set A p ).

The set of open balls {B(x, 1/n) : x ∈ B p,n } is a cover of B p,n . Then, by compactness, B p,n can be covered by a finite numbers of such balls. As the intersections of A p and any such a ball is a λ-null set, we get λ(B p,n ) = 0.

Hence we have:

λ(A ′ p ) = λ (A p \ ∪ n∈N B p,n ) = λ(A p ) > λ(Λ) -1/p. Let (x 1 , . . . , x n ) ∈ (A ′ p ) n . If (x 1 , . . . , x n ) / ∈ N, then F ((K(x i , x j )) 1≤i,j≤n ) ≥ 0.
Otherwise (x 1 , . . . , x n ) ∈ N. For any i ∈ 1, n and any r > 0, we have

λ(A p ∩ B(x i , r)) > 0, then λ ⊗n (A n p ∩ B((x 1 , . . . , x n ), r)) = λ ⊗n ( n i=1 (A p ∩ B(x i , r))) > 0.
where B((x 1 , . . . , x n ), r) denotes the open ball of radius r centered at x, in E n endowed with the distance d((x 1 , . . . , x n ), (y 1 , . . . ,

y n )) = max 1≤i≤n d(x i , y i ).
Then, as λ ⊗n (N) = 0, for any q ∈ N, there exists (y

(q)
1 , . . . , y (q) n ) ∈ A n p ∩B((x 1 , . . . , x n ), 1/q)\N and thus (y (q) 1 , . . . , y (q) n ) converge to (x 1 , . . . , x n ) when q → ∞. As (y (q) 1 , . . . , y (q) n ) / ∈ N, F ((K(y

(q) i , y (q) j )) 1≤i,j≤n ) ≥ 0. As K is continuous on A 2
p and F is continuous on C n 2 , we have that the function (x 1 , . . . , x n ) → F ((K(x i , x j )) 1≤i,j≤n ) is continuous on A n p . Hence we have:

F ((K(x i , x j )) 1≤i,j≤n ) ≥ 0. Therefore, in all cases, if (x 1 , . . . , x n ) ∈ (A ′ p ) n , F ((K(x i , x j )) 1≤i,j≤n ) ≥ 0.
As (A p ) p∈N is an increasing sequence, it is the same for (A ′ p ) p∈N . Hence we have:

∪ p∈N (A ′ p ) n = ∪ p∈N A ′ p n .
We obtain:

F ((K(x i , x j )) 1≤i,j≤n ) ≥ 0 for any (x 1 , . . . x n ) ∈ ∪ p∈N A ′ p n As λ(Λ\ ∪ p∈N A ′ p ) = 0, we finally obtain (ii) with Λ ′ = ∪ p∈N A ′ p .
We obtained that (i) and (ii) are equivalent conditions.

(i) is clearly a consequence of (iii). Assume now (ii). We will define a version K 1 of K satisfying the condition (iii).

As λ(Λ) = 0, Λ ′ = ∅. We set an arbitrary

x 0 ∈ Λ ′ . For (x, x ′ ) ∈ Λ 2 , we define, y = x if x ∈ Λ ′ , y = x 0 if x ∈ Λ\Λ ′ , y ′ = x ′ if x ′ ∈ Λ ′ , y ′ = x 0 if x ′ ∈ Λ\Λ ′ and K 1 (x, x ′ ) = K(y, y ′ ). For (x 1 , . . . , x n ) ∈ Λ n , we define, for 1 ≤ i ≤ n, y i = x i if x i ∈ Λ ′ and y i = x 0 if x i ∈ Λ\Λ ′ .
Then we have, F ((K 1 (x i , x j )) 1≤i,j≤n ) = F ((K(y i , y j )) 1≤i,j≤n ) ≥ 0 and K 1 is a version of K satisfying the condition (iii).

Remark 15. Let F n , n ∈ N, be continuous functions from C n 2 to C. For any non-λ -null compact set Λ, the condition:

(i) F n ((J Λ α (x i , x j )) 1≤i,j≤n ) ≥ 0, for any n ∈ N and λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n can always be replaced by the equivalent conditions:

(ii) there exists a set Λ ′ ⊂ Λ such that λ(Λ\Λ ′ ) = 0 and F n ((J Λ α (x i , x j )) 1≤i,j≤n ) ≥ 0, for any n ∈ N and (x 1 , . . . , x n ) ∈ (Λ ′ ) n . or:

(iii) there exists a version of the kernel J such that F n ((J Λ α (x i , x j )) 1≤i,j≤n ) ≥ 0, for any n ∈ N and (x 1 , . . . , x n ) ∈ Λ n .

Proof. The proof of (ii) =⇒ (iii) is done in the same way as in Lemma 14. The other parts of the proof are a direct application of Lemma 14.

Proof that (i) is necessary in Theorem 4. This has been mentioned by Vere-Jones in [START_REF] Vere-Jones | Alpha-permanents and their applications to multivariate gamma, negative binomial and ordinary binomial distributions[END_REF] for the multivariate binomial probability distribution, which corresponds to a determinantal process with E being finite. To our knowledge, this has not been proved in other cases. We consider the n × n matrix 1 n , whose elements are all equal to one.

We have:

n-1 j=0 (1 + jα) = 1 + n-1 k=1 1≤j 1 <•••<j k ≤n-1 j 1 . . . j k α k
We will show by induction on n that the number of permutations in Σ n having n-k cycles for k = 0 is a nk = 1≤j 1 <•••<j k ≤n-1 j 1 . . . j k : this is true for n = 2 and k = 1. Assume it is true for a given n ∈ N * and for any k ∈ 1, n -1 . If we consider the permutations σ ∈ Σ n+1 having n + 1k cycles (0 ≤ k ≤ n), we have 2 cases: -either σ(n + 1) = n + 1: there is exactly a nk permutations corresponding to this case (with the convention a nn = 0, for the case k = n), -or σ(n + 1) = n + 1. Then, if we denote τ n+1 σ(n+1) the transposition in Σ n+1 that exchange n + 1 and σ(n + 1), τ n+1 σ(n+1) • σ is a permutation having n + 1 as fixed point and n + 1k other cycles (with elements in 1, n ): there is exactly na n k-1 permutations corresponding to this case. Then we have

a n+1 n+1-k = a nk + na n k-1 = 1≤j 1 <•••<j k ≤n-1 j 1 . . . j k + 1≤j 1 <•••<j k-1 ≤n-1 j k =n j 1 . . . j k = 1≤j 1 <•••<j k ≤n j 1 . . . j k
which is what we expected. Thus:

det α 1 n = n-1 j=0 (1 + jα). If α < 0 but -1/α / ∈ N, there exists therefore n ∈ N such that det α 1 n < 0.
We suppose that there exists an α-determinantal process with α < 0 but -1/α / ∈ N and kernel K. Then we have det α (K(x i , x j )) 1≤i,j≤n ≥ 0 λ ⊗n -a.e. (x 1 . . . , x n ) ∈ E n . As we exclude the case of a point process having no point almost surely and there is a sequence of compact sets Λ p such that ∪ p∈N Λ p = E, there exists a compact set Λ ∈ E such that

E(ξ(Λ)) = Λ K(x, x)λ(dx) > 0.
Applying Lemma 14, we get that there exist a version K 1 of the kernel K such that det α (K 1 (x i , x j )) 1≤i,j≤n ≥ 0 for any (x 1 . . . , x n ) ∈ Λ n . We also have:

Λ K(x, x)λ(dx) = Λ K 1 (x, x)λ(dx) > 0.
Hence there exists x 0 ∈ Λ such that K 1 (x 0 , x 0 ) > 0. For (x 1 , . . . , x n ) = (x 0 , . . . , x 0 ), we get:

det α (K 1 (x i , x j )) 1≤i,j≤n = K(x 0 , x 0 ) n det α 1 n < 0
which is a contradiction. Therefore if α < 0 and an α-determinantal process exists, then α must be in {-1/m : m ∈ N}.

We consider a d×d square matrix

A. If n 1 , . . . , n d are d non-negative integers, A[n 1 , . . . , n d ] is the (n 1 + • • • + n d ) × (n 1 + • • • + n d ) square matrix composed of the block matrices A ij : A[n 1 , . . . , n d ] =       A 11 A 12 . . . A 1d A 21 A 22 . . . A 2d . . . . . . . . . . . . A d1 A d2 . . . A dd      
, where A ij is the n i × n j matrix whose elements are all equal to a ij (1 ≤ i, j ≤ d).

Lemma 16. Given a d × d square matrix A, the following assertions are equivalent

(i) det -1/m A[n 1 , . . . , n d ] ≥ 0, ∀n 1 , . . . , n d ∈ N (ii) det -1/m A[n 1 , . . . , n d ] ≥ 0, ∀n 1 , . . . , n d ∈ {0, . . . , m} (iii) det A[n 1 , . . . , n d ] ≥ 0, ∀n 1 , . . . , n d ∈ N (iv) det A[n 1 , . . . , n d ] ≥ 0, ∀n 1 , . . . , n d ∈ {0, 1}
Proof. If there exists k ∈ 1, d such that n k > 1, the matrix A[n 1 , . . . , n d ] has at least two identical rows and its determinant is null. So it is clear that (iii) and (iv) are equivalent.

We have:

det(I + ZA) m = ∞ n 1 ,...,n d =0 m n 1 +...n d d k=1 z n k k n k ! det -1/m A[n 1 , . . . , n d ] (6)
where Z = diag(z 1 , . . . , z d ) and z 1 , . . . , z d are d complex numbers. It is a special case of the formula (3) with α = -1/m, finite space E = 1, d and reference measure λ atomic, where each point of E has measure 1, Λ k = {k}, for k ∈ 1, d , Λ = E. Indeed, ZA = d k=1 z k A k , where A k is the d × d square matrix having the same k th row as A and the other rows with all elements equal to 0. The matrix A corresponds to the operator K, the matrix A k corresponds to the operator K Λ k Λ . Formula (6) also corresponds to the one given by Vere-Jones in [START_REF] Vere-Jones | A generalization of permanents and determinants[END_REF].

We also have for m = 1:

det(I + ZA) = 1 n 1 ,...,n d =0 d k=1 z n k k n k ! det A[n 1 , . . . , n d ]. (7)
as det A[n 1 , . . . , n d ] = 0 if there exists k ∈ 1, d such that n k > 1.

(i) is equivalent to the fact that the multivariate power series ( 6) has all its coefficients non-negative.

(iii) is equivalent to the fact that the multivariate power series [START_REF] Hough | Determinantal processes and independence[END_REF] has all its coefficients non-negative.

The power series (6) being the m th power of the power serie [START_REF] Hough | Determinantal processes and independence[END_REF], if there exists k ∈ 1, d such that n k > m, the coefficient of d k=1 z n k is null. Therefore, (i) is equivalent to (ii).

For the same reason, we also have that (i) is a consequence of (iii).

Conversely, following Vere-Jones in [START_REF] Vere-Jones | Alpha-permanents and their applications to multivariate gamma, negative binomial and ordinary binomial distributions[END_REF], we can show by induction on the order of the matrix A, that the fact that the power series ( 6) has all its coefficients non-negative implies that the power series [START_REF] Hough | Determinantal processes and independence[END_REF] has all its coefficient non negative. This proves the equivalence between (i) and (iii).

Proposition 17. Let α < 0 and K be an integral operator such that I + αK Λ is invertible, for any compact set Λ ⊂ E. An α-determinantal process with kernel K exists iff: Proof. We assume that there exists an α-determinantal process ξ with kernel K.

det α (J Λ α (x i , x j )) 1≤i,
We already proved that it is necessary to have -1/α ∈ N.

E z ξ(Λ) = Det (I + α(1 -z) K Λ ) -1/α
for any compact set Λ ⊂ E and z ∈ (0, 1].

Then Det (I + α(1z) K Λ ) > 0 for z ∈ (0, 1], and by continuity, Det (I + α K Λ ) ≥ 0. As we assumed that I + αK Λ is invertible, we have necessarily Det (I + α K Λ ) > 0.

For any non-negative function f , with compact support included in Λ

E   x∈ξ e -f (x)   = Det(I + αK[1 -e -f ]) -1/α = Det(I + αK Λ ) -1/α Det(I -αJ Λ α e -f ) -1/α = Det(I + αK Λ ) -1/α ∞ n=0 1 n! Λ n n i=1 e -f (x i ) det α (J Λ α (x i , x j )) 1≤i,j≤n λ(dx 1 ) . . . λ(dx n )
As the Laplace functional defines a.e. uniquely the Janossy density of a point process, one obtains:

det α (J Λ α (x i , x j )) 1≤i,j≤n ≥ 0 λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ E n
Conversely, we assume that the condition det α (J Λ α (x i , x j )) 1≤i,j≤n ≥ 0, for any n ∈ N, λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n and any compact set Λ. is fulfilled. We have

Det(I -αzJ Λ α ) -1/α = ∞ n=0 z n n! Λ n det α (J Λ α (x i , x j )) 1≤i,j≤n λ(dx 1 ) . . . λ(dx n )
As -1/α ∈ N, this formula is valid for any z ∈ C. Then we obtain for z = 1, Det(I -αJ Λ α ) -1/α ≥ 0. We also have (I -αJ Λ α )(I + αK Λ ) = (I + αK Λ )(I -αJ Λ α ) = I. Then Det(I -αJ Λ α ) > 0 and Det(I + αK Λ ) > 0. Thus the Janossy density is correctly defined and, on any compact set Λ we get the existence of a point process with kernel K and reference mesure λ. Then it can be extended to the complete space E by the Kolmogorov existence theorem (see Theorem 9.2.X in [START_REF] Daley | An introduction to the theory of point processes[END_REF]).

Proof of Theorem 4. For any m ∈ N, applying Lemma 16, we have for any compact set Λ det -1/m (J Λ -1/m (x i , x j )) 1≤i,j≤n ≥ 0, for any n ∈ N, and any (x 1 , . . . , x n ) ∈ Λ n is equivalent to det(J Λ -1/m (x i , x j )) 1≤i,j≤n ≥ 0, for any n ∈ N, and any (x 1 , . . . , x n ) ∈ Λ n Therefore, (L(ξ p k )) k∈N is tight. As E is Polish, X is also Polish (endowed with the Prokhorov metric). Thus there is a subsequence of (L(ξ p k )) k∈N converging weakly to the probability distribution of a point process ξ. By unicity of the distribution of an αdeterminantal process for given kernel and reference measure, ξ must be an α-determinantal process with kernel K, which gives the existence.

Lemma 18. Let J be a trace class self-adjoint integral operator with kernel J. We have det(J(x i , x j )) 1≤i,j≤n ≥ 0 for any n ∈ N, λ ⊗n -a.e.(x 1 , . . . , x n ) ∈ Λ n if and only if

Spec J ⊂ [0, ∞)
Proof. If we assume that the operator J is positive, the kernel can be written as follows:

J(x, y) = ∞ k=0 a k ϕ k (x)ϕ k (y)
where a k ≥ 0 for k ∈ N.

Hence: det(J(x i , x j )) 1≤i,j≤n ≥ 0 for any n ∈ N, and any (x 1 , . . . , x n ) ∈ Λ n Conversely, assume that det(J(x i , x j )) 1≤i,j≤n ≥ 0 for any n ∈ N, λ ⊗n -a.e.(x 1 , . . . , x n ) ∈ Λ n .

From formula (2) with α = -1, we have then for any z ∈ C

Det(I + zJ ) = ∞ n=0 z n n! E n det(J(x i , x j )) 1≤i,j≤n λ(dx 1 ) . . . λ(dx n ). ( 9
)
As J is assumed to be self-adjoint, its spectrum is included in R. Thanks to [START_REF] Shirai | Random point fields associated with certain Fredholm determinants. I: fermion, Poisson and boson point processes[END_REF], it is impossible to have an eigenvalue in R * -, as the power series has all its coefficients real non-negative and the first coefficient (n = 0) is real positive. Hence Spec J ⊂ [0, ∞).

Proof of Corollary 7. We assume: -1/α ∈ N and Spec K ⊂ [0, -1/α]. Then we have, as K is self-adjoint, that for any compact set Λ, Spec K Λ ⊂ [0, -1/α]. Then Det(I+βK Λ ) > 0 for any β ∈ (α, 0]. If I + αK Λ is invertible for any compact set Λ ⊂ E, we have Spec J Λ α ⊂ [0, ∞) and J Λ α is a trace class self adjoint operator for any compact set Λ. Then, applying Lemma 18, we get that det(J(x i , x j )) 1≤i,j≤n ≥ 0 for any n ∈ N, compact set Λ and λ ⊗n -a.e.(x 1 , . . . , x n ) ∈ Λ n Using Theorem 4, we get the existence of an α-determinantal process with kernel K.

When there exists a compact set Λ 0 such that I + αK Λ 0 is not invertible, by the same line of proof, we obtain the announced result, using Theorem 5.

Conversely, we assume that there exists an α-determinantal process with kernel K. Then, from Theorem 4 or 5, we get that -1/α ∈ N. If I + αK Λ is invertible for any compact set Λ ⊂ E, we have Spec J Λ α ⊂ [0, ∞), using Theorem 4 and lemma 18. Then Spec K Λ ⊂ [0, -1/α) ⊂ [0, -1/α], for any compact set Λ. If there exists a compact set Λ 0 such that I + αK Λ 0 is not invertible, we have Spec J Λ β ⊂ [0, ∞) for any compact set Λ and any β ∈ (α, 0), using Theorem 5 and lemma 18. Then Spec K Λ ⊂ [0, -1/β) for any β ∈ (α, 0). Therefore Spec K Λ ⊂ [0, -1/α] for any compact set Λ. As K is self-adjoint, this implies in both cases that Spec K ⊂ [0, -1/α].

Remark 19. Using the known result in the case α = -1 (see for example Hough, Krishnapur, Peres and Virág in [START_REF] Hough | Determinantal processes and independence[END_REF]) and corollary 6, one obtains a direct proof of Corollary 7.

Infinite divisibility

Proof of Theorem 8. For α < 0, we have proved that it is necessary to have -1/α ∈ N. If an α-determinantal process was infinitely divisible, with α < 0, it would be the sum of N i.i.d αN-determinantal processes for any N ∈ N * , as it can be seen for the Laplace functional formula [START_REF] Albeverio | Analysis and geometry on configuration spaces[END_REF]. This would imply that -1/(Nα) ∈ N, for any N ∈ N * , which is not possible. Therefore, an α-determinantal process with α < 0 is never infinitely divisible. Some charactization on infinite divisibility have also been given in [START_REF] Eisenbaum | On permanental processes[END_REF] in the case α > 0. Then, for any N ∈ N * and any compact set Λ ∈ E, det N α (J Λ α (x i , x j )/N) 1≤i,j≤n ≥ 0. From Theorem 1, we get that there exists a (Nα)-permanental process with kernel K/N. This means that an α-permanental process with kernel K is infinitely divisible.

Conversely, if we assume an α-permanental process with kernel K is infinitely divisible, we get the existence of a Nα-permanental process with kernel K/N, for any N ∈ N * . From Theorem 1, we have that Det(I + αK Λ ) ≥ 1 for any compact set Λ ∈ E. We also have 1 (Nα) n-1 det N α (J Λ α (x i , x j )) 1≤i,j≤n ≥ 0, for any N ∈ N * , any n ∈ N, any compact set Λ ∈ E and λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n . When N tends to ∞, we obtain:

σ∈Σn:ν(σ)=1 n i=1 J Λ α (x i , x σ(i) ) ≥ 0,
which is the desired result.

Proof of Theorem 10. We use the argument of Griffiths in [START_REF] Griffiths | Multivariate gamma distributions[END_REF] and Griffiths and Milne in [START_REF] Griffiths | A class of infinitely divisible multivariate negative binomial distributions[END_REF]. Assume

σ∈Σn:ν(σ)=1 n i=1 J Λ α (x i , x σ(i) ) ≥ 0,
for any n ∈ N and any (x 1 , . . . , x n ) ∈ Λ n . The condition J Λ α (x 1 , x 2 ) . . . J Λ α (x n-1 , x n )J Λ α (x n , x 1 ) ≥ 0 is satisfied for the elementary cycles, i.e. cycles such that J Λ α (x i , x j ) = 0 if i < j + 1 and (i = 1 or j = n). Then it can be extended to any cycle by induction, using J Λ α (x i , x j ) = J Λ α (x j , x i ).

With Lemma 14, we can then extend the proof to the case when σ∈Σn:ν(σ)=1 n i=1 J Λ α (x i , x σ(i) ) ≥ 0, for any n ∈ N and λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n .

Remark 20. Note that the argument from Griffiths and Milne in [START_REF] Griffiths | Multivariate gamma distributions[END_REF] and [START_REF] Griffiths | A class of infinitely divisible multivariate negative binomial distributions[END_REF] is only valid for real symmetric matrices.

Remark 11 .

 11 In Theorem 1, 9 and 10 , the condition Det(I + αK Λ ) ≥ 1, for any compact set Λ ⊂ E can be replaced by Det(I + αK Λ ) > 0, for any compact set Λ ⊂ E.

8 )Condition ( 8 )

 88 j≤n ≥ 0, for any n ∈ N, and any compact set Λ λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n (implies that -1 α ∈ N and Det(I + βK) > 0 for any β ∈ [α, 0].

Proof of Theorem 9 .

 9 For α > 0, assume that Det(I + αK Λ ) ≥ 1 andσ∈Σn:ν(σ)=1 n i=1 J Λ α (x i , x σ(i) ) ≥ 0,for any compact set Λ ⊂ E, n ∈ N and λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n . Then we have:σ∈Σn:ν(σ)=k n i=1 J Λ α (x i , x σ(i) ) = {I 1 ,...,I k } partition of 1,n σ 1 ∈Σ(I 1 ),...,σ k ∈Σ(I k ): ν(σ 1 )=•••=ν(σ k )=1 k q=1 i∈Iq J Λ α (x i , x σq(i) set Λ ⊂ E, n ∈ N, k ∈ 1, n and λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n , where, for a finite set I, Σ(I) denotes the set of all permutations on I.

  1≤i,j≤n ≥ 0, for any n ∈ N, any compact set Λ ⊂ E and any λ ⊗n -a.e. (x 1 , . . . , x n

Acknowledgements

I express sincere thanks to Nathalie Eisenbaum for her support in the writing of this paper. I also thank the referee for his valuable comments that helped in improving the exposition.

Now, assume we only have det -1/m (J Λ -1/m (x i , x j )) 1≤i,j≤n ≥ 0, for any n ∈ N, λ ⊗n -a.e. (x 1 , . . . , x n ) ∈ Λ n .

By lemma 14, for each n ∈ N, there exists a set Λ

Then, by Lemma 16, we have: det(J Λ -1/m (x i , x j )) 1≤i,j≤n ≥ 0, for any n ∈ N and (x 1 . . . , x n ) ∈ (Λ ′ ) n . Therefore, we have

The converse is done through a similar proof, using Lemma 14 and 16. Thus, we obtain:

Theorem 4 is then a consequence of Proposition 17.

Proof of Theorem 5. We assume that there exists ξ an α-determinantal process with kernel K.

For p ∈ (0, 1), let ξ p be the process obtained by first sampling ξ, then independently deleting each point of ξ with probability 1p.

Computing the correlation functions, we obtain that ξ p is an α-determinantal process with kernel pK. Thus we get from Theorem 4 that the conditions of the theorem must be fulfilled.

Conversely, we assume that these conditions are fulfilled. We obtain from Theorem 4 that an α-determinantal process ξ p with kernel pK exists, for any p ∈ (0, 1). We consider a sequence (p k ) ∈ (0, 1) N converging to 1 and a compact Λ.

As t → Det(I + αK Λ (1e -t ))


Amine Benelallam

Abel Gómez

Llana Massimo Tisi

Jordi Cabot
email: jordi.cabot@icrea.cat

Distributed Model-to-Model Transformation with ATL on MapReduce

Keywords: D.2.1 [Software Engineering]: Requirements/ Specifications-Languages, Tools; C.2.4 [Distributed Systems]: Distributed applications Languages, Performance Model Transformation, Distributed Computing, MapReduce, ATL, Language Engineering

Efficient processing of very large models is a key requirement for the adoption of Model-Driven Engineering (MDE) in some industrial contexts. One of the central operations in MDE is rule-based model transformation (MT). It is used to specify manipulation operations over structured data coming in the form of model graphs. However, being based on computationally expensive operations like subgraph isomorphism, MT tools are facing issues on both memory occupancy and execution time while dealing with the increasing model size and complexity. One way to overcome these issues is to exploit the wide availability of distributed clusters in the Cloud for the distributed execution of MT.

In this paper, we propose an approach to automatically distribute the execution of model transformations written in a popular MT language, ATL, on top of a well-known distributed programming model, MapReduce. We show how the execution semantics of ATL can be aligned with the MapReduce computation model. We describe the extensions to the ATL transformation engine to enable distribution, and we experimentally demonstrate the scalability of this solution in a reverse-engineering scenario.

Introduction

Model-Driven Engineering (MDE) is gaining ground in industrial environments, thanks to its promise of lowering software development and maintenance effort [START_REF] Kärnä | Evaluating the use of domain-specific modeling in practice[END_REF]. It has been adopted with success in producing software for several domains like civil engineering [START_REF] Volk | Building Information Modeling (BIM) for Existing Buildings: Literature Review and Future Needs[END_REF], car manufacturing [START_REF] Kuhn | An Exploratory Study of Forces and Frictions Affecting Large-Scale Model-Driven Development[END_REF] and modernization of legacy software systems [START_REF] Bruneliére | MoDisco: A Model Driven Reverse Engineering Framework[END_REF]. Core concepts of MDE are the centrality of (software, data and system) models in all phases of software engineering and the automation of model processing during the software life-cycle. Model Transformation (MT) languages have been designed to help users specifying and executing these model-graph manipulations. They are often used in implementing tooling for software languages, especially domain-specific [START_REF] Zschaler | Domain-specific metamodelling languages for software language engineering[END_REF], e.g. in reverse engineering [START_REF] Bruneliére | MoDisco: A Model Driven Reverse Engineering Framework[END_REF]. The AtlanMod Transformation Language (ATL) [START_REF] Jouault | ATL: A Model Transformation Tool[END_REF] is one of the most popular examples among them, and a plethora of transformations exist addressing different model types and intentions1 .

Similarly to other software engineering approaches, MDE has been recently facing the growing complexity of data and systems, that comes in MDE in the form of Very Large Models (VLMs) [START_REF] Clasen | Transforming Very Large Models in the Cloud: a Research Roadmap[END_REF]. For example, the Building Information Modeling language (BIM) [START_REF] Volk | Building Information Modeling (BIM) for Existing Buildings: Literature Review and Future Needs[END_REF] contains a rich set of concepts (more than eight hundred) for modeling different aspects of physical facilities and infrastructures. A building model in BIM is typically made of several gigabytes of densely interconnected graph nodes. Existing MDE tools, including MT engines, are based on graph matching and traversing techniques that are facing serious scalability issues in terms of memory occupancy and execution time. This stands especially when MT execution is limited by the resources of a single machine. In the case study that we selected for our experimentation, we show how typical MT tasks in the reverseengineering of large Java code bases take several hours to compute in local.

One way to overcome these issues is exploiting distributed systems for parallelizing model manipulation (processing) operations over computer clusters. This is made convenient by the recent wide availability of distributed clusters in the Cloud. MDE developers may already build distributed model transformations by using a general-purpose language and one of the popular distributed programming models such as MapReduce [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF] or Pregel [START_REF] Malewicz | Pregel: A System for Largescale Graph Processing[END_REF]. However such development is not trivial. Distributed programming (i) requires familiarity with concurrency theory that is not common among MDE application developers, (ii) introduces a completely new class of errors w.r.t. sequential programming, linked to task synchronization and shared data access, (iii) entails complex analysis for performance optimization.

In this paper we show that ATL, thanks to its specific level of abstraction, can be provided with semantics for implicit distributed execution. As a rule-based language, ATL allows the declarative definition of correspondences and data flows between elements in the source and target model. By our proposed semantics, these correspondence rules can be efficiently run on a distributed cluster. The distribution is implicit, i.e. the syntax of the MT language is not modified and no primitive for distribution is added. Hence developers are not required to have any acquaintance with distributed programming.

The semantics we propose is aligned with the MapReduce computation model, thus showing that rule-based MT fits in the class of problems that can be efficiently handled by the MapReduce abstraction. We demonstrate the effectiveness of the approach by making an implementation of our solution publicly available 2 and by using it to experimentally measure the speed-up of the transformation system while scaling to larger models and clusters. We identify specific properties of the ATL language that make the alignment possible and the resulting solution efficient. In future work we plan to study how our approach may be generalized to other MT languages (e.g. QVT [START_REF]Query/View/Transformation, QVT[END_REF] and ETL [START_REF] Kolovos | The epsilon transformation language[END_REF]) that share some properties with ATL.

The interest of this work extends also outside the MDE community, as we perform the first steps for proposing the rule-based MT paradigm as a high level abstraction for data transformation on MapReduce. High-level languages have already been proposed for data querying (as opposed to data transformation) on MapReduce [START_REF] Chaiken | SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets[END_REF][START_REF] Olston | Pig latin: a not-so-foreign language for data processing[END_REF][START_REF] Thusoo | Hive: a warehousing solution over a map-reduce framework[END_REF]. In the MapReduce context, they allow for independent representation of queries w.r.t. the program logic, automatic query optimization and maximization of query reuse [START_REF] Lee | Parallel Data Processing with MapReduce: A Survey[END_REF]. We want to extend this approach, aiming at obtaining similar benefits in data transformation scenarios.

The paper is structured as follows. Section 2 describes the running case of the paper, and uses it to introduce the syntax of ATL and its execution semantics. Section 3 describes the distributed execution of ATL over MapReduce. Section 4

Running Example: Model Transformation for Data-Flow Analysis

While our distribution approach is applicable to model transformations in any domain, to exemplify the discussion we refer throughout the paper to a single case study related to the analysis of data-flows in Java programs. The case study is well-known in the MDE community, being proposed by the Transformation Tool Contest (TTC) 2013 [START_REF] Horn | The TTC 2013 Flowgraphs Case[END_REF] as a benchmark for MT engines. We focus on one phase of the scenario, the transformation of the control-flow diagram of a Java program into a data-flow diagram. Such task would be typically found in real-world model-driven applications on program analysis and reverse engineering of legacy code [START_REF] Bruneliére | MoDisco: A Model Driven Reverse Engineering Framework[END_REF]. Excerpts of the source and target metamodels of this step are shown in Fig. 2. In a control-flow diagram (Fig. 2a), a FlowInstruction (FlowInstr) has a field txt containing the textual code of the instruction, a set of variables it defines or writes (def ), and a set of variables it reads (use). A FlowInstruction points to the potential set of instructions that may be executed after it (cfNext). Method signatures and SimpleStatements (SimpleStmt) are kinds of FlowInstruction. A Parameter is a kind of Variable that is defined in method signatures.

The data-flow diagram (Fig. 2b) has analogous concepts of FlowInstruction, Method and SimpleStatements but a different topology based on the data-flow links among instructions (dfNext). For every flow instruction n, a dfNext link has to be created from all nearest control-flow predecessors m that define a variable which is used by n. Formally [START_REF] Horn | The TTC 2013 Flowgraphs Case[END_REF]:

m → df N ext n ⇐⇒ def (m) ∩ use(n) = ∅ ∧ ∃ P ath m = n 0 → cf N ext . . . → cf N ext n k = n : (def (m) ∩ use(n))\ 0<i<k def (n i ) = ∅ (1)
Fig. 1 shows an example of models for each metamodel, derived from a small program calculating a number factorial. As it can be seen in the figure, the transformation changes the topology of the model graph, the number of nodes and their content, and therefore can be regarded as a representative example of general transformations. In this paper we refer to an ATL implementation of the transformation named ControlFlow2DataFlow and available at the article website 2 .

Model transformations in ATL are unidirectional. They are applied to read-only source models and produce writeonly target models. ATL developers are encouraged to use declarative rules to visualize and implement transformations. Declarative rules abstract the relationship between source and target elements while hiding the semantics dealing with rule triggering, ordering, traceability management and so on. However, rules can be augmented with imperative sections to simplify the expression of complex algorithms. In this paper, we focus on declarative-only ATL.

Languages like ATL are structured in a set of transformation rules encapsulated in a transformation unit. These transformation units are called modules (Listing 1, line 1). The query language used in ATL is the OMG's Object Constraints Language (OCL) [START_REF]Object Constraint Language, OCL[END_REF]. A significant subset of OCL data types and operations is supported in ATL. Listing 1 shows a subset of the rules in the ControlFlow2DataFlow transformation and Listing 2 an excerpt of its OCL queries (helpers).

ATL matched rules are composed of a source pattern and a target pattern. Both of source and target patterns might contain one or many pattern elements. Input patterns are fired automatically when an instance of the source pattern (a match) is identified, and produce an instance of the corresponding target pattern in the output model. Implicitly, transient tracing information is built to associate input elements to their correspondences in the target model.

Source patterns are defined as OCL guards over a set of typed elements, i.e. only combinations of input elements satisfying that guard are matched. In ATL, a source pattern lays within the body of the clause 'from' (Listing 1, line 14). For instance, in the rule SimpleStmt, the source pattern (List-Listing 1: ControlFlow2DataFlow -ATL transformation rules (excerpt) → S e q u e n c e { fi } , self , S e q u e n c e { } , self . →definers ( d )->excluding ( self ) ) ) )

1 module ControlFlow2DataFlow ;
5 ->flatten ( ) ; OCL helpers enable the definition of reusable OCL expressions. An OCL helper must be attached to a context, that can be a type or global context. Since target models are not navigable, only source types are allowed. Listing 2 shows our implementation of the computeNextDataFlows helper derived by the direct translation in OCL of the data-flow definition we gave in Equation 1. It has as context FlowInstr and returns a sequence of same type (Listing 2, line 1).

) = input ->collect ( i | i . →cfPrev ) ->flatten ( ) ->reject ( i | →visited ->exists ( v | v = i ) or →forbidden ->exists ( f | f = i ) ) i n 10 i f newInput ->isEmpty ( ) t
ATL matched rules are executed in two phases, a match phase and an apply phase. In the first phase, the rules are applied over source models' elements satisfying their guards. Each single match, corresponds to the creation of an explicit traceability link. This link connects three items: the rule that triggered the application, the match, and the newly created output elements (according to the target pattern). At this stage, only output pattern elements type is considered, bindings evaluation is left to the next phase.

The apply phase deals with the initialization of output elements' features. Every feature is associated to a binding in an output pattern element of a given rule application. Indeed, a rule application corresponds to a trace link. Features initialization is performed in two steps, first the corresponding binding expression is computed. Resulting in a collection of elements, it is then passed to a resolution algorithm (called resolve algorithm) for final update into the output model. The resolve algorithm behaves differently according to the type of each element. If the type is primitive (in case of attributes) or target, then it is directly assigned to the feature. Otherwise, if it is a source element type, it is first resolved to its respective target element -using the tracing information -before being assigned to the feature. Thanks to this algorithm we are able to initialize the target features without needing to navigate the target models.

It is noteworthy that the helpers' implementation illustrated in the paper is compact and straightforward (for an OCL programmer at least) but it has quadratic time complex-ity in the worst case (as the definition in Equation 1) 3 . As a consequence it does not scale to inter-procedural data-flow analysis of large code-bases like the ones typically found during modernization of legacy systems [START_REF] Bruneliére | MoDisco: A Model Driven Reverse Engineering Framework[END_REF]. In our experimental evaluation we will show that already for medium sized code bases (100,000 lines of code), the processing time of the full ControlFlow2DataFlow transformation might take several hours (more than 4 hours for our code base).

ATL on MapReduce

MapReduce is a programming model and software framework developed at Google in 2004 [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF]. It allows easy and transparent distributed processing of big data sets while concealing the complex distribution details a developer might cross. MapReduce is inspired from the map and reduce primitives that exist in functional languages. Both Map and Reduce invocations are distributed across cluster nodes, thanks to the Master that orchestrates jobs assignment.

Input data is partitioned into a set of chunks called Splits as illustrated in Fig. 3. The partitioning might be monitored by the user throughout a set of parameters. If not, splits are automatically and evenly partitioned. Every split comprises a set of logical Records, each containing a pair of key, value .

Given the number of Splits and idle nodes, the Master node decides the number of workers (slave machines) for the assignment of Map jobs. Each Map worker reads one or many Splits, iterates over the Records, processes the key, value pairs and stores locally the intermediate key, value pairs. In the meanwhile, the Master receives periodically the location of these pairs. When Map workers finish, the Master forwards these locations to the Reduce workers that sort them so that all occurrences of the same key are grouped together. The mapper then passes the key and list of values to the user-defined reduce function. Following the reduce tasks achievement, an output result is generated per reduce task. Output results do not need to be always combined, especially if they will subsequently be processed by other distributed applications.

Let's take a closer look to the MapReduce programming model by means of a simple example, depicted in Fig. 3. Assume we have set of log entries coming from a git repository. Each entry contains information about actions performed over a particular file (creation → + , deletion → X, or modification → * ). We want to know how many times each action was performed, using MapReduce. The master evenly splits the entries among workers. For every record (log entry), the map worker extracts the action type and creates a key,value pair with a key the action itself and value '1'. In the reduce phase, pairs with the same key are grouped together. In our example, the modification and deletion go to the first reducer, while the creation goes to the second one. For each group, the reducer combines the pairs, and creates a key,value pair, but this time with value the sum of the values with same key. This value refers to how many times the action occurred in the logs.

Much of the interest of MapReduce is due to its faulttolerant processing. The Master keeps track of the evolution of every worker execution. If after a certain amount of time a worker does not react, it is considered as idle and the job is re-assigned to another worker.

ATL and MapReduce Alignment

Transformations in ATL could be regarded as the union of elementary transformation tasks, where each takes charge of transforming a pattern of model elements. The approach we are proposing follows a data-distribution scheme, where each one of the nodes that are computing in parallel takes charge of transforming a part of the input model. This is made possible, thanks to the semantics alignment for ATL distributed execution with MapReduce described in this section.

However, implicit data distribution is not trivial for transformation languages where rules applied to different parts of the model can interact in complex ways with each other. As result of ATL's execution semantics, especially four specific properties of the language (below), we argue that inter-rule communication is made discernible. More precisely, interaction among ATL transformation rules are reduced to bindings resolution, where a target element's feature needs to reference to other target elements created by other rules:

1. Locality. Each ATL rule is the only one responsible of the computation of the elements it creates, i.e., the rule that creates the element is also responsible of initializing its features. In case of bi-directional references, responsibility is shared among the rules that create the source and the target ends of the reference. 4. Forbidden target navigation. Rules are not allowed to navigate the part of the target model that has already been produced, to avoid assumptions on the rule execution order. Thanks to the resolve algorithm along with the trace links that it is made possible. These properties strongly reduce the possible kinds of interaction among ATL rules, and allow us to decouple rule applications and execute them in independent execution units, as explained in the following.

As an example, Fig. 4 shows how the ATL transformation of our running example could be executed on top of a MapReduce architecture comprising three nodes, two map and one reduce workers. The input model is equally split according to the number of map workers (in this case each map node takes as input half of the input model elements). In the map phase, each worker runs independently the full transformation code but applies it only to the transformation of the assigned subset of the input model. We call this phase Local match-apply. Afterwards each map worker communicates the set of model elements it created to the reduce phase, together with trace information. These trace links (grey arrows in Fig. 4) encode the additional information that will be needed to resolve the binding, i.e. identify the exact target element that has to be referenced based on the tracing information. The reduce worker is responsible of gathering partial models and trace links from the map workers, and updating properties value of unresolved bindings. We call this phase Global resolve.

In the following (i) we describe the distributed execution algorithm we propose for ATL decomposing it in the Local match-apply phase assigned to mappers and the Global resolve phase assigned to reducers; (ii) we define the trace information that needs to be passed between mappers and reducers to allow the re-composition of the global model after distribution.

Local Match-Apply

At the beginning of the phase, input splits are assigned to map workers. Each one of these splits contains a subset of the input model for processing. Although, each worker has a full view of the input models in case it needs additional data for bindings computation. Note that while intelligent assignment strategies could improve the algorithm efficiency by increasing data locality, in this paper we perform a random assignment. Intelligent assignment strategies for The pseudo-code for the processing in this phase is given in Algorithm 1. For every model element in the split, the map function verifies if a rule guard matches and in this case instantiates the corresponding target elements (line 2), same as in the regular execution semantics (Sec. 2). In the case of rules that match multiple elements, the map function would consider the elements of the split as the first element of the matched pattern, and look for combinations of other elements satisfying the guard. For instance, in Fig. 1 the Method and FlowInstr rules instantiate the method signature and the instructions that define or use variables (all the instructions of the example). Variables (a and r) are not instantiated since no rule matches their type. For each instantiated output element, Subsequently, the algorithm starts processing the list of property bindings for the instantiated target elements. We extended the behavior of the resolve algorithm to enable handling elements transformed in other nodes, we call this algorithm local resolve. In the case of attribute bindings, the same standard behavior is preserved, the OCL expression is computed and the corresponding feature is updated accordingly (lines 4-5). While bindings related to references connect elements transformed by different rule applications, potentially in different nodes, the resolution is performed in two steps: (i) the OCL expression of the binding computes to a set of elements in the source model and ATL connects the bound feature to these source elements using trace links; (ii) the source-models elements are resolved, i.e. substituted with the corresponding target element according the rule application trace links. If source and target elements of the reference are both being transformed in the same node, both steps hap-pen locally (lines 8-9), otherwise trace links are stored and communicated to the reducer, postponing the resolution step to the Global resolve phase (lines 11-12).

For example, executing the binding dfNext over the method fact(int a), results in {while(a)>0, r*=a--;} (dashed grey arrows in Fig. 6 (a)). Since while(a) and fact(int a) reside in the same node, a dfNext reference between them is created in the target model. Instead, a trace property is created between fact(int a) and r*=a--; because they belong to different nodes( Fig. 6 (b)).

Global Resolve

At the beginning of the reduce phase, all the target elements are created, the local bindings are populated, and the unresolved bindings are referring to the source elements to be resolved. This information is kept consistent in the tracing information formerly computed and communicated by the mappers. Then it resolves the remaining reference bindings by iterating over the trace links, as depicted in Algorithm 2. For each trace link, the reducer iterates over the unresolved elements of its property traces (line 3), resolves their corresponding element in the output model (line 4), and updates the target element with the final references(line 5). In the right-hand side of Fig. 1 all the trace properties have been substituted with final references to the output model elements.

Trace Metamodel

MT languages like ATL need to keep track during execution of the mapping between source and target elements [START_REF] Yie | Advanced Traceability for ATL[END_REF]. We define a metamodel for transformation trace information in a distributed setting (see Fig. 5).

As in standard ATL, traces are stored in a TracelinkSet and organized by rules. Each TracedRule is identified by its name, and may contain a collection of trace links. A link maps a set of source pattern elements to a set of target pattern elements. Both source and target pattern elements are identified by a unique name within a trace link (same one in the rule). Likewise, source elements and target elements refer to a runtime object respectively from input model or output model. This layered decomposition breaks down the complexity of traversing/querying the trace links.

This trace information (source elements, rule name, and target elements) is not sufficient for the distributed semantics, that requires to transmit to the reducer trace information connecting each unresolved binding to the source elements to resolve. Thus, we extended the ATL trace metamodel with the TraceProperty data structure. Trace properties are identified by their name that refers to the corresponding feature name. They are contained in a trace link, and associated to the source elements to be resolved along with the target element to be updated.

Tool Support

Distributed Transformation Engine

We implemented our approach as a Distributed ATL engine, whose source code is available at the paper's website. The engine is built on top of the ATL Virtual Machine (EMFTVM [START_REF]ATL EMFTVM[END_REF]) and Apache Hadoop [START_REF]Apache Hadoop[END_REF]. Hadoop is the leading open-source implementation of MapReduce and comes with the Hadoop Distributed File System (HDFS) that provides high-throughput access to application data and data locality optimization for MapReduce tasks.

In ATL VM, the transformation engine iterates the set of matched rules, and looks for the elements that match its application condition (guard). Instead, our VM iterates over each input model element, and checks if it is matched by an existing rule (matchSingle(EObject) in Table . 1). In this perspective we extended the ATL VM with a minimal set of functions (see Table 1) allowing the VM to run either in standalone or distributed mode. In particular, the distributed VM is required to factorize and expose methods for launching independently small parts of the execution algorithms. For instance the distributed VM exposes methods to perform the transformation of single model elements. Typically the methods localApplySingle(EObject) and globalResolve() that we call at the map and reduce functions respectively.

Each node in the system executes its own instance of the ATL VM but performs either only the local match-apply or the global resolve phase. The standalone and distributed execution modes share most of the code and allow for a fair comparison of the distribution speedup. Configuration information is sent together with the tasks to the different workers, so that they can be able to run their local VMs independently of each other. This information includes the paths of transformation, models and metamodels in the distributed file system. More information about the tool usage and deployment can be found at the tool's website4 .

Data Distribution

Data locality is one of the aspects to optimize in distributed computing for avoiding bottlenecks. In Hadoop, it is encouraged to run map tasks with input data residing in HDFS, since Hadoop will try to assign tasks to nodes where data to be processed is stored. In Distributed ATL we make use of HDFS for storing input and output models, metamodels and transformation code.

Each mapper is assigned a subset of model elements by the splitting process. In Distributed ATL we first produce a text file containing model elements URIs as plain strings, one per line. This file will be splitted in chunks by Hadoop. Hadoop provides several input format classes with specific splitting behavior. In our implementation we use an NLineIn-putFormat, that allows to specify the exact number of lines per split. Finally, the default record reader in Hadoop creates one record for each line of the input file. As a consequence, every map function in Distributed ATL will be executing on a single model element.

Choosing the right number of splits has significant impact on the global performance. Having many splits means that the time taken to process each split will be small compared to the time to process the whole input. On the other hand, if splits are too small, then the overhead of managing the splits and creating map tasks for each one of them may dominate the total job execution time. In our case we observed better results where the number of splits matches the number of available workers. In other words, while configuring Distributed ATL, the number of lines per split should be set to model size available nodes .

Tool Limitations

Currently, our ATL VM supports only the default EMF serialization format XMI. This file-based representation faces many issues related to scalability. In particular, models stored in XMI need to be fully loaded in memory, but more importantly, XMI does not support concurrent read/write. This hampers our tool at two levels, first, all the nodes should load the whole model even though if they only need a subset of it. This prevents us from transforming very big models that would fit in memory. The second one concerns the reduce phase parallelization, and this is due to the fact that only one mapper can write to the output XMI file at once. In a recent work, we extended an existing persistence backend NeoEMF [START_REF] Gómez | Map-based transparent persistence for very large models[END_REF] with support for concurrent read/write [START_REF] Gómoz | Decentralized Model Persistence for Distributed Computing[END_REF] [START_REF]Apache HBase[END_REF]. NeoEMF is an extensible and transparent persistence layer for modeling tools designed to optimize runtime performance and memory occupancy. In future work, we plan to couple it with our VM to solve these two particular issues.

Experimental Evaluation

We evaluate the scalability of our proposal by comparing how the transformation of our running example performs in different test environments. The transformation covers a sufficient set of declarative ATL constructs enabling the specification of a large group of MTs. It also contains an interesting number of OCL operations, recursive helper's call included.

We use as input different sets of models of diverse sizes. The original case study [START_REF] Horn | The TTC 2013 Flowgraphs Case[END_REF] already includes a set of input models for the benchmark. These models are reverseengineered from a set of automatically generated Java programs, with sizes up to 12 000 lines of code. For our benchmark we used the same generation process but to stress scalability we produced larger models with sizes up to 105 000 lines of code. We consider models of these sizes sufficient for benchmarking scalability in our use case: in our experimentation, processing in a single machine the largest of these models takes more than four hours. All the models we generated and the experimentation results are available at the article website.

In what follows we demonstrate the scalability of our approach through two different but complementary experimentations. The first one shows a quasi-linear speed-up w.r.t. the cluster size for input models with similar size, while the second one illustrates that the speed-up grows with increasing model size.

Experiment I: Speed-Up Curve

For this experiment we have used a set of 5 automatically generated Java programs with random structure but similar size and complexity. The source Java files range from 1 442 to 1 533 lines of code and the execution time of their sequential transformation ranges from 620s to 778s. The experiments were run on a set of identical Elastic MapReduce clusters provided by Amazon Web Services. All the clusters were composed by 10 EC2 instances of type m1.large (i.e. 2 vCPU, 7.5GB of RAM memory and 2 magnetic Hard Drives). Each execution of the transformation was launched in one of those clusters with a fixed number of nodes -from 1 to 8 -depending on the experiment. Each experiment has been executed 10 times for each model and number of nodes. In total 400 experiments have been executed summing up a total of 280 hours of computation (1 120 normalized instance hours[1]). For each execution we calculate the distribution speed-up with respect to the same transformation on standard ATL running in a single node of the cluster. Fig. 7 summarizes the speed-up results. The approach shows good performance for this transformation with an average speed-up up between 2.5 and 3 on 8 nodes. More importantly, as it can be seen in upper side, the average speed-up shows a very similar curve for all models under transformation, with a quasi linear speedup indicating good scalability w.r.t. cluster size. We naturally expect the speed-up curve to become sub-linear for larger cluster sizes and very unbalanced models. The variance among the 400 executions is limited as shown by the box-plots in the lower side.

Experiment II: Size/Speed-Up Correlation

To investigate the correlation between model size and speedup we execute the transformation over 4 artificially generated Java programs with identical structure but different size (from 13 500 to 105 000 lines of code). Specifically, these Java programs are built by replicating the same imperative code pattern and they produce a balanced execution of the model transformation in the nodes of the cluster. This way, we abstract from possible load unbalance that would hamper the correlation assessment. This time the experiments have been executed in a virtual cluster composed by 12 instances (8 slaves, and 4 additional instances for orchestrating Hadoop and HDFS services) built on top of OpenVZ containers running Hadoop 2.5.1. The hardware hosting the virtual cluster is a Dell PowerEdge R710 server, with two Intel Xeon X5570 processors at 2.93GHz (allowing up to 16 execution threads), 72 GB of RAM memory (1 066MHz), and two hard disks (at 15K rpm) configured in a hardware-controlled RAID 1.

As shown in Fig. 8 and Table 2, the curves produced by Experiment II are consistent to the results obtained from Experiment I, despite the different model sizes and cluster architectures. Moreover, as expected, larger models produce higher speed-ups: for longer transformations the parallelization benefits of longer map tasks overtakes the overhead of the MapReduce framework.

Related Work

To our knowledge, our work is the first applying the Map-Reduce programming model to model transformation. The only other proposal addressing MT distribution is Lintra, by Figure 8: Execution times and speed-up on Experiment II Burgueño et al. [START_REF] Burgueño | On the Concurrent Execution of Model Transformations with Linda[END_REF], based on the Linda coordination language. Lintra uses the master-slave design pattern for their execution, where slaves are in charge of applying the transformation in parallel to submodels of the input model. The same authors propose a minimal set of primitives to specify distributed model transformations, LintraP [START_REF] Burgueño | LinTraP: Primitive Operators for the Execution of Model Transformations with LinTra[END_REF]. With respect to our approach, Lintra requires to explicitly use distribution primitives, but it can be used in principle to distribute any transformation language by compilation. However no compiler is provided, and it is difficult to compare their performance results with ours, since they only perform a local multi-threaded experimentation in a case with low speed-up (maximum 3.4 on 16 nodes). Among distributed graph transformation proposals, a recent one is Mezei et al. [START_REF] Mezei | Towards Truly Parallel Model Transformations: A Distributed Pattern Matching Approach[END_REF]. It is composed of a transformation-level parallelization and a rule-level parallelization with four different matching algorithms to address different distribution types. Unlike our approach, their main focus is on the recursive matching phase, particularly expensive for graph transformations, but less significant in MT (because of Property 3). In [START_REF] Izsó | IncQuery-D Incremental Graph Search in the Cloud[END_REF], Izso et al. present a tool called IncQuery-D for incremental query in the cloud. This approach is based on a distributed model management middleware and a stateful pattern matcher framework using the RETE algorithm. The approach has shown its efficiency, but it addresses only distributed model queries while we focus on declarative transformation rules.

Shared-memory parallelization is a closely related problem to distribution. For model transformation, Tisi et al. [START_REF] Tisi | Parallel Execution of ATL Transformation Rules[END_REF] present a systematic two-steps approach to parallelize ATL transformations. The authors provided a multi-threaded implementation of the ATL engine, where every rule is executed in a separate thread for both steps. The parallel ATL compiler and virtual machine have been adapted to enable a parallel execution and reduce synchronization overhead. A similar approach for parallel graph transformations in multicore systems [START_REF] Imre | Parallel Graph Transformations on Multicore Systems[END_REF] introduces a two-phase algorithm (matching and modifier) similar to ours. Bergmann et al. propose an approach to parallelize graph transformations based on incremental pattern matching [START_REF] Bergmann | Parallelization of Graph Transformation Based on Incremental Pattern Matching[END_REF]. This approach uses a message passing mechanism to notify of model changes. The incremental pattern matcher is split into different containers, each one is responsible for a set of patterns. The lack of distributed memory concerns make these solutions difficult to adapt to the distributed computing scenario. Moreover in these cases the authors investigate task distribution, while we focus on data distribution, especially for handling VLMs.

While MapReduce lacks a high-level transformation language, several high-level query languages have been proposed. Microsoft SCOPE [START_REF] Chaiken | SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets[END_REF], Pig Latin [START_REF] Olston | Pig latin: a not-so-foreign language for data processing[END_REF], and HiveQL [START_REF] Thusoo | Hive: a warehousing solution over a map-reduce framework[END_REF] are high level SQL-like scripting languages targeting massive data analysis on top of MapReduce. Pig Latin and SCOPE are hybrid languages combining both forces of a SQL-like declarative style and a procedural programming style using MapReduce primitives. They provide an extensive support for user defined functions. Hive is a data warehousing solution built on top of Hadoop. It comes with a SQL-like language, HiveQL, which supports data definition statements to create tables with specific serialization formats, and partitioning and bucketing columns. While all these query languages compile down to execution plans in the form of series of MapReduce jobs, in our approach each node executes its own instance of the transformation VM, re-using the standard engine. However our approach computes single transformations in only two MapReduce rounds, while these language may compile in multi-round MapReduce chains. We also manipulate EMF model elements instead of tool-specific data representations, hence leaning on a standardized way to represent data structure.

Conclusion and Future Work

In this paper we argue that model transformation with rulebased languages like ATL is a problem that fits in the Map-Reduce execution model. As a proof of concept, we introduce a semantics for ATL distributed execution on MapReduce. We experimentally show the good scalability of our solution. Thanks to our publicly available execution engine, users may exploit the availability of MapReduce clusters on the Cloud to run model transformations in a scalable and fault-tolerant way.

In our future work we plan to improve the efficiency of our approach, by addressing related research aspects. We aim to investigate:

• I/O optimization of model processing in MapReduce by coupling with the transformation engine our distributed model-persistence backend supporting concurrent read-/write;

• parallelization of the Global Resolve phase, made possible by high-performance I/O;

• efficient distribution of the input model over map workers aiming to optimize load balancing and minimize workload, relying on a static analysis of the transformation;

• global optimization and pipelining for transformation networks on MapReduce.

FlowInstrFigure 2 :

 2 Figure 2: Simplified ControlFlow and DataFlow metamodels

Figure 1 :

 1 Figure 1: ControlFlow2DataFlow transformation example

2 c 15 s

 215 r e a t e OUT : DataFlow from IN : ControlFlow ; : ControlFlow ! SimpleStmt ( not ( s . def -> 16 isEmpty ( ) and s . use->isEmpty ( ) ) )

6 7h

 6 e l p e r d e f : isDefinedBy ( start : ControlFlow ! →FlowInstr , input : S e q u e n c e ( ControlFlow ! →FlowInstr ) , end : ControlFlow ! FlowInstr , →visited : S e q u e n c e ( ControlFlow ! FlowInstr ) , →forbidden : S e q u e n c e ( ControlFlow ! FlowInstr ) ) : → B o o l e a n = 8 i f input->exists ( i | i = end ) t h e n true 9 e l s e l e t newInput : S e q u e n c e ( ControlFlow ! →FlowInstr

h e n false 11 e 12 e n d i f 13 e

 111213 l s e thisModule . isDefinedBy ( start , →newInput , end , visited->union ( →newInput )->asSet ( ) ->asSequence ( ) , →forbidden ) n d i f ; ing 1, line 15) matches an element of type SimpleStmt that defines or uses at least a variable. Output patterns, delimited by the clause 'to' (Listing 1, line 17) describe how to compute the model elements to produce when the rule is fired, starting from the values of the matched elements. E.g., the SimpleStmt rule produces a single element of type SimpleStmt. A set of OCL bindings specify how to fill each of the features (attributes and references) of the produced elements. The binding at line 19 copies the textual representation of the instruction, the binding at line 20 fills the dfNext link with values computed by the computeNextDataFlows OCL helper. The rule for transforming methods is analogous (Listing 1, lines 3-11).

Figure 4 :

 4 Figure 4: ControlFlow2DataFlow example on MapReduce

Figure 6 :

 6 Figure 5: Extended Trace metamodel

Algorithm 2 : 3 foreach

 23 Reduce function input : String key, Set<TraceLink> links 1 foreach link ∈ links do 2 foreach prop ∈ getTraceProperties(link) do // unresolved properties elmt ∈ getSourceElements(prop) do 4 trgElmt ← resolveTarget(elmt); 5 updateUnresolvedElement(prop, trgElmt);

3Figure 7 :

 7 Figure 7: Speed-up obtained in Experiment I

Re m ot e re ad <+, 1> <+ , 1> <*, 1> < , 1> <+, 1> <*, 1> < , 1> <*, 1> <+, 1> Log0 Log1 Log2 Log3 Log4 Log5 Log6 Log7 Log8 SPLIT1 SPLIT2 SPLIT3 Write result <*, 1> <*, 1> <*, 1> < , 1> < , 1> <+, 1> <+, 1> <+, 1> <+, 1> Map Reduce Worker Read split Local write <*, 3> < , 2> <+, 4> Record

		Figure 3: MapReduce programming model overview
	Listing 2: ControlFlow2DataFlow -OCL helpers (excerpt)
	1	h e l p e r Context ControlFlow ! FlowInstr d e f :
		→computeNextDataFLows ( ) : S e q u e n c e ( ControlFlow !
		→FlowInstr ) =
	2	self . d e f ->collect ( d | self . users ( d )
	3	->reject ( fi | i f fi = self t h e n	not fi .
		→isInALoop e l s e false e n d i f )
			17	t o
			18	t : DataFlow ! SimpleStmt (
			19	txt <-s . txt ,
			20	dfNext <-s . computeNextDataFlows ( )
			21	)
			22	}

4

->select ( fi | thisModule . isDefinedBy ( fi ,

2 .

 2 Single assignment on target properties. The assignment of a single-valued property in a target model element happens only once in the transformation execution. Multivalued properties can be updated only for adding values, but never deleting them. 3. Non-recursive rule application. Model elements that are produced by ATL rules are not subject to further matches. As a consequence, new model elements can not be created as intermediate data to support the computation. Target models in ATL are read-only. This differentiates ATL from typically recursive graph-transformation languages. Not to confuse with recursion in OCL helpers, that are responsible of intermediate computations over the source models, not target ones.

Table 1

 1

	: API extension

Table 2 :

 2 Execution times and speed-up (between parentheses) per model

				STD.		Distributed VM using x nodes (time and speed-up)
	#	SIZE	ELTS	VM	1	2	3	4	5	6	7	8
	1	∼4MB	20 706	244s	319s	165s	128s	107s	94s	84s	79s	75s
					(×0.8)	(×1.5)	(×1.9)	(×2.3)	(×2.6)	(×2.9)	(×3.1)	(×3.3)
	2	∼8MB	41 406	1 005s	1 219s	596s	465s	350s	302s	259s	229s	199s
					(×0.8)	(×1.7)	(×2.2)	(×2.9)	(×3.3)	(×3.9)	(×4.4)	(×5.1)
	3 ∼16MB	82 806	4 241s	4 864s	2 318s	1 701s	1 332s	1 149s	945s	862s	717s
					(×0.9)	(×1.8)	(×2.5)	(×3.2)	(×3.7)	(×4.5)	(×4.9)	(×5.9)
	4 ∼32MB 161 006 14 705s 17 998s	8 712s	6 389s	5 016s	4 048s	3 564s	3 050s	2 642s
					(×0.8)	(×1.7)	(×2.3)	(×2.9)	(×3.6)	(×4.1)	(×4.8)	(×5.6)

The Eclipse Foundation, ATL transformation zoo, http://www.eclipse. org/atl/atlTransformations/, visited on June

https://github.com/atlanmod/ATL_MR/

An algorithm with better efficiency, is described e.g. in the Dragonbook[START_REF] Lam | Compilers: Principles, Techniques, and Tools[END_REF], Chapter 9.1, and is implemented with ATL in[START_REF] Cosentino | Analyzing Flowgraphs with ATL[END_REF].

https://github.com/atlanmod/ATL_MR/

Acknowledgments

This work is partially supported by the MONDO (EU ICT-611125) project.