Mohammed Helal

Angélique Igel-Egalon

Abdelkader Lakmeche

Pauline Mazzocco

Angélique Perrillat-Mercerot

Laurent Pujo-Menjouet

Human Rezaei

Léon Matar

Léon M Tine

L Pujo
email: pujo@math.univ-lyon1.fr

Stability analysis of a steady state of a model describing Alzheimer's disease and interactions with prion proteins

Keywords: mathematical model analysis, steady state, Alzheimer's Disease, prions, numerical simulations Mathematics Subject Classification (2010) 34D23, 92B05

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Biological background Alzheimer's disease (AD) is a fatal incurable disease known as the most common form of dementia (60 to 80% of dementia cases [START_REF] Sosa-Ortiz | Epidemiology of Dementias and Alzheimer's Disease[END_REF]). Affecting more than 46 million people worldwide in 2015 [START_REF] Prince | World Alzheimer Report 2015 The Global Impact of Dementia[END_REF], it causes progressive neuron degeneration, leading to loss of mental functions such as memory, language or behaviour. Although AD arises most of the time in the elderly community, this disease is not considered as a normal consequence of ageing. Causes of Alzheimer's disease remain uncertain. Different hypotheses, such as cholinergic [START_REF] Francis | The cholinergic hypothesis of Alzheimers disease: a review of progress[END_REF], amyloid or Tau hypotheses, have been proposed to explain AD appearance. The two last hypotheses seem to be currently the most plausible ones. Indeed, accumulation of amyloid plaques inside the brain [START_REF] Karran | The amyloid cascade hypothesis for Alzheimer's disease: an appraisal for the development of therapeutics[END_REF] and abnormalities of Tau protein are observed in diseased patients [START_REF] Maccioni | The revitalized tau hypothesis on Alzheimer's disease[END_REF]. Although these two processes could evolve simultaneously [START_REF] Small | Linking Aβ and tau in late-onset Alzheimer's disease: a dual pathway hypothesis[END_REF], it seems that the first biomarkers becoming abnormal in AD are the concentrations of amyloid Aβ-40 and Aβ-42 in patient cerebrospinal fluid [START_REF] Jack | Update on hypothetical model of Alzheimers disease biomarkers[END_REF]. Aβ monomers are obtained from a specific cleavage of the amyloid precursor protein APP, leading to their release and accumulation inside the brain [START_REF] Nunan | Regulation of APP cleavage by alpha-, beta-and gamma-secretases[END_REF]. The major isoforms are composed of 39 to 43 amino acids, Aβ-40 being the most common type of monomers, and Aβ-42 a plausible evidence of Alzheimer's disease [START_REF] Bitan | Amyloid β-protein (Aβ) assembly: Aβ40 and Aβ42 oligomerize through distinct pathways[END_REF][START_REF] Johnson | Single-Molecule Imaging Reveals Aβ42:Aβ40 Ratio-Dependent Oligomer Growth on Neuronal Processes[END_REF]). Aβ monomers could at least follow two distinct polymerization pathways. The first one corresponds to the fibrillation pathway well described by the canonical nucleation elongation process [START_REF] Lomakin | On the nucleation and growth of amyloid beta-protein fibrils: detection of nuclei and quantitation of rate constants[END_REF] with the particularity that Aβ fibrils have been reported to be able to depolymerize [START_REF] Carulla | Molecular recycling within amyloid fibrils[END_REF] rendering each step of the fibrils elongation process reversible (Figure 1, blue part). The second pathway corresponds to the Aβ oligomerization pathway. As for fibrillation, the oligomerization process follows a nucleation elongation mechanism with the difference that the oligomerization pathway leads to the formation of highly stable Aβ assemblies structurally distinct from Aβ fibrils [START_REF] Nick | A long-lived aβ oligomer resistant to fibrillization[END_REF]; [START_REF] Barz | Pathways of amyloid-β aggregation depend on oligomer shape[END_REF]). Regarding the literature, several neurotoxic pathways not mutually exclusive and all involving specifically Aβ oligomers have been proposed [START_REF] Kessels | The prion protein as a receptor for amyloid-β[END_REF]; [START_REF] James | The role of amyloid beta in the pathogenesis of Alzheimer's disease[END_REF]; [START_REF] Kandel | Membrane binding and pore formation by a cytotoxic fragment of amyloid β peptide[END_REF]). Recently one of these pathways, involving the binding of Aβ oligomers to prion protein PrP C under its non-pathogenic monomeric conformer, has been reported to be involved in a deathsignal transduction into the neurons through the oligomerization of PrP C [START_REF] Kessels | The prion protein as a receptor for amyloid-β[END_REF]; [START_REF] Gimbel | Memory Impairment in Transgenic Alzheimer Mice Requires Cellular Prion Protein[END_REF]). Even if the molecular mechanisms of this transduction signal are not yet clear, the oligomerization of PrP C (named here PrP ol ) has been reported to be involved in the dead signal transduction [START_REF] Cissé | A prion protein connection[END_REF]; [START_REF] Laurén | Cellular prion protein mediates impairment of synaptic plasticity by amyloid-β oligomers[END_REF]; [START_REF] Gimbel | Memory Impairment in Transgenic Alzheimer Mice Requires Cellular Prion Protein[END_REF]). In term of physical-chemistry, the interaction between PrP C and Aβ oligomers leading to PrP ol formation could be decomposed into two steps: the first step corresponds to the formation of PrP C / Aβ complex [START_REF] Freir | Interaction between prion protein and toxic amyloid β assemblies can be therapeutically targeted at multiple sites[END_REF]; [START_REF] Gallion | Modeling amyloid-beta as homogeneous dodecamers and in complex with cellular prion protein[END_REF]). Then after a delay (denoted τ in this work), corresponding to a structural rearrangement [START_REF] Hilser | Structural and energetic basis of allostery[END_REF], the complex evolves to generate PrP C oligomerization.

Mathematical background

These processes are challenging for biologists. Indeed, it is not easy to explain the observed kinetic behaviours in experiments. Therefore an interdisciplinary collaboration between mathematicians and biologists lead to a new mathematical model where these considerations have been discussed and supported by biological assumptions and observations. While a number of studies focus either on aggregation of Aβ monomers (see for instance [START_REF] Lomakin | Kinetic theory of fibrillogenesis of amyloid beta -protein[END_REF]; [START_REF] Urbanc | Dynamics of Plaque Formation in Alzheimer ' s Disease[END_REF]; [START_REF] Craft | A Mathematical Model of the Impact of Novel Treatments on the AβBurden in the Alzheimer's Brain, CSF and Plasma[END_REF]; [START_REF] Achdou | A qualitative model for aggregation and diffusion of β-amyloid in Alzheimer's disease[END_REF]; [START_REF] Bertsch | Alzheimer's disease: a mathematical model for onset and progression[END_REF]) or on PrP C proliferation [START_REF] Greer | A mathematical analysis of the dynamics of prion proliferation[END_REF]; [START_REF] Prüss | Analysis of a model for the dynamics of prions[END_REF]; [START_REF] Engler | Analysis of a model for the dynamics of prions II[END_REF]; [START_REF] Calvez | Size distribution dependence of prion aggregates infectivity[END_REF]; [START_REF] Gabriel | The shape of the polymerization rate in the prion equation[END_REF], to cite a few), to the best of our knowledge, only two mathematical models have been proposed to study Aβ/ PrP C interactions [START_REF] Helal | Alzheimer's disease: analysis of a mathematical model incorporating the role of prions[END_REF][START_REF] Ciuperca | Alzheimer's disease and prion: analysis of an in vitro mathematical model[END_REF]. In the first one, authors describe plausible in vivo interactions between Aβ oligomers and PrP C , but did not focus on the whole process of polymerization [START_REF] Helal | Alzheimer's disease: analysis of a mathematical model incorporating the role of prions[END_REF]. In the second article, authors propose a complex model including Aβ polymerization and interactions with prion (Ciuperca et al.). However, this model assumes a continuous size for polymers, a hypothesis generally made for large objects, but which can be controversial for oligomers. Besides, because the model is based on partial differential equations, its analysis can be more complicated.

Objectives of this work

We aim herein at building a model describing in vitro polymerization process of Aβ monomers in fibrils or oligomers, and interactions with prion proteins, mechanisms that seem to initiate development of Alzheimer's disease. We base our model on Becker-Döring equations [START_REF] Becker | Kinetische Behandlung der Keimbildung in übersättigten Dämpfen[END_REF], assuming therefore a discrete size of polymers. Our paper is organized as follows: we first present the mathematical model proposed to describe the different mechanisms of interest. We then investigate its well-posedness and show that the model admits a unique and globally stable steady state. We finally present some numerical simulations and study the impact of model parameters on the whole dynamics.

Mathematical modelling

Description and notations

Our model is built in an in vitro context, as most experimental data are obtained in vitro. This means that no source or loss terms of any proteins involved in the system are considered. As a consequence, the total mass of the system should remain constant. We study evolution of Aβ monomers seeded at time t = 0 in an environment containing PrP C . The model consists of two main parts: 1) polymerization process, including formation of oligomers and fibrils and 2) interactions between oligomers and prion (Figure 1). During polymerization process, monomers can either form fibrils or proto-oligomers. These can then grow by attaching a monomer, or lose one at a rate b f for fibrils and b for proto-oligomers. Rates of polymerization depend on polymer size. Indeed, we assume that longer polymers have more probability to polymerize. Proto-oligomers can reach a maximal size i 0 , at which they become stable and can neither polymerize nor depolymerize. They then are called oligomers. A small proportion µ of oligomers are still able to split into two proto-oligomers of sizes i and i 0 -i. This process is not represented in Figure 1 for clarity. Aβ oligomers can then be transported to the amyloid plaque at a rate γ or form a complex with PrP C at a rate δ. This interaction takes an incompressible time τ during which PrP C is misfolded into PrP ol . The oligomer is released intact from the complex and can interact with another prion or be transported to the plaque. We also add the possibility for PrP C to directly transform into PrP ol at a rate α. This process can include other misfolding mechanisms that we are not aware of.

We assume that there is no fibril of infinite size, and therefore set i f as the maximal size they can reach. Fibrils of each size are also transported in the amyloid plaque at a rate γ f . As they are still able to depolymerize, monomers can escape the plaque at a rate b p . All notations and parameters are reported in Table 1 along with their description.

