Rami Katz
email: ramikatz@mail.tau.ac.il

Frédéric Mazenc
email: frederic.mazenc@l2s.centralesupelec.fr

Fellow, IEEE Emilia Fridman
email: emilia@tauex.tau.ac.il

ISS of rapidly time-varying systems via a novel superposition-based presentation

Keywords: stability, averaging, time-varying systems, ISS

We treat the input-to-state stability (ISS) of linear continuous-time systems with multiple time-scales. Such systems contain rapidly-varying, piecewise continuous and almost periodic coefficients with small parameters (time-scales). For systems with a single small parameter, a novel time-delay approach to averaging was recently introduced, whereas a complementary method for systems with multiple independent small parameters has been presented lately by the authors. The latter method relies on a novel system transformation, leading to a new system whose ISS guarantees the ISS of the original one. In this work, we unify this transformation with a new superposition-based system presentation. We employ timevarying Lyapunov functions for ISS analysis, where the novel system presentation plays a crucial role in deriving essentially less conservative compensating upper bounds. The analysis yields LMI conditions for ISS, leading to explicit bounds on the small parameters, decay rate and ISS gains. The LMIs are accompanied by suitable feasibility guarantees. Numerical examples demonstrate the efficacy of the proposed approach in comparison to existing methods.

I. INTRODUCTION

Systems with almost periodic signals and/or excitations are central to physics and engineering. Applications of such systems include vibrational control [START_REF] Cheng | On robustness analysis of linear vibrational control systems[END_REF], power systems [START_REF] Sandberg | Periodic modelling of power systems[END_REF] and time-delay systems [START_REF] Xie | Guaranteed cost control of periodic piecewise linear time-delay systems[END_REF] (see also references therein). Such systems often involve componenets evolving over multiple time-scales (see e.g. [START_REF] Hek | Geometric singular perturbation theory in biological practice[END_REF] for applications to systems biology). Hence, it is not surprising that perturbation theory played an essential part in the analysis of systems with rapidly timevarying coefficients and have led to important results [START_REF] Bogoliubov | Asymptotic methods in the theory of non-linear oscillations[END_REF], [START_REF] Khalil | Nonlinear systems third edition[END_REF], [START_REF] Kokotovic | Singular perturbations in systems and control[END_REF], [START_REF] Teel | A unified framework for inputto-state stability in systems with two time scales[END_REF], [START_REF] Moreau | Practical stability and stabilization[END_REF]. However, the majority of such results is qualitative in nature.

The method of averaging is an important perturbationbased technique for the study of stability of systems with oscillatory control inputs [START_REF] Bullo | Averaging and vibrational control of mechanical systems[END_REF], [START_REF] Krstić | Stability of extremum seeking feedback for general nonlinear dynamic systems[END_REF], [START_REF] Meerkov | Principle of vibrational control: theory and applications[END_REF]. The fundamental idea behind asymptotic averaging is that stability of the firstorder averaged system guarantees stability of the original rapidly-varying system for small enough values of the timescale parameter (see e.g. [START_REF] Murdock | Perturbations: theory and methods[END_REF]Chapter 8]). However, it is often the case that asymptotic averaging provides only an existence result, without an efficient and explicit bound on the small parameter under which the stability of the original system is preserved. For singularly perturbed systems, such bounds were derived in, e.g., [START_REF] Kokotovic | Singular perturbations in systems and control[END_REF] and [START_REF] Fridman | Effects of small delays on stability of singularly perturbed systems[END_REF] via a direct Lyapunov approach.

Recently, several advances in quantitative asymptotic averaging have been made. First, [START_REF] Fridman | Averaging of linear systems with almost periodic coefficients: A time-delay approach[END_REF] presented a constructive time-delay approach to periodic averaging of a system with a single fast time-scale. The approch relies on backward averaging of the system, which yields a neutral-type system presentation where the delay magnitude is equal to to the time-scale parameter. The stability of the delayed system was shown to guarantee the stability of the original system. Stability of the delayed system was analyzed via a direct Lyapunov method, leading to LMI conditions which yield an efficient upper bound on the small parameter that preserves the stability of the original system. This method is also well suited for averaging of systems with time-varying delays, where the delay magnitude is of equal order to the timescale parameter. These results were extended to L 2 -gain analysis for periodic averaging and to stochastic systems in [START_REF] Zhang | L2-gain analysis via time-delay approach to periodic averaging with stochastic extension[END_REF]. Second, [START_REF] Katz | Stability by averaging via timevarying lyapunov functions[END_REF] presented a complementary method for asymptotic averaging for ISS and stability in the presence of constant delays and multiple time-scales. Differently from [START_REF] Fridman | Averaging of linear systems with almost periodic coefficients: A time-delay approach[END_REF], this method employs a non-delayed system transformation, leading to a new system whose ISS guarantees the ISS of the original system. ISS analysis of the transformed system was performed via a direct Lyapunov method leading to LMIs which provide quantitative estimates on the small parameters, internal decay rate and ISS gains. The LMIs were accompanied by suitable feasibility guarantees. The approach in [START_REF] Katz | Stability by averaging via timevarying lyapunov functions[END_REF] was further extended to rapidly time-varying systems with constant delay, where the novel transformation decoupled the effects of the delay and time-scale parameter on stability, thereby leading to stability results for non-small delay (relative to the small parameter).

In this work we study ISS of rapidly time-varying systems with multiple time-scales. We employ a novel superpositionbased presentation of the system, in conjunction with a modified tranformation based on [START_REF] Katz | Stability by averaging via timevarying lyapunov functions[END_REF]. The superpositionbased presentation relies on two key ingredients: first, we write the rapidly-varying system matrices as superpositions of constant matrices with rapidly-varying scalar coefficients. Second, we force the latter coefficients to have zero averages. We then adapt the transformation from [START_REF] Katz | Stability by averaging via timevarying lyapunov functions[END_REF] to a new, superposition-based form, thereby obtaining a transformed system whose ISS guarantees the ISS of the original system. ISS of the transformed system is studied via time-varying Lyapunov functions leading to LMIs which provide quantitative estimates on the small parameters, internal decay rate and ISS gains. The LMIs are backed by theoretical feasibility guarantees. Extensive numerical examples show that our approach essentially improves the small parameter bounds for which ISS of the original system is preserved.

The article is organized as follows. Section 2 presents ISS results for rapidly time-varying systems. Numerical examples are given in Section 3. Conclusions are drawn in Section 4.

Notations: Throughout the paper R n denotes the ndimensional Euclidean space with the vector norm |•|, R n×m is the set of all n × m real matrices with the induced matrix norm ∥•∥. We also denote Z + = {0, 1, 2, . . . } and R ≥0 = [0, ∞). The superscript ⊤ denotes matrix transposition, and the notation P > 0, for P ∈ R n×n means that P is symmetric and positive definite. The symmetric elements of the symmetric matrix are denoted by * . For 0 < P ∈ R n×n and x ∈ R n , we write |x| 2 P = x ⊤ P x. ⊗ denotes the Kronecker product. The standard lexicographic order on R n is denoted by ≤ lex .

II. ISS-LIKE ESTIMATES OF RAPIDLY TIME-VARYING

SYSTEMS

A. Problem formulation

The recent work [START_REF] Fridman | Averaging of linear systems with almost periodic coefficients: A time-delay approach[END_REF] considered the fast-varying system

ẋ(t) = A t ϵ x(t) + B t ϵ d(t), t ≥ 0 (1)
where x(t) ∈ R n for t ≥ 0, ϵ > 0 is a small parameter defining a fast time-scale, d is a piecewise continuous disturbance and A : R → R n×n and B : R → R n×n d are piecewise continuous matrix functions, which are normbounded uniformly for t ∈ [0, ∞). Under the assumption that there exist 0 < T and A av , B av , such that

T -1 t+T t B(τ )dτ = B av + ∆B(t), T -1 t+T t A(τ )dτ = A av + ∆A(t), ∀t ∈ R (2)
with A av is Hurwitz and ∆A, ∆B : R → R n×n sufficiently small in norm, [START_REF] Fridman | Averaging of linear systems with almost periodic coefficients: A time-delay approach[END_REF] proposed a novel time-delay transformation, leading to quantitative estimate on ϵ for which ISS of (1) is preserved.

In this work we consider a more general system in the following superposition-based presentation:

ẋ(t) = A av + N i=1 a i t ϵi A i x(t) + B av + N d i=1 b i t ϵ d,i B i d(t), t ≥ 0 (3) where x(t) ∈ R n for t ≥ 0, N, N d ∈ N, {ϵ i } N i=1 and {ϵ d,i } N d i=1 are positive small parameters, {A i } N i=1 ⊆ R n×n , {B i } N d i=1 ⊆ R n×n d are constant matrices, and {a i } N i=1 , {b i } N d
i=1 are piecewise continuous scalar functions which are uniformly bounded on [0, ∞). We allow the arguments of the scalar functions to depend on different and independent time-scales.

For simplicity of presentation we will proceed with the case N = N d = 2. The general case follows the same arguments (see also Remark 8). We make the following assumption:

{T i } 2 i=1 , {T d,j } 2 j=1 such that T -1 i t+Ti t a i (τ )dτ =: ∆a i (t), T -1 d,j t+T d,j t b j (τ )dτ =: ∆b j (t), ∀t ∈ R (4) with {∆a i } 2 i=1 , {∆b j } 2 j=1 satisfying sup τ ∈R ∥∆a i (τ )∥ 2 ≤ ∆ ai,M , sup τ ∈R ∥∆b j (τ )∥ 2 ≤ ∆ bj ,M , 1 ≤ i, j ≤ 2 (5)
for some positive constants

{∆ ai,M } 2 i=1 , ∆ bj ,M 2
j=1 . We further assume that A av is Hurwitz.

Remark 1:

The assumption that the averages of a i and b j are zero is an essential component of the proposed superposition-based system presentation and leads to essentially less conservative LMI conditions for ISS. Note that this assumption poses no loss of generality, since we can always substract the averages from the corresponding functions, while retaining ∆a i and ∆b j on the right-hand side of (5) and modifying the matrices A av and B av .

Remark 2: The system (1) can be presented as (3) by fixing

ϵ i = ϵ d,j = ϵ, 1 ≤ i ≤ N, 1 ≤ j ≤ N d and presenting A t ϵ , B t ϵ
as linear combinations of constant matrices with time-varying coefficients. In this case N, N d ≤ n 2 .

