Ivan Gentil
email: gentil@ceremade.dauphine.fr

From the Prékopa-Leindler inequality to modified logarithmic Sobolev inequality

We develop in this paper an improvement of the method given by S. Bobkov and M. Ledoux in [BL00]. Using the Prékopa-Leindler inequality, we prove a modified logarithmic Sobolev inequality adapted for all measures on R n , with a strictly convex and super-linear potential. This inequality implies modified logarithmic Sobolev inequality, developed in [GGM05, GGM07], for all uniformly strictly convex potential as well as the Euclidean logarithmic Sobolev inequality.

Résumé

Dans cet article nous amélirons la méthode exposée par S. Bobkov et M. Ledoux dans [BL00]. En utilisant l'inégalité de Prékopa-Leindler, nous prouvons une inégalité de Sobolev logarithmique modifiée, adaptée à toutes les mesures sur R n possédant un potentiel strictement convexe et super-linéaire. Cette inégalité implique en particulier une inégalité de Sobolev logarithmique modifiée, développée dans [GGM05, GGM07], pour les mesures ayant un potentiel uniformément strictement convexe mais aussi une inégalité de Sobolev logarithmique de type euclidien.

Introduction

The Prékopa-Leindler inequality is the functional form of Brunn-Minkowski inequality. Let a, b be some positive reals such that a + b = 1, and u, v, w be some non-negative measurable functions on R n . Assume that, for any x, y ∈ R n , we have u(x) a v(y) b ≤ w(ax + by),

then u(x)dx a v(x)dx b ≤ w(x)dx, ( 1
)
where dx is the Lebesgue measure on R n . If we apply inequality (1) to characteristic functions of bounded measurable sets A and B in R n , we get the multiplicative form of the Brunn-Minkowski inequality vol(A) a vol(B) b ≤ vol(aA + bB),

where aA + bB = {ax A + bx B , x A ∈ A, x B ∈ B} and vol(A) is the Lebesgue measure of the set A. One can see for example two interesting reviews on this topic [START_REF] Gupta | Brunn-Minkowski inequality and its aftermath[END_REF][START_REF] Maurey | Inégalité de Brunn-Minkowski-Lusternik, et autres inégalités géométriques et fonctionnelles[END_REF]. Bobkov and Ledoux in [START_REF] Bobkov | From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities[END_REF] use the Prékopa-Leindler inequality to prove some functional inequalities like Brascamp-Lieb, Logarithmic Sobolev and Transportation inequalities.

More precisely, let ϕ be a C 2 strictly convex function on R n and let dµ ϕ (x) = e -ϕ(x) dx (2) be a probability measure on R n ( e -ϕ(x) dx = 1). The function ϕ is called the potential of the measure µ ϕ . Bobkov and Ledoux obtained in particular the following two results:

• (Proposition 2.1 of [START_REF] Bobkov | From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities[END_REF]) Brascamp-Lieb inequality: assume that ϕ is a C 2 function on R n , then for all smooth enough functions g,

Var µϕ (g) := g -gdµ ϕ 2 dµ ϕ ≤ ∇g • Hess(ϕ) -1 ∇gdµ ϕ , (3)
where Hess(ϕ) -1 is the inverse of the Hessian of ϕ.

• (Proposition 3.2 of [START_REF] Bobkov | From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities[END_REF]) Assume that for some c > 0 and p 2, for all t, s > 0 with t + s = 1, and for all x, y ∈ R n , ϕ satisfies, as s goes to 0, tϕ(x) + sϕ(y) -ϕ(tx + sy) c p

(s + o(s)) x -y p , ( 4
)
where • is the Euclidean norm in R n . Then for all smooth enough functions g, Ent µϕ (e g ) := e g log e g e g dµ ϕ dµ ϕ ≤ c ∇g q e g dµ ϕ ,

where 1/p + 1/q = 1. They also give an example: the function ϕ(x) = x p + Z ϕ (where Z ϕ is a normalization constant) which satisfies inequality (4) for some constant c > 0.

The main result of this paper is to prove an inequality satisfies for any measure µ ϕ with a potential strictly convex and super-linear (we also assume a technical hypothesis satisfied by the potential ϕ)). More precisely we obtain, for all smooth enough functions g on R n ,

Ent µϕ (e g ) ≤ {x • ∇g(x) -ϕ * (∇ϕ(x)) + ϕ * (∇ϕ(x) -∇g(x))}e g(x) dµ ϕ (x), (6)
where ϕ * is the Fenchel-Legendre transform of ϕ, ϕ * (x) := sup z∈R n {x • z -ϕ(z)}.

The main application of this result is to extend the modified logarithmic Sobolev inequalities presented in [START_REF] Gentil | Modified logarithmic Sobolev inequalities and transportation inequalities[END_REF][START_REF] Gentil | Logarithmic sobolev inequalities in curvature null[END_REF] for probability measures on R satisfying a uniform strictly convexity condition. It is well known that if the potential ϕ is C 2 on R such that for all x ∈ R, ϕ ′′ (x) λ > 0, then the measure µ ϕ defined on (2) verifies the logarithmic Sobolev inequality introduced by Gross in [START_REF] Gross | Logarithmic Sobolev inequalities[END_REF], for all smooth enough functions g, namely

Ent µϕ (e g ) ≤ 1 2λ g ′2 e g dµ ϕ .
This result comes from the Γ 2 -criterion of D. Bakry and M. Émery, see [B É85] or [ABC + 00] for a review. We then improve the classical logarithmic Sobolev inequality of Gross, in the situation where if the potential is even with ϕ(0) = 0 and satisfies

∀x ∈ R, ϕ ′′ (x) λ > 0 and lim |x|→∞ ϕ ′′ (x) = ∞.
Adding a technical hypothesis (see Section 3.1), we show that for all smooth functions g,

Ent µϕ (e g ) ≤ H ϕ (g ′ )e g dµ ϕ ,
where

H ϕ (x) =    C ′ ϕ * x 2 , if |x| > C 1 2λ x 2 , if |x| ≤ C,
for some constants C, C ′ , λ > 0 depending on ϕ. Remark that we always have

∀x ∈ R, H ϕ (x) ≤ C ′′ x 2 ,
for some other constant C ′′ . This inequality implies concentration inequalities which are more adapted to the measure studied, as we will see in Section 3.1.

The next section is divided into two subsections. In the first one we state the main theorem of this article, inequality (6). In the second subsection, we explain how this result improves results of [START_REF] Bobkov | From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities[END_REF].

In particular, inequality (5) or Brascamp-Lieb inequality (3). Section 3 deals with some applications. The first one is an improvement of the a classical consequence of the Γ 2 -criterion of Bakry-Émery for measures on R. We obtain then a global view of modified logarithmic Sobolev inequality for log-concave measures as introduced in joint work with A. Guillin and L. Miclo in [START_REF] Gentil | Modified logarithmic Sobolev inequalities and transportation inequalities[END_REF][START_REF] Gentil | Logarithmic sobolev inequalities in curvature null[END_REF]. Finally, we explain how the main theorem is equivalent to the Euclidean logarithmic Sobolev inequality. As a consequence, a short proof of the generalization given in [DPD03, Gen03, AGK04] is obtained.

2 Inequality for log-concave measures

The main theorem

Theorem 2.1 Let ϕ be a C 2 strictly convex function on R n , such that

lim x →∞ ϕ(x) x = ∞. (7)
Denotes by µ ϕ (dx) = e -ϕ(x) dx a probability measure on R n , where dx is the Lebesgue measure on R n , ( e -ϕ(x) dx = 1). Assume that µ ϕ satisfies for any R > 0,

( z + y 0 + R) 2 ∇ϕ(z) + sup y; y-z+y 0 ≤R Hess(ϕ)(y) dµ ϕ (z) < +∞, ( 8
)
where y 0 satisfies ∇ϕ(y 0 ) ≤ ∇ϕ(z) + R. If ϕ * is the Fenchel-Legendre transform of ϕ, ϕ * (x) := sup z∈R n {x • z -ϕ(z)}, then for all smooth enough functions g on R n , one gets

Ent µϕ (e g ) ≤ {x • ∇g(x) -ϕ * (∇ϕ(x)) + ϕ * (∇ϕ(x) -∇g(x))}e g(x) dµ ϕ (x). ( 9
)
Lemma 2.2 Let ϕ satisfying conditions on Theorem 2.1 then we have

• ∇ϕ is a bijection on R n to R n • lim x →∞ x•∇ϕ(x) x = +∞.
Proof ⊳ Condition (7) implies that for all x ∈ R n the supremum of x • z -ϕ(z) for y ∈ R n is reached for some y ∈ R n . Then y satisfies x = ∇ϕ(y) and it proves that ∇ϕ is a surjection. Then the strict convexity of ϕ implies that ∇ϕ is a bijection. The function ϕ is convex then for all x ∈ R n , x • ∇ϕ(x) ϕ(x) -ϕ(0), (7) implies the second properties satisfied by ϕ. ⊲

The proof of the theorem is based on the following lemma: Lemma 2.3 Let g be a C ∞ function with a compact support on R n . Let s, t 0 with t + s = 1 and denotes ∀z ∈ R n , g s (z) = sup z=tx+sy (g(x) -(tϕ(x) + sϕ(y) -ϕ(tx + sy))).

Then there exists R 0 such that, when s goes to 0,

g s (z) = g(z) + s{z • ∇g(z) -ϕ * (∇ϕ(z)) + ϕ * (∇ϕ(x) -∇g(x))} + ( z + y 0 + R) ∇ϕ(z) + ( z + y 0 + R) 2 sup y; y-z+y 0 ≤R Hess(ϕ)(y) O(s 2 ),
where