Mathematical equations

Based on Becker-Döring equations [START_REF] Becker | Kinetische Behandlung der Keimbildung in übersättigten Dämpfen[END_REF] , the first part of our model is as follows:

Monomers

c 1 (t) = -2(r 1 c 1 (t) 2 -bc 2 (t)) - i0-2 i=2 (r i c i (t)c 1 (t) -bc i+1 (t)) -r i0-1 c i0-1 (t)c 1 (t) -2(r f,1 c 1 (t) 2 -b f c f,2 (t)) - i f -1 j=2 (r f,i c f,i (t)c 1 (t) -b f c f,i+1 (t)) + 2b p c pl,2 + i f -1 j=2 b p c pl,i+1 (t), (1)
Proto-oligomers

(i ∈ {2, • • • , i 0 -2}) c i (t) = r i-1 c i-1 (t)c 1 (t) + bc i+1 (t) -r i c i (t)c 1 (t) -bc i (t) + µK i0,i c i0 (t), (2)
c i0-1 (t) = r i0-2 c i0-2 (t)c 1 (t) -r i0-1 c i0-1 (t)c 1 (t) -bc i0-1 (t), (3) Oligomers c i0 (t) = r i0-1 c i0-1 (t)c 1 (t) -(γ + µ 2 )c i0 (t) -δc i0 (t)p c (t) + δc i0 (t -τ )p c (t -τ ), (4)
Oligomers in plaque c pl (t) = γc i0 (t), ( 5)

Fibrils (j ∈ {2, • • • , i f -1}) c f,j (t) = r f,j-1 c f,j-1 (t)c 1 (t) + b f c f,j+1 (t) -r f,j c f,j (t)c 1 (t) -b f c f,j (t) -γ f c f,j (t), (6)
c f,i f (t) = r f,i f -1 c f,i f -1 (t)c 1 (t) -b f c f,i f (t) -γ f c f,i f (t), (7)
Fibrils in plaque

(j ∈ {2, • • • , i f -1}) c pl,j (t) = b p c pl,j+1 (t) -b p c pl,j (t) + γ f c f,j (t), (8)
c pl,i f (t) = -b p c pl,i f (t) + γ f c f,i f (t), (9)
with t in [τ, +∞) for equation (4) and t in [0, +∞) for others. For t in [0, τ ), equation (4) becomes:

c i0 (t) = r i0-1 c i0-1 (t)c 1 (t) -(γ + µ 2 )c i0 (t) -δc i0 (t)p c (t). ( 10
)
Initial conditions are the following:

           c 1 (t = 0) = m > 0, c i (t = 0) = 0, i ∈ {2, • • • , i 0 }, c pl (t = 0) = 0, c f,j (t = 0) = 0, j ∈ {2, • • • , i f }, c pl,j (t = 0) = 0, j ∈ {2, • • • , i f }, (11)
which means that there are only monomers initially. Equation ( 1) describes Aβ monomer evolution (orange part in Figure 1), obtained by computing monomer gain and loss from every proto-oligomer and fibril. Equation ( 2) governs proto-oligomer behaviour (green part in Figure 1). Proto-oligomers of size i come from proto-oligomers of size i -1 that have attached a monomer (first term in equation ( 2)) or from proto-oligomers of size i + 1 that have lost a monomer (second term in equation ( 2)). Similarly, proto-oligomers of size i can attach or lose a monomer, and leave this compartment (third and fourth terms in equation ( 2)). The last term in equation ( 2) describes the fragmentation process: oligomers can divide in two proto-oligomers of size lower than i 0 -1. An extra equation is needed for proto-oligomers of size i 0 -1 (equation ( 3)) as oligomers do not depolymerize and consequently no proto-oligomers of size i 0 -1 come from an oligomer. Equation ( 4) describes oligomer evolution. Delayed terms express oligomer release from a complex created τ units of time before. Finally, equation ( 5) describes the evolution of oligomers in plaque while equations ( 6)-( 7) (respectively equations ( 8)-( 9)) correspond to fibril dynamics (respectively fibrils in plaque) (blue part in Figure 1).

The second part of the model concerns Aβ oligomers and PrP C interactions (pink box in Figure 1):

p c (t) = -δc i0 (t)p c (t) -αp c (t), (12)
p ol (t) = δc i0 (t -τ )p c (t -τ ) + αp c (t), (13)
X (t) = δc i0 (t)p c (t) -δc i0 (t -τ )p c (t -τ ), ( 14
)
with t in [0, +∞) for equation ( 12) and t in [τ, +∞) for equations ( 13)-( 14). Evolution of prion concentration is given by equation ( 12): PrP C prions either form a complex with Aβ oligomer or directly transform into PrP ol . Equations ( 13) and ( 14) describe evolution of PrP ol and complexes.

On [0, τ ), equations ( 13)-( 14) become:

p ol (t) = αp c (t), X (t) = δc i0 (t)p c (t),
and initial conditions are the following:

   p c (t = 0) = p > 0, p ol (t = 0) = 0, X(t = 0) = 0, (15)
meaning that only PrP C are present initially.

We should now verify whether the total mass remains constant over time. We can actually divide this mass in two: Aβ polymer mass Q and prion mass Q p :

Q(t) = c 1 (t) + i0 i=2 ic i (t) + i f j=2 j(c f,j (t) + c p,j (t)) + i 0 (c pl (t) + X(t)), (16)
Q p (t) = m p (p c (t) + p ol (t) + X(t)). (17)
Derivatives of these functions should be equal to zero:

Q (t) = µc i0 (t)( i0-2 i=2 iK i0,i - i 0 2 ), Q p (t) = 0.
Therefore, the fragmentation kernel should satisfy the following relation:

2 i0-2 i=2 iK i0,i = i 0 . ( 18
)
This condition describes the fact that the sum of all successive fragment sizes should be equal to the initial size. Note that an oligomer can fragment either in proto-oligomers of sizes i and i 0 -i or in proto-oligomers of sizes i 0 -i and i. These two possibilities are taken into account thanks to the factor 2. For instance, the following fragmentation kernel verifies relation ( 18) and guarantees mass conservation with time:

K i0,i = 1 i 0 -3 , i ∈ {2, • • • , i 0 -2}.
This fragmentation kernel follows an uniform distribution, meaning that all fragmentations have the same probability to occur. As an example, this kernel has been used to describe the splitting of prion fibrils in [START_REF] Prüss | Analysis of a model for the dynamics of prions[END_REF].

Model analysis

In this section, we focus on the mathematical analysis of the model. We first present classical results of existence, uniqueness and non-negativity of solutions. We then prove the existence of a unique and non-trivial steady state. Besides, with a Lyapunov function, we show that it is globally stable, which constitutes our main result.

Existence, uniqueness and non-negativity of solutions

Proposition 1 System of equations ( 1)-( 14) admit a unique solution on [0, +∞). Besides, provided that the initial conditions are non-negative, the solution remains non-negative.

Proof We prove existence and uniqueness of solutions with the method of steps: we start by proving existence, uniqueness and non-negativity on [0, τ ), then on [τ, 2τ ), and extend these results on intervals [nτ, (n + 1)τ ), for all n in N.

Let us note, for all t in [0, +∞):

Z(t) = t [c 1 (t), c 2 (t), • • • , c i0 (t), c pl (t), c f,2 (t), • • • , c f,i f (t), c pl,2 (t), • • • , c pl,i f (t), p c (t), p ol (t), X(t)].
On [0, τ ), the system of equations ( 1)-( 14) can be written as

Z (t) = H 1 (t, Z(t)), with Z(0) = [m, c 2 (0) = 0, • • • , c pl,i f (0) = 0, p, 0, 0].
H 1 is a polynomial function given by:

H 1 (Z) =                                             H 1,1 (Z) r 1 Z 2 1 -bZ 2 -r 2 Z 2 Z 1 + bZ 3 + µK i0,2 Z i0 . . . r i-1 Z i-1 Z 1 -bZ i -r i Z i Z 1 + bZ i+1 + µK i0,i Z i0 . . . r i0-2 Z i0-2 Z 1 -bZ i0-1 -r i0-1 Z i0-1 Z 1 r i0-1 Z i0-1 Z 1 -(γ + µ 2 )Z i0 -δZ i0 Z i0+2i f γZ i0 r f,1 Z 2 1 -b f Z 2 -r f,2 Z i0+2 Z 1 + b f Z i0+3 -γ f Z i0+2 . . . r f,j-1 Z i0+j-1 Z 1 -b f Z i0+j -r f,j Z i0+j Z 1 + b f Z i0+j+1 -γ f Z i0+j . . . r f,i f -1 Z i0+i f -2 Z 1 -b f Z i0+i f -γ f Z i0+i f -b p Z i0+i f +1 + b p Z i0+i f +2 + γ f Z i0+2 . . . -b p Z i0+i f +j-1 + b p Z i0+i f +j + γ f Z i0+j . . . -b p Z i0+2i f -1 + γ f Z i0+ı f -δZ i0 Z i0+2i f -αZ i0+2i f αZ i0+2i f δZ i0 Z i0+2i f                                             , where H 1,1 (Z) = -2(r 1 Z 2 1 -cZ 2 ) - i0-2 i=2 (r i Z i Z 1 -bZ i+1 ) -r i0-1 Z i0-1 Z 1 -2(r f,1 Z 2 1 -b f Z i0+2 ) - i f -1 j=2 (r f,j Z i0+j + Z 1 -bZ i0+j+1 ) + 2b p Z i0+i f +1 + i f -1 j=2 b p Z i0+i f +j .
We can easily see that H 1 is a locally Lipschitz continuous function with respect to Z. The Cauchy-Lipschitz theorem gives local existence and uniqueness of solutions for the system on [0, τ ], for τ less than or equal to τ . The global existence of solution on [0, τ ) requires the solution to be bounded and non-negative on [0, τ ). One can easily verifies that H 1 is bounded on [0, τ ).

To prove the non-negativity of the solution, we use the fact that an ODE system y = f (y) on R n is called quasi-positive if the condition [START_REF] Prüss | Analysis of a model for the dynamics of prions[END_REF]. In our case, the system of equations ( 1)-( 9)