We aim to derive efficient and constructive conditions which guarantee ISS-like estimates for (3), with respect to d and ḋ (see Theorem 1).

B. System transformation and Lyapunov analysis

Inspired by [START_REF] Mazenc | Further results on strict Lyapunov functions for rapidly time-varying nonlinear systems[END_REF], for t ≥ 0, 1 ≤ i, j ≤ 2 we introduce

ϱ ϵ,i (t) = -1 ϵiTi t+ϵiTi t g i (τ )a i τ ϵi dτ, ω ϵ d,j (t) = -1 ϵ d,j T d,j t+ϵ d,j T d,j t g d,j (τ )b j τ ϵ d,j dτ, g i (τ ) = t + ϵ i T i -τ, g d,j (τ ) = t + ϵ d,j T d,j -τ.
(6) Remark 3: Differently from [START_REF] Katz | Stability by averaging via timevarying lyapunov functions[END_REF], ϱ ϵ,i , ω ϵ d,i , a i and b i , i = 1, 2 are scalar (as opposed to matrix-valued) functions. Hence, efficient upper bounds on them can be easily obtained via standard tools from analysis. This fact plays a key role in obtaining the less conservative LMI conditions for ISS-like estimates below. Inspired by [START_REF] Mazenc | Further results on strict Lyapunov functions for rapidly time-varying nonlinear systems[END_REF], for t ≥ 0, 1 ≤ i, j ≤ 2 we introduce

ϱ ϵ,i (t) = -1 ϵiTi t+ϵiTi t g i (τ )a i τ ϵi dτ, ω ϵ d,j (t) = -1 ϵ d,j T d,j t+ϵ d,j T d,j t g d,j (τ )b j τ ϵ d,j dτ, g i (τ ) = t + ϵ i T i -τ, g d,j (τ ) = t + ϵ d,j T d,j -τ.
(7) Remark 4: Differently from [START_REF] Katz | Stability by averaging via timevarying lyapunov functions[END_REF], ϱ ϵ,i , ω ϵ d,i , a i and b i , i = 1, 2 are scalar (as opposed to matrix-valued) functions. Hence, efficient upper bounds on them can be easily obtained via standard tools from analysis. This fact plays a key role in obtaining the less conservative LMI conditions for ISS-like estimates below. Differentiating [START_REF] Fridman | Introduction to time-delay systems: analysis and control[END_REF], we have for

t ≥ 0 ρϵ,i (t) = a i t ϵi -∆a i t ϵi , ωϵ d,j (t) = b j t ϵ d,j -∆b j t ϵ d,j . (8)
We introduce the following transformation

z(t) = x(t) - 2 i=1 ϱ ϵ,i (t)A i x(t) - 2 i=1 ω ϵ d,i (t)B i d(t). (9)
Remark 5: For the case of ( 1) with a single time-scale, the time-delay transformation employed in [START_REF] Fridman | Averaging of linear systems with almost periodic coefficients: A time-delay approach[END_REF] has the form

z(t) = x(t) -G(t), G(t) = 1 ϵT t t-ϵT g(τ ) [A(τ )x(ϵτ ) + B(τ )d(ϵτ )] dτ, g(τ ) = τ -t + ϵT,
which leads to a neutral-type system. This transformation allows for ISS analysis which employs averaging of B t ϵ for measurable functions d, whereas (9) allows ISS for non differentiable d without averaging of B t ϵ only, which may be restrictive.

Compared to [START_REF] Fridman | Averaging of linear systems with almost periodic coefficients: A time-delay approach[END_REF], here we consider multiple fast timescales and unify the transformation in [START_REF] Katz | Stability by averaging via timevarying lyapunov functions[END_REF] with a novel system presentation. The non-delayed transformation ( 9) simplifies the Lyaponov-based analysis whereas the new system presentation (3) significantly improves the results in the numerical examples (see Section III).

Assumption 2: We assume that I n -

2 i=1 ϱ ϵ,i (t)A i is invertible for all t ≥ 0 with sup t≥0 I n - 2 i=1 ϱ ϵ,i (t)A i -1 ≤ δ 1,x < ∞.
Note that a sufficient condition for Assumption 2 to hold is

2 i=1 ϵ i T i a i,M ∥A i ∥ < 2, where a i,M := sup τ ∈R |a i (τ )|.
Indeed, in this case we have

sup t≥0 2 i=1 ϱ ϵ,i (t)A i ≤ 2 i=1 ϵiTia i,M ∥Ai∥ 2 =: δ 2,x < 1. (10
) By using a Neumann series, the latter implies we can take

δ 1,x = 2 2 - 2 i=1 ϵ i T i a i,M ∥A i ∥ = 1 1 -δ 2,x . (11)
We will further employ the notation

δ d := sup t≥0 ∥ n i=1 ω ϵ d ,i (t)B i ∥ . ( 12
)
Analogously to [START_REF] Katz | Stability by averaging via timevarying lyapunov functions[END_REF], we have

δ d ≤ 1 2 2 i=1 ϵ i T i b i,M ∥B i ∥ , b i,M := sup τ ∈R |b i (τ )| . ( 13
)
Note that d ∈ C 1 ([0, ∞)) implies that z(t) is continuously differentiable. By employing (3) we obtain the following expression for ż(t), t ≥ 0:

ż(t) = A av z(t) + 2 i=1 ϱ ϵ,i (t)A i x(t) + 2 i=1 ω ϵ d,i (t) + ×B i d(t)] + B av d(t) - 2 i=1 ω ϵ d,i (t)B i ḋ(t) + 2 i=1 ∆a i t ϵi A i x(t) + ∆b i t ϵ d,i B i d(t) - 2 i=1 ϱ ϵ,i (t)A i A av + 2 j=1 a j t ϵj A j x(t) - 2 i=1 ϱ ϵ,i (t)A i B av + 2 j=1 b j t ϵ d,j B j d(t). (14) Recall that ≤ lex is the lexicographic order on R n ((i, j) ≤ lex (k, l) iff i < k or i = k, j ≤ l). To vectorize (14), let Υ ϱ (t) = col {ϱ ϵ,i (t)x(t)} 2 i=1 , Z ω (t) = col ω ϵ d,j (t)d(t) 2 j=1 , Z ϱ (t) = col {ϱ ϵ,i (t)d(t)} 2 i=1 , Ξ ω (t) = col ω ϵ d,j (t) ḋ(t) 2 j=1 , Υ ϱ,a (t) = col ϱ ϵ,i (t)a k t ϵ k x(t) {(i,k)} ≤ lex , Z ϱ,b (t) = col ϱ ϵ,i (t)b j t ϵ d,j d(t) {(i,j)} ≤ lex , Υ ∆a (t) = col ∆a i t ϵi x(t) 2 i=1 , Z ∆b (t) = col ∆b j t ϵ d,j d(t) 2 j=1 , A = A 1 A 2 , A 1 = [A 2 1 A 1 A 2 A 2 A 1 A 2 2 ], A 2 = [A 1 B 1 A 1 B 2 A 2 B 1 A 2 B 2 ], B = B 1 B 2 , W = W 1 W 2 , W i = A av A i -A i A av , 1 ≤ i ≤ 2.
(15) Employing ( 9) and ( 14), we obtain the following expression for ż(t), t ≥ 0:

ż(t) = A av z(t) + B av d(t) + AΥ ∆a (t) + BZ ∆b (t) -A (I 2 ⊗ B av ) Z ϱ (t) + WΥ ϱ (t) -BΞ ω (t) +A av BZ ω (t) -A 1 Υ ϱ,a (t) -A 2 Z ϱ,b (t). ( 16
) Let H ϱ = col h (i) ϱ 2 i=1 , H ω = col h (j) ω 2 j=1 , H ϱ,a = col h (i,k) ϱ,a {(i,k)} ≤ lex , H ϱ,b = col h (i,j) ϱ,b {(i,j)} ≤ lex (17)
be vectors with nonnegative entries such that for any 1 ≤ i, k, j ≤ 2 and t ≥ 0 the following conditions hold

I) ϱ 2 ϵ,i (t) ≤ h (i) ϱ , II) ω 2 ϵ d,j (t) ≤ h (j) ω , III) ϱ 2 ϵ,i (t)a 2 k t ϵ k ≤ h (i,k) ϱ,a , IV ) ϱ 2 ϵ,i (t)b 2 j t ϵ d,j ≤ h (i,j) ϱ,b . (18)
Note that all the inequalities involve scalar functions. Let

Λ Υϱ , Λ Zϱ , Λ Υ∆a ∈ R 2×2 , Λ Zω , Λ Ξω , Λ Z ∆b ∈ R 2×2 and Λ Υϱ,a , Λ Z ϱ,b ∈ R 4×4 be
diagonal matrices with positive diagonal entries and recall [START_REF] Meerkov | Principle of vibrational control: theory and applications[END_REF]. By ( 5) and [START_REF] Sandberg | Periodic modelling of power systems[END_REF] we have

Υ ⊤ ϱ (t) Λ Υϱ ⊗ I n Υ ϱ (t) ≤ Λ Υϱ H ϱ 1 |x(t)| 2 , Z ⊤ ϱ (t) Λ Zϱ ⊗ I n Z ϱ (t) ≤ Λ Zϱ H ϱ 1 |d(t)| 2 , (19)
Z ⊤ ω (t) (Λ Zω ⊗ I n ) Z ω (t) ≤ |Λ Zω H ω | 1 |d(t)| 2 , Ξ ⊤ ω (t) (Λ Ξω ⊗ I n ) Ξ ω (t) ≤ |Λ Ξω H ω | 1 ḋ(t) 2 , Υ ⊤ ϱ,a (t) Λ Υϱ,a ⊗ I n Υ ϱ,a (t) ≤ Λ Υϱ,a H ϱ,a 1 |x(t)| 2 , Z ⊤ ϱ,b (t) Λ Z ϱ,b ⊗ I n Z ϱ,b (t) ≤ Λ Z ϱ,b H ϱ,b 1 |d(t)| 2 , Υ ⊤ ∆a (t) (Λ Υ∆a ⊗ I n ) Υ ∆a (t) ≤ |Λ Υ∆a ∆ a,M | 1 |x(t)| 2 , Z ⊤ ∆b (t) (Λ Z ∆b ⊗ I n ) Z ∆b (t) ≤ |Λ Z ∆b ∆ b,M | 1 |d(t)| 2 where ∆ a,M = col {∆ ai,M } 2 i=1 , ∆ b,M = col ∆ bj ,M 2
j=1 . (20) The upper bounds [START_REF] Teel | A unified framework for inputto-state stability in systems with two time scales[END_REF] will be employed to compensate