y 0 satisfies ∇ϕ(y 0 ) ≤ ∇ϕ(z) + R and O(s 2 ) is uniform on z ∈ R n . Proof ⊳ Let s ∈]0, 1/2[ and x = z/t -(s/t)y, hence g s (z) = ϕ(z) + sup y∈R n g z t - s t y -tϕ z t - s t y -sϕ(y) .
Due to the fact that g has a compact support and by property (7) there exists

y s ∈ R n such that sup y∈R n g z t - s t y -tϕ z t - s t y -sϕ(y) = g z t - s t y s -tϕ z t - s t y s -sϕ(y s ). Moreover, y s satisfies ∇g z t - s t y s -t∇ϕ z t - s t y s + t∇ϕ(y s ) = 0. ( 10
)
Lemma 2.2 implies that there exists a unique solution y 0 of the equation

∇ϕ(y 0 ) = ∇ϕ(z) -∇g(z), y 0 = (∇ϕ) -1 (∇ϕ(z) -∇g(z)). (11)
We prove now that lim s→0 y s = y 0 .

First we show that there exists A 0 such that ∀s ∈]0, 1/2[, y s ≤ A. Indeed, if the function y s is not bounded one can found (s k ) k∈N such that s k → 0 and y s k → ∞. Definition of y s implies that

g z t - s t y s -tϕ z t - s t y s -sϕ(y s ) g z t -tϕ z t .
Due to the fact that lim x →∞ ϕ(x) = ∞ and since g is bounded we obtain s k y s k = O(1). Next using (10) one get

y s • ∇g z t -s t y s y s -t y s • ∇ϕ z t -s t y s y s + t y s • ∇ϕ(y s ) y s = 0.
The last equality is an contradiction with the second assertion of Lemma 2.2 which prove that the (y s ) s∈]0,1/2[ is bounded.

Let ŷ an accumulation point of the function y s , when s tends to 0. Then ŷ satisfies equation (11). By unicity of the solution of (11) we get ŷ = y 0 . Therefore we have proved that lim s→0 y s = y 0 .

Taylor formula gives

ϕ z t - s t y s = ϕ(z) + s z t - y s t • ∇ϕ(z) + s 2 1 0 (1 -t) z t - y s t •Hess(ϕ) z t -s y s t z t - y s t dt,
and the same for g. Using the continuity of y s at s = 0, ones gets

ϕ z t - s t y s = ϕ(z) + s(z -y 0 ) • ∇ϕ(z) + (z -y 0 ) • ∇ϕ(z) + sup t∈[0,1/2] z t - y t t 2 sup t∈[0,1/2] Hess(ϕ) z t - y s t O(s 2 ).
and the same for g

g z t - s t y s = g(z) + s(z -y 0 ) • ∇g(z)+ (z -y 0 ) • ∇g(z) + sup t∈[0,1/2] z t - y t t 2 sup t∈[0,1/2] Hess(g) z t - y s t O(s 2 ).
As a consequence,

g s (z) = g(z) + s{ϕ(z) -ϕ(y 0 ) + (z -y 0 ) • (∇g(z) -∇ϕ(z))} + (z -y 0 ) • (∇g(z) -∇ϕ(z)) + sup t∈[0,1/2] z t - y t t 2 sup t∈[0,1/2] Hess(ϕ + g) z t - y s t O(s 2 ).
The function g is C ∞ with a compact support then one obtains using (11) and the expression of the Fenchel-Legendre transformation for a strictly convex function

∀x ∈ R n , ϕ * (∇ϕ(z)) = ∇ϕ(z) • z -ϕ(z),
we get the result. ⊲

We are now ready to deduce our main result: Proof of Theorem 2.1 ⊳ The proof is based on the proof of Theorem 3.2 of [START_REF] Bobkov | From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities[END_REF]. First we prove inequality (9) for all functions g, C ∞ with compact support on R n . Let t, s 0 with t + s = 1 and denote for z ∈ R n ,

g t (z) = sup z=tx+sy (g(x) -(tϕ(x) + sϕ(y) -ϕ(tx + sy))).
We apply Prékopa-Leindler inequality to the functions

u(x) = exp g(x) t -ϕ(x) , v(y) = exp (-ϕ(y)), w(z) = exp (g s (z) -ϕ(z)), to get exp(g/t)dµ ϕ t ≤ exp(g s )dµ ϕ .
The differentiation of the L p norm gives the entropy, and thanks to a Taylor's formula we get exp(g/t)dµ ϕ t = e g dµ ϕ + sEnt µϕ (e g ) + O(s 2 ).

Then applying Lemma 2.3 and inequality (8) yield exp(g s )dµ ϕ =

e g µ ϕ + s {z • ∇g(z) -ϕ * (∇ϕ(z)) + ϕ * (∇ϕ(z) -∇g(z))}e g(z) dµ ϕ (z) + O(s 2 ).
When s goes to 0, inequality (9) arises and can be extended for all smooth enough functions g. ⊲ Note that hypothesis (8) is satisfied by a large class of convex functions. For example if ϕ(x) = x 2 /2 + (n/2) log(2π) we obtain the classical logarithmic Sobolev of Gross for the canonical Gaussian measure on R n , with the optimal constant.

Remarks and examples

In the next corollary we recall a classical result of perturbation. If Φ is a function on R n such that e -Φ dx < ∞ we note the probability measure µ Φ by

dµ Φ (x) = e -Φ(x) Z Φ dx, (12)
where Then for all smooth enough functions g on R n , one has

Z Φ = e -Φ(x)
Ent µ Φ (e g ) ≤ e 2osc(U ) {x • ∇g(x) -ϕ * (∇ϕ(x)) + ϕ * (∇ϕ(x) -∇g(x))}e g(x) dµ Φ (x), ( 13
)
where osc(U ) = sup(U ) -inf(U ).

Proof ⊳ First we observe that e -osc(U ) ≤ dµ Φ dµ ϕ ≤ e osc(U ) . (14)
Moreover we have for all probability measures ν on R n , Ent ν (e g ) = inf

a 0 e g log e g a -e g + a dν .

Using the fact that for all x, a > 0, x log x a -x + a 0, we get e -osc(U ) Ent µ Φ (e g ) ≤ Ent µϕ (e g ) ≤ e osc(U ) Ent µ Φ (e g ) .

Then if g a smooth enough function on R n we have

Ent µ Φ (e g ) ≤ e osc(U ) Ent µϕ (e g ) ≤ e osc(U ) {x • ∇g(x) -ϕ * (∇ϕ(x)) + ϕ * (∇ϕ(x) -∇g(x))}e g(x) dµ ϕ (x).
The convexity of ϕ * R n and th relation ∇ϕ

* (∇ϕ(x)) = x lead to ∀x ∈ R n , x • ∇g(x) -ϕ * (∇ϕ(x)) + ϕ * (∇ϕ(x) -∇g(x)) 0.
Finally by (14) we get

Ent µ Φ (e g ) ≤ e 2osc(U ) {x • ∇g(x) -ϕ * (∇ϕ(x)) + ϕ * (∇ϕ(x) -∇g(x))}e g dµ Φ .
⊲ Remark 2.5 It is not necessary to state a tensorization result, as we may obtain exactly the same expression when computing directly with a product measure.

Theorem 2.1 implies also examples given in [START_REF] Bobkov | From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities[END_REF] and [START_REF] Bobkov | Entropy bounds and isoperimetry[END_REF].

Corollary 2.6 ([BL00]) Let p 2 and let Φ(x) = x p /p where • is Euclidean norm in R n . Then there exists c > 0, such that for all smooth enough functions g,

Ent µ Φ (e g ) ≤ c
∇g q e g dµ Φ ,

where 1/p + 1/q = 1 and µ Φ is defined on (12).

Proof ⊳ Using Theorem 2.1, we just have to prove that there exists c > 0 such that,

∀x, y ∈ R n , x • y -Φ * (∇Φ(x)) + Φ * (∇Φ(x) -y) ≤ c y q .
Assume that y = 0 and define the function ψ by,

ψ(x, y) = x • y -Φ * (∇Φ(x)) + Φ * (∇Φ(x) -y) y q .
Then ψ is a bounded function. We know that Φ * (x) = x q /q. Choosing z = x x p-2 / y and denoting e = y/ y , we obtain

ψ(x, y) = ψ(z, e) = z • e z q-2 - 1 q z q + 1 q z -e q .
Taylor's formula then yields ψ(z, e) = O( z q-2 ). But p 2 implies that q ≤ 2, so that ψ is a bounded function. We then get the result with c = sup ψ = sup ψ. ⊲ Optimal transportation is also used by Cordero-Erausquin, Gangbo and Houdré in [START_REF] Cordero-Erausquin | Inequalities for generalized entropy and optimal transportation[END_REF] to prove the particular case of the inequality (15). In Proposition 2.1 of [BL00], Bobkov and Ledoux prove that the Prékopa-Leindler inequality implies Brascamp-Lieb inequality. In our case, Theorem 2.1 also implies Brascamp-Lieb inequality, as we can see in the next corollary.

Corollary 2.7 Let ϕ satisfying conditions of Theorem 2.1. Then for all smooth enough functions g we get,

Var µϕ (g) ≤ ∇g • Hess(ϕ) -1 ∇gdµ ϕ ,
where Hess(ϕ) -1 denote the inverse of the Hessian of ϕ.

Proof ⊳ Assume that g is a C ∞ function with a compact support and apply inequality (9) with the function ǫg where ǫ > 0. Taylor's formula gives

Ent µϕ (exp ǫg) = ǫ 2 2 Var µϕ (g) + o(ǫ 2 ),
and

{x • ∇g(x) -ϕ * (∇ϕ(x)) + ϕ * (∇ϕ(x) -∇g(x))}e g (x)dµ ϕ (x) = ǫ 2 2 ∇g • Hess(ϕ * )(∇ϕ)∇gdµ ϕ + o(ǫ 2 ).
Because of ∇ϕ * (∇ϕ(x)) = x, one has Hess(ϕ * )(∇ϕ) = Hess(ϕ) -1 which finished the proof. ⊲ Remark 2.8 Let ϕ satisfying the conditions of Theorem 2.1, and L be defined by

∀x, y ∈ R n , L(x, y) = ϕ(y) -ϕ(x) + (y -x) • ∇ϕ(x).
The convexity of ϕ implies that L(x, y) 0 for all x, y ∈ R n . Let F be a density of probability with respect to the measure µ ϕ , we defined the following Wasserstein distance with the cost function L by

W L (F dµ ϕ , dµ ϕ ) = inf L(x, y)dπ(x, y) ,
where the infimum is taken over all probability measures π on R n × R n with marginal distributions F dµ ϕ and dµ ϕ . Bobkov and Ledoux proved in [START_REF] Bobkov | From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities[END_REF] the following transportation inequality

W L (F dµ ϕ , dµ ϕ ) ≤ Ent µϕ (F ) . ( 16
)
The main result of Otto and Villani in [START_REF] Otto | Generalization of an inequality by Talagrand, and links with the logarithmic Sobolev inequality[END_REF] is the following: Classical logarithmic Sobolev inequality of Gross (when ϕ(x) = x 2 /2 + (n/2) log(2π)) implies the transportation inequality (16) for all functions F , density of probability with respect to µ ϕ (see also [START_REF] Bobkov | Hypercontractivity of Hamilton-Jacobi equations[END_REF] for an another proof ). The method developed in [START_REF] Bobkov | Hypercontractivity of Hamilton-Jacobi equations[END_REF], enables to extend the property for ϕ(x) = x p + Z ϕ (p 2). In the general case, inequality proved in this article, we do not know if the modified logarithmic Sobolev inequality (9) implies transportation inequality (16).

Applications

Application to modified logarithmic Sobolev inequalities

In [GGM05, GGM07], a modified logarithmic Sobolev inequality for measure µ ϕ on R is given with a potential between |x| and x 2 . More precisely let Φ be a function on the real line and assume that Φ is even and satisfies the following property: there exist M 0 and 0 < ε ≤ 1/2 such that,

∀x M , (1 + ε)Φ(x) ≤ xΦ ′ (x) ≤ (2 -ε)Φ(x). (H)
Then there exist A, B, D > 0 such that for all smooth functions g we have

Ent µ Φ (e g ) ≤ A H Φ g ′ e g dµ Φ , (17)
where

H Φ (x) = Φ * (Bx) if |x| D, x 2 if |x| ≤ D,
and µ Φ is defined on (12). The proof of inequality ( 17) is rather technical and is divided in two parts: the large and the small entropy. Using Theorem 2.1 one obtains two results in this direction. In the next theorem, we extend (17) in the case where the potential is "bigger" than x 2 .

Theorem 3.1 Let ϕ be a real function satisfying conditions of Theorem 2.1. Assume that ϕ is even, ϕ(0) = 0, ϕ ′′ in decreasing on ] -∞, 0] and increasing on [0, +∞[ and satisfies,

∀x ∈ R, ϕ ′′ (x) ϕ ′′ (0) = λ > 0 and lim |x|→∞ ϕ ′′ (x) = ∞. ( 18
)
Assume also that there exists A > 1 such that for |x| C for some C > 0,

Aϕ(x) ≤ xϕ ′ (x). ( 19
)
Then there exists C > 0 such that for all smooth enough functions g,

Ent µϕ (e g ) ≤ H ϕ (g ′ )e g dµ ϕ , (20)
where

H ϕ (x) =      2A A -1 ϕ * x 2 , if |x| > C 1 2λ x 2 , if |x| ≤ C. ( 21
)
The proof of this theorem is a straightforward application of the following lemma:

Lemma 3.2 Assume that ϕ satisfies conditions of Theorem 3.1, then we get

∀x, y ∈ R, xy -ϕ * (ϕ ′ (x)) + ϕ * (ϕ ′ (x) -y) ≤ H ϕ (y). ( 22
) Proof ⊳ We know that for all x ∈ R n , x = ϕ * ′ (ϕ ′ (x))
, and the convexity of ϕ * yields

xy -ϕ * (ϕ ′ (x)) + ϕ * (ϕ ′ (x) -y) ≤ y ϕ * ′ (ϕ ′ (x)) -ϕ * ′ (ϕ ′ (x) -y) . (23)
Let y ∈ R be fixed and notes ψ y (x) = ϕ * ′ (x + y) -ϕ * ′ (x). The function ϕ is convex, so one gets for all x ∈ R, ϕ * ′′ (ϕ ′ (x))ϕ ′′ (x) = 1, and the maximum of ψ y (x) is reached on x 0 ∈ R which satisfies the condition ϕ * ′′ (x 0 ) = ϕ * ′′ (x 0 + y). Since ϕ is even, ϕ ′′ is decreasing on ] -∞, 0] and increasing on ] -∞, 0] one get that x 0 + y = -x 0 . Then one obtains