y i 0, i = k and y k = 0 =⇒ f k (y) 0 is valid for all k in {1, • • • , n}
is quasi-positive (for i in {2, • • • , i 0 -2} and j in {2, • • • , i f -1}): c 1 (t) = 0 =⇒ c 1 (t) = bc 2 (t) + b i0-1 i=2 c i (t) + b f c f,2 (t) + b p c pl,2 (t) + i f j=2 (b f c f,j (t) + b p c pl,j (t)) 0, c i (t) = 0 =⇒ c i (t) = r i-1 c i-1 (t)c 1 (t) + bc i+1 (t) + µK i0,i c i0 (t) 0, c i0-1 (t) = 0 =⇒ c i0-1 (t) = r i0-2 c i0-2 (t)c 1 (t) 0, c i0 (t) = 0 =⇒ c i0 (t) = r i0-1 c i0-1 (t)c 1 (t) 0, c pl (t) = 0 =⇒ c pl (t) = γc i0 (t) 0, c f,j (t) = 0 =⇒ c f,j (t) = r f,j-1 c f,j-1 (t)c 1 (t) + b f c f,j+1 (t) 0, c f,i f (t) = 0 =⇒ c f,i f (t) = r f,i f -1 c f,i f -1 (t)c 1 (t) 0, c pl,j (t) = 0 =⇒ c pl,j (t) = b p c pl,j+1 (t) + γ f c f,j (t) 0, c pl,i f (t) = 0 =⇒ c pl,i f (t) = γ f c f,i f (t) 0.
Moreover, non-negativity of solutions of equations ( 12)-( 14) has been proven in (Ciuperca et al.).

Solutions on [0, τ ) are bounded and non-negative on [0, τ ) and are therefore global solutions on [0, τ ), and we further define Z(τ ) = lim t→τ -Z(t). On [τ, 2τ ), the system of equations ( 1)-( 14) can be written as Z (t) = H 2 (t, Z(t), Z(t -τ )), with initial conditions Z(τ ), and where H 2 is a polynomial function. Because Z(t -τ ) is known from the previous step, H 2 can be written as a function of Z(t) only. Once again, it is a locally Lipschitz continuous function, bounded and non-negative on [τ, 2τ ). Therefore, the Cauchy-Lipschitz theorem gives existence and uniqueness of solutions on [τ, 2τ ). We finally extend this result on intervals [nτ, (n + 1)τ ), for all n in N, and prove existence, uniqueness and non-negativity of solution on [0, +∞).

Steady state

In this section we present our main result, concerning the steady state of the model.

Proposition 2 System of equations ( 1)-( 14) has a unique steady state, where all variables are equal to zero, except for c pl and p ol :

Z = [c 1 , c2 , • • • , ci0 , cpl , cf,2 , • • • , cf,i f , cpl,2 , • • • , cpl,i f , pc , pol , X], = [0, 0, • • • , 0, Q i 0 , 0, • • • , 0, 0, • • • , 0, Q p m p , 0, 0]. ( 19
)
Besides, this steady state is globally stable.

Proof We first define a reduced system, using mass equations ( 16)-( 17) and properties of equation ( 14). Indeed, we can express c pl and p ol as function of masses and other variables:

c pl = 1 i 0 (Q -c 1 (t) - i0 i=2 ic i (t) - i f j=2 j(c f,j (t) + c pl,j (t)) -i 0 X(t))), (20)
p ol (t) = Q p m p -(p c (t) + X(t)). (21)
Equation ( 14) can be written as:

X(t) = δ t t-τ c i0 (s)p c (s)ds, (22)
for t in [τ, +∞). This formulation is obtained by integrating equation ( 14) on [τ, +∞) and by replacing X(τ ) by its value obtained when we integrate equation ( 14) on [0, τ ).

We finally focus on the system of equations ( 1)-( 14), in which we remove equations ( 5), ( 13) and ( 14). This reduced system has a unique trivial steady state. Equations ( 20)-( 22) give us the steady state for the whole system.

Steady state global stability is obtained through the following Lyapunov function:

V (Z) = i0-1 i=1 ic i (t) + i f j=2 j(c f,j (t) + c pl,j (t)) + (i 0 -1)c i0 (t) + p c (t) + X(t) + µ i0-2 i=2 i K i0,i γ Q i 0 -c pl (t) + (i 0 -1) Q p m p -p ol (t) . (23)
A sketch of its construction is given below. We define the general form of the Lyapunov function:

V (Z) = j N j=1 D j ( Zj -Z j ) + N j=j N +1 D j Z j ,
where N is the number of functions, D j are positive coefficients to determine and Z is the steady state we study. In this form, Z j with j in {1, • • • , j N } corresponds to variables with a non-trivial steady state. In our case, these functions are thus c pl and p ol . By construction, this Lyapunov function is equal to zero only at steady state and is positive elsewhere. Indeed, we can note that each variable is upper-bounded, using mass equations ( 16)-( 17). Specifically, c pl is upper-bounded by Q i0 and p ol by Qp mp , corresponding to the values of cpl and pol . We now have to choose coefficients D j so that V is non-positive. Let us write the V expression in our case:

V = i0-1 i=1 S i c i (t) + i f j=1 M j c f,j (t) + i f j=1 N j c pl,j (t) V1 + D 1 Q i 0 -c pl (t) + D 2 Q p m p -p ol (t) + D 3 X(t) + D 4 p c (t) + D 5 c i0 (t) V2 , where S i , i in {1, • • • , i 0 -1}, M j , N j , j in {2, • • • , i f }, and D k , k in {1, • • • , 5}
are positive coefficients to determine, to obtain non-positive derivative of V .

Taking the V 1 derivative, according to equations (1)-( 9) gives us:

V 1 = W 1 + W 2 + W 3 ,
where W 1 corresponds to the oligomerization process part, W 2 to the fibrillation part and W 3 to the fibrillation in plaque part. W 1 can be written as follows:

W 1 = i0-1 i=2 S i (G i-1 (t) -G i (t) + µK i0,i c i0 (t)) + S i0-1 G i0-2 (t) -S i0-1 r i0-1 c i0-1 (t)c 1 (t) -2S 1 G 1 (t) -S 1 i0-2 i=2 G i (t) -S 1 r i0-1 c i0-1 (t)c 1 (t),
where

G i (t) = r i c i (t)c 1 (t) -bc i+1 (t), i ∈ {1, • • • , i 0 -2} and G i0-1 (t) = r i0-1 c i0-1 (t)c 1 (t)
. With these notations, we obtain:

W 1 = -r i0-1 c i0-1 (t)c 1 (t)(S i0-1 + S 1 ) + i0-1 i=2 S i µK i0,i c i0 (t) + i0-2 i=1 G i (t) (S i+1 -S i -S 1 ) .
We take

S i = iS 1 , for i in {2, • • • i 0 -1}.
W 2 can be written as follows (denoting M 1 = S 1 ):

W 2 = i f -1 j=2 M j (F j-1 (t) -F j (t) -γ f c f,j (t)) + M i f F i f -1 (t) -M i f γ f c f,i f (t) -2S 1 F 1 (t) -S 1 i f -1 j=2 F j (t),
where

F 1 (t) = r f,1 c 1 (t) 2 -b f c f,2 (t) and F i (t) = r f,i c f,i (t)c 1 (t) -b f c f,i+1 (t), i ∈ {2, • • • , i f -1}.
We then obtain:

W 2 = -γ f i f j=2 M j c f,j (t) + i f -1 j=1 F j (t) (M j+1 -M j -S 1 ) .
In this case, we take M j = jS 1 , for j in {2, • • • i f }. W 3 can be written as follows, denoting N 1 = S 1 and with

P i (t) = -b p c p,i+1 (t), i ∈ {1, • • • , i f -1}: W 3 = i f -1 j=2 N j (P j-1 (t) -P j (t) + γ f c f,j (t)) + N i f P i f -1 (t) + N i f γ f c f,i f (t) -2S 1 P 1 (t) -S 1 i f -1 j=2 P j (t), W 3 = γ f i f j=2 N j c f,j (t) + i f -1 j=1 P j (t) (N j+1 -N j -S 1 ) .
Once again, we take

N j = jS 1 , for j in {2, • • • i f }. Finally V 1 is: V 1 = -r i0-1 c i0-1 (t)c 1 (t)(S i0-1 + S 1 ) + i0-1 i=2 S i µK i0,i c i0 (t).
The derivative of V 2 has the following expression:

V 2 = δc i0 (t)p c (t)(D 3 -D 4 -D 5 ) + δc i0 (t -τ )p c (t -τ )(D 5 -D 2 -D 3 ) + D 5 r i0-1 c i0-1 (t)c 1 (t) -c i0 (t) D 5 γ + µ 2 + γD 1 -αp c (t)(D 2 + D 4 ).
We choose D 3 = D 4 and D 2 = D 5 to ensure negativity of the two first terms. We finally have the following expression for V , with the different choices made for coefficient values:

V = -r i0-1 c i0-1 (t)c 1 (t)(i 0 S 1 -D 5 ) + c i0 (t) S 1 µ i0-1 i=2 iK i0,i -D 5 (γ + µ 2 ) -D 1 γ -D 5 δc i0 (t)p c (t) -D 3 δc i0 (t -τ )p c (t -τ ) -αp c (t)(D 2 + D 4 ).
Let us recall that this derivative should be equal to zero at steady state and negative elsewhere.

To guarantee this, we finally choose D 5 = (i 0 -1)S 1 and D 1 = 23) is finally obtained by taking S 1 = 1. By construction this function is equal to zero at steady state and positive elsewhere, with a non-positive derivative. One can easily verify that the derivative is equal to zero only at steady state.