Υ ϱ (t), Z ϱ (t), Z ω (t), Ξ ω (t), Υ ϱ,a (t), Z ϱ,b (t), Υ ∆a (t)
and Z ∆b (t) in the derivation of ISS-like estimates below.

Remark 6: Recall that we assume the averages of the functions {a i } 2 i=1 and {b j } 2 j=1 to be zero (this is an essential part of the proposed superposition-based system presentation). By doing this, {ϱ ϵ,i } 2 i=1 and {ω ϵ d ,j } 2 j=1 obtained in [START_REF] Fridman | Introduction to time-delay systems: analysis and control[END_REF] have smaller L ∞ norms, whence the upper bounds in (18) will be of smaller magnitude. This fact plays a key role in achieving the less conservative LMIs (29) in the Lyapunov analysis.

For ISS-like estimates of (3), let 0 < α and 0 < P ∈ R n×n . We introduce the Lyapunov function

V (t) = |z(t)| 2 P (21)
and the notation

Q α := P A av + A ⊤ av P + 2αP (22)
Differentiating V along the solution to [START_REF] Moreau | Practical stability and stabilization[END_REF], we obtain

V + 2αV = |z(t)| 2 Qα + 2z ⊤ (t)P B av d(t) +2z ⊤ (t)P [AΥ ∆a (t) + BZ ∆b (t) + WΥ ϱ (t) + A av BZ ω (t)] -2z ⊤ (t)P [A (I 2 ⊗ B av ) Z ϱ (t) + BΞ ω (t)] -2z ⊤ (t)P [A 1 Υ ϱ,a (t) + A 2 Z ϱ,b (t)] .
(23) Substituting [START_REF] Hek | Geometric singular perturbation theory in biological practice[END_REF] and recalling [START_REF] Meerkov | Principle of vibrational control: theory and applications[END_REF], we have

|z(t)| 2 Qα = |x(t) -AΥ ϱ (t) -BZ ω (t)| 2 Qα = |x(t)| 2 Qα + |Υ ϱ (t)| 2 A ⊤ QαA + |Z ω (t)| 2 B ⊤ QαB -2x ⊤ (t)Q α AΥ ϱ (t) -2x ⊤ (t)Q α BZ ω (t) + Υ ⊤ ϱ (t)A ⊤ Q α BZ ω (t). (24) Similarly, z ⊤ (t)P B av d(t) = [x(t) -AΥ ϱ (t) -BZ ω (t)] ⊤ P B av d(t), z ⊤ (t)P [AΥ ∆a (t) + BZ ∆b (t) + WΥ ϱ (t) + A av BZ ω (t) -A (I 2 ⊗ B av ) Z ϱ (t) -BΞ ω (t) -A 1 Υ ϱ,a (t) -A 2 Z ϱ,b (t)] = [x(t) -AΥ ϱ (t) -BZ ω (t)] ⊤ P [AΥ ∆a (t) + BZ ∆b (t) +A av BZ ω (t) -A (I 2 ⊗ B av ) Z ϱ (t) -BΞ ω (t) -A 1 Υ ϱ,a (t) -A 2 Z ϱ,b (t) + WΥ ϱ (t)] (25)
Let

η(t) = col x(t), d(t), ḋ(t), Υ ϱ (t), Υ ϱ,a (t), Υ ∆a (t) Z ϱ (t), Z ϱ,b (t), Z ∆b (t), Z ω (t), Ξ ω (t)} (26)
Then, [START_REF] Teel | A unified framework for inputto-state stability in systems with two time scales[END_REF] implies that

0 ≤ W = η ⊤ (t) [Λ 0 -Λ 1 ] η(t), Λ 0 = diag Λ (1) 0 , Λ (2)
0 , Λ

0 , 0, 0, 0, 0, 0, 0, 0, 0 , Λ 1 = diag 0, 0, 0, Λ 19)-( 27) and the S-procedure ( [START_REF] Fridman | Introduction to time-delay systems: analysis and control[END_REF])