∀y ∈ R, ∀x ∈ R, ϕ * ′ (x + y) -ϕ * ′ (x) ≤ 2ϕ * ′ y 2 , ∀y ∈ R, ∀x ∈ R, xy -ϕ * (ϕ ′ (x)) + ϕ * (ϕ ′ (x) -y) ≤ y2ϕ * ′ y 2 .
By (19) one gets

∀|y| C, ∀x ∈ R, xy -ϕ * (ϕ ′ (x)) + ϕ * (ϕ ′ (x) -y) ≤ 2A A -1 ϕ * y 2 . (24)
A Taylor's formula then leads to

∀x, y ∈ R, xy -ϕ * (ϕ ′ (x)) + ϕ * (ϕ ′ (x) -y) ≤ y 2 2 ϕ * ′′ (ϕ ′ (x) -θy) ≤ y 2 2λ ,
for some θ ∈ (0, 1), and one gets (24). ⊲ Remark 3.3 • The last theorem improved the classical consequence of Bakry-Émery criterion for the logarithmic Sobolev inequality. In fact when a probability measure is more log-concave than the Gaussian measure, we obtain a modified logarithmic Sobolev inequality sharper than the classical inequality of Gross. Using a such inequality then one obtains concentration inequality which is more adapted to the probability measure studied.

• Theorem 3.1 is more precise than Corollary 2.6 proved by Bobkov, Ledoux and Zegarlinski in [START_REF] Bobkov | From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities[END_REF][START_REF] Bobkov | Entropy bounds and isoperimetry[END_REF]. The particularity of the function H ϕ defined on (21) is its behaviour around the origin. One can obtain easily that if a probability measure satisfies inequality (20) then it satisfies a Poincaré inequality with constant 1/λ.

• Note also that this method can not be applied for measures with a concentration between e -|x| and e -x 2 described in [START_REF] Gentil | Modified logarithmic Sobolev inequalities and transportation inequalities[END_REF][START_REF] Gentil | Logarithmic sobolev inequalities in curvature null[END_REF]. In particular Lemma 3.2 is false in this case.

• Note finally that the condition (19) is a technical condition, satisfied for a large class of functions.

A natural application of Theorem 3.1 is a concentration inequality in the spirit of Talagrand, see [START_REF] Talagrand | Concentration of measure and isoperimetric inequalities in product spaces[END_REF].

Corollary 3.4 Assume that ϕ satisfies conditions of Theorem 3.1 and there exists B > 1 such that for |x| large enough,

xϕ ′ (x) ≤ Bϕ(x). (25)
Then there exists constants C 1 , C 2 , C 3 0, independent of n such that: if F is a function on R n such that ∀i, ∂ i F ∞ ≤ 1, then we get for λ ≥ 0,

µ ⊗n ( F -µ ⊗n (F ) λ) ≤        2 exp -nC 1 Φ C 2 λ n if λ > nC 3 , 2 exp -C 1 λ 2 n if 0 ≤ λ ≤ nC 3 . ( 26
)
Proof ⊳ Using the additional hypothesis (25), the proof of ( 26) is the same as for Proposition 3.2 of [START_REF] Gentil | Logarithmic sobolev inequalities in curvature null[END_REF]. ⊲

A n-dimensional version of ( 20) is also available.

Proposition 3.5 Let Φ be a C 2 , strictly convex and even function on R n and satisfying (7) and (8).

Assume also that Φ 0 and Φ(0) = 0 (it implies that 0 is the unique minimum of Φ), lim α→0, α∈[0,1]

sup x∈R n    (1 -α) Φ * x 1-α Φ * (x)    = 1, (27)
and also that there exists A > 0 such that

∀x ∈ R n , x • ∇Φ(x) ≤ (A + 1)Φ(x). ( 28
)
Then there exist C 1 , C 2 , C 3 0 such that for all smooth enough functions g such that e g dµ Φ = 1we get

Ent µ Φ (e g ) ≤ C 1 Φ * (C 2 ∇g)e g dµ Φ + C 3 . (29)
Proof ⊳ Let apply Theorem 2.1 with ϕ = Φ + log Z Φ , one has