µ i 0 -1 i=2 iKi 0 ,i γ S 1 . Expression (
We prove that this model admits a unique solution, which remains non-negative provided that the initial conditions are non-negative. Moreover, we find a unique steady state, which is globally stable. From a biological point a view, this means that regardless of the initial conditions of the experiment, all monomers will eventually polymerize into oligomers that will be transported in the amyloid plaque, while all PrP C prions will be misfolded in PrP ol prions.

In the following section, we focus on the global kinetics, to comprehend the role and the impact of each parameter on the dynamics without any experimental data.

Numerical analysis

We perform a sensitivity analysis and different numerical simulations. We focus on the impact of model parameters on the dynamics of prion proteins, as they might drive the neuronal loss in Alzheimer's disease, and is the new feature in this model.

Numerical simulations

First, we randomly sample 5000 parameter sets and simulate the model with each of them. We arbitrarily set i 0 = 20 and i f = 40, and choose r i = r f,i = a × i as the polymerization rate for proto-oligomers and fibrils, where i is the polymer size (number of monomers it contains). Initial values for monomers and prions are respectively m = 1 and p = 1. We keep a set of parameters for which all PrP C are misconformed in PrP ol . To prevent a direct transformation of PrP C in PrP ol , we force α to take a small value. Parameter values are the following, and the corresponding simulations are displayed on Figure 2. Note that these parameters should next be estimated with experimental data, to determine optimal values and corresponding units. However, to the best of our knowledge such data are still really challenging to obtain. As expected, the mass of oligomeric prions tends to the PrP C initial value, as it is the steady state value (see Section 3.2). Similarly, the mass of oligomers in the plaque tends to the initial mass of Aβ monomers. The misconformation of PrP C in PrP ol is mainly due to the interaction between prions and oligomers, as the value of direct transformation rate α is small. Because the reaction rate between PrP C and Aβ oligomers is greater than the displacement rate of oligomers into the plaque (δ > γ), oligomers are more likely to interact with prions to form complexes. After τ units of time, they are released from this complex, causing oscillations in the evolution of complexes and oligomers. The formation of complexes decreases with time as less PrP C are remaining.

Sensitivity analysis

To better understand the impact of each parameter on the emergence of PrP ol , we perform a sensitivity analysis through first order Sobol' indices [START_REF] Iooss | A review on global sensitivity analysis methods[END_REF] given by the following expression:

S i = V (E[Y |X i ]) V (Y ) , i = 1, • • • N, ( 24
)
where Y is the model output (evolution of PrP ol in our case), X i is a model parameter, V (Y ) represents the total variance of Y , E[Y |X i ] is the conditional mean of Y given X i , and N is the number of model parameters. First order Sobol' indices S i determine how much the model output varies when a parameter value varies. A parameter associated with a Sobol' index close to 1 has a large impact on Y variability, meaning that the model output is very sensitive to change in this parameter. In this work, we apply a sensitivity analysis to highlight the impact of each parameter on PrP ol emergence and to determine which ones contribute most to the output. We limit our study to first order Sobol' indices. Note that the impact of the interaction of several parameters on model output can be also be assessed through Sobol' indices, but can be more difficult to interpret. Because we do not know ranges of values for the different parameters, the interpretation of Sobol' indices should be taken with caution. Figure 3 displays results of sensitivity analysis: for each parameter, Sobol' index is calculated and its evolution with time is represented. Based on these results, parameters can be divided in three groups:

parameters that impact model output most (solid lines on Figure 3): displacement rate of oligomers in plaque γ, reaction rate between Aβ oligomers and PrP C δ, duration of oligomers and PrP C interaction τ and rate of direct transformation of PrP C into PrP ol α, parameters having little impact on model output (dashed lines on Figure 3): oligomer size i 0 , polymerization rate a (r i = r f,i = a × i) and depolymerization rates of proto-oligomers b and fibrils in plaque b p ,

parameters having no impact on model output (dotted lines on Figure 3): maximal fibril size i f , depolymerization rate of fibrils b f , displacement rate of fibrils in plaque γ f and proportion of oligomer fragmentation µ.

This is consistent with the role of each parameter. Indeed, we expect that parameters related to Aβ oligomers/PrP C interaction play a greater role in the emergence of PrP ol . As Aβ oligomers are required to misconform PrP C in PrP ol , it seems reasonable that parameters related to oligomer formation also impact PrP ol emergence. However, fibrils do not interact with PrP C and therefore do not impact PrP ol evolution. To go further, we illustrate the impact of parameters a (polymerization rate), b (proto-oligomer depolimerization rate), γ (diplacement rate of oligomers in plaque) and δ (reaction rate between Aβ oligomers and PrP C ). These parameters are chosen as they have a relatively strong impact on PrP ol evolution. Moreover, the processes they describe could constitute new therapeutic targets to slow down the emergence of PrP ol , and thus the progression of Alzheimer's disease.

Impact of displacement rate of oligomers into the plaque γ Impact of reaction rate between oligomers and PrP C δ Figure 5 displays the impact of δ, the reaction rate between Aβ oligomers and prions PrP C on evolutions of PrP ol (top left), complexes (top right), oligomers (bottom left) and oligomers in plaque (bottom right). For small values of δ, Aβ oligomers are less likely to interact with PrP C than to be transported in the plaque. This is the reason why we observe a stronger increase of the mass of oligomers in the plaque, while few complexes are created. For greater values of δ, Aβ oligomers interact with PrP C and therefore more PrP ol are created. We observe that for these values oligomers are found in the form of complexes or in the plaque, but few are left free.

Impact of polymerization rate a

We also study the impact of polymerization parameters on the emergence of PrP ol . Although the polymerization rate a does not explicitly take part in the interaction sub-model, it impacts the evolution of PrP ol through the formation of oligomers. Results of simulations for this parameter are displayed on Figure 6. We observe that for small values of a, few PrP ol are created. Indeed, because the polymerization rate is small, few oligomers are formed and therefore the interaction between PrP C and Aβ oligomers is less likely to occur. As a value increases, we observe an increase in the mass of complexes and of oligomers, leading to a faster emergence of PrP ol . We notice that the decrease of a value also slows down the increase of oligomer mass into the plaque. Indeed, as less oligomers are created, less are transported into the amyloid plaque. Consequently, the system will take more time to reach the steady state and Aβ monomers remain free in the brain.

Impact of depolymerization rate b

We finally present results of simulations for different values of the depolymerization rate of Aβ proto-oligomers b (Figure 7). For this parameter, we observe two cases. For small values of b, proto-oligomers do not depolymerize a lot, and therefore the monomer reserve cannot renew. Consequently, proto-oligomers have difficulties to evolve in bigger structures and to form oligomers. Prions PrP C are then less likely to interact with Aβ oligomers and PrP ol emergence is slowed down. With greater values of b, PrP C are misconformed in PrP ol faster. Depolymerization of proto-oligomers is stronger and enables monomer concentration to remain at a sufficient level to induce polymerization process and formation of oligomers. This leads to the interaction between Aβ oligomers and PrP C , and to the emergence of PrP ol . Note that for b = 3, less oligomers are present in the plaque at the end of the simulation, due to polymeriation slowing down. Similarly for the effect of parameter a, we observe that for small values of b, less oligomers are transported into the amyloid plaque.

Plausible therapeutic approaches? These four parameters could constitute plausible new therapeutic targets to treat Alzheimer's disease, as they slow down the emergence of oligomeric prions, that are supposedly toxic for the neurons. However, they do not have the same impact on monomers and oligomers. Indeed, while parameters γ and δ favours one mechanism between PrP ol emergence and oligomer displacement into the plaque, parameters a and b also reduce the mass of oligomers in the plaque. It is then relevant to analyse monomer and proto-oligomer evolutions, to determine under which structures Aβ monomers could be found in the brain.

We perform four additional numerical simulations using parameter values as given previously.

For each of these simulations, we replace γ, δ, a or b values with the value that reduces the most the emergence of PrP ol (from previous simulations), and we compare the evolution of monomers, proto-oligomers of size 10, PrP ol and oligomers in the plaque (Figure 8). As expected, γ and δ have the same impact on monomer and proto-oligomer evolutions, and similar results in terms of evolutions of PrP ol and oligomers in the plaque. However, because the value of a is low, few protooligomers and oligomers are created and consequently monomers remain free in the brain. The effect of b is quite the opposite: proto-oligomers are created, but because the depolymerization rate is low, the monomer reserve is not renewed and proto-oligomers cannot evolve in bigger structures and accumulate in the brain.

Discussion

Aβ oligomers and prions seem to play an important role in the emergence of Alzheimer's disease although it remains to be fully understood. Recent evidence suggests that oligomers can bind to neuron membrane receptors such as prions PrP C . This interaction induces first a structural re-arrangement of PrP C , leading then to its oligomerization into PrP ol . This last phenomenon is responsible for the transmission of a death signal to neurons. This process has been proposed to be one of the mechanisms responsible of neuron lose [START_REF] Cissé | A prion protein connection[END_REF]; [START_REF] Laurén | Cellular prion protein mediates impairment of synaptic plasticity by amyloid-β oligomers[END_REF]; [START_REF] Gimbel | Memory Impairment in Transgenic Alzheimer Mice Requires Cellular Prion Protein[END_REF].

In this work, based on individually well characterized pathways, we present a mathematical model describing the formation of oligomers and their interaction with PrP C . The sub-model for polymerization process (oligomerization and fibrillation) is composed of differential equations, based on Becker-Döring equations [START_REF] Becker | Kinetische Behandlung der Keimbildung in übersättigten Dämpfen[END_REF]. They include different mechanisms: polymerization/depolymerization, displacement in amyloid plaque and fragmentation of oligomers. The sub-model for Aβ/PrP C interaction is based on delayed differential equations and describes misfolding due to this interaction as well as direct transformation of PrP C into PrP ol , due to possible other mechanisms we are not aware of. We prove that this model admits one unique solution, which remains non-negative for non-negative initial conditions. Moreover, the model has an unique non-trivial steady state. We demonstrate that this steady state is globally stable, through the construction of a Lyapunov function, which constitutes the main result of this work. Although the mathematical tools used in this work are quite standard, we believe that finding a rlevant Lyapunov function could prove to be quite challenging. From a biological point of view, this means that, regardless of the initial conditions, the system tends to a unique state, where all monomers have polymerized in oligomers and are in the amyloid plaques, while all prions are misconformed into oligomeric prions.

We analyse the model from a numerical point of view, using sensitivity analysis and numerical simulations. We highlight the impact of different parameters, namely the reaction rate between oligomers and PrP C δ, the displacement rate of oligomers in the plaque γ, the polymerization rate a and the depolymerization rate of proto-oligomers b, on the evolution of PrP ol . We show that small values of parameters a and b slow down the emergence of oligomeric prions, as they prevent a fast polymerization into oligomers. Moreover, as less oligomers are created, we see that the mass of oligomers in the amyloid plaque is drastically reduced, and therefore it will take more time for the system to reach the steady state. This is not observed for parameters δ and γ because these parameters favour one mechanism between Aβ oligomers and PrP C interaction and oligomer displacement into the plaque. Although our results should be assessed with experimental data, we think that these processes could constitute targets for the pharmaceutical industry, to slow down the emergence of Alzheimer's disease [START_REF] Canter | The road to restoring neural circuits for the treatment of alzheimer's disease[END_REF]. Different strategies could be considered. Reducing proto-oligomer polymerization or depolymerization may slow down the emergence of oligomers and therefore the emergence of oligomeric prions, but induces an accumulation of free monomers or proto-oligomers into the brain. Decreasing the reaction rate between oligomers and prions or increasing the transport of oligomers in the amyloid plaque may slow down the emergence of oligomeric prions, but oligomer mass in the plaque increases faster. One should then find the right balance between the emergence of oligomeric prions, the accumulation of monomers or proto-oligomers into the brain, and the increase of oligomers into the amyloid plaque.

To go further, experimental data is required to validate the model from a biological point of view, and estimate model parameters. Besides, the model should include two types of Aβ monomers: Aβ-40, which is the most common type of monomers present in the brain, and Aβ-42, whose presence may indicate the emergence of Alzheimer's disease. It could be interesting to study the impact of these two types of monomers on the whole dynamics. Indeed they do not have the same polymerization kinetics [START_REF] Bitan | Amyloid β-protein (Aβ) assembly: Aβ40 and Aβ42 oligomerize through distinct pathways[END_REF][START_REF] Johnson | Single-Molecule Imaging Reveals Aβ42:Aβ40 Ratio-Dependent Oligomer Growth on Neuronal Processes[END_REF], and may not interact with ISSN 0006-3495.

Fig. 1 :

 1 Fig. 1: Schematic representation of Aβ polymerization processes and interactions with PrP C prions. Orange part corresponds to monomer evolution. Blue part is related to fibrillation process, while green part is related to oligomerization part. Finally pink box (top right corner) corresponds to Aβ/PrP C interaction. All parameters, quantities and interactions are described in the main text.

Fig. 2 :

 2 Fig. 2: Numerical simulations with parameter values as given in the main text. Top left: Time evolution of prions PrP C (dashed line) and oligomeric prions PrP ol (solid line). Top right: Time evolution of Aβ/ PrP C complex mass (assumed to be i 0 ). Bottom left: Time evolution of oligomer mass. Bottom right: Time evolution of the mass of oligomers in plaque.

Fig. 3 :

 3 Fig.3: Evolution of Sobol' indices with time for each parameter. Solid lines are used for parameters impacting PrP ol emergence most, dashed lines are used for parameters with a small impact and dotted lines for parameters with no impact.

Figure 4

 4 displays the impact of parameter γ, the displacement rate of Aβ oligomers into plaque, on the evolution of PrP ol . We perform model simulations with different values for this parameter while the others are fixed to the values given previously. We represent the evolution of PrP ol (Figure4, top left) along with evolutions of Aβ/PrP C complexes (top right), Aβ oligomers (bottom left) and oligomers in plaque (bottom right). These simulations represent the impact of γ on the dynamics described by the model. As expected, for small values of γ, Aβ oligomers are less likely to be transported to the plaque, and therefore can bind to PrP C . Consequently, more complexes are created, leading to a faster emergence of PrP ol . On the contrary, for larger values of γ, the mass of Aβ oligomers in plaque increases faster, and therefore less PrP C are misconformed in PrP ol .

Fig. 4 :

 4 Fig. 4: Impact of the displacement rate of oligomers into plaque γ on different outputs. Simulations are obtained with different values of γ (γ = 0.01: blue curve, γ = 0.05: red curve, γ = 0.2: yellow curve, γ = 0.5: purple curve and γ = 2: green curve), while other parameters are fixed to the values given previously. Top left: evolution of oligomeric prions PrP ol . Top right: evolution of Aβ/ PrP C complexes. Bottom left: evolution of Aβ oligomers. Bottom right: evolution of Aβ oligomers in plaque.

Fig. 5 :

 5 Fig. 5: Impact of the reaction rate between Aβ oligomers and PrP C δ on different outputs. Simulations are obtained with different values of δ (δ = 0.05: blue curve, δ = 0.1: red curve, δ = 0.5: yellow curve, δ = 1: purple curve and δ = 3: green curve), while other parameters are fixed to the values given previously. Top left: evolution of oligomeric prions PrP ol . Top right: evolution of Aβ/ PrP C complexes. Bottom left: evolution of Aβ oligomers. Bottom right: evolution of Aβ oligomers in plaque.

Fig. 6 :

 6 Fig. 6: Impact of the polymerization rate a (r i = r f,i = a × i) on different outputs. Simulations are obtained with different values of a (a = 0.5: blue curve, a = 0.8: red curve, a = 1: yellow curve, a = 2: purple curve and a = 3: green curve), while other parameters are fixed to the values given previously. Top left: evolution of oligomeric prions PrP ol . Top right: evolution of Aβ/ PrP C complexes. Bottom left: evolution of Aβ oligomers. Bottom right: evolution of Aβ oligomers in plaque.

Fig. 7 :

 7 Fig. 7: Impact of the depolymerization rate of proto-oligomers b on different outputs. Simulations are obtained with different values of b (b = 0.05: blue curve, b = 0.1: red curve, b = 0.5: yellow curve, b = 1: purple curve and b = 3: green curve), while other parameters are fixed to the values given previously. Top left: evolution of oligomeric prions PrP ol . Top right: evolution of Aβ/ PrP C complexes. Bottom left: evolution of Aβ oligomers. Bottom right: evolution of Aβ oligomers in plaque.

Fig. 8 :

 8 Fig. 8: Comparison between "best" values of γ, δ, a and b parameters, ie values that slow down the emergence of PrP ol : γ = 2 (black), δ = 0.05 (blue), a = 0.5 (red) and b = 0.05 (yellow). Top left: evolution of monomers. Top right: evolution of proto-oligomers of size 10 (i 0 /2). Bottom left: evolution of oligomeric prions PrP ol . Bottom right: evolution of oligomers in the amyloid plaque.

Table 1 :

 1 Description of model variables and parameters.

	Parameter/Variable	Definition
	Monomer
	c 1 (t) = c f,1 (t)	Aβ monomer concentration
	Oligomerization
	i 0	Maximal size of Aβ proto-oligomers
	c i (t), i ∈ {2, • • • , i 0 -1}	Size i proto-oligomer concentration
	c i 0 (t), c pl (t)	Aβ oligomer and oligomer in plaque concentrations
	r i , i ∈ {1, • • • , i 0 -1}	Polymerization rate of size i proto-oligomers (or monomers)
	b	Depolymerization rate of proto-oligomers
	γ	Displacement rate of Aβ oligomers into the plaque
	K i 0 ,i	Fragmentation kernel for oligomers
	µ	Proportion of oligomer fragmentation
	Fibrillation
	i f	Maximal size of Aβ fibrils
	c f,i (t), c pl,i (t), i ∈ {2, • • • , i f }	Size i fibril and fibril in plaque concentrations
	r f,i , i ∈ {1, • • • , i f -1}	Polymerization rate of size i fibrils (or monomers)
	b f , bp	Depolymerization rates of fibrils and fibrils in plaque
	γ f	Displacement rate of Aβ fibrils into the plaque
	Aβ/ PrP C interaction
	pc(t), p ol (t), X(t)	PrP C , PrP ol and Aβ/PrP C complex concentrations
	δ	Reaction rate between Aβ oligomers and PrP C
	τ	Duration of Aβ and PrP C interaction
	α	Rate of direct transformation of PrP C into PrP ol

Acknowledgements The authors thank Prof Glenn F. Webb for his valuable reading and corrections.

This work has been supported by Association France-Alzheimer, SM 2014

prions in the same way, which could constitute another therapeutic strategy. However, without experimental data comparing their dynamics, it is quite difficult to model their differences.


Yérom-David Bromberg
email: david.bromberg@irisa.fr

Quentin Dufour
email: quentin.dufour@inria.fr

Davide Frey
email: davide.frey@inria.fr

Multisource Rumor Spreading with Network Coding

Keywords: network coding, gossip-based dissemination, peer-to-peer network, epidemic algorithm, rumor spreading

The last decade has witnessed of a rising surge interest in Gossip protocols in distributed systems. In particular, as soon as there is a need to disseminate events, they become a key functional building block due to their scalability, robustness and fault tolerance under high churn. However, Gossip protocols are known to be bandwidth intensive. A huge amount of algorithms has been studied to limit the number of exchanged messages using different combination of push/pull approaches. We are revisiting the state of the art by applying Random Linear Network Coding to further increase performances. In particular, the originality of our approach is to combine sparse vector encoding to send our network coding coefficients and Lamport timestamps to split messages in generations in order to provide an efficient gossiping.

Our results demonstrate that we are able to drastically reduce the bandwidth overhead and the delay compared to the state of the art.

I. INTRODUCTION

Distributed systems are becoming increasing large and complex, with an ever-growing shift in their scale and dynamics. This trend leads to revisit key known challenges such as inconsistencies across distributed systems due to an inherent increase of unpredictable failures. To be highly resilient to such failures, an efficient and robust data dissemination protocol is the cornerstone of any distributed systems. The last decade gossip protocols, also named epidemics protocols, have been widely adopted as a key functional building block to build distributed systems. For instance, gossip protocols have been used for overlay construction [START_REF] Jelasity | T-man: Gossip-based overlay topology management[END_REF], [START_REF] Bouget | Pleiades: Distributed Structural Invariants at Scale[END_REF], membership and failure detection [START_REF] Lakshman | Cassandra: A Decentralized Structured Storage System[END_REF]- [START_REF] Das | Swim: Scalable weaklyconsistent infection-style process group membership protocol[END_REF], aggregating data [START_REF] Jelasity | Gossip-based aggregation in large dynamic networks[END_REF] and live streaming [START_REF] Frey | Live Streaming with Gossip[END_REF], [START_REF] Frey | Stretching gossip with live streaming[END_REF]. This wide adoption comes from the resilience of gossip protocols while being simple and naturally distributed [START_REF] Androulaki | Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains[END_REF] [3] [START_REF] Ndelec | CRATE: Writing Stories Together with Our Browsers[END_REF]. Gossip based dissemination can be simply represented as the random phone call problem; at the beginning, someone learns a rumor, and calls a set of random friends to propagate it. As soon as someone learns a new rumor, in turn, she randomly propagates it to her own set of friends, and so on recursively. Further, depending on whether there are one or more sources of rumors (i.e. dissemination of one or multiple messages to all nodes), gossip protocols may be either single or multi source. In both cases, randomness and recursive probabilistic exchanges provide scalability, robustness and fault tolerance under high churn to disseminate data while staying simple.

To appear in Proc. IEEE INFOCOM 2019.

However, due to its probabilistic aspect, gossip based dissemination implies high redundancy with nodes receiving the same message several times. Many algorithms have been studied to limit the number of exchanged messages to disseminate data, using different combination of approaches such as push (a node can push a message it knows to its neighbors), pull (a node pulls a messages it does not know from its neighbors) or push-pull (a mix of both) for either single or multi-source gossip protocols [START_REF] Koldehofe | Simple gossiping with balls and bins[END_REF] [13] [START_REF] Felber | Pulp: An adaptive gossipbased dissemination protocol for multi-source message streams[END_REF].

In this paper, we make a significant step beyond these protocols, and provide better performance with respect to the state of the art of multi-source gossip protocols.

The key principle of our approach is to consider the redundancy as a key advantage rather than as a shortcoming by leveraging on the Random Linear Network Coding (RNLC) techniques to provide efficient multi-source gossip based dissemination. Indeed, it has been shown that RLNC improves the theoretical stopping time, i.e., the number of rounds until protocol completeness, by sending linear combination of several messages instead of a given plain message, which increases the probability of propagating something new to recipients [START_REF] Deb | Algebraic gossip: A network coding approach to optimal multiple rumor mongering[END_REF], [START_REF] Haeupler | Analyzing network coding gossip made easy[END_REF].

Unfortunately, applying RNLC to multi-source gossip protocols is not without issues, and three key challenges remain open. First, existing approaches suppose that a vector, where each index identifies a message with its associated coefficient as a value, is disseminated. This approach implies a small namespace. In the context of multi source, the only option is to choose a random identifier over a sufficiently large namespace to have a negligible collision probability. However this does not scale. Some algorithms provide a mechanism to rename messages to a smaller namespace [START_REF] Castaeda | The renaming problem in shared memory systems: An introduction[END_REF], but this kind of techniques are not applicable to gossip protocols as they would substantially increase the number of exchanged messages, and inherently the delay. Second, to reduce the complexity of the decoding process, messages are split in groups named generations. Existing rules to create generations require having only one sender, which is impractical in the context of multiple sources. Third, the use of RNLC implies linear combinations of multiple messages. This leads to potential partial knowledge of messages received, making precise message pull requests useless and breaks pull frequency adjustment based on missing messages count.

In this paper, we introduce CHEPIN, a CHeaper EPidemic dissemINation approach for multi-source gossip protocols.

To the best of our knowledge, our approach is the first one to apply RNLC to multi-source gossip protocols, while overcoming all the inherent challenges involved by the use of network-coding techniques.

More precisely, we make the following contributions.

• We solve the identifier namespace size via the use of sparse vectors. The data sent over the network stays reasonable. • We create generations for messages from multiple sources by leveraging on Lamport timestamps. All messages sharing the same clock are in the same generation whatever its source. • We overcome the issue of partial message knowledge by providing an adaptation of push, pull, push-pull gossip protocols. We pull specific generations instead of specific messages.

• We introduce updated algorithms to make our approach applicable to the current state of the art of multi-source gossip protocols. • Finally, we are evaluating CHEPIN thoroughly by simulation. We show that our solution reduces the bandwidth overhead by 25% and the delivery delay by 18% with respect to PULP [START_REF] Felber | Pulp: An adaptive gossipbased dissemination protocol for multi-source message streams[END_REF], while keeping the same properties.

II. RELATED WORK

Epidemic protocols were introduced in 1988 by Xerox researchers on replicated databases [START_REF] Demers | Epidemic Algorithms for Replicated Database Maintenance[END_REF]. They introduce three protocols to exchange rumors: push, pull and push pull.

a) Push protocols: to transmit rumors, push-based protocols imply that informed nodes relay the message to their neighbors. Some protocols are active, as they have a background thread that regularly retransmits received rumors, like balls and bins [START_REF] Koldehofe | Simple gossiping with balls and bins[END_REF]. But it can also be implemented as a reactive protocols, where rumors are directly forwarded to the node's neighbors upon reception, like infect and die and infect forever protocols [START_REF] Euster | From epidemics to distributed computing[END_REF]. Push protocols are particularly efficient to quickly reach most of the network, however reaching all the nodes takes more time and involves significant redundancy, and thus bandwidth consumption.