(1) 1 , Λ (3) 0 = |Λ Ξω H ω | 1 I n d , Λ (1) 0 = Λ Υϱ H ϱ 1 + Λ Υϱ,a H ϱ,a 1 + |Λ Υ∆a ∆ a,M | 1 I n , Λ (2) 0 = Λ Zϱ H ϱ 1 + |Λ Zω H ω | 1 + Λ Z ϱ,b H ϱ,b 1 + |Λ Z ∆b ∆ b,M | 1 I n d , Λ (1) 1 = diag Λ Υϱ , Λ Υϱ,a , Λ Υ∆a , Λ Zϱ , Λ Z ϱ,b , Λ Z ∆b , Λ Zω , Λ Ξω } ⊗ I n (27) By (
V + 2αV -γ 2 1 |d(t)| 2 -γ 2 2 ḋ(t) 2 ≤ V + 2αV -γ 2 1 |d(t)| 2 -γ 2 2 ḋ(t) 2 + W ≤ η ⊤ (t)Ψ ϵ,ϵ d η(t) ≤ 0, (28) provided Ψ ϵ,ϵ d =     Ψ (1) ϵ,ϵ d Ψ (2) ϵ,ϵ d Ψ (3) ϵ,ϵ d Ψ (4) ϵ,ϵ d * Ψ (5) ϵ,ϵ d Ψ (6) ϵ,ϵ d Ψ (7) ϵ,ϵ d * * Ψ (8) ϵ,ϵ d Ψ (9) ϵ,ϵ d * * * Ψ (10) ϵ,ϵ d     < 0 (29)
with

Ψ (1) ϵ,ϵ d =   Qα + Λ (1) 0 P Bav 0 * -γ 2 1 In d + Λ (2) 0 0 * * -γ 2 2 In d + Λ (3) 0   , Ψ (2)
ϵ,ϵ d = -QαA + P W -P A1 P A -B ⊤ av P A 0 0 0 0 0 , Ψ (3)
ϵ,ϵ d =

-P A (I2 ⊗ Bav) -P A2 P B 0 0 0 0 0 0 , Ψ (4)
ϵ,ϵ d = -QαB + P AavB -P B -B ⊤ av P B 0 0 0 , Ψ (5)
ϵ,ϵ d = ψ (1) ϵ,ϵ d A ⊤ P A1 -A ⊤ P A * -ΛΥ ϱ,a ⊗ In 0 * * -(ΛΥ ∆a ⊗ In) , Ψ (6)
ϵ,ϵ d = ψ (4) ϵ,ϵ d A ⊤ P A2 -A ⊤ P B 0 0 0 0 0 0 , Ψ (7)
ϵ,ϵ d =   ψ (2) ϵ,ϵ d A ⊤ P B A ⊤ 1 P B 0 -A ⊤ P B 0   , Ψ (9)
ϵ,ϵ d =   ψ (3) ϵ,ϵ d 0 A ⊤ 2 P B 0 -B ⊤ P B 0   , Ψ (8) ϵ,ϵ d = -diag Λ Zϱ , Λ Z ϱ,b , Λ Z ∆b ⊗ I n , Ψ (10) ϵ,ϵ d = -(ΛZ ω ⊗ In) + 2αB ⊤ P B B ⊤ P B * -(ΛΞ ω ⊗ In) , ψ (1) ϵ,ϵ d = -Λ Υϱ ⊗ I n + A ⊤ Q α A -A ⊤ P W -W ⊤ P A, ψ (2) ϵ,ϵ d = A ⊤ Q α B -W ⊤ P B -A ⊤ P A av B, ψ (3) ϵ,ϵ d = (I 2 ⊗ B av ) ⊤ A ⊤ P B, ψ (4) ϵ,ϵ d = A ⊤ P A (I 2 ⊗ B av ) .

Summarizing, we arrive at

Theorem 1: Consider the system (3) subject to Assumptions 1 and 2. Let H ϱ , H ω , H ϱ,a , H ϱ,b be given by [START_REF] Murdock | Perturbations: theory and methods[END_REF] and satisfying [START_REF] Sandberg | Periodic modelling of power systems[END_REF]. Given matrices A av , B av and

positive constants α, {ϵ i } 2 i=1 , {ϵ d,j } 2 j=1 , {T i } 2 i=1 {T d,j } 2 j=1 , {∆ ai,M } 2 i=1 , ∆ bj ,M 2 j=1 let there exist 0 < P ∈ R n×n , diagonal matrices Λ Υϱ , Λ Zϱ , Λ Υ∆a ∈ R 2×2 , Λ Zω , Λ Ξω , Λ Z ∆b ∈ R 2×2 and Λ Υϱ,a , Λ Z ϱ,b ∈ R 4×4
with positive diagonal entries, and positive scalars γ 2 1 , γ 2 2 such that Ψ ϵ,ϵ d < 0, with Ψ ϵ,ϵ d given in (29). Then (3) satisfies the ISS-like estimates

|x(t)| 2 ≤ β 2 1 e -2αt |x(0)| 2 + β 2 2 max s∈[0,t] |d(s)| 2 +β 2 3 max s∈[0,t] ḋ(s) 2 , t ≥ 0 (30)
for some β i > 0, i = 1, 2, 3. The LMI Ψ ϵ,ϵ d < 0 is always feasible for small enough α,

{ϵ i } 2 i=1 , {ϵ d,j } 2 j=1 , {∆ ai,M } 2 i=1 , ∆ bj ,M 2 j=1 and large γ 2 i , i = 1, 2. Moreover, there exist α, {ϵ i } 2 i=1 , {ϵ d,j } 2 j=1 such that Ψ ϵ ′ ,ϵ ′ d < 0 is feasible for all ϵ ′ i < ϵ i , i = 1, 2 and ϵ ′ d,j < ϵ d,j , j = 1, 2, implying that β i in (30) do not depend on ϵ ′ i < ϵ i , i = 1, 2 and ϵ ′ d,j < ϵ d,j , j = 1, 2. Proof: Fix τ > 0. Feasibility of (29) implies that for all t ∈ [0, τ ] V + 2αV -γ 2 1 |d(t)| 2 -γ 2 2 ω ϵ d (t) ḋ(t) 2 ≤ 0 ⇒ V (t) ≤ e -2αt V (0) + t 0 e -2α(t-s) γ 2 1 |d(s)| 2 + γ 2 2 ḋ(s) 2 ds.
Since [START_REF] Moreau | Practical stability and stabilization[END_REF] satsfies ISS-like estimates with respect to d and ḋ . To obtain ISS-like estimates for (3), we employ the transformation [START_REF] Hek | Geometric singular perturbation theory in biological practice[END_REF]. By Assumption 2, (10), ( 12), Young's inequality and the triangle inequality

|z(0)| 2 ≤ 2δ 2 2,x |x(0)| 2 + 2δ 2 d max s∈[0,τ ] |d(s)| 2 |x(t)| 2 ≤ δ 2 1,x z(t) + 2 i=1 ω ϵ d,i (t)B i d(t) 2 ≤ 2δ 2 1,x |z(t)| 2 + 2δ 2 1,x δ 2 d max s∈[0,τ ] |d(s)| 2 .
By combining the latter with (31), we obtain (30) with

β 2 1 = 4δ 2 1,x δ 2 2,x λmax(P ) λmin(P ) , β 2 3 = 2δ 2 1,x γ 2 2 2αλmin(P ) , β 2 2 = 2δ 2 1,x δ 2 d 2λmax(P )+λmin(P ) λmin(P ) + γ 2 1 2αλmin(P ) .
For LMI feasiblity guarantees, it is enough to consider the case when the small parameters satisfy ϵ i = ϵ d,j = ϵ, i, j = 1, 2. Recall ( 7) and [START_REF] Sandberg | Periodic modelling of power systems[END_REF]. It can be easily verified that there exists a constant K > 0 large enough, such that [START_REF] Sandberg | Periodic modelling of power systems[END_REF] holds when all entries of ( 17) are equal to Kϵ 2 . Next, choose Λ Υϱ , Λ Zϱ , Λ Υ∆a , Λ Zω , Λ Ξω , Λ Z ∆b = λI 2 and Λ Υϱ,a , Λ Z ϱ,b = λI 4 , where λ > 0. Henceforth, we fix these choices. We begin by choosing α = 0, 0 < P ∈ R n such that Q α < 0 (see ( 22)). Fixing P and ϵ < 1 we look at the LMI (29). Considering the bottom-right 3 × 3 block submatrix (which we will henceforth denote as Ξ ϵ,ϵ d ) we see that Ξ ϵ,ϵ d < 0 for λ > λ * with λ * > 0 large enough (the diagonal elements are linear and negative in λ). Next, we apply Schur complement with respect to Ξ ϵ,ϵ d , to obtain the equivalent matrix inequality

Ψ (1) ϵ,ϵ d -1 λ Ψ (2) ϵ,ϵ d Ψ (3) ϵ,ϵ d Ψ (4) ϵ,ϵ d λ -1 Ξ ϵ,ϵ d -1 × Ψ (2) ϵ,ϵ d Ψ (3) ϵ,ϵ d Ψ (4) ϵ,ϵ d ⊤ < 0. ( 32
)
Note that λ -1 Ξ ϵ,ϵ d -1 is bounded as λ → ∞ (converges to the identity matrix), whereas

Ψ (2) ϵ,ϵ d Ψ (3) ϵ,ϵ d Ψ (4)
ϵ,ϵ d is independent of λ. On the other hand, for any λ > 0, we can always find ϵ > 0 small enough and γ i > 0, i = 1, 2 large enough so that Ψ

(1) ϵ,ϵ d < 0. Indeed, by choosing

γ i = λ 2 , i = 1, 2, ϵ = 1
λ 2 , we obtain that (32) holds for λ > 0 large enough, whence feasibility of (29) follows. The fact that feasibility of (29) for some α,

{ϵ i } 2 i=1 , {ϵ d,j } 2 j=1
implies its feasibility for all ϵ ′ i < ϵ i , i = 1, 2 and ϵ ′ d,j < ϵ d,j , j = 1, 2 and the same α, γ i , i = 1, 2 follows from monotonicity of (29) with respect to ϵ ′ i < ϵ i , i = 1, 2 and ϵ ′ d,j < ϵ d,j , j = 1, 2 (meaning that as the small parameters decrease, the eigenvalues of Ψ ϵ ′ ,ϵ ′ d are non-increasing). Remark 7: Recall ( 17) and ( 18). In the Lyapunov analysis above we assume the scalar bounds on the right-hand side of ( 18) are identical for all t ≥ 0. Assume that there exists a partition of [0, ∞) into intervals such that every interval in the partition belong to one of finitely many classes (types), denoted by {I j } ζ j=1 . As an example, consider Example 2.3.1 below, where we treat a switched system with two functioning modes (35). In this case ζ = 2 and I 1 corresponds to subintervals where A(τ ) ≡ A 1 , whereas I 2 corresponds to subintervals where A(τ ) ≡ A 2 . Assume that for each 1 ≤ j ≤ ζ, there exist vectors H ϱ,j , H ω,j , H ϱ,a,j , H ϱ,b,j whose entries serve as upper bounds in (18) whenever t ≥ 0 belongs to an interval of type I j (the vectors may vary between classes). In this case our proposed approach can be applied to each of the classes separately and will yield ζ LMIs of the form (29) (one for each class). Feasibility of the LMIs can then be verified simultaneously with the same P and γ i , i = 1, 2. Note that the auxilliary matrices

Λ Υϱ , Λ Zϱ , Λ Υ∆a , Λ Zω , Λ Ξω , Λ Z ∆b , Λ Υϱ,a , Λ Z ϱ,b
may differ between LMIs corresponding to different classes. This approach is expected to yield less conservative results than choosing bounds in [START_REF] Sandberg | Periodic modelling of power systems[END_REF] which hold uniformly for all t ≥ 0, and verifying feasibility of a single LMI (29).

Remark 8: For the case of general N, N d ∈ N, the approach presented above requires only minor modifications, which are related to the dimensions of the matrices. In particular, in [START_REF] Meerkov | Principle of vibrational control: theory and applications[END_REF] the dimensions of the vectors require changing, whereas the matrices now having the form

A = A 1 . . . A N , B = B 1 . . . B N d , A 1 = [A 2 1 . . . A 1 A N . . . A N A 1 . . . A 2 N ], A 2 = [A 1 B 1 . . . A 1 B N d . . . A N B 1 . . . A N B N d ], W = W 1 . . . W N , W i = A av A i -A i A av , 1 ≤ i ≤ N. (33)
The system [START_REF] Moreau | Practical stability and stabilization[END_REF] (and the derived LMIs) will have the same form with I 2 replaced by I N d . Therefore, the Lyapunov analysis and resulting LMIs of Section 2.3 will be identical, subject to the changes in (33) and I 2 replaced by I N d will guarantee (30) for (3).

Remark 9: Note that instead of the ISS-like estimates (30), we are also able to obtain standard ISS bounds (meaning, with respect to d only) for (3). Indeed, consider the system (3). In order to avoid introducing the disturbance derivative one can simply not use averaging for

2 i=1 b i t ϵ d,i B i d(t).
Instead, one can treat this term as a norm bounded time-varying matrix-valued function which multiplies the disturbance. In this case the presentation of this matrix valued function as a linear combination is obviously not needed and (9) will be replaced with z(t) = x(t) -

2 i=1 ϱ ϵ,i (t)A i x(t). The norm bound on 2 i=1 b i t ϵ d,i B i
will be employed in a standard ISS analysis. This approach is expected to result in larger estimates on the ISS gains.

III. NUMERICAL EXAMPLES

Set

A(τ ) = A 1 , τ ∈ [k, k + 0.4), k ∈ Z + A 2 , τ ∈ [k + 0.4, k + 1), k ∈ Z + . ( 35
)
Given τ ∈ [k, k + 1), (35) can be written as

A (τ ) = χ [k,k+0.4) (τ ) A 1 + 1 -χ [k+0.4,k+1) (τ ) A 2 ,
where χ [k,k+0.4) is the indicator function of [k, k+0.4). Note that A (τ ) is 1-periodic. We further set B(t) ≡ 0 2×1 . Consider (3) with (35),

ϵ i = ϵ, T i = 1, i = 1, 2 and B av = B 1 = B 2 = 0. Here a 1 (τ ) = 0.6, τ ∈ [k, k + 0.4), k ∈ Z -0.4, τ ∈ [k + 0.4, k + 1), k ∈ Z , a 2 (τ ) = -a 1 (τ ).
Note that the latter functions are 1-periodic, meaning that ∆ ai,M = 0, i = 1, 2 in (20). Let t ∈ [mϵ, (m + 1)ϵ), m ∈ Z + and denote w = t -mϵ ∈ [0, ϵ), m ∈ Z + . An explicit computation of ϱ ϵ,i (t), i = 1, 2 in (7) yields the bounds ϱ 2 ϵ,1 (t) ≤ 0.0144ϵ 2 and ϱ 2 ϵ,2 (t) ≤ 0.0144ϵ 2 . We then use the fact that a 1 (τ ), a 2 (τ ) are indicator functions to separate the analysis into two cases

a 1 t ϵ ϱ ϵj (t) = 0.6ϱ ϵ,j (t), w ∈ [0, 0.4ϵ) -0.4ϱ ϵ,j (t), w ∈ [0.4ϵ, ϵ) a 2 t ϵ ϱ ϵ,j (t) = -a 1 t ϵ ϱ ϵj (t)
and obtain tight upper bounds in [START_REF] Sandberg | Periodic modelling of power systems[END_REF] for each of the cases. Thus, we separate the analysis into the two subintervals 0 ≤ w < 0.4ϵ and 0.4ϵ ≤ w < ϵ. For each subinterval (and its corresponding bounds [START_REF] Sandberg | Periodic modelling of power systems[END_REF]) we obtain an LMI of the form (29) (see Remark 7). We verify feasibility for both LMIs with the same α and P .

We consider α ∈ {0, 0.005, 0.01} and verify the LMIs of Theorem 1 to obtain the maximal value ϵ * which preserves feasibility of the LMIs. Note that ϵ * guarantees internal exponential stability (and thus the ISS-like bounds) of ( 3). The values of ϵ * are given in Table I, where we further compare our results to the bounds in the recent work [START_REF] Zhang | L2-gain analysis via time-delay approach to periodic averaging with stochastic extension[END_REF]. It is seen that our results essentially improve the results of [START_REF] Zhang | L2-gain analysis via time-delay approach to periodic averaging with stochastic extension[END_REF] with a value of ϵ * larger by more than 2.5 times. Next, we set B av = [0 1] ⊤ and B 1 = B 2 = 0 2×1 and verify feasibility of (29) in order to guarantee (30). Note that in this case the transformation (9) will not result in terms involving ḋ. Hence, we obtain classical ISS estimates (i.e., we have γ 2 = 0 in (28) β 3 = 0 in (30)). Table II presents several pairs (β 1 , β 2 ) (see proof of Theorem 30) for different choices of α and ϵ. Note that in this case δ 1,x and δ 2,x were computed using the bounds [START_REF] Katz | Stability by averaging via timevarying lyapunov functions[END_REF] and [START_REF] Khalil | Nonlinear systems third edition[END_REF].

α = 0 α = 0.005 α = 0.
ϵ =

B. Example 3.2: Stabilization by fast switching II

We consider stabilization by fast switching of a linear system with three functioning modes ( [START_REF] Albea | Time-triggered and event-triggered control of switched affine systems via a hybrid dynamical approach[END_REF] and [START_REF] Caiazzo | Averaging of systems with fast-varying coefficients and non-small delays with application to stabilization of affine systems via time-dependent switching[END_REF]) . Let ϵ > 0 and A av = 0.047 0.33 -0.6 -0.87

, A 1 = 0 0.5 0 -1 , A 2 = 0.1 0 -1 -1 , A 3 = 0 1 -1 0 (36)
and set

A(τ ) =      A 1 , τ ∈ [k, k + 0.4), k ∈ Z + A 2 , τ ∈ [k + 0.4, k + 0.87), k ∈ Z + A 3 , τ ∈ [k + 0.87, k + 1), k ∈ Z + . (37)
Note that A (τ ) is 1-periodic. We further set B(t) ≡ 0 2×1 . Consider (3) with (35), ϵ i = ϵ, T i = 1, i = 1, 2, 3 and

B av = B 1 = B 2 = B 3 = 0. Here for k ∈ Z + a 1 (τ ) = χ [k,k+0.4) (τ ) -0.4, a 2 (τ ) = χ [k+0.4,k+0.87) (τ ) -0.47, a 3 (τ ) = χ [k+0.87,k+1) (τ ) -0.13.
where χ [a,b) (τ ) denotes the indicator of [a, b) ⊆ R. Note that the latter functions are 1-periodic, meaning that ∆ ai,M = 0, i = 1, 2, 3 in (20). Similarly to Example 3.2.1, an explicit computation of ϱ ϵ,i (t), i = 1, 2 in (7) yields the bounds ϱ 2 ϵ,1 (t) ≤ 0.0144ϵ 2 , ϱ 2 ϵ,2 (t) ≤ 0.0155127ϵ 2 and ϱ 2 ϵ,3 (t) ≤ 0.0031979ϵ 2 . We then use the fact that a 1 (τ ), a 2 (τ ) and a 3 (τ ) are indicator functions to separate the analysis into three cases, corresponding to the subintervals in (37). For each subinterval (and corresponding bounds ( 18)) we obtain an LMI of the form (29) (see Remarks 7,[START_REF] Fridman | Averaging of linear systems with almost periodic coefficients: A time-delay approach[END_REF]. We verify feasibility for both LMIs with the same α and P .

We consider α ∈ {0, 0.005, 0.25} and verify the LMIs of Theorem 1 to obtain the maximal value ϵ * which preserves feasibility of the LMI. Note that ϵ * guarantees internal exponential stability (and thus ISS-like bounds) of ( 3). The values of ϵ * are given in Table III.

(τ ) = χ [k,k+0.4) (τ ), a 2 (τ ) = χ [k+0.4,k+1) (τ ), Example 2.3.2: a 1 (τ ) = χ [k,k+0.4) (τ ), a 2 (τ ) = χ [k+0.4,k+0.87) (τ ), a 3 (τ ) = χ [k+0.87,k+1) (τ ).
leads to essentially smaller ϵ * . For example, for α = 0 we find ϵ * = 0.1566 (compared to 0.4332) in example 2.3.1 and ϵ * = 0.141 (compared to 0.4341) in example 2.3.2.

The reason for the significantly improved results is that ϱ ϵ,i become essentially smaller when the averages a av,i are zero (see Remark 1), thereby decreasing the bounds required on the right-hand side of (18).

C. Example 3.3: Control of a pendulum

We consider a suspended pendulum with the suspension point that is subject to vertical vibrations of small amplitude and high frequency (see [START_REF] Khalil | Nonlinear systems third edition[END_REF]Example 10.10] Note that a i , i = 1, 2 are 2π-periodic, whence ∆ ai,M = 0, i = 1, 2 in ( 20). An explicit computation of ϱ ϵ,i (t), i = 1, 2 in (7) yields ϱ ϵ,1 (t) = ϵ sin (τ ) , a 2 (τ ) ϱ ϵ,2 (t) = ϵ 4 sin (4τ ) , ϱ ϵ,2 (t) = a 1 (τ ) ϱ ϵ,1 (t) = ϵ cos (τ ) sin (τ ) , a 2 (τ ) ϱ ϵ,1 (t) = (2 cos 2 (τ ) -1)ϱ ϵ,1 (t), a 1 (τ ) ϱ ϵ,2 (t) = cos 2 (τ ) ϱ ϵ,1 (t), τ = t ϵ which are used to derive the upper bounds in [START_REF] Sandberg | Periodic modelling of power systems[END_REF]. Differently from the previous examples, here we obtain only one LMI of the form (29).

We consider α ∈ 0, 1 10π and verify the LMIs of Theorem 1 to obtain the maximal value ϵ * which preserves feasibility of the LMI. Note that ϵ * guarantees internal exponential stability (and thus the ISS-like bounds) of ( 3). The values of ϵ * are given in Table IV, where we further compare our results to the bounds in the recent work [START_REF] Zhang | L2-gain analysis via time-delay approach to periodic averaging with stochastic extension[END_REF].

α = 0 α = (10π) -1
Zhang & Fridman 0.0074 0.005 Thm. 1 0.0457 0.0321 Finally, we consider this example subject to uncertainty. For that purpose, we replace a 2 (τ ) = cos(2τ ) with a 2 (τ ) = cos(2τ )+0.4g(τ ), where ∥g∥ ∞ ≤ 0.1. In this case we obtain a nonzero ∆a 2 (t) in (4), satisfying ∥∆a 2 ∥ ∞ ≤ 0.04 =: ∆ a2,M . We consider α ∈ 0, 1 10π and verify the LMIs of Theorem 1 to obtain the maximal value ϵ * which preserves feasibility of the LMI. We further compare our results with [START_REF] Zhang | L2-gain analysis via time-delay approach to periodic averaging with stochastic extension[END_REF]Example 4.1]. The results are given in Table V. Our results are essentially better than the results of [START_REF] Zhang | L2-gain analysis via time-delay approach to periodic averaging with stochastic extension[END_REF].

α = 0 α = (10π) -1
Fridman & Zhang 0.0058 0.0034 Thm. 1 0.0204 0.0146

IV. CONCLUSION

We introduced a novel quantitative methodology for deriving ISS-like estimates for linear continuous-time systems. The presented methodology relies on a superpositionbased system presentation, in conjunction with a system transformation. Differently from the time-delay approach to averaging, the presented method is efficient for ISS of systems with fast-varying almost periodic coefficients subject to multiple independent time-scale parameters, and achieves essentially less conservative LMI conditions for ISS-like estimates. Future work may include extension of the method to systems with delays and applications to control problems that employ averaging.

Assumption 1 : 2 i=1 and {b j } 2 j=1

 122 {a i } are almost periodic and there exist positive

A. Example 3 . 1 :

 31 Stabilization by fast switching I Consider stabilization by fast switching of a linear system [8, Example 2.2]. Let ϵ > 0 and

Remark 10 :

 10 In examples 3.1 and 3.2, presenting the systems as (3) with A av = 0 and Example 2.3.1: a 1

B 2 = 1

 21 and [8, Example 2.1]). Let ϵ > 0 andA(τ ) = cos(τ ) 1 0.04 -cos 2 (τ ) -0.2 -cos(τ ) , B(τ ) ≡ 0 2×1 . (38) Note that A(τ ) is 2π periodic. Consider (3) with ϵ i = ϵ, T i = 2π, i = 1, 2, B 0 = B 1 = (τ ) = cos(τ ), a 2 (τ ) = cos(2τ ).