Ent µ Φ (e g ) ≤ {x • ∇g(x) -Φ * (∇Φ(x)) + Φ * (∇Φ(x) -∇g(x))}e g dµ Φ .
The convexity of Φ * implies, for all α ∈ [0, 1[,

∀x ∈ R n , Φ * (∇Φ(x) -∇g(x)) ≤ (1 -α)Φ * ∇Φ(x) 1 -α + αΦ * -∇g(x) α . (30)
Recall that Φ * is also an even function. Young's inequality implies that

∀x ∈ R n , x • ∇g(x) α ≤ Φ(x) + Φ * ∇g(x) α . (31)
Using ( 30) and (31) we get Ent µ Φ (e g ) ≤ 2α Φ * ∇g α e g dµ Φ + α Φ(x)e g dµ Φ +

(1 -α)Φ * ∇Φ(x) 1 -α -Φ * (∇Φ(x)) e g dµ Φ .

We have Φ * (∇Φ(x)) = x • ∇Φ(x) -Φ(x), then inequality (28) implies that Φ * (∇Φ(x)) ≤ AΦ(x).

Because of Φ(0) = 0 one has Φ * 0, so that

Ent µ Φ (e g ) ≤ α Φ * ∇g α e g dµ Φ + α Φ * ∇g α e g dµ Φ + (α + A|ψ(α) -1|) Φe g dµ Φ ,
where

ψ(α) = sup x∈R n    (1 -α) Φ * x 1-α Φ * (x)    . (32)
Let λ > 0, recall that e g dµ Φ = 1 then yields Φe g dµ Φ ≤ λ Ent µ Φ (e g ) + log e Φ/λ dµ Φ .

One has lim

λ→∞ log e Φ/λ dµ Φ = 0. Let then let now choose λ large enough so that log e Φ/λ dµ Φ ≤ 1.

Using the property (27), taking α such that (α + A|ψ

(α) -1|)λ ≤ 1/2 implies Ent µ Φ (e g ) ≤ 2α Φ * ∇g α e g dµ Φ + 1 2 (Ent µ Φ (e g ) + 1), which gives
Ent µ Φ (e g ) ≤ 4α Φ * ∇g α e g dµ Φ + 1/2.

⊲

The main difference between the inequality obtained and the modified logarithmic inequality (20) is that we do not have equality if f = 1. Then (29) is called a no tight inequality and it is more difficult to obtain.

Application to Euclidean logarithmic Sobolev inequality

Theorem 3.6 Assume that the function ϕ satisfies conditions of Theorem 2.1. Then for all λ > 0 and for all smooth enough functions g on R n , Ent dx (e g ) ≤ -n log (λe) e g dx + ϕ * (-λ∇g)e g dx.

(

) 33
This inequality is optimal in the sense that if g = -ϕ(x -x) with x ∈ R n and λ = 1 we get an equality.

Proof ⊳ Integrating by parts in the second term of (9) yields for all g smooth enough x • ∇g(x)e g(x) dµ ϕ (x) = (-n + x • ∇ϕ(x))e g(x) dµ ϕ (x).

Then using the equality ϕ * (∇ϕ) = x • ∇ϕ(x) -ϕ(x) we get for all smooth enough functions g, Ent µϕ (e g ) ≤ (-n + ϕ + ϕ * (∇ϕ -∇g))e g dµ ϕ ,

Let now take g = f + ϕ to obtain

Ent dx e f ≤ (-n + ϕ * (-∇g))e g dx.

Finally, let λ > 0 and take f (x) = g(λx), we get then Ent dx (e g ) ≤ -n log (λe) e g dx + ϕ * (-λ∇g)e g dx, which proves (33).

If now g = -ϕ(x -x) with x ∈ R n an easy computation proves that if λ = 1 the equality holds. ⊲

In the inequality (33), there exists an optimal λ 0 > 0 and when C is homogeneous, we can improve the last result. We find an inequality called Euclidean logarithmic Sobolev inequality which is explained on the next corollary.

Corollary 3.7 Let C be a strictly convex function on R n satisfying condition of Theorem 2.1 and assume that C is q-homogeneous for some q > 1, ∀λ 0 and ∀x ∈ R n , C(λx) = λ q C(x).

Then for all smooth enough functions g in R n we get Ent dx (e g ) ≤ n p e g dx log p ne p-1 L p/n C * (-∇g)e g dx e g dx ,

where L = e -C dx and 1/p + 1/q = 1.

Proof ⊳ Let apply Theorem 3.6 with ϕ = C + log L. Then ϕ satisfies conditions of Theorem 3.6 and we get then

Ent dx (e g ) ≤ -n log λeL 1/n e g dx + C * (-λ∇g)e g dx.

Due to the fact that C is q-homogeneous an easy computation proves that C * is p-homogeneous where 1/p + 1/q = 1. An optimization over λ > 0 gives inequality (34). ⊲ Remark 3.8 Inequality (34) is useful to prove regularity properties as hypercontractivity for nonlinear diffusion as the p-Laplacian, see [START_REF] Del Pino | Nonlinear diffusions, hypercontractivity and the optimal L p -Euclidean logarithmic Sobolev inequality[END_REF]. The function C is then adapted to the nonlinear diffusion studied. Remark 3.9 As explained in the introduction, computation used in Corollary 3.7 clearly proves that inequality (34) is equivalent to inequality (33). Agueh, Ghoussoub and Kang, in [START_REF] Agueh | Geometric inequalities via a general comparison principle for interacting gases[END_REF], used Monge-Kantorovich theory for mass transport to prove inequalities (33) and (34). Their approach gives another way to establish Theorem 2.1. Note finally that inequality (34) is optimal, extremal functions are given by g(x) = -bC(x -x), with x ∈ R n and b > 0. If they are only ones is still an open question.

Acknowledgments: I would like to warmly thank referee for pointed out errors in the first version.

Inequality ( 34 )

 34 is called Euclidean logarithmic Sobolev inequality and computations of this section is the generalization of the work of Carlen in [Car91]. This inequality with p = 2, appears in the work of Weissler in [Wei78]. It was discussed and extended to this last version in many articles see [Bec99, DPD03, Gen03, AGK04].

  dx• Corollary 2.4 Assume that ϕ satisfies conditions of Theorem 2.1. Let Φ = ϕ + U , where U is a bounded function on R n and denote by µ Φ the measure defined by (12).


Yehia Abd

Rocco De Nicola

Giulio Garbi

Michele Loreti

A Distributed Coordination Infrastructure for Attribute-based Interaction

Keywords: Attribute-based Interaction, Semantics, Process Calculi. 1 Introduction

Collective-adaptive systems offer an interesting notion of interaction where run-time contextual data are the driving force for interaction. The attribute-based interaction has been proposed as a foundational theoretical framework to model CAS interactions. The framework permits a group of partners to interact by considering their run-time properties and their environment. In this paper, we lay the basis for an efficient, correct, and distributed implementation of the attribute-based interaction framework. First, we present three coordination infrastructures for message exchange, then we prove their correctness, and finally we model them in terms of stochastic processes to evaluate their performance.

infrastructure (i.e., they are infrastructure-agnostic). They rely on anonymous multicast communication where components interact based on mutual interests. Message transmission is non-blocking while reception is not. Each component has a set of attributes to represent its run-time status. Communication actions (both send and receive) are decorated with predicates over attributes that partners have to satisfy to make the interaction possible. The interaction predicates are also parametrised with local attribute values and when values change, the interaction groups do implicitly change, introducing opportunistic interactions.

Basing the interaction on run-time attribute values is indeed a nice idea, but it needs to be supported by a middleware that provides efficient ways for distributing messages, checking attribute values, and updating them. A typical approach is to rely on a centralised broker that keeps track of all components, intercepts every message and forwards it to registered components. It is then the responsibility of each component to decide whether to receive or discard the message. This is the approach used in the Java-based implementation [START_REF] Abd Alrahman | Programming of CAS systems by relying on attribute-based communication[END_REF] of AbC . A similar approach, still based on a centralised broker, is used in the Erlang-based implementation [START_REF] De Nicola | Aerlang at work[END_REF]. There however to avoid broadcasts the broker has an attribute registry where components register their attribute values and the broker is now responsible for message filtering.

Clearly, any centralised solution may not scale with CAS dynamics and thus becomes a bottleneck for performance. A distributed approach is definitely preferable for large systems. However, distributed coordination infrastructures for managing the interaction of computational systems are still scarce [START_REF] Lopes | A virtual machine for a process calculus[END_REF] and/or inefficient [START_REF] Vukolić | The quest for scalable blockchain fabric: Proof-of-work vs. bft replication[END_REF]. Also the correctness of their overall behaviour is often not obvious. In this paper, we propose an efficient distributed coordination infrastructure for message exchange. We prove its correctness with respect to the original semantics of AbC and finally we evaluate its performance in terms of stochastic simulation. Though this paper assumes perfect communication links and does not deal with dropped messages or node's failures, we believe that existing techniques for resilience and failure-recovery can be integrated transparently.

The rest of this paper is structured as follows: In Section 2, we briefly review the AbC calculus. In Section 3, we give a full formal account of a distributed coordination infrastructure for AbC and its correctness. In Section 4, we provide a detailed performance evaluation and we discuss the results. Finally, Section 5 concludes the paper and surveys related works.

AbC in a Nutshell

In this section we briefly introduce the AbC calculus by means of a running example. We give an intuition of how to model a distributed variant of the well known Graph Colouring Problem [START_REF] Jensen | Graph coloring problems[END_REF] using AbC constructs. We render the problem as a typical CAS scenario where a collective of agents, executing the same code, collaborate to achieve a system-level goal without any centralised control. The presentation is intended to be intuitive and full details concerning the example, the syntax, and the semantics of AbC can be found in [START_REF] Abd Alrahman | On the power of attribute-based communication[END_REF][START_REF] Abd Alrahman | Programming the Interactions of Collective Adaptive Systems by Relying on Attribute-based Communication[END_REF].

The problem consists of assigning a colour (an integer) to each vertex in a graph while avoiding that two neighbours get the same colour. The algorithm consists of a sequence of rounds for colour selection. At the end of each round at least one vertex is assigned a colour. A vertex, with identity id. uses messages of the form ("try", c, r, id) to inform its neighbours that at round r it wants to select colour c and messages of the form ("done", c, r, id) to communicate that colour c has been definitely chosen at the end of round r. At the beginning of a round, each vertex selects a colour and sends a try-message to all of its neighbours N. A vertex also collects try-messages from its neighbours. The selected colour is assigned to a vertex only if it has the greatest id among those that have selected the same colour in that round. After the assignment, a done-message (associated with the current round) is sent to neighbours.

AbC Syntax. An AbC component (C), is either a process P associated with an attribute environment Γ (denoted by Γ : P ) or the parallel composition C 1 C 2 of components. The attribute environment Γ is a partial map from attribute identifiers a ∈ A to values v ∈ V . Values can be numbers, strings, tuples, etc.

C ::= Γ : P | C 1 C 2
Example (step 1/4): Each vertex, in the colouring scenario, can be modelled in AbC as a component of the form C i = Γ i : P C . The overall system is the parallel composition of vertices (i.e., C 1 C 2 , . . . , C n ).

The attribute environment of a vertex Γ i relies on the following attributes to control the behaviour of a vertex: The attribute "round" stores the current round while "used" is a set, registering the colours used by neighbours. The attribute "counter" counts the number of messages collected by a component while "send" is used to enable/disable forwarding of messages to neighbours. Attribute "assigned" indicates if a vertex is assigned a colour while "colour" is a colour proposal. Finally, attributes id and N are used to represent the vertex id and the set of neighbours, respectively. These attributes initially have the following values: round = 0, used = ∅, send = tt, and assigned = ff.

It should be noted that new values for these attributes can only be learnt by means of message exchange among vertices.

The behavior of an AbC process can be generated by the following grammar:

P ::= 0 | α.P | [ã := Ẽ]P | Π P | P 1 + P 2 | P 1 |P 2 | K
The process 0 denotes the inactive process; α.P denotes a process that executes action α and continues as P ; process [ã := Ẽ]P behaves as P given that its attribute environment is first updated by setting the value of each attribute in the sequence ã to the evaluation of the corresponding expression in the sequence Ẽ. The attribute updates and the first move of P are atomic; Π P denotes an awareness process, it blocks the execution of process P until the predicate Π evaluates to true; the processes P 1 + P 2 , P 1 |P 2 , and K are standard for nondeterminism, parallel composition, and process definition respectively. The parallel operator "|" does not allow communication between P 1 and P 2 , they

: P λ -→ Γ : P iComp Γ : P Π(ṽ) ---→Γ : P Γ : P Π(ṽ) ---→ Γ : P fComp C1 Π(ṽ) ---→ C 1 C2 Π(ṽ) ---→ C 2 C1 C2 Π(ṽ) ---→ C 1 C 2 Com C1 Π(ṽ) ---→ C 1 C2 Π(ṽ) ---→ C 2 C1 C2 Π(ṽ) ---→ C 1 C 2

Sync

can only interleave while the parallel operator " " at the component level allows communication between components. The expression this.b denotes the value of attribute b in the current component.

Example (step 2/4): Process P C , specifying the behaviour of a vertex is now defined as the parallel composition of these four processes:

P C F | T | D | A.
Process F forwards try-messages to neighbours, T handles try-messages, D handles done-messages, and A is used for assigning a final colour.

The AbC communication actions ranged by α can be either ( Ẽ)@Π or Π(x). The construct ( Ẽ)@Π denotes an output action, it evaluates the sequence of expressions Ẽ under the local attribute environment and then sends the result to the components whose attributes satisfy the predicate Π. Furthermore, Π(x) denotes an input action, it binds to sequence x the corresponding received values from components whose communicated attributes or values satisfy Π.

Example (step 3/4): We further specify process F and a part of process T .

F

send ∧ ¬assigned [colour := min{i ∈ this.used}, send := ff] ("try", this.colour, this.round, this.id)@(this.id ∈ N).F

T [counter := counter + 1] ((x = "try") ∧ (this.id > l) ∧ (this.round = z))(x, y, z, l).T + . . .

In process F , when the value of attribute send becomes true, a new colour is selected, send is turned off, and a message containing this colour and the current round is sent to all the vertices having this.id as neighbour. The new colour is the smallest colour that has not yet been selected by neighbours, that is min{i ∈ this.used}. The guard ¬assigned is used to make sure that vertices with assigned colours do not take part in the colour selection anymore.

Process T receives messages of the form ("try", c, r, id). If r = this.round then the received message has been originated by a vertex performing the same round of the algorithm. The condition this.id > l means that the sender has an id smaller than the id of the receiver. In this case, the message is ignored (there is no conflict), simply the counter of collected messages (this.counter) is incremented. Other cases, not reported here, e.g., this.id < l, the received colour is recorded to check the presence of conflicts.

AbC Semantics. The main semantics rules of AbC are reported in Table 1. Rule iComp states that a component evolves with (send Π(ṽ) or receive Π(ṽ), denoted by λ) if its internal behaviour, denoted by the relation →, allows it. Rule fComp states that a component can discard a message Π(ṽ) if its internal behaviour does not allow the reception of this message by generating the discarding label Π(ṽ). Rule Com 3 states that if C 1 evolves to C 1 by sending a message Π(ṽ) then this message should be delivered to C 2 which evolves to C 2 as a result. Note that C 2 can be also a parallel composition of different components. Thus, rule Sync states that multiple components can be delivered the same message in a single transition.

The semantics of the parallel composition operator, in rules Com and Sync in Table 1, abstracts from the underlying coordination infrastructure that mediates the interactions between components and thus the semantics assumes atomic message exchange. This implies that no component can evolve before the sent message is delivered to all components executing in parallel. Individual components are in charge of using or discarding incoming messages. Message transmission is non-blocking, but reception is not. For instance, a component can still send a message even if there is no receiver (i.e., all the target components discard the message); a receive operation can, instead, only take place through synchronisation with an available message. However, if we want to use the attribute-based paradigm to program the interactions of distributed applications, atomicity and synchrony are neither efficient nor applicable.

One solution is to rely on existing protocols for total-order broadcast to handle message exchange. However, these protocols are mostly centralised [START_REF] Cristian | The pinwheel asynchronous atomic broadcast protocols[END_REF] or rely on consensus [START_REF] Vukolić | The quest for scalable blockchain fabric: Proof-of-work vs. bft replication[END_REF]. Clearly, centralised solutions have always scalability and efficiency problems. Furthermore, consensus approaches are not only inefficient [START_REF] Vukolić | The quest for scalable blockchain fabric: Proof-of-work vs. bft replication[END_REF] but also impossible in asynchronous systems in the presence of even a single component's failure [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF]. They also assume that components know each other and can agree on a specific order. However, this contradicts the main design principles of the AbC calculus where anonymity and openendedness are crucial factors. Since AbC components are agnostic to the infrastructure, they cannot participate in establishing the total order. Thus, we need an infrastructure that guarantees the total order seamlessly and without involving the interacting components.

The focus of this paper, as we will see later, is on providing an efficient distributed coordination infrastructure that behaves in agreement with the parallel composition operator of AbC . Thus in Table 1, we only formalised the external behaviour of a component, i.e., its ability to send and receive. The following example shows how interactions are derived based on internal behaviour.

Example (step 4/4): Consider the vertices C 1 , C 2 , and C 3 where Γ 2 (N) = {3}, Γ 3 (N) = {1, 4}, Γ 3 (id) = 3, and Γ 3 (round) = 5. Now C 1 sent a try message:

Γ 1 : P C (1∈N)("try",3,5,1) ------------→ C 1 Γ 1 [colour ← 3, send ← ff] : P C
3 For the sake of brevity, we omit the symmetric rule of Com.

We have that C 2 discards this message because Γ 2 |= (1 ∈ N) while C 3 accepts the message (Γ 3 |= (1 ∈ N) and the receiving predicate of process T is satisfied). The system evolves with rule Com as follows:

C 1 C 2 C 3 (1∈N)("try",3,5,1) ------------→ C 1 C 2 Γ 3 [counter ← counter + 1] : P C ["try"/x, 3/y, 5/z, 1/l]

A Distributed Coordination Infrastructure

In this section, we consider three possible coordination infrastructures that we have also implemented4 in Google Go. We will refer to them as cluster -based, ringbased, and tree-based. These infrastructures behave in agreement with the parallel composition operator of AbC . Our approach consists of labelling each message with an id that is uniquely identified at the infrastructure level. Components execute asynchronously while the semantics of the parallel composition operator is preserved by relying on the unique identities of exchanged messages. In essence, if a component wants to send a message, it sends a request to the infrastructure for a fresh id. The infrastructure replies back with a fresh id and then the component sends a data (the actual) message with the received id. A component receives a data message only when the difference between the incoming data message id and the id of the last received data message equals 1. Otherwise the data message is added to the component waiting queue until the condition is satisfied.

In what follows, we give a full formal account of the proposed infrastructures and also investigate the correctness of the tree-based one. The reason is that we want to avoid redundancy and also because the tree infrastructure is theoretically the most challenging one. Actually, the proofs of correctness for the other infrastructures are simple cases of the tree's one. Moreover, as we will see in Section 4, the tree exhibits better performance characteristics.

Furthermore to provide compact semantics, we use the following definition of a Configuration. For the sake of clarity, we will postfix the configuration of a component, an infrastructure, and a server with the letter a, n, and s respectively.

Definition 1 (Configuration).

A configuration C, is a tuple C = c 1 , . . . , c n which is commutative. The symbol '. . . ' is formally regarded as a meta-variable ranging over unmentioned elements of the configuration. The explicit '. . . ' is obligatory, and ensures that unmentioned elements of a configuration are never excluded, but they do not play any role in the current context. Different occurrences of '. . . ' in the same context stand for the same set of unmentioned elements.

We use the reduction relation ∼∼ ⊆ Cfig × Lab × Cfig to define the semantics of a configuration where Cfig denotes the set of configurations, Lab denotes the set of reduction labels which can be a message m, a silent transition τ , or an empty label, and ∼∼ * denotes the transitive closure of ∼∼ . Moreover, we will use the following notations:

-We have two kinds of messages, an AbC message 'msg' (i.e., Π(ṽ)) and an infrastructure message 'm'; the latter can be of three different templates: (i) request {'Q', route, dest}, (ii) reply {'R', id, route, dest}, and (iii) data {'D', id, src, dest, msg}. The route field in a request or a reply message is a linked list containing the addresses of the nodes that the message traversed. -The notation ? = denotes a template matching.

-The notation T [f ] denotes the value of the element f in T .

Also the following operations will be used: L.get() returns the element at the front of a list/queue, while L ← m returns the list/queue resulting from adding m to the back of L, and L\x removes x from L and returns the rest.

Infrastructure Component

Now, we formally define a general infrastructure component and its external behaviour. In the following sections, we proceed by formally defining the proposed infrastructures and their behaviours.

Definition 2 (Infrastructure component). An infrastructure component, a, is defined by the configuration: a = addr, nid, mid, on, W, X , G where addr refers to its address, nid (initially 0) refers to the id of the next data message to be received, mid (initially -1) refers to the id of the most recent reply, on (initially 0) indicates whether a request message can be sent. W is a priority waiting queue where the top of W is the data message with the least id, and X refers to the address of the parent server. Furthermore, G ranges over Γ : P and [Γ : P ] where [Γ : P ] indicates an AbC component in an intermediate state.

The intermediate state, in Definition 2, is important to allow co-located processes (i.e, [Γ : P 1 |P 2 ] where P 1 is waiting an id to send and P 2 is willing to receive) to interleave their behaviours without compromising the semantics.

The semantics of an infrastructure component is reported in Table 2. Rule Out states that if the AbC component Γ : P encapsulated inside an infrastructure component is able to send a message Γ : P Π(ṽ) ---→ Γ : P , the flag on is set to 1 and Γ : P goes into an intermediate state [Γ : P ]. Rule Med states that an intermediate state component can only receive a message Π(ṽ) if it was able to receive it before the intermediate state. Rule Req states that a component sends a request, to the parent server, only if on == 1. In this case, it adds its address to the route of the message and resets on to 0. Rule RcvR states that a component receives a reply if the destination field of the reply matches its address; after that mid gets the value of the id received in the reply. Rule Snd states that a component Γ : P can send a message Π(ṽ) and evolves to Γ : P only if nid == mid; this implies that a fresh id is received (mid = -1) and all messages with m[id] < mid have been already received. By doing so, an infrastructure data message, with msg field equals to Π(ṽ), is sent, nid is incremented, and mid is reset. Rule RcvD states that a component receives a data message from the infrastructure if m[id] ≥ nid; this is important to avoid duplicate messages. The

Hnd

message is then added to the priority queue, W. Finally, rule Hnd states that when the id of the message on top of W matches nid, component G is allowed to receive that message; by doing so, nid is incremented and m is removed.

Cluster-based Infrastructure

We consider a set of server nodes, sharing a counter for sequencing messages and one FIFO queue to store messages sent by components. Cluster nodes can have exclusive locks on both the cluster's counter and the queue. Components register directly to the cluster and send messages to be added to the FIFO queue. When a server node retrieves a request from the cluster queue, it replies to the requester with the value of the cluster counter. By doing so, the cluster counter is incremented. If a server retrieves a data message, it forwards the message to all components in the cluster except for the sender.

Definition 3 (Cluster node).

A server node, s, is defined by the configuration s = addr, A, M, I where addr is its address, A is a set containing the addresses of all cluster components, M is a multicast set (initially M = A). Finally, I is a FIFO input queue.

Definition 4 (Cluster infrastructure). A cluster, N , is defined by the configuration N = addr, ctr, S, A, I where ctr is a counter to generate fresh ids, initially the value of ctr equals 0, S is a set containing the addresses of the infrastructure server nodes, and the rest is defined as before. We start by defining the overall infrastructure semantics and then we zoom in and we define the semantics of individual servers. The cluster semantics is reported in Table 3. Rule Qin states that a component sends a message and the cluster adds it to its input queue. Rule Qout states that the cluster evolves when a server gets a message from the input queue of the cluster. Rule "a" states that the cluster evolves when one of its components evolves independently. Rule Dmsg states that the cluster evolves when a server can forward a data message to a component in the cluster. Rule Rmsg states that the cluster evolves when a node sends a reply message to a component. The reply is labeled with the current value of the the cluster counter and after that the counter is incremented.

The semantics of a cluster node is reported in Table 4. Rule In states that a node gets a message and adds it to its input queue. Rule Reply states that if a node gets a request message from its input queue, it sends a reply to the requester by getting and removing its address from the route of the message. Rule dFwd states that if a node gets a data message from its input queue, it forwards the message to all components in the cluster one by one except for the sender (addr ). Notice that this rule can be applied many times as long as the multicast set M contains more than one element, i.e., |M| > 1. Once M has only one element, rule eFwd is applied to forward the message to the last address in M, resets the multicast set to its initial value, and the message is removed.

Ring-based Infrastructure.

We consider a set of server nodes, organised in a logical ring and sharing a counter for sequencing messages coming from components. Each node manages a group of components and can have exclusive locks to the ring counter. When a request message arrives to a node from one of its components, the node acquires a lock on the ring counter, copies it current value, releases it after incrementing it by 1, and finally sends a reply, carrying a fresh id, to the requester. Data messages are directly added to the node's waiting queue; and will be only forwarded to the node's components and to the neighbour node when all previous messages (i.e., with a smaller id) have been received.

Definition 5 (Ring node).

A server node, s, is defined by the configuration s = addr, nid, X , D, M, I, W where X is its neighbour's address, D is a set containing the addresses of components connected to this sever node and also the neighbour's address X , and M initially equals D. The rest is defined as before.

Definition 6 (Ring infrastructure). A ring, N , is defined by the configuration N = S, A, ctr . We have that:

-∀s ∈ N [S] : s[X ] = ⊥ ∧ s[X ] ∈ N [S]. -∀s 1 , s 2 ∈ N [S] : s 1 [X ] = s 2 [X ] implies s 1 = s 2 .
The semantics rules of a ring infrastructure are reported in Table 5. The rules (s↔s) and (s↔a) state that a ring evolves when a message m is exchanged either between two of its servers (s 1 and s 2 ) or between a server and a component respectively. The latter rule concerns only request and data messages. Furthermore, the rules (s) and (a) state that a ring evolves when one of its servers or one of its connected components evolves independently. Finally, rule Rmsg states that a ring evolves also when a reply is exchanged between a server node and a component, but in this case the counter of the ring is increased.

The semantics rules of a ring node are reported in Tabel 6. Rule In states that a node receives a message m and adds it to its input queue (I ← m) if the destination field of m matches its own address addr. Rule Reply states that if a node gets a request message from its input queue m :: I, it sends a reply, to the requester. Rule wIn states that if a node gets a data message from its input queue, it adds the message to its waiting queue W only if m[id] ≥ nid otherwise the message is discarded as stated by rule Discard. This is important to avoid duplicates. Furthermore, rule dFwd states that when the id of the message on top of W matches nid (i.e., m[id] == nid), the server starts forwarding m to its children one by one except for the sender. Notice that this rule can be applied many times as long as the multicast set M contains more than one element, i.e., |M| > 1. Once M has only one element, rule eFwd is applied to forward the message to the last address in M. As a result, nid is incremented, m is removed from W, and the multicast set M is reset to its initial value.

A Tree-based Infrastructure

We consider a set of servers, organised in a logical tree. A component can be connected to one server (its parent) in the tree and can interact with others in any part of the tree by only dealing with its parent. When a component wants to send a message, it asks for a fresh id from its parent. If the parent is the root of the tree, it replies with a fresh id, otherwise it forwards the message to its own parent in the tree. Only the root of the tree can sequence messages.

Definition 7 (Tree server).

A tree server, s, is defined by the configuration: s = addr, ctr, nid, D, M, I, W, X where D is a set containing the addresses of the server's children which include connected components and servers, M is a multicast set (initially M = D). The rest are defined as before.

Definition 8 (Tree infrastructure). A tree infrastructure, N , is defined by the configuration: N = S, A where S denotes the set of servers and A denotes the set of connected components such that:

-∀s 1 , s 2 ∈ S, we say that s 1 is a direct child of s 2 , written s 1 ≺ s 2 , if and only if s 1 [X ] = s 2 [addr]; ≺ + denotes the transitive closure of ≺. The semantics rules of a tree infrastructure are reported in Table 7. The rules (s↔s) and (s↔a) state that a tree evolves when a message m is exchanged either between two of its servers (s 1 and s 2 ) or between a server and a component respectively. Furthermore, the rules (s) and (a) state that a tree evolves when one of its servers or one of its connected components evolves independently.

The semantics rules of a tree server are defined by the rules in Table 8. Rule In states that a server receives a message m and adds it to the back of its input queue (I ← m) if the destination field of m matches its own address addr. Rule Reply states that if a root server gets a request from the front of its input queue m :: I , it sends a reply to the requester by getting its address from the route of the message x = route.get(). The id of the reply is assigned the value of the root's counter ctr. By doing so, the counter is incremented. On the other hand, a non-root server adds its address to the message's route and forwards it to its parent as stated by rule qFwd. Rule rFwd instead is used for forwarding Table 7: Tree infrastructure semantics

s 1 m ∼∼ s 1 s 2 m ∼∼ s 2 {s 1 , s 2 } ∪ S , A n ∼∼ {s 1 , s 2 } ∪ S , A n s↔s s τ ∼∼ s {s} ∪ S , A n ∼∼ {s } ∪ S , A n s s m ∼∼ s a m ∼∼ a {s} ∪ S , {a} ∪ A n ∼∼ {s } ∪ S , {a } ∪ A n s↔a a τ ∼∼ a S, {a} ∪ A n ∼∼ S, {a } ∪ A n a
reply messages. Rule wIn states that if a server gets a data message from its input queue I and it is the root or its parent is the source of the message (i.e., X == addr ∨ X == ⊥), the server evolves silently and the message is added to its waiting queue. If the condition (X == addr ∨ X == ⊥) does not hold, the message is also forwarded to the parent as stated by rule wNxt. Furthermore, rule dFwd states that when the id of the message on top of W matches nid (i.e., m[id] == nid), the server starts forwarding m to its children one by one except for the sender. Notice that this rule can be applied many times as long as the multicast set M contains more than one element, i.e., |M| > 1. Once M has only one element, rule eFwd is applied to forward the message to the last address in M. As a result, nid is incremented, m is removed from W, and the multicast set M is reset to its initial value.

Correctness. Since there is a single sequencer in the tree, i.e., the root, two messages can never have the same id. We only need the following propositions to ensure that the tree behaves in agreement with the AbC parallel composition operator. In essence, Proposition 1, ensures that if any component in the tree sends a request for a fresh id, it will get it. Proposition 3, ensures that any two components in the tree with different nid will converge to the same one. However, to prove Proposition 3, we need to prove Lemma 1 and Proposition 2 which guarantee the same results among tree' servers. This implies that messages are delivered to all components. Proposition 4 instead ensures that no message stays in the waiting queue indefinitely. Due to space limitations all proofs are omitted. Proposition 1. For any component, with address addr and a parent X , connected to a tree infrastructure N , we have that: if addr, on, X , . . . a {'Q',{addr},X } ∼∼∼∼∼∼∼∼∼∼∼∼∼ addr, 0, X , . . . a then N ∼∼ * N and addr, mid, . . . a {'R',id,{},addr} ∼∼∼∼∼∼∼∼∼∼ addr, id, . . . a . Lemma 1. For every two tree nodes s 1 and s 2 and a tree-based infrastructure N such that s 1 , s 2 ∈ N [S], we have that:

-If s 1 ≺ s 2 ∧ s 1 [nid] < s 2 [nid] then N ∼∼ * N and s 1 [nid] = s 2 [nid]. -If s 2 ≺ s 1 ∧ s 1 [nid] < s 2 [nid] then N ∼∼ * N and s 1 [nid] = s 2 [nid].
Proposition 2. Let s 1 and s 2 be two tree nodes and N be a tree-based infrastructure,

∀s 1 , s 2 ∈ N [S] ∧ s 1 [nid] < s 2 [nid], we have that N ∼∼ * N and s 1 [nid] = s 2 [nid].

Performance Evaluation

We compare the above mentioned infrastructures by modeling them in terms of a Continuous Time Markov Process [START_REF] Robertson | Continuous-time markov chains (W. j. anderson)[END_REF]. The state of a process represents possible infrastructure configurations, while the transitions (that are selected probabilistically) are associated with events on messages. We can consider three types of events: a new message sent by a component; a message transmitted from a node to another in the infrastructure; a message locally handled by a node (i.e. removed from an input/waiting queue). Each event is associated with a rate that is the parameter of the exponentially distributed random variable governing the event duration. We developed a simulator5 for performance evaluation.

To perform the simulation we need to fix three parameters: the component sending rate λ s ; the infrastructure transmission rate λ t ; and the handling rate λ h . In all experiments, we fix the following values: λ s = 1.0, λ t = 15.0, and λ h = 1000.0 and rely on kinetic Monte Carlo simulation [START_REF] Schulze | Efficient kinetic monte carlo simulation[END_REF]. The infrastructure configurations are defined as follows:

-C[x, y], indicates a cluster with x nodes and y components; -R[x, y] indicates a ring with x nodes each of which manages y components; -T [x, y, z] indicates a tree with x levels. Each node (but the leafs) has y + z children: y nodes and z components. A leaf node has z components.

We consider two scenarios: (1) Data Providers (DP): In this scenario only a fraction of components sends data messages that they, for example, acquire via sensors in the environment where they operate. An example could be a Traffic Control System where data providers are devices located in the city and data receivers are the vehicles traveling in the area; (2) communication intensive (CI): This scenario is used to estimate the performance when all components send messages continuously at a fixed rate so that we can evaluate situations of overloaded infrastructures. The former scenario is more realistic for CAS.

We consider two measures: the average delivery time and the average message time gap. The first measure indicates the time needed for a message to reach all components, while the latter indicates the interval between two different messages received by a single component (i.e., an indication of throughput).

Data provider scenario (DP)

We consider configurations with 31 server nodes 155, 310, or 620 components and assume that only 10% of the components is sending data. The average delivery time is reported in Fig. 1 while the average message time gap (with confidence intervals) is reported in Fig. 2. The tree structure offers the best performance while the cluster one is the worst. When the cluster reaches an equilibrium (at time ∼ 2000), ∼ 90 time units are needed to deliver a message to 155 components while the ring and the tree need only ∼ 25 and ∼ 10 time units, respectively. The reason is that in the cluster all server nodes share the same input queue while in the tree and the ring each server node has its own queue. We can also observe that the performance of the ring in this scenario is close to the one of the tree. Moreover, in the cluster, the performance degrades when the number of components increases. This does not happen for the tree and the ring. Finally, we can observe that messages are delivered more frequently in the ring (∼ 1.9 time units) and the tree (∼ 1.1 time units) than in the cluster (∼ 5.5 time units) as reported in Fig. 2.

Communication intensive scenario (CI)

We consider infrastructures composed by 155 components that continuously send messages to all the others. Simulations are performed by considering the following configurations: Fig. 3 shows that the cluster has the worst performance. One can easily notice that when the cluster reaches an equilibrium (∼ 2000), ∼ 800 time units are needed to deliver a message to all components. We also observe that the number of nodes in the cluster has a minimal impact on this measure because they all share the same input queue. The Average Message Time Gap, in Fig. 4, indicates that in the long run a component receives a message every 6/5.5 time units.

Better performance can be obtained if the ring infrastructure is used. In the first two plots of Fig. 5 we report the average delivery time for the configurations R [START_REF] Agha | Actors: A Model of Concurrent Computation in Distributed Systems[END_REF]31] and R[31, 5]. The last plot compares the average message time gap of the two configurations. In the first one, a message is delivered to all the components in 350 time units while in the second one 250 time units are needed. This indicates that increasing the number of nodes in the ring enhances performance. This is because in the ring all nodes cooperate to deliver a given message. Also the time gap decreases, i.e., a message is received every 2.6 and 1.8 time units.

Fig. 6 shows how the average delivery time changes during the simulation for T [5, 2, 5] and T [START_REF] Abd Alrahman | Programming the Interactions of Collective Adaptive Systems by Relying on Attribute-based Communication[END_REF][START_REF] Agha | Actors: A Model of Concurrent Computation in Distributed Systems[END_REF][START_REF] Agha | Actors: A Model of Concurrent Computation in Distributed Systems[END_REF]. The two configurations have exactly the same number of nodes (31) with a different arrangement. The two configurations work almost in the same way: a message is delivered to all the components in about 120 time units. Clearly, the tree is 5-time faster than the cluster and 2-time faster than the ring. Moreover, in the tree-based approach, a message is delivered to components every ∼ 1.1 time units as reported in Fig. 7. This means that messages in the tree are constantly delivered after an initial delay. The results show that tree infrastructures offer the best performance; clusterbased ones do not work well while ring-based ones are in between the two.

Concluding Remarks, Future Work, and Related Work

The contribution of our paper is twofold: (i) the definition of a distributed tree-based infrastructure for coordinating attribute-based interaction and its actual implementation in Google Go; (ii) the proof of correctness of the proposed infrastructure and its performance evaluation. The results showed that the tree infrastructure has a better performance when compared with others in terms of minimising the average delivery time and maximising throughput.

As for future work, we plan to integrate (possibly) existing techniques for resilience to deal with imperfect communication links, dropped messages, and node's failures. Apart from simulation, we will consider large and realistic case studies to investigate the actual performance of the current Go implementation.

We would like to conclude by relating to existing approaches. For implementations of attribute-based interaction, we refer to the Java-based [START_REF] Abd Alrahman | Programming of CAS systems by relying on attribute-based communication[END_REF] and the Erlang-based [START_REF] De Nicola | Aerlang at work[END_REF] implementations. As we mentioned before, these implementations are centralised while we are aiming for a distributed one.

Many approaches have been proposed to deal with distributed coordination, but they are difficult to compare as they differ in their assumptions, properties, objectives, or target applications [START_REF] Défago | Total order broadcast and multicast algorithms: Taxonomy and survey[END_REF]. However, they can be classified according to their ordering mechanisms. Below we relate to well-known approaches.

In the fixed sequencer approach [START_REF] Cristian | The pinwheel asynchronous atomic broadcast protocols[END_REF], a single sequencer maintains the order of message delivery and components communicate by interacting only with the sequencer. The cluster infrastructure is a natural distributed extension; and also the tree is a generalisation of this approach where instead of a single sequencer, we consider a propagation tree. The ordering decisions are resolved along tree paths. Actually, a propagation tree with depth 1 is a fixed sequencer.

The moving sequencer approach [START_REF] Chang | Reliable broadcast protocols[END_REF] avoids the bottleneck of a single sequencer by transferring the sequencer role among several nodes. Nodes form a logical ring and circulate a token, carrying a counter and a list of sequenced messages. Once token is received, a sequencer sequences its messages, sends all sequenced messages to its connected components, updates the token, and passes it along with sequenced messages to next node; thus the load is distributed among several nodes. However, the liveness of the algorithm depends on the token and, if the number of senders in one node is larger than others, fairness is hard to achieve. The ring-based infrastructure can be viewed as a generalisation of this technique where fairness is "resolved" by sharing a common counter.

In the privilege-based approach [START_REF] Cristian | Asynchronous atomic broadcast[END_REF], senders circulate a token and each sender has to wait for the token. Upon receipt of token, the sender sequences its messages, sends them to destinations, and passes the token to the next sender. This approach is not suitable for open systems, since it assumes that all senders know each other. Also fairness is hard to achieve, e.g., some components send larger number of messages than others.

  → Γ : P on, Γ : P, . . . a τ ∼∼ 1, [Γ : P ], . . . a Out Γ : P Π(ṽ) ---→ Γ : P [Γ : P ] Π(ṽ) ---→ [Γ : P ] Med on == 1 addr, on, X , . . . a {'Q', {addr}, X } ∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ addr, 0, X , . . . a Req addr, mid, . . . a {'R', id, {}, addr} ∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ addr, id, . . . a RcvR nid == mid Γ : P Π(ṽ) ---→ Γ : P addr, nid, mid, [Γ : P ], X , . . . a {'D',mid,addr,X ,Π(ṽ)} ∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ addr, nid + 1, -1, Γ : P , X , . . . a Snd m ? = {'D', id, X , addr, msg} id ≥ nid addr, nid, W, X , . . . a m ∼∼∼∼ addr, nid, W ← m, X , . . . a RcvD m[id] == nid G m[msg] -----→ G nid, G, m :: W , . . . a τ ∼∼∼∼ nid + 1, G , W , . . . a

  Q', {addr }, addr} m :: I , . . . n {'R',,{},addr } ∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ I , . . . n Reply |M| > 1 m ? = {'D', id, addr , addr , msg} M = M\addr x = M .get() addr, A, M, m :: I s {'D',id,addr,x,msg} ∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ addr, A, M \x, m :: I s dFwd |M| = 1 m ? = {'D', id, addr , addr, msg} x = M.get() addr, A, M, m :: I s {'D',id,addr,x,msg} ∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ addr, A, A, I s eFwd

m?=

  [dest] == addr addr, I, . . . s m ∼∼ addr, I ← m, . . . s In m {'Q', {addr }, addr} addr, m :: I , . . . s {'R',,{},addr } ∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ addr, I , . . . s Reply m ? = {'D', id, addr , addr, msg} id ≥ nid addr, nid, W, m :: I , . . . s τ ∼∼ addr, nid, W ← m, I , . . . s wIn m ? = {'D', id, addr , addr, msg} id < nid addr, nid, W, m :: I , . . . s τ ∼∼ addr, nid, W, I , . . . s Discard |M| > 1 m[id] == nid m ? = {'D', id, addr , addr, msg} M = M\addr x = M .get() addr, nid, D, M, m :: W , . . . s {'D',id,addr,x,msg} ∼∼∼∼∼∼∼∼∼∼∼∼∼∼ addr, nid, D, M \x, m :: W , . . . s dFwd |M| = 1 m[id] == nid m ? = {'D', id, addr , addr, msg} x = M.get() addr, nid, D, M, m :: W , . . . s {'D',id,addr,x,msg} ∼∼∼∼∼∼∼∼∼∼∼∼∼∼ addr, nid + 1, D, D, W , . . . s eFwd -∀s ∈ S, we have that s ≺ + s. -The root: ∃s ∈ S such that for any s ∈ (S\{s}), s ≺ + s and we have that: • s [nid] ≤ s[ctr]. • For any message m ∈ s [W] we have that m[id] ≤ s[ctr]. -A root is unique: if s, s ∈ S and s[X ] = s [X ] = ⊥ then we have that s = s . -∀s ∈ S and for each message m ∈ s[W], we have that m[id] ≥ s[nid].

Table 8 :?=?=Proposition 3 .Proposition 4 .

 834 Tree server semantics m[dest] == addr addr, I, . . . s m ∼∼ addr, I ← m, . . . s In m ? = {'Q', route, addr} X == ⊥ x = route.get() addr, ctr, X , m :: I , . . . s {'R',ctr,route\x,x} ∼∼∼∼∼∼∼∼∼∼∼ addr, ctr + 1, X , I , . . . s Reply m {'Q', route, addr} X = ⊥ route = route.add(addr) addr, X , m :: I , . . . s {'Q',route ,X } ∼∼∼∼∼∼∼∼∼∼∼∼ addr, X , I , . . . s qFwd m ? = {'R', id, route, addr} x = route.get() addr, m :: I , . . . s {'R',id,route\x,x} ∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ addr, I , . . . s rFwd m ? = {'D', id, addr , addr, msg} (X == addr ∨ X == ⊥) addr, X , W, m :: I , . . . s τ ∼∼ addr, X , W ← m, I , . . . s wIn m {'D', id, addr , addr, msg} (X = addr ∧ X = ⊥) addr, X , W, m :: I , . . . s {'D',id,addr,X ,msg} ∼∼∼∼∼∼∼∼∼∼∼∼∼∼ addr, X , W ← m, I , . . . s wNxt |M| > 1 m[id] == nid m ? = {'D', id, addr , addr, msg} M = M\addr x = M .get() addr, nid, D, M, m :: W , . . . s {'D',id,addr,x,msg} ∼∼∼∼∼∼∼∼∼∼∼∼ addr, nid, D, M \x, m :: W , . . . s dFwd |M| = 1 m[id] == nid m ? = {'D', id, addr , addr, msg} x = M.get() addr, nid, D, M, m :: W , . . . s {'D',id,addr,x,msg} ∼∼∼∼∼∼∼∼∼∼∼∼ addr, nid + 1, D, D, W , . . . s eFwd Given any two components a 1 and a 2 in a tree infrastructure N such that a 1 [nid] < a 2 [nid], we have that N ∼∼ * N and a 1 [nid] = a 2 [nid]. Given a tree infrastructure N = S, A , for any c ∈ S ∪ A where c[W] = m :: W , we have that N ∼∼ * N and c[W] = W + + W where + + returns a priority queue composed by the sub queues W and W .

Fig. 1 :

 1 Fig. 1: DP scenario: Avg. Delivery Time for Cluster, Ring, and Tree.

Fig. 2 :

 2 Fig. 2: DP scenario: Avg. Message Time Gap for Cluster, Ring, and Tree.

Fig. 3 :

 3 Fig. 3: CI scenario: Avg. Delivery Time for Cluster with 10, 20 and 31 servers.

-

  Cluster-based infrastructure: C[10, 155], C[20, 155] and C[31, 155]; -Ring-based infrastructure: R[5, 31] and R[31, 5]; -Tree-based infrastructure: T [5, 2, 5] and T [3, 5, 5].

Fig. 4 :

 4 Fig. 4: CI scenario: Avg. Message Time Gap for Cluster with 10, 20 and 31 servers.

Fig. 5 :

 5 Fig. 5: CI scenario: Avg. Delivery Time and Avg. Message Time Gap for Ring with 5 and 31 servers.

Fig. 6 :

 6 Fig. 6: CI scenario: Avg. Delivery Time: Tree/ T [5, 2, 5] and T [3, 5, 5].

Fig. 7 :

 7 Fig. 7: CI scenario: Avg. Message Time Gap: Tree/ T [5, 2, 5] and T [3, 5, 5].

Table 1 :

 1 AbC Communication Rules

Γ : P λ -→Γ : P Γ

Table 2 :

 2 The semantics of a component

Table 3 :

 3 The Cluster semantics , I, . . . n ∼∼ addr, {a } ∪ A , I ← m, . . . n , m :: I , . . . n ∼∼ {s } ∪ S , I , . . . n , . . . n ∼∼ {a } ∪ A . . . n , {a} ∪ A , ctr, . . . n ∼∼ {s } ∪ S , {a } ∪ A , ctr + 1, . . .

				m
			a	∼∼ a	m[dest] == addr
		addr, {a} ∪ A Qin
					m
			s {s} ∪ S Qout ∼∼ s
					τ
			a {a} ∪ A a ∼∼ a
		{'D',id,addr ,addr,msg}	{'D',id,addr ,addr,msg}
	s	∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ s	a
			{'R',,{},addr}	{'R',ctr,{},addr}
		s	∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ s	a	∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ a
		{s} ∪ S

∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ a a[addr] == addr {s} ∪ S , {a} ∪ A , . . . n ∼∼ {s } ∪ S , {a } ∪ A , . . . n Dmsg n Rmsg

Table 4 :

 4 Cluster node semantics

Table 5 :

 5 Ring infrastructure semantics {s 1 , s 2 } ∪ S , A, . . . n ∼∼ {s 1 , s 2 } ∪ S , A, . . . n , A, . . . n ∼∼ {s } ∪ S , A, . . . n {}, addr} {s} ∪ S , {a} ∪ A , . . . n ∼∼ {s } ∪ S , {a } ∪ A , . . . n , . . . n ∼∼ S, {a } ∪ A , . . . n , {a} ∪ A , ctr n ∼∼ {s } ∪ S , {a } ∪ A , ctr + 1 n Rmsg

					m	m
				s 1	∼∼ s 1	s 2	∼∼ s 2	s↔s
					τ
			s {s} ∪ S s ∼∼ s
			m		m
		s	∼∼ s	a	∼∼ a	m
						s↔a
					τ
			a S, {a} ∪ A a ∼∼ a
			{'R',,{},addr}	{'R',ctr,{},addr}
	s	∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ s	a	∼∼∼∼∼∼∼∼∼∼∼∼∼∼∼ a
	{s} ∪ S

? = {'R', ,

Table 6 :

 6 Ring Node Semantics

Go implementations: https://github.com/giulio-garbi/goat

The simulator: https://bitbucket.org/Lazkany/abcsimulator

This research has been supported by the European projects IP 257414 ASCENS and STReP 600708 QUANTICOL.