b) Pull protocols: nodes that miss messages ask other nodes for the missing messages. As a consequence, pull protocols more efficiently reach the last nodes of the network, as inherently, they get messages with higher probability. However, they require sending more messages over the network: (i) one to ask a missing message, and (ii) one other for the reply that contains the missing message. Furthermore a mechanism or a rule is needed to know what are the missing messages to pull, which explains why these protocols are generally used in conjunction with a push phase. c) Push-Pull protocols: the aim is to conciliate the best from push and pull protocols by reaching as many nodes as possible without redundancy on the push phase. Then, nodes that have not received the message will send pull requests to other nodes of the network. By ordering messages, Interleave [START_REF] Sanghavi | Gossiping With Multiple Messages[END_REF] proposes a solution to discover the missing messages in the pull phase, but works only with a single source. Instead of ordering messages, Pulp [START_REF] Felber | Pulp: An adaptive gossipbased dissemination protocol for multi-source message streams[END_REF] piggybacks a list of recently received messages identifiers in every sent messages, allowing multiple sources.

Gossip-based disseminations are caracterized by the reception of many redundant messages in the push and pull phases in order to receive every message with high probability. By using Random Linear Network Coding, we aim at increasing the usefulness of exchanged messages.

d) Random Linear Network Coding: To improve dissemination, some protocols use erasure coding [START_REF] Champel | FoG: Fighting the Achilles' Heel of Gossip Protocols with Fountain Codes[END_REF] [START_REF] Sanghavi | Gossiping With Multiple Messages[END_REF] or Random Linear Network Coding [START_REF] Chou | Practical Network Coding[END_REF] but need encoding at the source or message ordering, which limits these techniques to single-source scenarios. Theoretical bounds have also been studied for multi-sender scenarios [START_REF] Deb | Algebraic gossip: A network coding approach to optimal multiple rumor mongering[END_REF] [16] but they do not consider generations and suppose that messages are previously ordered. Network Coding is also used on wireless networks [START_REF] Fragouli | Efficient Broadcasting Using Network Coding[END_REF] [23] but with different system models, as emitted messages can be received by every node within range.