TABLE I SWITCHED

 I SYSTEM I -MAXIMUM VALUE ϵ * PRESERVING LMI

FEASIBILITY.

TABLE II SWITCHED

 II SYSTEM I -ISS GAINS: (β 1 , β 2 ).

TABLE III SWITCHED

 III

SYSTEM II -MAXIMUM VALUE ϵ * PRESERVING LMI FEASIBILITY.

TABLE IV PENDULUM

 IV -MAXIMUM VALUE ϵ * PRESERVING LMI FEASIBILITY.

TABLE V PENDULUM

 V WITH UNCERTAINTY -MAXIMUM VALUE ϵ * PRESERVING LMI FEASIBILITY.

Supported by Israel Science Foundation (grant no. 673/19) and by Chana and Heinrich Manderman Chair at Tel Aviv University.


Ludovic Paillat
email: ludovic.paillat@hivenet.com

Claudia-Lavinia Ignat

Davide Frey
email: davide.frey@inria.fr

Mathieu Turuani
email: mathieu.turuani@inria.fr

Amine Ismail
email: amine.ismail@hivenet.com

Design of an Efficient Distributed Delivery Service for Group Key Agreement Protocols

Keywords: Distributed systems, Group key agreement, Consensus protocols, Reliable broadcast

End-to-end encrypted messaging applications such as Signal became widely popular thanks to their capability to ensure the confidentiality and integrity of online communication. While the highest security guarantees were long reserved to two-party communication, solutions for n-party communication remained either inefficient or less secure until the standardization of the MLS Protocol (Messaging Layer Security). This new protocol offers an efficient way to provide end-to-end secure communication with the same guarantees originally offered by the Signal Protocol for two-party communication. However, both solutions still rely on a centralized component for message delivery, called the Delivery Service in the MLS Protocol. The centralization of the Delivery Service makes it an ideal target for attackers and threatens the availability of any protocol relying on MLS. In order to overcome this issue, we propose the design of a fully distributed Delivery Service that allows clients to exchange protocol messages efficiently and without any intermediary. It uses a Probabilistic Reliable-Broadcast mechanism to efficiently deliver messages and the Cascade Consensus Protocol to handle messages requiring an agreement. Our solution strengthens the availability of the MLS Protocol without compromising its security.

Introduction

To protect the privacy of their users, a number of Internet-based services have started to develop solutions based on end-to-end encryption (E2EE) that prevent third parties from accessing user data transferred from one endpoint to another.

Secure messaging applications such as Signal and WhatsApp are well-known to advertise their use of E2EE. Indeed, the Signal Protocol was the first to propose E2EE for two-party conversations using the Double Ratchet algorithm [START_REF] Perrin | The double ratchet algorithm[END_REF].

However, the solutions proposed by these same messaging applications for nparty secure communication were either inefficient by requiring the establishment of encrypted communication between all pairs of group members, or less secure when using a common encryption key (e.g. Sender Keys Protocol [START_REF] Balbás | Analysis and improvements of the sender keys protocol for group messaging. XVII Reunión española sobre criptología y seguridad de la información[END_REF]) which may not be refreshed as the group dynamically changes.

To address the topic of secure group communication, industrial and academic organizations such as Cisco, Mozilla, Facebook and Inria proposed the Messaging Layer Security Protocol (MLS) standardized as RFC 9420 [START_REF] Barnes | The Messaging Layer Security (MLS) Protocol[END_REF]. This protocol relies on a Group Key Agreement Protocol called TreeKEM [START_REF] Bhargavan | TreeKEM: Asynchronous Decentralized Key Management for Large Dynamic Groups A protocol proposal for Messaging Layer Security (MLS)[END_REF] allowing members of a group to derive a common secret called group key which serves as a basis to secure group communications. It is scalable in terms of the number of operations modifying the group and it supports periodic group-key renewals preventing compromised communication.

The MLS Protocol offers an efficient solution to guarantee the confidentiality and integrity of communication. However, the availability of the protocol depends on the Delivery-Service component, which remains centralized most of the time. The centralization of this component makes it an ideal target for attackers who wish to disrupt communication. Notably, with the help of a compromised Delivery Service, an attacker can prevent group members from refreshing their keys and resolving the compromise.

In order to overcome these limitations we propose a fully distributed Delivery Service. It combines two distributed communication mechanisms adapted to the need of the messages exchanged by the protocol. We use a Probabilistic Reliable Broadcast mechanism [START_REF] Guerraoui | Scalable Byzantine Reliable Broadcast (Extended Version)[END_REF] to reliably deliver messages allowing users to propose changes to the group (i.e. Proposal messages) and the Cascade Consensus Protocol [START_REF] Albouy | Context adaptive cooperation[END_REF] to deliver the messages that actually modify the group (i.e. Commit messages) and thus require an agreement between members.

Our contribution is two-fold:

the formalization of the MLS protocol's Delivery Service, detailing the necessary properties of this component; a novel algorithm describing a fully distributed Delivery Service.

We start by reviewing the state of the art of distributed communication mechanisms in Section 2. We then present the TreeKEM Protocol and formalize the Delivery Service in Section 3. Section 4 presents the details of our solution and discusses how it increases the security of the protocol with respect to a centralized approach. Finally, Section 5 concludes the paper and presents some future work directions.

Related work

Secure communication requires securely sharing encryption keys thus preventing attackers from gaining access to them. Additionally, as communications can remain established for a long time, protocols must provide a way to mitigate the eventual compromise of some keys. The following security properties need to be ensured:

-Backward secrecy: the knowledge of previous keys does not affect the security of the current key and future ones. -Forward secrecy: the knowledge of a key does not affect the security of previous keys. -Post-Compromise security: if a member is compromised, an Update operation from this member will resolve the compromise and restore the security of the group in subsequent states.

The Signal protocol based on the Double Ratchet Algorithm [START_REF] Perrin | The double ratchet algorithm[END_REF] provides strong security guarantees for two-party communication. The Double Ratchet algorithm provides Forward secrecy by generating a new encryption key for each message while periodical Diffie-Hellman key exchanges provide fresh security material ensuring Post-Compromise security. However, this approach cannot be applied to group (i.e. n-party) communication and the use of pairwise communication channels (i.e. a group member sends a message to the group by using n -1 secure communication channels established with the other members) does not scale well.

An alternative, Sender Keys [START_REF] Balbás | Analysis and improvements of the sender keys protocol for group messaging. XVII Reunión española sobre criptología y seguridad de la información[END_REF], allows one member to use pairwise communication channels to share a common encryption key that can be used to encrypt messages. While this key can be used to deterministically generate individual message keys to provide Forward Secrecy, Post-Compromise security is not ensured as the common key is only renewed in rare occasions such as member removal. Thus, the compromise of one member makes it possible to spy on future messages for a long time.

Secure group-communication protocols address these drawbacks. In the following, we first present the main existing protocols for secure group communication and we highlight the advantages of TreeKEM [START_REF] Bhargavan | TreeKEM: Asynchronous Decentralized Key Management for Large Dynamic Groups A protocol proposal for Messaging Layer Security (MLS)[END_REF]. We then describe the distributed communication mechanisms we selected to make it distributed.

Secure Group Communication

First attempts to secure group communication were Conference Key Distribution Systems in which a member generates a conference key and distributes it to all group members. Different topologies for Distribution Systems [START_REF] Burmester | A secure and efficient conference key distribution system[END_REF] were proposed. However the Star-Based topology is inefficient as it requires O(n) key exchanges, while other topologies such as a Tree or a Cyclic System cannot tolerate the fault of even one participant.

Group Key Agreement protocols were introduced as a way to establish and manage dynamic groups whose members can derive a common encryption key called group key. These protocols mainly provide three operations: the Add and Remove operations to manage the group and the Update operation to allow group members to refresh their secret keys. Each operation leads to a new group key, thereby Add and Remove operations guarantee backward and forward secrecy for the group key while periodical Updates ensure post-compromise security. Thus, if a member does not renew its secret key, this member should be removed from the group as a compromise of this member threatens the security of the group.

Collaborative Group Key Agreement protocols were the first to establish a group key built on the principle of the Diffie-Hellman key exchange. The GDH protocols [START_REF] Ateniese | Authenticated group key agreement and friends[END_REF][START_REF] Steiner | Key agreement in dynamic peer groups[END_REF] allow members to collaboratively build the group key presented in Equation 1. However, the computation of this key requires O(n) communication rounds. The TGDH (Tree-based Group Key Agreement) protocol [START_REF] Kim | Simple and fault-tolerant key agreement for dynamic collaborative groups[END_REF] establishes a group key more efficiently in O(log n) rounds. The underlying binary-tree structure contains the member keys in the leafs, intermediate keys exchanged between sub-groups (i.e. members sharing one node in their path to the root of the tree) and the root representing the group key. The resulting group key for a 5-member group is presented in Equation 2. Additionally, operations on the group only require the modification of O(log n) intermediate keys.

K = α r1×r2ו••×rn (1) K = α α ( α r 1 ×r 2 ) × ( α r 3 ×r 4 ) ×r5 (2)
Nevertheless, the TGDH protocol cannot tolerate the fault or disconnection of any member, as each member can only modify their path to the root of the tree. Thus, the removal of one member from the tree requires the participation of the closest neighbor to this member in the tree. The ART (Asynchronous Ratcheting Trees) protocol [START_REF] Cohn-Gordon | On ends-toends encryption: Asynchronous group messaging with strong security guarantees[END_REF] enhances TGDH with the capability of creating a group in which all members but the group creator are not required to be online. In this protocol, the group creator can create the initial tree by using the X3DH key exchange algorithm [START_REF] Moxie | Signal -specifications -the x3dh key agreement protocol[END_REF] with ephemeral keys stored by each group member in a Public Key Infrastructure. This key exchange guarantees that each group member will be able to derive only the keys they should know with the exception of the group creator who initially knows the entire tree.

The more recent TreeKEM protocol [START_REF] Bhargavan | TreeKEM: Asynchronous Decentralized Key Management for Large Dynamic Groups A protocol proposal for Messaging Layer Security (MLS)[END_REF] allows clients to issue asynchronous group operations. By replacing the tree structure based on Diffie-Hellman with a tree structure based on the principle of Key Derivation, the TreeKEM protocol allows any member to carry out operations on the tree without requiring the help of any particular group member. The TreeKEM protocol achieves good performance and was backed by multiple security analyses (i.e. [START_REF] Alwen | Modular design of secure group messaging protocols and the security of mls[END_REF], [START_REF] Brzuska | Security analysis of the mls key derivation[END_REF], . . . ). It is part of a complete solution for Secure Group Communication, the MLS Protocol [START_REF] Barnes | The Messaging Layer Security (MLS) Protocol[END_REF] standardized in RFC 9420. For all these reasons we rely on TreeKEM as a basis for our proposed distributed Group Key Agreement mechanism.

Distributed Communication Mechanisms

We extend TreeKEM by focusing on two distributed communication mechanisms adapted for the delivery of Proposal and Commit messages as described in Section 3.1.

In the case of Proposal messages, which are sent by members only to propose modifications to the group, and thus do not require agreement, we use a Reliable Broadcast protocol. This protocol only focuses on the correct delivery of a message from a specific sender to all group members. Specifically we adopt a gossip-based Scalable Reliable Broadcast protocol [START_REF] Guerraoui | Scalable Byzantine Reliable Broadcast (Extended Version)[END_REF] with a O(log(n)) per-process communication and computation complexity where n is the number of processes. More precisely, we adopt Murmur [START_REF] Guerraoui | Scalable Byzantine Reliable Broadcast (Extended Version)[END_REF], a gossipbased dissemination protocol which only guarantees the delivery of messages without the ability to provide an order of messages for a given member. This protocol perfectly fits the requirements for Proposal messages as these messages do not need to be ordered in any way.

For dealing with Commit messages, which need to be totally ordered and thus require agreement between group members, we use the Cascade Consensus Protocol [START_REF] Albouy | Context adaptive cooperation[END_REF]. Below, we first provide a description of the Context-Adaptative Cooperation abstraction which is an important part of Cascade Consensus and then we detail the Cascade Consensus protocol.

Context-Adaptative Cooperation. Context-Adaptative Cooperation (CAC)

is a new broadcast abstraction that sits between reliable broadcast and consensus [START_REF] Albouy | Context adaptive cooperation[END_REF]. It allows multiple senders to send concurrent messages and focuses on the ability to detect when some messages are indeed sent concurrently and conflict with each other.