Applying RLNC gossip in a multi-sender scenario implies determining to which generation a message will belong to without additional coordination, and finding a way to link network coding coefficients to their respective original messages inside a generation.

III. BACKGROUND ON NETWORK CODING AND CHALLENGES

A B C D E M 1 M 1 M 2 M 2 c 1 , c 1 1 M 1 + c 1 2 M 2 c 2 , c 2 1 M 1 + c 2 2 M 2
Fig. 1: With RLNC, C can send useful information to D and E without knowing what they have received RLNC [START_REF] Fragouli | Network Coding: An Instant Primer[END_REF] provides a way to combine different messages on a network to improve their dissemination speed by increasing the chance that receiving nodes learn something new. In Figure 1, node C cannot know what D and E have received. By sending a linear combination of M 1 and M 2 , nodes D and E can respectively recover M 2 and M 1 with the help of the plain message they also received. Without RLNC, node C would have to send both M 1 and M 2 to D and E involving two more messages. Every message must have the same size, defined as L bits thereafter. To handle messages of different size, it is possible to split or pad the message to have a final size of L bits.

The message content has to be split as symbols over a field F 2 n . The F 2 8 field has interesting properties when doing RLNC. First, a byte can be represented as a symbol in this field. Thereafter, this field is small enough to speed up some computing with discrete logarithm tables and at the same time sufficiently large to guarantee linear independence of the random coefficients with very high probability.

Encoded messages are linear combinations over F 2 n of multiple messages. This linear combination is not a concatenation: if the original messages are of size L, the encoded messages will be of size L too. An encoded message carries a part of the information of all the original messages, but not enough to recover any original message. After receiving enough encoded messages, the original messages will be decodable.

To perform the encoding, the sources must know n original messages defined as M 1 , ..., M n . Each time a source want to create an encoded message, it randomly chooses a sequence of coefficients c 1 , ..., c n , and computes the encoded message X as follows: X = n i=1 c i M i . An encoded message thus consists of a sequence of coefficients and the encoded information: (c, X).

Every participating node can recursively encode new messages from the one they received, including messages that have not been decoded. A node that received (c 1 , X 1 ), ..., (c m , X m ) encoded messages, can encode a new message (c , X ) encoded by choosing a random set of coefficients d 1 , ..., d m , computing the new encoded information X = m j=1 d j X j and computing the new sequence of coefficients c i = m j=1 d j c j i . An original message M i can be considered as an encoded message by creating a coefficient vector 0, ..., 1, .., 0 where 1 is at the ith position. The encoding of a message can therefore be considered as a subset of the recursive encoding technique.

Even if there is no theoretical limit on the number n of messages that can be encoded together, there are two reasons to limit it. First, Gauss-Jordan elimination has a O(n 3 ) complexity, which becomes rapidly too expensive to compute. Then, the more the messages encoded together, the bigger the sequence of coefficients while the encoded information remains stable. In extreme cases this can result in sending mainly coefficients on the network instead of information. To encode more data, splitting messages in groups named generations solves the previous problems, as only messages in the same generation are encoded together.

However applying network coding to epidemic dissemination raises several challenges. a) Assigning a message to a generation: Generations often consist of integers attached to a message. Messages with the same generation value are considered in the same generation and can be encoded between them. The value must be assigned in such a way than enough messages are in the same generation to benefit from RLNC properties but not too many to keep the decoding complexity sufficiently low and limit the size of the coefficients sent on the network. In a single source scenario, the size of the generation is a parameter of the protocol, and is determined by counting the number of messages sent in a given generation. However, with multiple sources, there is no way to know how many messages have been sent in a given generation.

b) Sending coefficients on the network: Coefficients are generally sent under the form of a dense vector over the network. Each value in the vector is linked to a message. On a single source scenario, that is not a problem, the source knows by advance how many messages it will send and can assign each message a position in the vector and start creating random linear combinations. In the case of multiple sources, the number of message is not available, and waiting to have enough messages to create a generation could delay message delivery and above all, the network traffic required to order the messages in the dense vector would ruin the benefits of network coding. c) Pulling with RLNC: When doing pull-based rumor mongering, a node must have a way to ask what rumors it needs. Without network coding, it simply sends a message identifier to ask for a message. But sending a message identifier in the case of network coding raises several questions: does the node answer only if it has decoded the message? Or if it can generate a linear combination containing this message? d) Estimating the number of missing packets: Some algorithms need to estimating the number of missing messages. Without network coding, the number of missing packets corresponds to the number of missing messages. But with RLNC, it is possible to have some linear combination for a given set of messages but without being able to decode them. All the messages are considered as missing but one packet could be enough to decode everything.

IV. CONTRIBUTION

A. System model

Our model consists of a network of n nodes that all run the same program. These nodes communicate over a unicast unreliable and fully connected medium, such as UDP over Internet. Nodes can join and leave at any moment, as no graceful leave is needed, crashes are handled like departures. We consider that each nodes can obtain the address of some other nodes of the service via a Random Peer Sampling service [START_REF] Jelasity | Gossip-based Peer Sampling[END_REF]. There is no central authority to coordinates nodes, all operations are fully decentralized and all exchanges are asynchronous. We use the term message to denote the payload that must be disseminated to every node of the network, and the term packet to denote the exchanged content between two nodes. We consider the exchange of multiple messages and any node of the network can inject messages in the network, without any prior coordination between nodes (messages are not pre-labeled).

B. Solving RLNC challenges

Due to our multiple independent source model and our goal to cover push and pull protocols, we propose new solutions to the previously stated challenges:

a) Assigning generations with Lamport timestamps: With multiple senders, we need to find a rule that is applicable only with the knowledge of a single node when assigning a generation as relying on network would be costly, slow and unreliable. We chose Lamport timestamps [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] to delimit generations by grouping every messages with the same clock on the same generation. This method doesn't involve sending new packets as the clock is piggybacked on every network coded packet. When a node wants to disseminate a message, it appends its local clock to the packet and update it, when it receives a message, it uses its local clock and the message clock to update its clock. This efficiently associated messages that are disseminated at the same time into the same generation.

b) Sending coefficients in sparse vectors: When multiple nodes can send independent messages, they have no clue on which identifiers are assigned by the other nodes. Consequently, they can only rely on their local knowledge to choose their identifiers. Choosing identifiers randomly on a namespace where all possible identifiers are used would lead to conflicts. That is why we decided to use a bigger namespace, where conflict probabilities are negligible when identifiers are chosen randomly. On a namespace of this size, it is impossible to send a dense vector over the network, however we can send a sparse vector: instead of sending a vector c 1 , ..., c n , we send m tuples, corresponding to the known messages, containing the message id and their coefficient:

(id(M i1 ), c i1 ), ..., (id(M im ), c im ).
c) Pulling generations instead of messages: A node sends a list of generations that it has not fully decoded to its neighbors. The target node answers with one of the generation it knows. To determine if the information will be redundant, there is no other solution than asking the target node to generate a linear combination and try to add it to the node's local matrix. During our tests, it appears that blindly asking generations didn't increase the number of redundant packets compared to a traditional Push-Pull algorithm asking for a message identifier list while greatly decreasing message sizes.

d) Count needed independent linear combinations: To provide adaptiveness, estimating the number of useful packets needed to receive all the missing messages is needed by some protocols. Without network coding, the number of needed packets corresponds to the number of missing messages. With network coding, partially decoded packets are also considered as missing messages, but to decode them we need fewer packets than missing messages. In this case, the number of useful packets needed corresponds to the number of independent linear combinations needed.

C. CHEPIN

To ease the integration of RLNC in gossip-based dissemination algorithms, we encapsulated some common logic in algorithm 1. We represent a network-coded packet by a triplet: g, c, e , where g is the generation number, c an ordered set containing the network coding coefficients and e the encoded payload.

We define 3 global sets: rcv, ids and dlv. rcv contains a list of network coded packets as described before that are modified each time a new one is received to stay linear independent until all messages are decoded. ids contains a list of known messages identifiers under the form g, gid where g is the generation and gid is the identifier of the message inside the generation. By using this tuple as unique identifier, we can reduce the number of bytes of gid as the probability of collision inside a generation is lower than the one in the whole system. Finally dlv contains a list of if p = ∅ then 7:

return False 8:

g 1 , c 1 , ← p 9:
oldRank ← RANK(g 1 , rcv)

10:

rcv ← SOLVE(g 1 , rcv ∪ {p})

11:

if oldRank = RANK(g 1 , rcv) then 12:

return False Packet was useless 13:

for all id, ∈ c 1 do 14:

ids ← ids ∪ { g 1 , id } Register new identifiers 15:
for all g 2 , c 2 , e ∈ rcv do

16: id, ← c 2 [0] 17: if g 1 = g 2 ∧ LEN(c 2 ) = 1 ∧ g 2 , id / ∈ dlv then 18: dlv ← dlv ∪ { g 2 , id } 19:
DELIVER(e) New decoded message 20:

if g 1 > g ∨ RANK(g, rcv) ≥ 1 then 21: g ← MAX(g 1 , g) + 1 Update Lamport Clock 22:
return True Packet was useful message identifiers similar to ids, but contains only identifiers of decoded messages.

The presented procedure relies on some primitives. RANK returns the rank of the generation, by counting the number of packets associated to the given generation. SOLVE returns a new list of packets after applying a Gaussian elimination on the given generation and removing redundant packets. DELIVER is called to notify a node of a message (if the same message is received multiple time, it is delivered only once).

This procedure updates the 3 global sets previously defined, delivers decoded messages and return the usefulness of the given packet. Internally, the node starts by adding the packet to the matrix and do a Gaussian elimination on the packet's generation (line 10), if decoding the packet didn't increase the matrix rank, the packet was useless and the processing stops here. Otherwise, the node must add unknown message identifiers from the packet coefficient list to the known identifiers set. After that, the node delivers all decoded messages thanks to the received packet and stores their identifiers in dlv. Finally, the node checks if the clock must be updated.

Algorithms 2 and 3 show how the above procedures can be used to implement push and pull gossip protocols. For push, we do not directly forward the received packet, but instead forward a linear combination of the received packet's generation after adding it to our received packet list. For Pull, we request generations instead of messages. Like existing protocols, we keep a rotation variable that rotates the set of missing identifiers, allowing missing generations to be generated in a different order on the next execution of the code block. if dottl then 20:

headers.ttl ← headers.ttl -1

21:

SENDTONEIGHBOURGS(h, headers)

V. APPLICATION TO PULP

To apply our network-coding approach to a concrete use case, we design CHEPIN-Pulp, a protocol inspired by Pulp [START_REF] Felber | Pulp: An adaptive gossipbased dissemination protocol for multi-source message streams[END_REF]. Pulp achieves cost-effective dissemination by optimizing the combination of push-based and pull-based gossip. In particular, nodes disseminate each message through a pushphase with little redundancy due to a fanout and a TTL configured to reach only a small portion of the network. As the push-phase doesn't provide a complete dissemination, the message will be retrieved by the rest of the network during a pull phase. To this end, each node periodically sends its list of missing messages to a random node. The target node answers with the first message it knows. To discover missing messages, nodes piggyback the list of recently received messages on every packet exchange. To improve reactivity and reduce delays, Pulp provides a pulling frequency-adaptation mechanism based on the node's estimation of missing messages and usefulness of its pull requests. for all m ∈ ROTATE(ids \ dlv, rotation) do 6:

ask ← ask ∪ GEN(m, rcv)

SEND(PULL, ask, headers)

8: function NCPULL(asked, headers)

9:
p ← ∅ 10:

if ∃ g ∈ asked, RANK(g, rcv) > 0 then 11:

p ← RECODE(g, rcv)

12:

SEND(PULLREPLY, p, headers)

13: function NCPULLREPLY(p) 14:

PROCESSPACKET(p)