In CAC, contrary to classical reliable broadcast protocols, the protocol will not only deliver a message but also a conflict-set indicating other messages that might conflict with the delivered one. Therefore, CAC can act as a reliable broadcast when there is not any conflict during a broadcast instance. Otherwise, in the case of a conflict between multiple senders, this conflict will be detected and CAC can trigger a classical consensus protocol to handle the conflict.

The protocol works by collecting signatures from other processes about the different broadcast messages. When a process broadcasts a protocol message to others, this process includes the signed messages received from other processes. The use of signatures prevents a malicious process from presenting different views to other processes as processes share their own views by means of these signed messages. Then, after reaching a sufficient count of signatures, the protocol can move forward with the associated messages. The CAC protocol is organized in two phases (Witness and Ready) detailed below.

In the Witness phase, each process broadcasts a Witness message targeting the first broadcast message that this process received. After receiving Witness signatures from a quorum of q W processes, the current process can move on to the next phase for this given message. However, in the event of multiple broadcast messages, it is possible that none reaches the quorum of q W processes. Thus, an unlocking mechanism is triggered when a process knows that it received a response from at least n -t processes, n being the total number of processes with at most t Byzantine processes. In that case this process will also send a Witness message for all witnessed messages that satisfy a lower threshold. These messages are likely to conflict and appear in the conflict-set that will later be computed. The size of the quorum q W = 2t + k is based on a parameter k that tunes the sensitivity of the protocol to conflicting messages: a small k can lead to multiple conflicts whereas with a larger k fewer messages will likely reach the quorum.

The Ready phase is reached for a given message when this message reaches the quorum of q W distinct Witness signatures. Then, the process can broadcast a Ready message and wait for q R distinct Ready signatures for the same message. The purpose of this phase is to ensure totality meaning that if the current process delivers the message then all the other correct processes also deliver it. Finally, as mentioned earlier, CAC associates the delivered messages with a conflict-set. This conflict-set contains messages that received enough Witness signatures to be considered in conflict.

Cascade Consensus Protocol. The CAC abstraction enables the construction of a consensus protocol named Cascade Consensus. In this protocol, a process starts by using CAC to broadcast a message. Then, if there are no conflicts, meaning that CAC delivers a single message with a conflict-set of size 1, the protocol can directly finish and deliver this message. Otherwise in case of a conflict, with a conflict-set containing two messages or more, the protocol triggers a Restrained Consensus between the senders associated with the messages in the conflict-set. This Restrained Consensus involves only the senders in conflict and thus is less costly than regular consensus provided that none of its participants is Byzantine and no period of asynchrony occurs during its execution. Thus, either one of the participants is chosen by Restrained Consensus and its message can be delivered, or in the event of a timeout, a classical Consensus algorithm is used to settle the Cascade Consensus protocol and reach a final decision.

We choose this protocol as the graceful conditions allowing the early termination of Cascade Consensus match the expected behavior of TreeKEM. Indeed, depending on the size and the dynamics of a group, conflicts may not occur very often, in which cases the consensus ends after a CAC broadcast. Additionally, these conflicts may usually be restricted to a few members of the group, reducing the complexity of consensus by triggering Restrained Consensus.

The TreeKEM Protocol and its Delivery Service

The TreeKEM protocol underlying Messaging Layer Security (MLS) [START_REF] Barnes | The Messaging Layer Security (MLS) Protocol[END_REF] provides a standard and well-secured solution for end-to-end secure group communication such as group messaging and video conferencing. We first present the Propose and Commit approach used by TreeKEM to handle concurrent operations in the group. Next, we introduce the core structure of TreeKEM based on the ratcheting tree. We then describe the Delivery Service component of TreeKEM which is in charge of handling protocol communication and resolving conflicts between members. We present our formalization of the role and the properties of this Delivery Service component. Finally, we describe the centralized solution of the Delivery Service adopted by TreeKEM and its follow-up protocols.

Propose and Commit

The 8 th draft of the MLS Protocol, introduces the principle of Propose and Commit in the TreeKEM Protocol which describes the current way of organizing the operations in the protocol. This allows group members to perform concurrent operations in the form of Proposals. Then, these proposals can be merged into a Commit which materializes these changes into the group and leads to a new epoch for the group. In TreeKEM, it is up to the application using the protocol to decide which client commits the Proposals.

In the case of conflicting Proposals (e.g. multiple add/remove/update Proposals for the same member), the commiter must choose between those proposals to solve the conflicts. Additionally, if one Commit contains Proposals to add one or multiple members, the protocol generates a Welcome message that allows them to effectively join the group.

Therefore, based on the MLS RFC [START_REF] Barnes | The Messaging Layer Security (MLS) Protocol[END_REF] we propose the following formalization of the TreeKEM protocol:

-s ← Init(

Ratcheting Tree

One way to implement the protocol would be for a member to generate a new group key and encrypt this key with the public keys of each user. However this kind of approach would scale poorly in the case of large groups. Thus, TreeKEM uses the concept of the ratcheting tree in order to improve scalability. The ratcheting tree is organized as a balanced binary tree of public-private key-pairs whose leaves represent members of the group. Group members do not share the same view of the tree as each member only knows a subset of the private keys: the keys on the path from the leaf associated with this member to the root of the tree. Therefore the only private key known by all members is the root of the tree which gets to be used as the group key. Figure 1 presents the example of a ratcheting tree in the case of a 4-member group. In the tree, members 1 and 2 share the secret associated with A, 3 and 4 share the secret associated with B and C's secret is shared among all members and considered the group key. When a member creates a Commit message to advance the group state, this member modifies one or more leaves in the tree to apply the operations described by the associated proposals. Then, this member updates path to the root in order to ensure the renewal of the group key. This can be done in two steps:

-First, a key derivation mechanism, similar to a hash function, makes it possible to generate the new keys. For example, member 1 would generate a new leaf key k 1 ′ , and iterate a key derivation mechanism to generate the following keys:

k 1 ′ → k A ′ → k C ′ .
-Then, the tree structure can be used to limit the number of encryptions: k A ′ can be encrypted to member 2, and k C ′ can be encrypted to the remaining sub-group using the public key of B.

As members can complete the chain of keys using the key-derivation mechanism, the number of keys and needed encryptions to generate a Commit message is limited to log(n) in a group of size n, which offers good scalability. However, the protocol does not provide a way to merge the modifications conveyed by multiple commits. Thus, in the event of concurrent commits, only one commit must be chosen to be applied by all group members. The task of resolving these conflicts falls under the responsibility of the Delivery Service that will be described in the following subsection.

The TreeKEM's Delivery Service

The MLS Architecture draft [8] describes the typical architecture in which clients implementing the MLS Protocol [START_REF] Barnes | The Messaging Layer Security (MLS) Protocol[END_REF] interact with each other. In this architecture, clients communicate with each other using a Delivery Service whose detailed description falls out of the scope of the MLS Protocol.

Thus, the role of the Delivery Service is essentially to ensure the delivery of the different types of messages: Application messages exchanged between users, Proposal messages and Commit messages. The only constraint for Application and Proposals messages is that they must eventually reach their recipients.

However, Commit messages present different challenges. In fact, the MLS Protocol imposes a linear history of epochs. This means that the members should process the Commit messages in the same order and only one Commit message can exist per epoch, as the protocol is not capable of merging multiple Commits. Ensuring this linear history can be a problem as the members may generate concurrent commits in different situations:

-On the one hand, some members might not take advantage of concurrent operations (i.e. send a Proposal directly followed by a corresponding Commit) and in dynamic and/or large groups, there is a high probability of members issuing multiple Commits simultaneously. -On the other hand, even when members first send Proposals to allow operations to be executed concurrently, there is still the need for one of those members to commit the operations. This member can be determined deterministically to limit the cost, for example based on the set of received proposals. But, in a distributed system the presence of failures and asynchronous periods may prevent all members from deciding on the same commiter. Thus, even if the probability of conflicts is lowered, it is still possible for concurrent commits to be issued. Addressing this situation requires solving consensus.

Therefore, in case of conflicts, the Delivery Service must act as a reference, capable of deciding on one Commit that all members will consider as the right one for a given epoch.

Formalization.

Based on the specifications provided in the MLS Protocol [START_REF] Barnes | The Messaging Layer Security (MLS) Protocol[END_REF] and the MLS Architecture draft [8], we now present our formalization of the role and the properties of the TreeKEM Delivery Service.

The Delivery Service is a group communication mechanism that provides two operations and two callbacks:

-ds_proposal_broadcast(pm): a process p i can invoke this operation to submit a proposal message pm. -ds_proposal_deliver(p i , pm): callback triggered to deliver a proposal message pm broadcast by process p i . -ds_commit_propose(ep, cm): a process p i can invoke this operation to submit a commit message cm for the current epoch ep.

-ds_commit_deliver(ep, p i , cm): callback triggered to deliver the commit message cm for the epoch ep and broadcast by process p i , which allows members to progress to the next epoch and state.

The Delivery Service satisfies the following properties:

-Proposal Validity. If a correct process p i ds-proposal-delivers a pair (p j ,pm), then pm is a valid proposal message, p j is a correct process and p j has previously ds-proposal-broadcast pm. -Proposal Totality. If a correct process p i ds-proposal-broadcasts a proposal message pm, then all correct processes eventually ds-proposal-deliver the pair (p i ,pm). -Epoch Validity. If a correct process p i ds-commit-delivers a tuple (ep,p j ,cm), then ep is the current epoch, cm is a valid commit message in the current epoch, p j is a correct process and p j has previously ds-commit-proposed cm. -Epoch Agreement. If any two correct processes ds-commit-deliver respective tuples (ep,-,cm) and (ep ′ ,-,cm ′ ), and if ep = ep ′ then we have cm = cm ′ . -Epoch Termination. If a correct process p i ds-commit-proposes a commit message cm for the epoch ep, then all correct processes eventually ds-commitdeliver a pair (ep,-,-). -Epoch-Content Consistency If a correct process ds-commit-delivers a tuple (-,-,cm), then for all proposal messages pm referenced by cm all correct processes have previously ds-proposal-delivered a tuple (-,pm).

Centralized Delivery Service

The approach adopted by TreeKEM and other protocols it inspired (e.g. [START_REF] Klein | Keep the dirt: Tainted treekem, adaptively and actively secure continuous group key agreement[END_REF], [START_REF] Alwen | Cocoa: Concurrent continuous group key agreement[END_REF]) is to rely on a central authority to implement the Delivery Service. In this case, the Delivery Service would be operated by a central server. To keep confidentiality this central server is assumed to be untrusted. This means that, as the messages are end-to-end encrypted, the server cannot read or modify the messages exchanged between members, but has access to a limited set of metadata necessary to fulfill its task (i.e. group id and epoch).

Due to its limited view on the content of messages, an untrusted centralized Delivery Service can only accomplish the role of an ordering server, providing the different messages in the same order for all clients. Then, in case of conflicts, the members can choose the first valid commit message and coherently resolve the conflict.

However, this central server can easily become a target of attacks such as Denial of Service which can impact its availability. In more complex settings, a compromised Delivery Service can be used to mount attacks against specific groups. By blocking the operations of given members, one can prevent these members from refreshing their keys and thus eventually lead to the failure of the Post-Compromise Security property.

A Distributed Delivery Service

In this section, we describe our solution for a fully distributed Delivery Service. Instead of relying on a third-party untrusted server, the participants in the key agreement protocols, or a subset of them, directly run the delivery service. We illustrate our solution as a flowchart in Figure 2 and formally in Algorithm 1. The flowchart in Figure 2 describes the verification process and the delays that messages can encounter between their receipt from the communication component and their delivery. The Algorithm 1 details how the execution unfolds. Our solution relies on two basic communication mechanisms adapted to the different messages of the TreeKEM protocol: a Probabilistic Reliable Broadcast (i.e. the Murmur protocol from [START_REF] Guerraoui | Scalable Byzantine Reliable Broadcast (Extended Version)[END_REF]) for Proposal messages and the Cascade Consensus Protocol [START_REF] Albouy | Context adaptive cooperation[END_REF] for Commit messages. We introduce a slight modification to the Cascade Consensus Protocol and to the CAC broadcast mechanism on which it is based (see Section 2). Specifically, we delay the acknowledgement of a commit (i.e. the emission of a Witness message upon receipt of a first Witness message) until the client considers this commit as valid. We materialize this validation by a call to ccb.receiveCommit (l. 17). This ensures that the commit message can be introduced as a candidate in the consensus protocol only when all members agree that this commit is valid. Delaying commits allows our solution to control the flow of epochs, making sure that it only delivers messages belonging to the current epoch, and that all members have moved to the current epoch before deciding on the next one. This prevents an attacker from executing a Denial of Service attack by submitting a large number of commits in a short time. To implement this delay, Algorithm 1 employs two waiting queues (incomplete_commits, f uture_commits) initialized on line 7. Together, these queues allow our solution to wait until all the proposals referenced by a commit are received before starting an agreement (i.e. a consensus) on this commit. This leads to the satisfaction of the Epoch-Content-Consistency property.

In a similar manner, we also introduce a delay on proposal messages (by means of the f uture_proposals waiting queue initialized on line 8 of Algorithm 1). This makes it possible to delay proposals whose messages belong to a future epoch-that a member suffering from network delays cannot immediately verify-or that were created by an attacker in an attempt to block the progress of the group.

We handle proposal messages using the Murmur [START_REF] Guerraoui | Scalable Byzantine Reliable Broadcast (Extended Version)[END_REF] protocol (l. 20), which guarantees Proposal Totality. When a member receives a proposal message, two cases can arise. If the proposal belongs to the current epoch, and thus satisfies Proposal Validity, we can directly deliver the message (l. 29). Otherwise, we wait for this message to become valid by inserting this message in the list of future proposals (l. 31). Additionally, we check if this proposal is referenced by any commit previously received (l. 22). This check may unblock a commit whose acknowledgment was delayed to ensure Epoch-Content Consistency.

To handle commit messages, on the other hand, we employ the modified cascade-consensus mechanism (l. 36). Commits whose proposals are missing are delayed (l. 38), either if some of their proposals are missing to guarantee Epoch-Content Consistency or to guarantee Commit Validity if the commit belongs to a future epoch (l. 15) that cannot yet be verified. Then, valid commits are transmitted as candidates for the next epoch to the Cascade Consensus Protocol. This protocol ensures the Epoch Agreement and Epoch Termination.

Finally, when members all agree on the same commit, this commit is delivered by the consensus protocol (l. 43). This commit can be transmitted to the TreeKEM protocol to take effect. Additionally, the change of epoch can unblock proposals (l. 47) and commits (l. 53) that were previously delayed if the client received messages out of order.

Conclusion

In this paper we presented a completely distributed solution for the design of the Delivery-Service component of TreeKEM by combining a Probabilistic Broadcast [START_REF] Guerraoui | Scalable Byzantine Reliable Broadcast (Extended Version)[END_REF] method with the Cascade Consensus Protocol [START_REF] Albouy | Context adaptive cooperation[END_REF]. We formalized the role and the necessary properties of this Delivery-Service component and we proposed a novel algorithm supporting its distributed counterpart. This design allows users to run the TreeKEM protocol or any similar Group Key Agreement protocol without requiring their communication to go through a central server. Our approach increases the security and the availability of group communication making it harder for an attacker to compromise the Delivery Service. Mounting attacks against the group requires compromising one third of the clients [START_REF] Albouy | Context adaptive cooperation[END_REF] instead of only one server in the standard centralized solution.

We plan to implement our Distributed Delivery Service solution and to conduct a performance evaluation in the context of peer-to-peer networks. Additionally, we plan to conduct a formal security analysis of our protocol. We will further extend our solution in order to explicitly support offline group members. Currently, the TreeKEM protocol supports offline members using a central server that stores messages for these users. We plan to design completely distributed alternative solutions for offline communication by relying on State-Machine-Replication [START_REF] Bessani | State machine replication for the masses with bft-smart[END_REF] mechanisms such as State Transfer. This should allow previously offline members to get up to date with the group by directly synchronizing with some other members. In order to support a completely distributed group-key-management component for our real-time peer-to-peer collaborative editor MUTE [START_REF] Nicolas | MUTE: a peer-topeer web-based real-time collaborative editor[END_REF], we plan to integrate the TreeKEM protocol and our distributed Delivery Service. We further plan to combine this distributed groupkey-management mechanism with a distributed access control mechanism such as ACCURE [START_REF] Rault | Access control based on CRDTs for Collaborative Distributed Applications[END_REF].

Fig. 1 .

 1 Fig. 1. Example of a TreeKEM ratcheting tree in the case of a 4-user group.

Fig. 2 .

 2 Fig. 2. Diagram detailing our solution for a Distributed Delivery Service

  ID): initiates the group state s for the user associated with the identity ID.p ← ProposeAdd(s, ID ′ ): creates a proposal to add the user corresponding to ID ′ to the group with the current state s. The operation outputs a proposal p. p ← ProposeRemove(s, ID ′ ): creates a proposal to remove the user corresponding to ID ′ from the group with current state s. The operation outputs a proposal p.

p ← ProposeUpdate(s, k): creates a proposal to update the current user's key in current state s with k. The operation outputs a proposal p.

-(C, W ) ← Commit(s, P ): commits a set P of valid and non conflicting proposals (i.e. according to Section 12.2 of the RFC

[START_REF] Barnes | The Messaging Layer Security (MLS) Protocol[END_REF]

) to make the current group state s progress. The operation outputs a commit message C to make current members transition to the new group state and possibly a welcome message W to allow proposed new users to join the group. -(s ′ , K) ← Process(s, M ): processes a commit or welcome message M to transition from the old group state s to the new group state s ′ . The transition additionally generates a new group key K.

  Algorithm 1 Formalization of our solution for a Distributed Delivery Service based on the Cascade Consensus Protocol and the Murmur broadcast protocol.

	36: upon event < ccb.ReceiveCommit | [Commit, commit] > do	▷ ignore past and
	invalid commits
	Implements: 37: if commit.proposals ̸ ⊆ proposals then
	1: DistributedDeliveryService, instance dds 38: incomplete_commits ← incomplete_commits ∪ commit
	Uses: 39:	else
	2: MurmurBroadcast, instance mb 40: handleCommit(commit)
	3: CascadeConsensusBroadcast, instance ccb 41: end if
	4: TreeKEMProtocol, instance tkem 42:
	5: 43: upon event < ccb.Deliver | [Commit, commit] > do
	6: upon event < Init > do 44: tkem.apply(commit)
	7: 45:	proposals = ∅ ; incomplete_commits = ∅ ; f uture_commits = ∅ ; for proposal ∈ f uture_proposals do
	8: 46:	f uture_proposals = ∅ if tkem.currentEpoch = proposal.epoch and tkem.isValid(proposal) then
	9: 47:	trigger < dds.DeliverProposal | [Proposal, proposal] >
	10: upon event < dds.BroadcastProposal | [Proposal, proposal] > do 48: f uture_proposals ← f uture_proposals \ proposal
	11: 49:	trigger < mb.Dispatch | [Proposal, proposal] > end if
	50: 12: 13: procedure handleCommit(commit) end for 51: for commit ∈ f uture_commits do 52: if tkem.currentEpoch = commit.epoch and tkem.isValid(commit) then ▷ handle commits that are or became complete 14: 53: ccb.receiveCommit(commit) if commit.epoch > tkem.currentEpoch then 15: 54: f uture_commits ← f uture_commits \ commit f uture_commits ← f uture_commits ∪ commit 16: 55: end if else 17: 56: end for ccb.receiveCommit(commit) 18: end if 57:
	19:
	20: upon event < mb.Deliver | [Proposal, proposal] > do ▷ ignore past and invalid
	proposals
	21:	proposals ← proposals ∪ proposal
	22:	for commit ∈ incomplete_commits do
	23:	if commit.proposals ⊆ proposals then
	24:	handleCommit(commit)
	25:	incomplete_commits ← incomplete_commits \ commit
	26:	end if
	27:	end for
	28:	if proposal.epoch = tkem.currentEpoch then
	29:	trigger < dds.DeliverProposal | [Proposal, proposal] >
	30:	else
	31:	f uture_proposals ← f uture_proposals ∪ proposal
	32:	end if
	33:
	34: upon event < dds.ProposeCommit | [Commit, commit] > do
	35:	trigger < ccb.Propose | tkem.currentEpoch,[Commit, commit] >

trigger < dds.DeliverCommit | [Commit, commit] >

Acknowledgments

This work is supported by the "Alvearium" Inria and hive partnership.