On top of the two previously defined algorithms 2 and 3, we propose a push-pull algorithm inspired by Pulp (Algorithm 4. First, we must convert the Pulp message discovery mechanism which consists on exchanging recent message history via a trading window. The trading window is generated by the GETHEADERS function, which will be added to every packets. On reception, the trading window will be retrieved and its new identifiers will be added to the ids set. The major difference with Pulp is that we don't trade identifiers of delivered messages but any identifiers we know, even if we compare both approaches in Section VI.

The adaptation mechanism is the second feature of Pulp, the pull frequency is adapted according to the number of missing packets and the usefulness of the pull requests. Our only modification is made on how to compute the number of missing packets, as we retained the number of needed independent linear combinations instead of the number of missing messages. To do so, we compute the difference between the number of messages identifiers and the number of independent linear combinations we have.

VI. EVALUATION

We evaluated our solution in the Omnet++ simulator, using traces from PlanetLab and Overnet to simulate respectively the latency and the churn. To assess the effectiveness of CHEPIN, we implemented a modified version of Pulp as described in Section V, and compare it with the original Pulp protocol.

A. Experimental setup

We run our experiments with 1 000 nodes, sending 1 000 messages at a rate of 150 messages per second. Each message weighs 1KB and has a unique identifier. For Pulp, it is simply an integer encoded on 8 bytes. In the case of CHEPIN-Pulp, the unique identifier is composed of its generation encoded on In order to accurately simulate latency, we use a PlanetLab trace [START_REF] Zhu | Network Latency Estimation for Personal Devices: A Matrix Completion Approach[END_REF]. Latency averages at 147 ms for a maximum of almost 3 seconds. Most of the values (5th percentile and 95th percentile) are between 20 ms and 325 ms. Finally we have a long tail of values between 325 ms and the maximum value.

B. Configuring the Protocols

To configure protocols, we chose an experimental approach. First, we selected a suitable value for the size of the trading window. As explained in Section V, too small values of this parameter result in wasted pull requests, and missing messages, while too large ones lead to wasted bandwidth. We therefore tested the ability of the original Pulp, and of our solution to achieve complete dissemination (i.e. all messages reach all nodes) with different trading window sizes, and a safety margin of 10. Results, not shown for space reasons, show that our solutions reaches complete dissemination with trading window sizes of at least 6, while Pulp requires tradingwindow sizes of at least 9. For the rest of our analysis, we therefore considered a trading-window size of 9, and a safety margin of 10. Nonetheless, this first experiment already hints at the better efficiency of our network-coding-based solution.

(a) 6.9 Next, we selected values for fanout and TTL. Figure 2 reports the delivery delays and bandwidth consumption of the two protocols with several values of these two parameters. To measure bandwidth consumption, we consider the ratio between the average amount of bandwidth consumed by the protocol, and the lower bound represented by the bandwidth required for the same task in a tree structure in a stable network. First, we observe that in terms of delays and bandwidth used, our network coding variant is more stable than the original Pulp. That is, with low values of fanout and ttl, the original algorithm deteriorates faster.

Next, we see that our network coding variant performs better or similarly for every combination of fanout and ttl both in terms of sent bandwidth and delay. The best configuration in term of sent data for Pulp corresponds to the configuration k = 6, ttl = 4 with 2.12 KB for 1KB of useful data and an average of 0.67 seconds to disseminate a message. Our network-coding solution reduces delay to 0.55, with a bandwidth consumption of 1.83KB/msg. With a fanout of 5 our solution further decreases consumed bandwidth to 1.66 KB/msg but with a slight increase in delay (0.83 s). Clearly, to achieve the minimum delays, the best strategy consists in boosting the push phase by increasing the TTL, but this defeats the bandwidth-saving goal of Pulp and our approach. As a result, we use the configuration with k = 6, ttl = 4 for both protocols in the rest of our comparison.

C. Bandwidth and delay comparison

We evaluate how our algorithm performs over time in Figure 3. First, we logged the number of packets sent per second for the three types of packets: push, pull and pull reply. As we configured the two protocols with the same fanout and TTL, we would expect seeing almost the same number of push packets. But our network-coded variant sends 12% more push packets. Pulp stops forwarding a push packet if the corresponding message is already known. But since our variant can use a large number of linear combinations, our algorithm manages to exploit the push-phase better, thereby reducing the number of packets sent in the pull phase: 33% fewer pull and pull reply packets. This strategy enables us to have a packet ratio of only 2.27 instead of 2.70.

As network coded packets include a sparse vector containing messages identifiers and values, our the algorithm has larger pull and pull reply packets than Pulp. Considering push packets, we also send more of them, which explains why we send 17% more data for these packets. However, as our pull phase is way smaller than the one from Pulp, the pull reply packets of our algorithm consume 28% less data than the ones from Pulp. We can also notice that the pull packets consume less data than the two others. Indeed, these packets never contain the 1 KB payload. However, we can notice that our algorithm still consumes less data than Pulp as we transmit generation id instead of each message id. With 150 messages/second, at a given time time, every nodes will be aware of a huge list of missing messages and ask it to their peers. Generally, this list will contain messages sent approximately at the same time, so probably in the same generation, which explain why it is way more efficient to ask for generation identifiers, and why pull packets will be smaller for our algorithm. These two facts enable us to have a data ratio 1.84 instead 2.12.

Finally, we study the distribution delay of each message. As our algorithm has a longer push phase, delays are smaller on average. We see a downward slope pattern on our algorithm's delays, especially on the maximum delays part. This pattern can be explained by the fact that decoding occurs at the end of each generation, so messages that are sent earlier wait for longer than the most recent ones.

D. Adaptiveness optimization

We now carry out a sensitivity analysis to understand the reasons for our improved performance. To this end, Figure 4 compares our algorithm with to Pulp and with two intermediate variants.

The first variant corresponds to a modification in the GET-TRADINGWINDOW function of algorithm 1. Instead of using the message identifiers contained in the ids variable, we use the message identifiers contained in the dlv variable like in the case of the standard Pulp protocol. In other words, we disseminate the identifiers of messages we have decoded and not those we are aware of.

The second variant is a modification on how we count the number of missing messages at line 21 in algorithm 4. For this variant, we do missingSize ← |missing| like in the original pulp. We thus evaluate the number of missing messages by counting all the message identifiers we have not yet decoded, without taking into account the progress of the decoding in our generations.

The two variants perform worse than our solution both in terms of delay and bandwidth. Variant 1 does not manage to achieve complete dissemination with a fanout of 6 and a TTL of 4, while Variant 2 achieves complete dissemination but at a higher cost ratio: 2.4 instead of 1.83 for our solution. This shows the importance of the modifications we made to the Pulp protocol.

To understand how these modifications behave, Figure 4 shows the different between the number of useful and useless packets. We see that our algorithm and Variant 1 perform similarly. The Pulp algorithm has a more efficient pull strategy than ours, possibly because there are more messages to pull, we receive redundant linear combination for the requested generation or the frequency adaptation is not optimal in our case. However, we see that we obtain way better results than the second variant, which mainly pull useless messages. At the end, we see lot of useless messages, as we don't inject useful messages anymore. The adaptive part of the algorithm therefore decreases the number of pull per second, to reduce useless messages.

When we look at the pull period, we see that Variant 1 and our algorithm are quite similar, with the biggest pull period as they have less messages to pull. Pulp has a smaller pull period, but has it has more messages to pull, it is not surprising. Our second variant pull period is the smallest even though this variant hasn't more messages to pull than our algorithm or our first variant, and explain why we have many useless messages: we pull to frequently.

Finally, when we study the evolution of our missing message estimation, it appears that the first variant has the lowest estimation of missing messages. It is due to the fact that we relay only decoded messages via the trading window, which adds a delay and improve the chances to receive the information via network coding coefficients.

However, it appears that this method is not efficient to disseminate message identifiers as it fails to achieve a complete dissemination with high probability. Indeed, if a message is sent at the end of a generation, its content and existence will only be forwarded on its push phase and not by other messages of the generation.

E. Behaviour under network variation

Figure 5 shows how our algorithm performs under different network configurations. We see that when the number of messages per second decreases, the difference in term of data sent between the algorithms decreases too. This can be explained by the fact that our generations become smaller At an extreme, when we have only one message per generation, we have the same model as Pulp: asking for a list of generation identifiers is similar to asking a list of message identifiers in Pulp. The network coded packets will contain a generation identifier, a sparse vector containing only one message identifier and one coefficient and the message. As a generation identifier plus a message identifier of our algorithm has the same size of a message identifier in Pulp, the only We use an Overnet trace to simulate churn [START_REF] Bhagwan | Understanding Availability[END_REF]. The trace contains more than 600 active nodes over 900 with continuous churn-around 0.14143 events per second.

We use this trace replayed at different speed to evaluate the impact of churn on the delivery delays of our messages, as plotted on Figure 6. We chose to re-execute the trace at different speed: 500, 1000 and 2000 times faster for respectively 71, 141 and 283 churn events per second. We see that the original Pulp algorithm is not affected by churn, as the average and maximum delivery delays stay stable and similar to those without churn. Considering the average delay, it's also the case for our algorithm, where the average delay didn't evolve. The maximum delay doesn't evolve significantly either. However Fig. 6: Delay observation with churn on the system we can see huge differences in the shape of the maximum delay for each individual messages. Indeed, the decoding order and the generation delimitation are affected by the churn, but limited impact on message dissemination.

VII. CONCLUSION

Distributed systems become more and more complex and dynamic with time. Due to their properties and resistance to failure, data dissemination protocols are the cornerstone of any distributed system. However, these advantages come at the cost of bandwidth spent by the embedded redundancy in the protocol. We introduce CHEPIN, a multi source gossip protocol that uses Lamport clocks to create generations, and sparse vectors to exchange coefficients. We have demonstrated that is possible to apply RLNC for push and pull algorithm by thoroughly evaluating our approach. At worst, CHEPIN performs like the state of the art. At best, CHEPIN significantly improves both delay and bandwidth consumption. As future work, we would like to investigate benefits of overlapping generations on message discovery and efficiency. We are also interested by improving CHEPIN's adaptiveness and extend its generation management.

  rotation ← rotation + 1 mod |ids \ dlv| 5:

Algorithm 4 8 :

 48 Pulp NC 1: ts, sm ← ... Trading window size and margin 2: ∆ adjust , ∆ pull min , ∆ pull max ← ... Periods config. 3: dottl, dodie ← T rue, T rue Set push strategyy 4: ∆ pull ← ∆ adjust 5: function GETHEADERS 6: start ← MAX(0, |ids| -sm -tm) 7: end ← MAX(0, |ids| -sm) return {tw : ids[start : end]} 9: upon receive PUSH(p, headers) 10: ids ← ids ∪ headers.tw 11: NCPUSH(p, GETHEADERS()) 12: upon receive PULL(asked, headers) 13: ids ← ids ∪ headers.tw 14: NCPULL(asked, GETHEADERS()) 15: upon receive PULLREPLY(p, headers) 16: ids ← ids ∪ headers.tw else if missingSize > 0 ∧ prev useless ≤ prev usef ul then 25: ∆ pull ← ∆ pull × 0.9 26: else 27: ∆ pull ← ∆ pull × 1.1 28: ∆ pull ← MAX(∆ pull , ∆ pull min ) 29: ∆ pull ← MIN(∆ pull , ∆ pull max ) 30: prev useless ← 0 31: prev usef ul ← 0 32: prevM issingSize ← missingSize 4 bytes and a unique identifier in this generation, also encoded on 4 bytes. ∆ adapt is set to 125 ms.

Fig. 2 :

 2 Fig. 2: Pulp (2a) and our algorithm (2b) behavior under various configuration of the protocol (fanout and time to live)

Fig. 3 :Fig. 4 :

 34 Fig. 3: Comparison of exchanged packet rate, used bandwidth and message delay for 3a pulp original (k = 6, ttl = 4) and 3b our algorithm (k = 5, ttl = 4)

Fig. 5 :

 5 Fig. 5: Variation of network configuration

ACKNOWLEDGMENT

We wish to thank the authors of [14] for providing useful information about their work. This work was partially funded by the O'Browser ANR grant (ANR-16-CE25-0005-03).