Amel Karoui

Laura Bear

Pauline Migerditichan

Mostafa Bendahmane

Nejib Zemzemi

The Heart Recording Conditions Impact the Assessment of the Electrocardiography Imaging Inverse Solution

Our purpose is to assess different methods for choosing the regularization parameter combined with the Method of Fundamental Solutions (MFS) for solving the electrocardiography imaging (ECGi) inverse problem but also to assess their sensitivity to the nature of recorded signals. Results are provided using LV, RV and bi-ventricular pacing experiments performed in an ex-vivo pig heart. In the experiment, some electrodes are too close to the pericardium so that they seem to be measuring monophasic action potential signals (MAPs) rather then extracellular epicardial potential. The electrodes suspected to measure MAPs are identified by thresholding the epicardial potential in the plateau phase. This leads to compare the computed epicardial potential to measurement results with and without considering these electrodes measurements. Removing the MAPs electrodes improves the quality of the RE and CC by at least 5% . Results show that the Generalized Cross Validation (GCV) approach provides the best results in the three pacing cases.

Introduction

The electrocardiographic imaging (ECGi) is a noninvasive technique providing the electrical potential on the epicardial surface from measures realized on the thoracic surface using a set of electrodes. It's based on a mathematical model which describes the heart-torso electrical activity. This is called an inverse problem and is known to be ill-posed resulting from different factors such as the uncertainty of the mathematical model. In fact, modeling the electrical activity by a laplacian equation and considering the heart-torso domain as homogeneous generate modeling errors. In addition, experimental protocols yields measurement errors and geometries' innaccuracy especially in determining the heart position [START_REF] Messinger-Rapport | Computational issues of importance to the inverse recovery of epicardial potentials in a realistic heart-torso geometry[END_REF][START_REF] Messinger-Rapport | Regularization of the inverse problem in electrocardiography: A model study[END_REF]. These conditions can generate large and even discontinuous errors in the inverse solution. Regularization procedures are then used to stabilize the solution and ensure its uniqueness and its dependence on the data. To date, many regularization approaches are suggested. In this work, we depicted the zero-order Tikhonov regularization, presumed to be the most simple and appropriate non-a-priori regularization method to solve the inverse problem of electrocardiography [START_REF] Figuera | Regularization techniques for ecg imaging during atrial fibrillation: a computational study[END_REF]. One of the issues of the regularization methods is the choice of the regularization parameter. Actually, few works have compared the different developed approaches [START_REF] Cheng | Comparison of potentialand activation-based formulations for the inverse problem of electrocardiology[END_REF][START_REF] Barnes | Application of robust generalised cross-validation to the inverse problem of electrocardiology[END_REF][START_REF] Bauer | Comparingparameter choice methods for regularization of ill-posed problems[END_REF]. In this study, we compare different regularization parameter choice approaches combined with the Method of Fundamental Solutions using an experimental set of data containing monophasic action potential-like signals presumed to be ischemic ones in order to assess their effects on the reconstruction process.

Methods

The regularization approach most commonly used to solve the ECGI inverse problem is the Tikhonov regularization defined by the following objective function:

min x Ax -b 2 + λ 2 Lx 2 , ( 1
)
where A is the transfer matrix defined by MFS, b is the vector illustrating the Dirichlet and Neumann boundary conditions and x is a vector of weighting coefficients used to compute the epicardial potential in any point of the torso domain. The regularization operator L can be the identity matrix for zero-order Tikhonov or a gradient operator for first or second order regularization. The λ is the regularization parameter and . is the L2-norm. Here, L is the identity matrix.

To day, the use of the Singular Value Decomposition (SVD) of A is the best way to assess the different regularization parameter choice methods. Following [START_REF] Hansen | Rank-Deficient and Discrete Ill-posed Problems[END_REF], we decompose A as follows :

A = U ΣV T = n i=1 u i σ i v T i , (2)
where U is a m × n orthonormal matrix containing the left singular vectors of A,V is a n × n orthonormal matrix containing the right singular vectors of A and Σ is a n × n diagonal matrix with the singular values of A on its diagonal. Note that u i , v i and σ i are respectively, the columns of U, V and the singular values of A arranged in a decreasing order. The solution of the regularized problem is expressed, using the SVD, by:

x = A * b = (A T A + λ 2 I) -1 A T b = n i=1 σ 2 i σ 2 i + λ 2 u T i b σ i v i .
(3) As shown in [START_REF] Johnston | A new method for regularization parameter determination in the inverse problem of electrocardiography[END_REF], the two terms of (1) can be written as :

ρ(λ) = Ax -b 2 = n i=1 λ 4 µ 2 i (λ 2 + σ 2 i ) 2 + r ⊥ 2 (4)
and

η(λ) = x 2 = n i=1 σ 2 i µ 2 i (λ 2 + σ 2 i ) 2 , (5)
where r ⊥ 2 = Ax LSS -b 2 is the residual of the least squares solution x LSS and µ i = u T i b.

Determination of the Regularization Parameter

U-Curve

The U-Curve is a plot of the sum of the inverse of η(λ) and the inverse of the corresponding residual ρ(λ) in terms of λ on a log-log scale:

U curve(λ) = 1 ρ(λ) + 1 η(λ) (6)
The U-Curve method was first proposed by [START_REF] Krawczyk-Stado | Regularization parameter selection in discrete ill-posed problems -the use of the ucurve[END_REF]. It has been shown that U curve(λ) reaches a local minimum λ u , the optimum value of λ, in the interval δ

2/3 n , δ 2/3 1
, where δ 1 and δ n are respectively the biggest and the smallest singular values.

ADPC

ADPC is a regularization parameter choice method based on the Discrete Picard Condition (DPC) [START_REF] Hansen | Truncated singular value decomposition solutions to discrete ill-posed problems with ill-determined numerical rank[END_REF]. The idea is to look for the last index i before the DPC is no longer satisfied [START_REF] Chamorro-Servent | Improving the spatial solution of electrocardiographic imaging: A new regularization parameter choice technique for the tikhonov method[END_REF]. This means before σ i becomes smaller than |u T i b t | in a log-log scale where t is time. For the sake of simplification, log(|u T i b t |) is fitted by a polynomial p t (i, log(|u T i b t |)) of degree 5 to 7. Then, for each p t , we seek for α t = σ j such that log(σ i ) ≥ p t , for all i < j. The ADPC regularization parameter is then λ = median(α t ).

CRESO

According to the Composite REsidual and Smoothing Operator (CRESO) method [START_REF] Colli-Franzone | A mathematical procedure for solving the inverse potential problem of electrocardiography. analysis of the time-space accuracy from in vitro experimental data[END_REF], the optimal λ corresponds to the first local maximum of the derivative of the difference between the constraint term and the residual term with respect to λ 2 .

C(λ) = d d(λ 2 ) (λ 2 η(λ) -ρ(λ)) (7)
In terms of SVD, this can be written as [START_REF] Johnston | A new method for regularization parameter determination in the inverse problem of electrocardiography[END_REF]:

C(λ) = n i=1 σ 2 i µ 2 i (σ 2 i -3λ 2 ) (σ 2 i + λ 2 ) 3 (8)

GCV

The idea behind The Generalized-Cross Validation (GCV) [START_REF] Wahba | Practical approximate solutions to linear operator equations when the data are noisy[END_REF] is that the optimum of the regularization parameter provides the best prediction of a measurement as a function of the others. It provides the optimal value of λ by minimizing the function :

G(λ) = ρ(λ) [T race(I -AA * )] 2 (9)
In terms of SVD, G(λ) is expressed by :

G(λ) = n i=1 λ 4 µ 2 i (σ 2 i + λ 2 ) 2 + r ⊥ 2 m - n i=1 σ 2 i σ 2 i + λ 2 2 (10)

RGCV

In [START_REF] Lukas | Robust generalized cross-validation for choosing the regularization parameter[END_REF], the RGCV estimate is defined by the minimizer of the following function:

R(λ) = [γ + (1 -γ)ξ(λ)] G(λ), (11)
where G(λ) is given by ( 9) and ξ(λ) is defined as:

ξ(λ) = T race (AA * ) 2 = n i=1 σ 4 i (λ 2 + σ 2 i ) 2 (12)
Here, γ is called a robustness parameter, γ ∈ [0, 1].

The RGCV method is based on the average influence

1 m m i=1 Ax λ -Ax [i] λ 2 , where Ax λ -Ax [i] λ
2 is a measure of the influence of the i th data point on the regularized solution.

2.2.

Ex vivo experimental data and metrics

Experimental data were obtained using an ex-vivo pig heart perfused in Langendorff mode suspended into a human-shaped torso tank paced on the left and right ventricular surface. Epicardial ventricular electrograms were recorded using a 108-electrode sock, from which 93 were used, simultaneously with torso potentials from 128 electrodes embedded in the tank surface as it appears in Figure 1. The tank mesh contains 1234 nodes and the epicardium 649 nodes. More details about the ex-vivo experimental protocol can be found in Bear et al [START_REF] Bear | Cardiac electrical dyssynchrony is accurately detected by noninvasive electrocardiographic imaging[END_REF]. Preprocessing of the experimental data revealed the existence of a few localized sites of ischemia produced due to electrode pressure on the epicardium represented in Fig- ure 1C. This produced monophasic action potential-like signals (MAPs). These electrodes are identified when the potential is greater than a fixed threshold equal to 50% of the maximum signal magnitude in the plateau phase, 250 ms after pacing as it's illustrated in Figure 1D. This choice is based on observations of the QT interval in order to eliminate the ischemic signals. This leads us to run two sets of comparisons, with all the working electrodes (WE) and after removing the above threshold electrodes (TE). According to the ex-vivo experimental protocol, the sock doesn't cover the whole surface of the epicardium. So, a linear interpolation was applied to the ex-vivo recordings with and without thresholding to obtain respectively potential recordings (TE) and (WE) for all the mesh nodes. To assess the performance of the different methods, we use the standard metrics : the relative error (RE) and the correlation coefficient (CC).

Results

Table 1 presents the mean RE and CC of the reconstructed epicardial potentials using the different regularization parameter choice methods combined with MFS for the 3 experiences : RV, LV and BiV. Also, we compare, in this table, the results obtained using the non-thresholded signals versus those computed with the thresholded signals.

Results show that thresholding improves the RE from 0.92 to 0.80 for RV, from 0.78 to 0.72 for LV and from 0.99 to 0.72 for BiV, using GCV. CC values are also improved. Regarding the regularization parameter choice methods, we observe that GCV outperforms the other methods. Figure 2 shows a measured monophasic action potential-like signal and the corresponding thresholded one with the reconstructed version by MFS-GCV. We observe that the thresholding affects the results essentially during the plateau phase where it reduces the gap between the reconstructed and the measured amplitudes.

discussion and conclusion

In this paper, we assessed 5 methods for choosing the regularization parameter for a zero-order Tikhonov regu- Regarding the thresholding applied to the reference potential measures, results seem to be better using the thresholded epicardial potentials. Nevertheless, we can't decide on the impact of the monophasic action potential-like signals on the quality of the results unless we have experiments providing non ischemic potentials.

Figure 1 .

 1 Figure 1. A : The heart-human shaped torso tank model used for the experiments, B : The segmented pig heart covered by the sock used for potential records, C : Measured Epicardial potential map at a sample time of the plateau phase. The surrounded zones are ischemic regions, D : Measured ischemic electrograms.

Figure 2 .

 2 Figure 2. Measured(WE), thresholded(TE) and reconstructed electrograms of the RV (A), LV (B) and BiV (C) in an ischemic-like point using MFS-GCV.

Table 1 .

 1 Means of RE and CC of the reconstructed epicardial potentials using MFS combined with the different regularization parameter choice methods for thresholded data sets and non-thresholded ones.

					Simulation
			RVP		LVP		BiVP
	Method	Data set	RE	CC	RE	CC	RE	CC
	CRESO	WE TE	0.93 0.32 0.84 0.61 1.00 0.40 0.82 0.57 0.81 0.66 0.81 0.66
	GCV	WE TE	0.92 0.31 0.78 0.67 0.99 0.34 0.80 0.60 0.72 0.72 0.72 0.72
	RGCV	WE TE	0.93 0.32 0.86 0.61 1.00 0.40 0.85 0.54 0.84 0.66 0.84 0.66
	UCurve	WE TE	0.94 0.33 0.98 0.96 0.53 0.97 0.65 0.97 0.65 0.6 1.02 0.40
	ADPC	WE TE	0.92 0.31 0.82 0.62 0.98 0.38 0.82 0.56 0.78 0.67 0.78 0.67


G Fraisse
email: gilles.fraisse@univ-savoie.fr

M Lazard
email: mlazard@insic.fr

C Goupil

J Y Serrat

STUDY OF A THERMOELEMENT'S BEHAVIOUR THROUGH A MODELLING BASED ON ELECTRICAL ANALOGY

Keywords: Modelling, thermoelectric element, heat transfer, temperature-entropy diagram

This study presents a new thermoelectric element modelling based on an electrical analogy. The balance equation for a node of the analogical model is equivalent to the local energetic balance of a thermoelectric element. A particular attention is paid on taking into account all the effects Peltier, Joule and Thomson. This approach leads to a noticeable modification of the performances compared to previous estimations obtained by classical approaches where the Thomson contribution is neglected and no thermo-dependence of the thermophysical properties is assumed. This analogical modelling is appropriate for description of steady states but also for transient state and for non conventional geometries. The general behaviour of a thermoelectric leg under cooling mode is studied and the different possibilities of improving the performances are investigated. The analysis of the thermodynamical behaviour is also presented by separating the contribution of each effect.

Thermoelectric effects have been discovered in the first part of the XIX th century: Seebeck effect (1821) [START_REF] Seebeck | Ueber den magnetismus der galvenische kette[END_REF], Peltier effect (1834) [START_REF] Peltier | Nouvelles expériences sur la caloricité des courants électriques[END_REF] and Thomson effect (1851) [START_REF] Thomson | On a mechanical theory of thermo-electric currents[END_REF] [START_REF] Thomson | Account of researches in thermo-electricity[END_REF]. Although these physical phenomena are well known, they are not always correctly included in theoretical description and models [START_REF] Ioffe | Semiconductor Thermoelements and thermoelectric Cooling[END_REF]. For instance, the modeling of the Thomson effect is often neglected and, when it is not, some new issues can be observed, as it has been recently reported [START_REF] Gurevich | Theory of thermoelectric cooling in semiconductors structures[END_REF]. The exact contribution of the Thomson effect is also sometimes misleading and it is quite difficult to consider the equations because of the affectation of the sign concerning the Thomson effect. As a consequence there is a doubt on its final contribution on the heating or the cooling of the thermoelectric element.

In this paper, after recalling the basic theoretical background of thermoelectricity deriving from the Onsager's theory [START_REF] Onsager | Reciprocal Relations in Irreversible Processes I&II[END_REF][START_REF] Callen | The Application of Onsager's Reciprocal Relations to Thermoelectric, Thermomagnetic and Galvanomagnetic Effects[END_REF], we develop a method based on an electrical analogy in order to model a thermoelectric element. The Thomson effect and the thermo-dependence of the parameters are all taken into account. Transient states and non conventional geometries are also considered. The results obtained for temperature distribution, fluxes and entropy generation lead to a better understanding of the thermoelement's performances.

MODELLING OF A THERMOELECTRIC ELEMENT

2.1 Equations for a unique element N or P type.

The figure 1 shows the principal case-study of this paper. It consists into a single couple of thermoelectric elements of n-type and p-type. The complete hors of equilibrium thermodynamic of the Onsager's development is out of the scope of the present article and only the principal results will be presented, for developed description see references [START_REF] Onsager | Reciprocal Relations in Irreversible Processes I&II[END_REF][START_REF] Callen | The Application of Onsager's Reciprocal Relations to Thermoelectric, Thermomagnetic and Galvanomagnetic Effects[END_REF][START_REF] Domenicali | Irreversible Thermodynamics of Thermoelectricity[END_REF]. On the basis of this formalism, the terms of the electrical and thermal fluxes can be written with the following matrix formulation [START_REF] Vining | The Thermoelectric Process[END_REF] :

        ∇ - ⋅       =         → T E T J j E T T T Q . . . . r κ σ α σ α σ (1)
According to the linear response theory, this description only considers the electronic gas.

Consequently, the contribution of the lattice to the heat current is neglected in this approach. In order to include the lattice contribution we now consider the total thermal conductivity k instead of κ E .

Eliminating the electrical field E in the previous formulation, the heat flux vector within the thermoelectric element (n-type and p-type) is now given by equation ( 2) [START_REF] Landau | Electrodynamics of Continous Media[END_REF]:

( ) T j T k J Q ⋅ ⋅ + ∇ ⋅ - = → α (2)
This equation leads to the following expression of the variation of the heat flux

Q J → ∇ . r : ( ) [ ] T k j T J Q ∇ ⋅ - ⋅ ⋅ ∇ = ∇ → α . . r r
(3) And finally :

( ) ( ) [ ] T k j E j j T J T Q ∇ ⋅ ⋅ ∇ - - ⋅ + ∇ ⋅ ⋅ = ∇ → σ α 2 . r r r (4)
This expression (4) contains four terms which are respectively:

-the Peltier-Thomson term which account for every variation of the Seebeck coefficient whatever is the variation, isothermal junction or spatial variation due to the effect of the temperature, -the electrical power supplied, -the power dissipated by the Joule effect, -the heat generation due to non isothermal conduction.

( ) ( ) ( ) ( ) ( ) [ ] T j T T T j T T j T j T ∇ ⋅ - Π ∇ ⋅ =       ∇ ⋅ Π ⋅ - Π ∇ ⋅ ⋅ =       Π ∇ ⋅ ⋅ = ∇ ⋅ ⋅ r r r r r r α α 2 1 1 (5)
then we get the classical Thomson development [START_REF] Chakraborty | Thermodynamic formulation of temperature-entropy diagram for the transient operation of a pulsed thermoelectric cooler[END_REF] writing, ( ) ( )

T dT d ∇ ⋅ Π = Π ∇ r r (6)
Then, one obtains:

( ) ( ) T j j T ∇ ⋅ ⋅ = ∇ ⋅ ⋅ r r τ α (7)
The expression of the heat flux given by equation ( 4) is then:

( ) ( ) [ ] T k j E j T j J T Q ∇ ⋅ ⋅ ∇ - - ⋅ + ∇ ⋅ ⋅ = ∇ → σ τ 2 . r r r (8)
Moreover, if the total flux of energy W J → which includes heat, work and electrochemical flux is considered, it could be written [START_REF] Huang | System dynamic model and temperature control of a thermoelectric cooler[END_REF]:

j e q J W ⋅ + = → µ r (9)
The conservation of energy and of the mass leads to 0 . = ∇ W r and 0 . = ∇ j r and then it comes:

→ → → → =       ⋅ ∇ - = ∇ j E j e J Q . . . µ r (10)
The local balance equation can then be considered [START_REF] Chakraborty | Thermodynamic modelling of a solid state thermoelectric cooling device : Temperature-entropy analysis[END_REF]:

( ) [ ] ( ) 0 . 2 = ∇ ⋅ ⋅ - + ∇ ⋅ ⋅ ∇ = ⋅ - ∇ → T j j T k j E J T Q r r r r τ σ (11)
All the following quantities are assumed to be constant in the elementary volume cell:

-the section of the element (but can change through the total length) -the thermal conductivity (which is temperature dependent) -the current density (which depends on the section) -the three thermoelectric parameters : Peltier, Seebeck and Thomson coefficients.

Nevertheless, these values can vary along the thermoelectric leg because the thermophysical parameters (thermoelectric parameters and conductivity) depend on the temperature whereas the current density changes if the section of the elementary volume changes. Assuming one dimensional and steady state conditions, the balance equation of the elementary volume cell becomes:

dx dT j j T j dx dT k dx d ⋅ ⋅ + =       ⋅ ⋅ + ⋅ - α σ α ² (12)
The parameters α and j are algebraically defined and their sign depend of the element's nature and of the electrical current orientation (see figure 1).

Under all these assumptions, we get the following equations:

-for a N-leg :

0 ) ( ² ) ( 2 2 = ⋅ ⋅ - + ⋅ dx x dT j j dx x T d k τ σ (13)
-for a P-leg :

0 ) ( ² ) ( 2 2 = ⋅ ⋅ + + ⋅ dx x dT j j dx x T d k τ σ (14)
In the two legs, the last term is negative because the temperature gradient is positive in the Nleg (and respectively negative in the P-leg). As a consequence, the influence of the Thomson coefficient is the same in the two legs: the Thomson effect contributes to the cooling of the elements between x=-L and x=+L. It is then adequate for thermoelectric modules used for cooling applications. As a general rule, the Thomson effect may lead to a warming up or cooling of the element depending on the sign of the third term [START_REF] Gurevich | Theory of thermoelectric cooling in semiconductors structures[END_REF].

If the transient state is considered, the local balance equation in the N-leg is [START_REF] Huang | System dynamic model and temperature control of a thermoelectric cooler[END_REF][START_REF] Chakraborty | Thermodynamic modelling of a solid state thermoelectric cooling device : Temperature-entropy analysis[END_REF]:

dx ) t , x ( dT j ² j dx ) t , x ( T d k dt ) t , x ( dT Cp ⋅ ⋅ - + ⋅ = ⋅ ⋅ τ σ ρ 2 2 (15)
The boundary conditions for the thermal problem are imposed temperatures:

C T ) t , x ( T = = 0 and H T ) t , L x ( T = = (16)
From the temperature distribution, the total heat flux going through the N-leg is:

      ⋅ - ⋅ ⋅ ⋅ = dx t x dT k t x T j x A t x Q ) , ( ) , ( ) ( ) , ( α & (17)
When the section varies for the elementary volume, the balance equation becomes [START_REF] Yang | Transient cooling of thermoelectric coolers and its applications for microdevices[END_REF]:

dx t x dT j j dx t x dT x A k dx d x A dt t x dT Cp ) , ( ² ) , ( ) ( ) ( 1 ) , ( ⋅ ⋅ - +       ⋅ ⋅ ⋅ = ⋅ ⋅ τ σ ρ (18)
Since the size of the elementary cell is small we can neglect the contribution of the term

dx t x dT dx x dA x A ) , ( ) ( ) ( 1 ⋅ ⋅
. Then using a general analogical model approach, we replicate the thermoelectric elementary cell along the complete leg. The same method is used to take into account the effect of the temperature on the different thermoelectric parameters ρ . Even if these parameters are supposed to be constant in each cell, their variation along the whole leg can be correctly taken into account.

It should be noticed here that the Thomson effect is often neglected in such descriptions [START_REF] Yang | Transient cooling of thermoelectric coolers and its applications for microdevices[END_REF][START_REF] Snyder | Supercooling of Peltier cooler using a current pulse[END_REF]. We show here that this is an error since its role is not negligible at all [START_REF] Huang | The influence of the Thomson effect on the performance of a thermoelectric cooler[END_REF][START_REF] Pramanick | Constructal design of a thermoelectric device[END_REF]. It is even possible to improve the performances of a thermoelectric element using cross-contributions of the merit figure Z and the Thomson effect [START_REF] Gurevich | Theory of thermoelectric cooling in semiconductors structures[END_REF].

Analogical modeling of a thermoelectric element

The electrical analogy allows to easily describe complex phenomena such as the thermal dependence of the thermoelectric parameters, the transient state, the variable section of the thermoelement and other linear processes. The electrical analogy is schematically represented in the figure 2 for cells with a thickness equal to x ∆ .

The thermophysical parameters are temperature dependent and the section

) x ( A can also vary.
As a consequence, the parameters of the analogical model, i.e. the thermal capacitances and resistances, are given by the following expressions:

x x A T Cp T C n ∆ ⋅ ⋅ ⋅ = ) ( ) ( ) ( ρ (18) ) ( ) ( x A T k x R n ⋅ ∆ = (19)
with n the number of the considered node.

The Joule and Thomson effects are taken into account through the heat flux n Φ injected in each node of the temperature. For a N-leg the expression is given by:

2 1 1 2 - + - ⋅ ⋅ - ⋅ = Φ n n e n T T I I R τ (20) where ) ( ) ( x A x T R e e ∆ ⋅ = ρ
is the electrical resistance of slice whose thickness is equal to x ∆ .

It is then possible to determine the total heat flux n Q & within the thermoelement:

x T T x A T k T I Q n n n n ∆ ⋅ - ⋅ ⋅ - ⋅ ⋅ = - + 2 ) ( ) ( 1 1 α & (21)

Other modeling approaches

A very simple model for a thermoelement can be directly derived from the energy global balance, assuming that the joule production is equally shared at the hot and the cold side. For large section or material, the validity of this is questionable but in the present, since each cell is consider to be isothermal, this assumption becomes totally valid. We consider here a thermoelectric leg with a positive Seebeck coefficient and an electrical current flowing along the increasing x direction.

At the cold side ( 0 = x ) and at the hot side ( L x = ), the expressions of the heat fluxes are then,

T I I R T K T I Q C C ∆ ⋅ ⋅ ⋅ + ⋅ ⋅ - ∆ ⋅ - ⋅ ⋅ = τ α 2 1 2 1 2 & (22) T I I R T K T I Q H H ∆ ⋅ ⋅ ⋅ - ⋅ ⋅ + ∆ ⋅ - ⋅ ⋅ = τ α 2 1 2 1 2 & ( 23
)
where K is the thermal conductance between the two faces, R the electrical resistance of the element and

C H T T T - = ∆ .
In the previous expressions of the heat fluxes, the Thomson effect has been taken into account, which is rarely the case for such studies [START_REF] Snyder | Supercooling of Peltier cooler using a current pulse[END_REF][START_REF] Min | Cooling performance of integrated thermoelectric microcooler[END_REF][START_REF] Nuwayhid | On entropy generation in thermoelectric devices[END_REF][START_REF] Riffat | Improving the coefficient of performance of thermoelectric cooling systems : a review[END_REF][START_REF] Chen | Performance optimization of a two-stage semiconductor thermoelectric-generator[END_REF][START_REF] Yang | Transient cooling of thermoelectric coolers and its applications for microdevices[END_REF].

If the parameters and the section are constants all over the leg then it is possible to determine the analytical solution for steady state cases, taking into account the contribution of the Thomson effect [START_REF] Chakraborty | Thermodynamic modelling of a solid state thermoelectric cooling device : Temperature-entropy analysis[END_REF]. Heat flux and the temperature solutions are then:

      - -             - ⋅       ⋅ ⋅ + - + ⋅ ⋅ - ⋅ ⋅ = L x Q Q L x Q Q Q Q I k Q I k x T I x Q F T F T F T e F exp 1 exp ) ( ) ( τ ρ σ τ α & (24) ( ) ( ) x b c L b x b L b c T T T x T C H C + - ⋅ - - ⋅ - ⋅       - - + = 1 exp 1 exp ) ( (25)
where

k j b τ - = σ ⋅ - = k j c ² L T A k Q F ∆ ⋅ ⋅ = T I Q T ∆ ⋅ ⋅ = τ
The electrical output power is:

C H Q Q P & & - = (26)
The analytical and simplified solutions give:

( )

T I I R P ∆ ⋅ ⋅ - + ⋅ = τ α 2
(the parameters are assumed to be positive) (27) The temperature dependence of the coefficients is usually not considered in the literature, and only averages values between hot and cold side are taken into account [START_REF] Chakraborty | Thermodynamic formulation of temperature-entropy diagram for the transient operation of a pulsed thermoelectric cooler[END_REF]. But the temperature dependence is far from being a small effect when considering the Temperature-Entropy diagram [START_REF] Chakraborty | Thermodynamic modelling of a solid state thermoelectric cooling device : Temperature-entropy analysis[END_REF].

Evaluation of the performance

In order to qualify the performances of a thermoelectric module for cooling applications, we need to define two terms:

-the performance coefficient

C H C Q Q Q COP & & & - = (28)
-the power obtained at the cold side (i.e. for 0 = x

) C Q & (29)
When dealing with performance optimization, it is usually not obvious to find a compromise between the values of COP and C Q & . This can be achieved in modelling by varying the parameters values. For instance, the length of the leg is optimal when the thermal gradient is equal to zero for [START_REF] Xuan | Optimization of two-stage thermoelectric coolers with two design configurations[END_REF]. The introduction of the effect of the Thomson coefficient on the performances can be found in the reference [START_REF] Huang | The influence of the Thomson effect on the performance of a thermoelectric cooler[END_REF], and the optimization of the geometry is achieved in the references [START_REF] Min | Cooling performance of integrated thermoelectric microcooler[END_REF][START_REF] Xuan | Optimization of two-stage thermoelectric coolers with two design configurations[END_REF]. Using transient mode, the over-cooling has also been studied thanks to pulsed intensity and duration [START_REF] Chakraborty | Thermodynamic formulation of temperature-entropy diagram for the transient operation of a pulsed thermoelectric cooler[END_REF][START_REF] Snyder | Supercooling of Peltier cooler using a current pulse[END_REF][START_REF] Yang | Transient cooling of thermoelectric coolers and its applications for microdevices[END_REF].

L x = because H Q & is then maximum
From a thermodynamical point of view, the behaviour of a thermoelectric element can be described using a flux-force approach [START_REF] Chakraborty | Thermodynamic formulation of temperature-entropy diagram for the transient operation of a pulsed thermoelectric cooler[END_REF][START_REF] Chakraborty | Thermodynamic modelling of a solid state thermoelectric cooling device : Temperature-entropy analysis[END_REF][START_REF] Nuwayhid | On entropy generation in thermoelectric devices[END_REF][START_REF] Xuan | Optimization of two-stage thermoelectric coolers with two design configurations[END_REF].This thermodynamical analysis give insight into the root causes of the entropy production. Then, an optimization of the working cycle can be considered using the Temperature-Entropy diagram (T-S). The two main root causes are well known since they are due to the internal Joule effect and, in a less contribution, to the non isothermal heat conduction. In the T-S diagram the COP is directly given by the surfaces of the diagram, which are currently symmetrical, and consider constant parameters.

According to the previous expressions of the fluxes, we can easily get the expression of the entropy flux density S J [START_REF] Xuan | Optimization of two-stage thermoelectric coolers with two design configurations[END_REF] :

( ) j T T k J S ⋅ + ∇ ⋅ - = α (30)
In the N-leg, this expression becomes:

) ( ) ( ) ( ) ( ) ( ) ( x T x A x Q j dx x dT x T k x J S ⋅ = ⋅ + ⋅ - = & α (31)
Assuming constant coefficients and purely adiabatic conditions, the analytical solution

) x ( J S
can easily be determined from the expression

) (x Q & [14].
For the steady state case and for adiabatic conditions, the local creation of entropy is:

( )       ∇ ⋅ ∇ ⋅ - ⋅ = T T k T ² j gen S 1 σ & (32)
For the whole system, the total production of entropy is then:

( ) ( ) C C S H H S C C H H A J A J T Q T Q gen S ⋅ - ⋅ = - = & & & (33) with C S S C ) J ( ) x ( J and A ) x ( A , x = = = 0 H S S H ) J ( ) x ( J and A ) x ( A , L x = = =
From the analytical expression of Q(x) (in the steady-state case and constants coefficients), we can now derive total entropy production as follow :

( ) ( )       ⋅ + - ⋅ ⋅ - ⋅ - ∆ ⋅ ⋅ +         - ⋅ ⋅ ⋅ = H C H C T K I exp T K I exp I R T I T T I R K gen S τ τ τ τ 1 1 1 1 2 & (34)
The Thomson effect is reversible and its contribution to the total entropy production is directly due to the temperature gradient within the thermoelectric leg. Taking the Thomson effect into account in the expressions of C Q & and H Q & , we get :

( )

        - ⋅ ∆ ⋅ -         + ⋅ ∆ ⋅ ⋅ - ⋅ ⋅ = C H C H T T T K T T T I I R gen S 1 1 1 1 2 1 2 τ & (35)
Next, the local production of entropy for transient state and temperature dependent coefficients can also be evaluated thanks to the analogical scheme, ( ) ( )

n n n S n n S n A x A J A J gen S ⋅ ∆ ⋅ ⋅ - ⋅ = - - + + 2 1 1 1 1 & (36)
The optimal configuration obtained by the minimization of the produced entropy [START_REF] Nuwayhid | On entropy generation in thermoelectric devices[END_REF]. The equivalence between the maximization of the electrical production and the minimization of the produced entropy is presented in [START_REF] Bejan | Advanced Engineering Thermodynamics[END_REF]. But it is usually preferred to maximize the electrical production because the entropy minimization needs precautions [START_REF] Nuwayhid | On entropy generation in thermoelectric devices[END_REF]. Moreover, the maximization of the electrical production and the minimization of the production of entropy are not equivalent since the maximal operating point for electrical production can lead to large production of entropy due to non optimized heat transfer. When considering cooling applications, the generated entropy should be compared with the optimization of the COP and

C Q & .

STUDY OF THE ELEMENT'S BEHAVIOUR FOR A COOLING USE: POSSIBLE WAYS TO PERFORMANCE IMPROVEMENT

In this section, all the thermoelectric parameters will be assumed to be positive. Using the analogical approach we take into account the thermal dependence of the parameters for a N-leg.

Thomson effect contribution

The result of the evaluation of the COP and C Q & either with the analytical or simplified model are plotted in the figure 3 as functions of the electrical current intensity. The parameters values of the model are summarized in table 1. One can notice that the introduction of the Thomson coefficient contribution modifies the COP value from 18%, if compared to the analogical solution which takes into account the temperature dependence and consequently the Thomson contribution. We see that the inclusion of the Thomson coefficient into the simplified model can be sufficient to obtain a very good estimation of the COP value, which appears to be close to those obtained with the analytical solution with constants parameters. We see that the introduction of the temperature dependence of the parameters slightly reduces the maximal value by 3.5%.

We also confirm that the best cooling performances are obtained when the Thomson coefficient exhibits large values. This phenomenon is observed for both the COP and the cold production

Temperature influence

Up to now we have considered analogical and analytical solutions compared to the constants coefficients case. We see that the results obtained for the temperature field

C H Q Q & & -
becomes larger with temperature dependence of the coefficients. As far as the temperature distribution is concerned, the differences are very small. These results have been obtained for a small temperature difference between the cold and the hot side. But obviously, a larger temperature difference between the cold and the hot sides will lead to larger difference between the analogical and analytical results.

In the figure 6, the evolutions of the parameters are plotted as functions of the temperature.

Since the temperature difference is small ( C T °= ∆ 30 ), the observed variations are almost linear, and the larger difference compared to the mean value is 8% for the electrical resistivity.

Complete contribution

The

Variable section influence

The figure 11 shows the evolution of the COP, of C Q & , and of gen S

for various conical geometries of the leg. The section at the hot side is A H and A=1.4 10 -6 m² (constant section as indicated in table 1). The volume and the length of the conical leg are constant (1.96 10 -9 m 3 and L=1.4 10 -3 m). When the ratio A H / A is equal to 1, the section is constant. The model is based on the electrical analogy with thermodependent thermoelectric coefficients. For a constant section leg, the COP reaches a maximum of 0.89 at 2A. This geometrical configuration leads to a minimum of the entropy production. If we now consider an increase of the section at the hot side (i.e. a reduction of the section at the cold side), the COP decreases to 0.72 but the heat flux C Q slightly increases. Nevertheless, a too small section at the ends of the leg will limit the exchange between the thermoelement and the exchangers leading to poor performances of the overall system.

As expected the entropy production is maximal when the section is minimal, it is due to the dissipation caused by the Joule effect. This is the major contribution to the reduction of the performances, so we now consider a possible extraction of the entropy by a thermal connection of the middle of the leg with a third thermal source, acting as a trash to evacuate a fraction of the Joule production. This cooling can be obtained for instance by blowing air on the element or using micro-caloducs. The total efficiency of the system including this third thermal source will of course decrease, but the local COP of the element will be enhanced. In the figure 12, the COP is plotted as a function of the percentage of the total Joule effect extracted from the leg for a current equal to 2A. This value of the COP is compared to the value of the COP Carnot . Due to thermal conduction entropy, the COP never reaches the Carnot value.

Over-cooling and pulsed current

The effect of a pulsed current has been studied by several authors [START_REF] Chakraborty | Thermodynamic formulation of temperature-entropy diagram for the transient operation of a pulsed thermoelectric cooler[END_REF][START_REF] Snyder | Supercooling of Peltier cooler using a current pulse[END_REF][START_REF] Yang | Transient cooling of thermoelectric coolers and its applications for microdevices[END_REF] since this correspond to a sudden strong increase of the Peltier heat pumping. The cooling is rapidly obtained on the cold side when the pulsed current is applied because the Peltier effect acts instantaneously, while the Joule heat diffuses slowly due to thermal inertia. It is then possible to obtain an over-cooling compared to the steady-state case. Unfortunately, the Joule heat finally diffuses and a large over-heating occurs. The global efficiency of the operation is clearly not satisfactory. We present in the figure 13 the temperature T1 measured very close to the cold side (boundary condition corresponding to heat flux equal to zero) and T20 close to the hot side (boundary condition corresponding to imposed temperature equal to 308K). The steady state current is 0.96A and the pulsed value is 2.1 A, during 2 seconds (t=100s to t=102s).

The figure 14 underlines the very local and brief nature of the cooling effect. One can see that it only occurs for 10% of the total length of the leg and for a very short duration. According to this observation the current pulse operation is advantageous only for short time over-cooling. The exact duration of the over cooling is given by the thermal inertia of the thermoelectric leg which is here close to 6 seconds [START_REF] Yang | Transient cooling of thermoelectric coolers and its applications for microdevices[END_REF]. Such a device has been proposed in [START_REF] Chakraborty | Thermodynamic modelling of a solid state thermoelectric cooling device : Temperature-entropy analysis[END_REF] with high intensity operating point. In order to avoid any diffusion of heat into the cold zone (cold source), it is proposed to thermally disconnect the thermoelement and the cold zone just after the overcooling in order to let the extra Joule effect diffuse into the hot source. This seems to be unlikely since the well known advantage of the Peltier module is this absence of any moving part, the thermal disconnection process would reduce to nothing this advantage. On the other hand the use of a third thermal source, previously proposed, could be a solution for the extraction of this extra Joule heat, leading to a possible increase of the maximal ∆T between hot and cold source, actually close to 70K for the best Peltier refrigerating systems.

CONCLUSION

We have presented an electrical analogy model of thermoelectric element. It is shown that this model is able to take into account complex phenomena and various experimental conditions.

This compact model can be easily inserted in a thermoelectric device or directly coupled with heat exchangers. Lateral heat losses (convective and radiative exchanges) can easily be added to the elementary cell in order to treat more complex configurations. The behaviour of a thermoelectric element has been compared using various models and some ways to improve the

C n-1 C n C n+1 T n T n-1 T n+1 R n-1 R n R n+1 Φ n Φ n-1 Φ n+1 0 +L x Q C Q H n.∆x T n T n-1 T n+1 ∆x ∆x

  usual Thomson contribution (effect of the thermal gradient) and the Peltier contribution (effect of the spatial gradient

CQ

  & as it is shown on the figure 4 for current intensities from 1A to 9A. An increase of 200% of the Thomson coefficient τ leads to an improvement of the COP and of C Q & (52% for the COP and 32% for C Q & ).

  these two models are the same. On the contrary, when the coefficients are temperature dependent, which is only possible for the analogical model, then the heat flux repartition is slightly changed (figure5) reducing the COP by a small amount. More precisely, C Q & gets smaller whereas the difference

  figures 7 and 8 show the contribution of all the previous effects on the distribution of the heat flux and the temperature. When only considering the conduction contribution (case 1), we observe an obvious large heat flux. Next we introduce the Peltier contribution (case 2) of symmetrical repartition of the Joule contribution. This lead to lowering the COP. The influence of the Thomson effect is inverse to the contribution of the Joule effect since it tends to cool the thermoelectric element. The Thomson contribution has a symmetrical repartition between the two sides and the variation is about the contribution of each previous term in the T-S diagram. The total production of entropy in the whole element is proportional to the length of the legs since the section is assumed to be constant. No entropy production can be evidenced by the Peltier effect (1) since the total Peltier heat flux average to zero. The entropy produced by pure thermal conduction (2) is lower than those produced by the Joule effect (3). When introducing the Thomson contribution, the entropy production is slightly reduced. Introducing the temperature dependence of the parameters leads to an increase of the entropy production (4 and 5). The figure 10 shows the cycling transformations in the T-S diagram, following the current going through the N-leg: the ratio of the area delimited by 3-4-10-9 over the area delimited by 1-2-8-9-3-4. the ratio of the area delimited by 4-6-7-10 over the area delimited by 1-5-7-10.

  performances have been proposed (influence of the Thomson coefficient, of the geometry, of the current pulse). The role of each phenomenon has been investigated and evaluated by considering the temperature and the heat fluxes within the thermoelectric element. The results obtained have proved the assumption of symmetrical repartition of the Joule effect for the evaluation of H Q and C Q currently used in the simplified approach. The model has been improved by the addition of the Thomson contribution and the temperature dependence of all the parameters. Using a thermodynamical analysis, we have precise the different contribution to entropy and clarify the important role of the Joule effect on the performances of the thermoelectric element. The possible extraction of heat from a fraction of the thermoelectric leg gives promising result for better local COP or larger maximal ∆T if connected with pulse mode current.

Figure 1 :Figure 2 :Figure 3 :Figure 4 :Figure 5 :Figure 6 :Figure 7 :Figure 8 :Figure 9 :Figure 10 :Figure 11 :Figure 12 :Figure 13 :Figure 14 :Figure 1 :

 12345678910111213141 Figure 1 : Configuration studied (two adiabatic thermoelectric elements) with α the Seebeck coefficient and j the electrical current density Figure 2 : Analogical scheme of the thermoelectric phenomena with the thermal capacitances C i and thermal resistances R i Figure 3 : Performance of the thermoelectric element as a function of the intensity for several models (analo for the analogical model, analy for the analytical model, simpl for the simple model, and Thomson when the Thomson effect is taken into account) Figure 4 : COP and C Q & evolution for different intensities (from 1A up to 9A) Figure 5 : Heat flux and temperature in the thermoelectric element: analogical model versus analytical model Figure 6 : Variation of the different thermophysical parameters as functions of the temperature Figure 7 : Influence of the different effects (Seebeck, Joule, Thomson) on the heat flux repartition Figure 8 : Influence of the different effects (Seebeck, Joule, Thomson) on the temperature repartition Figure 9 : Representation of the different effects in the Temperature Entropy diagram Figure 10 : Representation of the T-S diagram in the N-element Figure 11 : Evaluation of the performance (COP , Qc and Sgen) for conical geometries Figure 12 : Influence of the Joule effect evacuation at the middle of the element Figure 13 : Effect of the pulsed intensity on the temperatures as function of time Figure 14 : Effect of the pulsed intensity on the temperatures as function of space

Figure 2 :Figure 3 :

 23 Figure 2 : Analogical scheme of the thermoelectric phenomena with the thermal capacitances C i and thermal resistances R i

Figure 5 :

 5 Figure 5 : Heat flux and temperature in the thermoelectric element: analogical model versus analytical model

Figure 5 :Figure 6 :αFigure 7 :Figure 8 :Figure 9 :Figure 10 :Figure 11 :

 567891011 Figure 5 : Heat flux and temperature in the thermoelectric element: analogical model versus analytical model

Figure 12 :Figure 13 :Figure 14 :

 121314 Figure 12 : Influence of the Joule effect evacuation at the middle of the element

Table 1 :

 1 Data of the thermoelectric element used for the simulations

& & &

Acknowledgments

This study is financed by CNRS in the framework of " Programme Interdisciplinaire Energie du CNRS "


S Boroomandi Barati

J C Pinoli

S Valette

Y Gavet

Modeling and simulation of ellipsoidal droplets growing on patterned substrates during dropwise condensation

Introduction

Aim: presenting a mathematical model for simulating growth of ellipsoidal droplets on patterned substrates.

Application: studying how to control the size of water droplets formed on the vitreous substrates like glasses, optical lens and car light shields.

Dropwise condensation

The process of dropwise condensation consists of five main steps: nucleation of initial droplets growth rate due to adsorption growth rate due to coalescence nucleation of new small droplets sliding very big droplets from the surface.

Flat v .s textured substrates

The most important difference between droplets on flat and textured substrates is their geometry: For calculating the intersection between two ellipses in two dimension, one has to solve the system of equations of two ellipses, considering the point of (0,0) in the center of first ellipse. So the equation of the first ellipse will reduce to equation [START_REF] Boroomandi Barati | Investigation spatial distribution of droplets and the percentage of surface coverage during dropwise condensation[END_REF].

Mathematical modeling

Y X X Z a b a (X0,Y0) (X0,Z0) c 1 a 2 (X -X 0 ) 2 + 1 b 2 (Y -Y 0 ) 2 + 1 c 2 (Z -Z 0 ) 2 = 1
A 1 X 2 + Y 2 = R 1 , (1) A 2 (X -X 0 ) 2 + (Y -Y 0 ) 2 = R 2 , (2)
A 1 = b 2 1 a 2 1 , R 1 = b 2 1 , A 2 = b 2 2 a 2 2 , R 2 = b 2 2 .
Mean errors of the model

Conclusions

we presented a mathematical model for simulating coalescence of ellipsoidal droplets on textured substrates

The presented model is applied to 6 different pillared surfaces and its mean error is calculated on all the surfaces of about 10% for droplets density and 2% for droplets size.

The main source of error is recognized as the similarity between the droplets appearance and pillars that makes it difficult to identify the exact number of droplets.

Figure :

 : Figure: Formation of water droplets (because of dropwise condensation) on car light shields reduces light reflection in foggy days.

Figure

  Figure: (a) Spherical droplets on the flat, (b) elliptical droplets on the sinusoidal substrates.

Figure :

 : Figure:Hemi-ellipsoidal droplets in two planes (X -Y ) and (X -Z ) and their corresponding equation.

Acknowledgements

This work was funded by LABEX MANUTECH-SISE (ANR-10-LABX-0075, within the program "Investissements dAvenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).

Contact information

solmaz.boroomandi@emse.fr 0033-477429333


Brice Nédelec

Pascal Molli

Achour Mostefaoui

Achour Mostéfaoui

Causal Broadcast: How to Forget?

Keywords: Causal broadcast, complexity trade-off, large and dynamic systems

come

INTRODUCTION

Causal broadcast constitutes the core communication primitive of many distributed systems [START_REF] Hadzilacos | A modular approach to fault-tolerant broadcasts and related problems[END_REF]. Applications such as distributed social networks [START_REF] Borthakur | Petabyte scale databases and storage systems at facebook[END_REF], distributed collaborative software [START_REF] Heinrich | Exploiting single-user web applications for shared editing: a generic transformation approach[END_REF][START_REF] Nédelec | Crate: Writing stories together with our browsers[END_REF], or distributed data stores [START_REF] Bailis | Bolt-on causal consistency[END_REF][START_REF] Bravo | Saturn: A distributed metadata service for causal consistency[END_REF][START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF][START_REF] Lloyd | Don't settle for eventual: Scalable causal consistency for wide-area storage with cops[END_REF][START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF] use causal broadcast to ensure consistency criteria. Causal broadcast ensures reliable receipt of broadcast messages, exactly-once delivery, and causal delivery following Lamport's happen before relationship [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF]. When Alice comments on Bob's picture, nobody sees Alice's comment without Bob's picture, and nobody sees multiple occurrences of Alice's comment or Bob's picture.

Vector clock-based approaches [START_REF] Malkhi | Concise version vectors in winfs[END_REF][START_REF] Mukund | Optimized or-sets without ordering constraints[END_REF][START_REF] Nédelec | Breaking the Scalability Barrier of Causal Broadcast for Large and Dynamic Systems[END_REF] need to keep all their control information forever. They cannot forget any control information. The consumed memory monotonically increases with the number of processes that ever broadcast a message O(N ). They become unpractical in large and dynamic system comprising from hundreds to millions of processes joining, leaving, self-reconfiguring, or crashing at any time.

©Brice Nédelec, Pascal Molli and Achour Mostéfaoui In this paper, we propose a novel implementation of causal broadcast that forgets all and only obsolete control information. A process p that has i incoming links receives each message i times. A message m is active for p between its first and last reception by p. Process p keeps control information about all its active messages. As soon as a message becomes inactive, the process can forget all control information related to it. Consequently, processes do no store any permanent control information about messages. When no message is active, no control information is stored in the system. Our contribution is threefold:

• We define the notion of link memory as a mean for each process to forbid multiple delivery. Link memory allows each process to identify processes from which it will receive a copy of an already delivered message. This allows each process to safely remove obsolete control information about broadcast messages that will never be received again. We prove that using causal delivery, each process can build such knowledge even in dynamic systems where processes may join, leave, self-reconfigure, or crash at any time.

• We propose an implementation of causal broadcast that uses the notion of link memory, where each process manages a local data the size of which is O(i • A) where i is the number of incoming links and A is the number of active messages. Moreover, the only control information piggybacked on messages is a scalar Lamport clock.

• We evaluate our implementation using large scale simulations. The experiments highlight the space consumed and the traffic generated by our protocol in dynamic systems with varying latency. The results confirm that the proposed approach scales with system settings and use.

The rest of this paper is organized as follows. Section 2 describes the model, highlights the issue, introduces the principle solving the issue, provides an implementation solving the issue along with its complexity analysis. Section 3 shows the experiments. Section 4 reviews related work. We conclude and discuss about perspectives in Section 5.

OPODIS'18 draft

PROPOSAL

In this section, we present a causal broadcast protocol providing a novel trade-off between speed, memory, and traffic. Among others, it safely removes obsolete control information about broadcast messages. Its memory consumption increases and decreases over receipts. The key ideas are:

(1) Every process broadcasts or forwards a message once, hence every link carries a message once. A process expects to receive as many copies of a message as its number of links. Once a process received all expected copies, it can forget about this broadcast message, i.e., it can safely remove the control information associated to this broadcast message.

(2) Adding links between pair of processes adds uncertainty.

The receiver cannot state any longer when it should expect a message from a link. (3) By exploiting causal order, processes remove this uncertainty. Causal order allows processes to remove batches of obsolete information while reasoning about temporarily buffered broadcast messages.

Model

A distributed system comprises a set of processes that can communicate with each other using messages. Processes may not have the knowledge of all processes in the system. Instead, processes build and maintain overlay networks: each process updates a local partial view of logical communication links, i.e., a set of processes to communicate with. The partial view is usually much smaller than the actual system size. We use the terms of overlay networks, and distributed systems interchangeably. Causal broadcast ensures properties similar to those of reliable broadcast. Each process may receive each broadcast message multiple times but delivers it once. In this paper, we tackle the issue of implementing these properties.

Definition 3 (Uniform reliable broadcast). When a process A broadcasts a message to all processes of its system b A (m), each correct process B eventually receives it and delivers it d B (m).

Uniform reliable broadcast guarantees 3 properties: [START_REF] Saleh | Garbage collecting the internet: A survey of distributed garbage collection[END_REF] Validity: If a correct process broadcasts a message, then it eventually delivers it. (2) Uniform Agreement: If a process -correct or notdelivers a message, then all correct processes eventually deliver it.

(3) Uniform Integrity: A process delivers a message at most once, and only if it was previously broadcast.

In static systems, implementing these properties only requires a local structure the size of which grows and shrinks over receipts [START_REF] Raynal | Distributed algorithms for messagepassing systems[END_REF]. Every process knows the number of copies of each delivered message it should expect. When this number drops down to 0, the process safely removes the control information associated to the delivered messages. This forbids multiple delivery for the process will never receive -hence deliver -this message again.

However, in dynamic systems where processes join, leave, or self-reconfigure their out-view at any time, the removal of a link may impair the consistency of the number of expected messages. Either processes cannot safely garbage collect obsolete control information, or processes suffer from multiple delivery.

In this paper, we solve this issue by exploiting causal broadcast's ability to ensure a specific order on message delivery. To characterize the order among events such as send, or receive, we define time in a logical sense using Lamports definition.

Definition 4 (Happens-before [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF]). The happens-before relationship defines a strict partial order of events. The happensbefore relationship → is transitive (e 1 → e 2 ∧ e 2 → e 3 =⇒ e 1 → e 3 ), irreflexive (e 1 → e 1 ), and antisymmetric (e 1 → e 2 =⇒ e 2 → e 1 ). The sending of a message always precedes its receipt s AB (m) → r BA (m). Two messages are concurrent if none happens before the other (r

A (m 1 ) → s A (m 2 ) ∧ r A (m 2 ) → s A (m 1 )).
Definition 5 (Causal order). The delivery order of messages follows the happen before relationships of the corresponding broadcasts.

d A (m) → b A (m ) =⇒ d B (m) → d B (m )
Definition 6 (Causal broadcast). Causal broadcast is a uniform reliable broadcast ensuring causal order.

Link memory

We define link memory as a mean for processes to forbid multiple delivery while safely removing obsolete control information. Processes attach control information about expected messages to each link of their respective in-view. it will receive from this link; and forgets among its delivered messages those that it will never receive from this link. remember BA (m) ≡ d B (m) ∧ ¬r BA (m) Theorem 1 (Link memory forbids multiple delivery). A process that delivers only messages it does not remember using link memory delivers each broadcast message exactly once.

Proof. We must show that, for any message m, its receipt cannot lead to its delivery if a copy of m has already been delivered before: Assuming that each link carries each message once, Process B eventually receives a copy of m from link (A, B): remember BA (m) → r BA (m). Since remembering a message forbids its delivery, this cannot lead to another delivery of m: m, r BA (m) → d B (m). Finally, since every process delivers, hence forwards each message once, each link carries each messages once.

m, d B (m) → r BA (m) ∧ r BA (m) → d B (m).
Algorithm 1 shows a set of instructions that implements causal broadcast for static systems. It uses reliable FIFO links to ensure causal order [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF], and implements link memory to forbid multiple delivery. Every process maintains a local structure the size of which increases and decreases over receipts. The first receipt of a broadcast message from a link tags the other links (see Line 15). The receipt on other links of this broadcast message removes the corresponding tag (see Line 16). Figure 1 depicts its functioning in a system comprising 3 processes. In Figure 1a, Process B broadcasts b. It awaits a copy of b from the only link in its in-view. In Figure 1b, Process A receives b. It delivers it, for no link in Algorithm 1: Causal broadcast for static systems. In Figure 2d, Process C receives a again. However, it did not keep control information about this message. It mistakes it for a first receipt. It delivers and forwards a. Not only Process C suffers multiple delivery but this has cascading effects over the whole system. The rest of this section describes how causal broadcast can exploit causal order to initialize link memory, an implementation of such broadcast, and its complexity analysis.

1 Qo // Out-view 2 Qi // In-view 3 E ← ∅ // Map of expected messages Q i : M * 4 DISSEMINATION: 5 function C-broadcast(m) 6 receive(m, ) 7 upon receive(m, l) 8 if ¬received(m, l) then 9 foreach q ∈ Qo do sendTo(q, m) 10 C-deliver(m) 11 function received(m, l) 12 rcvd ← ∃q ∈ E with m ∈ E[q] 13 if ¬rcvd then 14 foreach q ∈ Qi do 15 E[q] ← E[q] ∪ m 16 E[l] ← E[l] \ m

Link memory for dynamic systems

This section demonstrates that causal broadcast can use causal order to initialize link memory, thereby enabling the use of link memory in dynamic systems.

Algorithm 1 already implements the maintenance of link memory over receipts. Every process safely removes obsolete control information over receipts. However, Figure 2 highlights that new links lack of consistent initialization. The challenge consists in initializing such memory without history of past messages. Causal broadcast starts to build the knowledge on-demand, i.e., when a process wants to add a link to another process. The protocol disables the new link until initialized. This initialization requires round-trips of control messages and message buffering. Causal broadcast takes advantage of causal order to provide guarantees on messages included in buffers.

Figure 3 depicts the principle of the approach. When a Process A adds a link to Process B, Process A notifies Process B using a control message α. This control message α, as all control messages that will follow (β, π, ρ), must be delivered after all its preceding messages. Hence, at receipt, Process B implicitly removes obsolete information: messages delivered by Process A before the sending of the notification A 1 . At receipt of α, Process B can start gathering con-trol information about its delivered messages in a buffer B α . Among other, Process B wants to identify messages concurrent to the correct establishment of the new link. Process B acknowledges Process A's notification using a control message β. At receipt of β, Process A removes obsolete information: messages delivered by Process B before the sending of the acknowledgment A 1 ∪ B 1 . This solves the issue identified in Figure 2, for a would belong to A 1 or B 1 . However, this is not sufficient to initialize link memory. Process A sends a control message π to Process B, and starts to gather control information about its delivered messages in a buffer B β . Upon receipt of π, Process B closes its first buffer B α .

Lemma 1 (Messages in buffer B α ). The buffer B α contains messages delivered by Process B after the sending of β and before the receipt of π. This includes all messages delivered by Process A before the sending of π that were not delivered by Process B before the sending of β: A 2 . Above all, this also includes all messages delivered by Process B that were not delivered by Process A at the sending of π: B 2 .

Proof. Since control messages are delivered after preceding messages, all broadcast messages delivered by Process A before the sending of α precede the buffering:

∀m, d A (m) → s A (α AB ) =⇒ m ∈ B α . Since messages are de- livered once, ∀m, d A (m) → s A (π AB ) ∧ d B (m) → s B (β AB ) =⇒ m ∈ B α . This removes A 1 and B 1 .
The buffer B α contains the rest of messages delivered by Process B before the receipt of π. This includes messages delivered by Process A between the sending of α and π but not delivered by Process B before the sending of β (A 2 ); and messages delivered by Process B but not delivered by Process A before the sending of π (B 2 ).

Upon receipt of π, Process B continues to gather control information about its delivered messages in another buffer B π . Some messages in this buffer will be expected from Process A, but Process B cannot determine which ones just yet. It sends the last acknowledgment ρ to Process A. Upon receipt of this acknowledgment, Process A closes its buffer and sends it using the new link. Afterwards, Process A uses the draft OPODIS'18

A B A1 α A1 ∪ B1 β B1 ∪ A2 π Bα A2 ∪ B2 ρ B β B2 ∪ A3 B β Bπ A 3 ∪ B3 with A 3 ⊆ A3
B β ∩ (B α ∪ B π ) = B 2 ∪ A 3 are messages to ignore; B β \ B α \ B π = A 3 \ A 3 are messages to deliver; B π \ B β = B 3 are messages to expect from Process A.
new link for causal broadcast, for it knows that Process B will receive B β before upcoming broadcast messages on this new link, and the receipt of B β will allow Process B to initialize this new link memory. Upon receipt of B β , Process B stops buffering in B π .

Lemma 2 (Messages in buffer B β ). The buffer B β contains messages delivered by Process A after the sending of π and before the receipt of ρ. This includes all messages delivered by Process B before the sending of ρ that were not delivered by Process A before the sending of π: B 2 . This also includes all messages delivered by Process A that were not delivered by Process B at the sending of ρ: A 3 .

Proof. The proof is similar to that of Lemma 1. Control messages shift roles. π becomes ρ; β becomes π; α becomes β.

Lemma 3 (Messages in buffer B π ). The buffer B π contains messages delivered by Process B after the sending of π and before the receipt of B β . This may includes messages delivered by Process A before the sending of B β that were not delivered by Process B before the sending of ρ: A 3 . This also includes all messages delivered by Process B that were not delivered by Process A at the sending of

B β : B 3 .
Proof. The proof is similar to that of Lemmas 2 and 3. The difference being that B β is not necessarily delivered after preceding messages. Hence, the receipt of B β follows the sending of ρ but Process B cannot state if it received all, part, or none of messages in A 3 . Thus, A 3 ⊆ A 3 .

Using B α , B β , and B π buffers, Process B identifies messages in B β it must deliver against messages it must ignore, and messages in B π it must receive from Process A. This allows Process B to initialize link memory.

Theorem 2 (B α , B β , and B π initialize link memory). A process consistently initializes link memory at receipt of B β using B α and B π .

Proof. From Lemma 1, B α = A 2 ∪ B 2 . From Lemma 2, B β = B 2 ∪ A 3 . From Lemma 3, B π = A 3 ∪ B 3 .
First, we must show that Process B delivers all and only messages from B β it did not deliver yet:

m ∈ A 3 \ A 3 . Since B β \ B α \ B π = (B 2 ∪ A 3 ) \ (A 2 ∪ B 2 ) \ (A 3 ∪ B 3 ) = A 3 \ (A 3 ∪ B 3 ). Since B 3 ∩ A 3 = ∅, we have B β \ B α \ B π = A 3 \ A 3 .
Second, we must show that Process B initializes the new link memory with all and only messages from B π that Process A did not deliver at the sending of

B β : m ∈ B 3 . B π \ B β = (A 3 ∪ B 3 ) \ (B 2 ∪ A 3 ). Since B 3 ∩ B 2 = ∅ and A 3 ⊆ A 3 , B π \ (B β \ B α ) = B 3 .

Implementation

PRC-broadcast stands for Preventive Reliable Causal broadcast. It prevents both causal order violations and multiple delivery by using all and only links that are safe [START_REF] Nédelec | Breaking the Scalability Barrier of Causal Broadcast for Large and Dynamic Systems[END_REF], and the memory of which is correctly initialized and maintained. PRC-broadcast ensures that control messages are delivered after all their preceding messages by sending them on reliable FIFO links used for causal broadcast. PRC-broadcast uses a local structure the size of which increases and decreases over receipts. Every process safely removes obsolete control information about past broadcast messages.

Algorithm 2 shows the instructions of PRC-broadcast. Figure 4 illustrates its operation in a scenario involving 3 processes. In this example, Process B adds a link to Process C. Process B disables the new link for causal broadcast until it is safe and guaranteed that Process C correctly initialized its memory. Process B sends a first control message α to Process B using safe links (see Line 17 and Figure 4a). After being routed to Process C by intermediary processes (see Figure 4b), α reaches Process C (see Figure 4c). Process C starts to register messages it delivers in a buffer B α . Process C acknowledges the receipt of α by sending a second control message β to Process B using safe links (see Line 25).

Delivered by Process B

To deliver:

B β \ Bα \ Bπ [c 1 , b 1 , b 2 , c 2 ] \ {c 1 , c 2 } \ {b 1 , c 3 } [b 1 , b 2 ] \ {b 1 , c 3 } [b2]
To expect from B:

Bπ \ B β {b 1 , c 3 } \ [c 1 , b 1 , b 2 , c 2 ]
{c3}

To ignore:

B β ∧ (Bα ∪ Bπ) [c 1 , b 1 , b 2 , c 2 ] ∧ ({c 1 , c 2 } ∪ {b 1 , c 3 }) [c 1 , b 1 , b 2 , c 2 ] ∧ {b 1 , c 1 , c 2 , c 3 } {c1, b1, c2}

Delivered by

Process C

(j) Process C categorizes each message of B β and Bπ. Once Process C receives the buffer, it ends its buffer B π (see Figure 4i). Using B α , and B π , Process C identifies among messages from B β the array of messages to deliver (see Line 38). In Figure 4j, this array only includes b 2 . Using B α , and B π , Process C also identifies the set of messages to ignore which is the rest of the buffer. In Figure 4j, this set includes c 1 , b 1 and c 2 . Finally, Process C identifies among its own delivered messages the messages to expect from Process B (see Line 39). In Figure 4j, this set includes c 3 . This set constitutes the memory of the new safe link. Afterwards, messages received by this new link are processed normally.

PRC-broadcast builds link memory using control messages that acknowledges the delivery of preceding messages. Every process safely removes obsolete control information about past broadcast messages. The size of the local structure increases and decreases over receipts. In the next section, we analyze the complexity of this causal broadcast implementation. draft OPODIS'18

Complexity

In this section, we analyze the complexity of PRC-broadcast in terms of broadcast message overhead, delivery execution time, local space consumption, and number of control messages.

The broadcast message overhead is constant O(1). The protocol uses reliable FIFO links to transmit messages. The delivery execution time, i.e., the time complexity of the receipt function is O(|Q i |). The protocol checks and updates control information associated to each link in the inview Q i . The size of in-views can be much smaller than the number of processes in the system |P |. For instance, peersampling approaches [START_REF] Ayalvadi | Scamp: Peer-to-peer lightweight membership service for large-scale group communication[END_REF][START_REF] Nédelec | An adaptive peer-sampling protocol for building networks of browsers[END_REF] provides every process with an in-view the size of which is logarithmically scaling with the number of processes O(ln(|P |)).

The local space consumption depends on the size of buffers and the size of the in-view. Each link in the in-view has its buffer of control information about messages. A message appears in the structure after its first receipt and disappears at its last receipt. So the local space complexity is O(|Q i | • M ) where M is the number of messages already delivered that will be received again from at least a link in the in-view Q i . The local space consumption depends on system settings (e.g. processes do not consume space when the system topology is a ring or a tree) and use (e.g. processes do not consume space when no process broadcasts any message).

The overhead in terms of number of control messages per added link in an out-view varies from 6 to 4 • |P | 2 depending on the overlay network; P being the set of processes currently in the system. It achieves 6 messages when Process A adds Process B using Process C as mediator, and Process B has Process A in its out-view. It achieves 8 control messages when peer-sampling protocols build out-views using neighbor-to-neighbor interactions [START_REF] Jelasity | Gossip-based peer sampling[END_REF][START_REF] Nédelec | An adaptive peer-sampling protocol for building networks of browsers[END_REF]. It achieves O(4 • log(|P |)) control messages when peer-sampling protocols allows processes to route their messages [START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF][START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF]. It achieves O(4 • |P | 2 ) control messages when Process A adds Process B without knowledge of any route. Process A and Process B fall back to reliable broadcast instead of routing to disseminate control messages. This complexity analysis shows that PRC-broadcast proposes a novel trade-off in terms of complexity. In systems allowing a form of routing, processes only send a few control messages to handle dynamicity. Every process maintains a local structure the size of which increases and decreases over receipts. Every process safely removes obsolete control information about past messages. It constitutes an advantageous trade-off that depends on the actual system settings and use instead of past deliveries. The next section describes an experiment highlighting the effects of the system settings on the space consumed by processes.

EXPERIMENTATION

PRC-broadcast proposes a novel trade-off between speed, memory, and traffic. Most importantly, its space consumed varies over receipts. In this section, we evaluate the impact of the actual system on the space consumed and traffic generated by processes. The experiments run on the PeerSim simulator [START_REF] Montresor | Peersim: A scalable P2P simulator[END_REF] that allows to build large and dynamic systems. Our implementation is available on the Github platform at http://github.com/chat-wane/ peersim-prcbroadcast. Objective: To confirm that local space complexity depends on in-views and message receipts. Description: We measure the average size of buffers and arrays of expected messages. This constitutes the average local space overhead consumed by PRC-broadcast to detect and forbid multiple delivery in dynamic systems. Runs involve 3 overlay networks comprising 100, 1k, and 10k processes. Spray [START_REF] Nédelec | An adaptive peer-sampling protocol for building networks of browsers[END_REF] builds a highly dynamic overlay networks. The resulting topology has properties close to those of random graphs such as low diameter, or low clustering coefficient. Such systems are highly resilient to random crashes, and allows processes to balance the load of the traffic generated by broadcasting. Each process maintains an out-view logarithmically scaling with the number of processes in the system. Each process of the 100-processes system has an out-view of ≈ 10 neighbors. Each process of the 1k-processes system has an out-view of ≈ 13.5 neighbors. Each process of the 10k-processes system has a out-view of ≈ 15 neighbors. Each process dynamically reconfigures its out-view: it gives half of its correctly initialized links to a chosen neighbor; the latter gives half of its correctly initialized links to the former as well. Each exchange leads to link memory initialization and safety checks of the new links, and removal of given links. Each process starts to reconfigures its out-view as soon as it joins the system and reconfigures its out-view every minute. This uniformly spreads reconfigurations over the duration of the experiment. Links are bidirectional, their safety must be checked in both directions but the overhead remains minor. Since the peersampling protocol that builds the system uses neighbor-toneighbor communication to establish new links, each control message is two hops away from its destination. Overall, a new link requires 8 control messages to be initialized properly. Links have transmission delay, i.e., the time between the sending of a message and its receipt is not null. The experiments start with 1 millisecond transmission delay. At 15 minutes, the delay starts to increase. At 17 minutes, links reach 300 milliseconds transmission delay. At 40 minutes, links reach 2.5 seconds transmission delay and it stops increasing. From 2 minutes to 50 minutes, every second, 10 processes chosen uniformly at random among all processes broadcast a message. Figure 5a confirms that the local space consumption depends on the in-view size. Systems with larger in-views consume more space. Each new delivered message adds control information on each link of the in-view (see Algorithm 1). Figure 5a confirms that the local space consumption depends on network condition. The overhead increases as the latency increases. Latency increases the time between the first and the last receipt of each message. Processes store messages longer until their safe removal. Figure 5a confirms that the local space consumption depends on broadcast messages. When processes stops broadcasting, the space consumed at each process drops to 0. Each process eventually receive each message and safely remove the corresponding entry. Figure 5a shows that at a rate of 10 broadcasts per second and when latency stays under a realistic bound (300 milliseconds), the overhead is lower than vector-based approaches. Whatever system conditions, it would require a vector of 100, 1k entries, 10k entries to forbid multiple delivery in the 100-processes system, 1k-processes system, 10k-processes system respectively. However, it is worth noting that the overhead of PRC-broadcast increases linearly with the number of messages currently transiting. 100 broadcasts per second would multiply measurements made on PRC-broadcast by a factor of 10. In such case, the 100-entries vector would be better than PRC-broadcast even under a latency of 300 milliseconds. PRC-broadcast provides a novel trade-off between speed, memory, and traffic. Among other, its space consumed increases and decreases depending on the system and its current use; instead of past use (see Section 4. This result means that it constitutes an advantageous trade-off in (i) dynamic systems (ii) comprising up to millions of processes (iii) that could broadcast at any time.

Objective: To confirm that the generated traffic overhead depends on the dynamicity of the system. Description: We measure the average number of control messages received by each process during a second. This includes the routing of messages. The setup is identical to that of prior experiment.

Results: Figure 5b shows the results of this experiment. The top part of the figure depicts the traffic overhead generated by PRC-broadcast while the bottom part of the figure depicts the evolution of transmission delays. Figure 5b shows that the number of control messages received by processes depends on the dynamicity of the system. The more dynamic the higher the traffic overhead. At the beginning of the experiment, processes join the system. Numerous links are established at once, hence the high number of control messages. Then processes shuffle their out-view during 50 minutes. The number of links to add and remove is roughly constant over time, hence the stabilization in number of control messages. Finally, processes stop shuffling at 50 minutes. Processes do not receive additional control messages. Figure 5b confirms our traffic overhead complexity analysis. For instance, in the 10k-processes system, views comprises 15 processes which belong half from the out-view and half from the in-view. Each process shuffles every draft OPODIS '18 Table 1: Complexity of broadcast algorithms at each process. N the number of processes that ever broadcast a message. P is the set of processes in the system. w the number of messages received but not delivered yet. Q i is the set of incoming links. M is the set of messages already delivered that will be received again from at least one link in Q i . Figure 5b shows that latency smooth and decreases the number of control messages. The peer-sampling protocol only shuffles links already safe and the memory of which is initialized. Since increasing latency increases the initialization time of links, processes exchange less links at each shuffle. The generated traffic decreases accordingly. Latency also spreads control messages over time, hence the smoothing in measurements.

Assuming peer-sampling protocols that enable a form of routing, PRC-broadcast forbids multiple delivery at the cost of a few lightweight control messages in dynamic systems. In this experiment, the underlying peer-sampling protocol builds a random graph topology that has numerous desirable properties such as resilience to failures, quick dissemination of information, or load balancing [START_REF] Jelasity | Gossip-based peer sampling[END_REF]. It fits dynamic systems where numerous processes join and leave continuously. Nonetheless, other peer-sampling protocols could be used depending on the configuration of the system. One could minimize latency [START_REF] Dabek | Vivaldi: A decentralized network coordinate system[END_REF], or gather people based on user preferences [START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF]. Overall, this section showed that PRC-broadcast proposes a novel trade-off in terms of complexity. Its complexity actually depends on the system (its dynamicity, its latency, its topology) and current use (broadcasts per second). PRC-broadcast forbids multiple delivery and safely removes obsolete control information about broadcast messages. The next section reviews state-of-the-art approaches designed to forbid multiple delivery.

RELATED WORK

Causal broadcast ensures causal order and forbids multiple delivery. PRC-broadcast uses the former to improve on the complexity of the latter. This section reviews state-of-the-art broadcast protocols that forbid multiple delivery in asynchronous and dynamic systems.

Building specific dissemination topologies such as tree or ring guarantees that every process receives each message once [START_REF] Bravo | Saturn: A distributed metadata service for causal consistency[END_REF][START_REF] Raynal | Distributed algorithms for messagepassing systems[END_REF]. Processes deliver messages as soon as they arrive. They do not need to save any control information about messages, for they will never receive a copy of this message again. While these approaches are lightweight, they stay confined to systems where failures are uncommon, and where churn rate remains low [START_REF] Krasikova | Evaluating the cost and robustness of self-organizing distributed hash tables[END_REF]. PRC-broadcast generalizes on these specific topologies. It follows the same principle where the topology impacts on the number of receipts. Its space complexity scales linearly with this number of receipts. In turns, PRC-broadcast inherits from the resilience of the underlying topology maintained by processes. PRCbroadcast supports dynamic systems without assuming any specific topology.

Without any specific dissemination topology, each process may receive each broadcast message multiple times. Despite multiple receipts, a process must deliver a message once. Using local structures based on logical clocks [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF], every process differentiates between the first receipt of a broadcast message and the additional receipts of this message. It allows to deliver the former while ignoring the latter. Unfortunately, the size of these structures increases monotonically and linearly with the number of processes that ever broadcast a message [START_REF] Malkhi | Concise version vectors in winfs[END_REF][START_REF] Mukund | Optimized or-sets without ordering constraints[END_REF]. Processes cannot reclaim the space consumed, for it would require running an overcostly distributed garbage collection that is equivalent to a distributed consensus [START_REF] Saleh | Garbage collecting the internet: A survey of distributed garbage collection[END_REF]. This limits their use to context where the number of broadcasters is known to be small. PRC-broadcast uses local structures based on logical clocks too. However, instead of saving the past deliveries of broadcasters, its saves the messages expected from direct neighbors. The set of expected messages varies over receipts, and the number of neighbors can be far smaller than the set of broadcasters. PRC-broadcast scales in large and dynamic systems. Among others, PRC-broadcast fits contexts where the number of participants is unknown, such as distributed collaborative editing [START_REF] Nédelec | Crate: Writing stories together with our browsers[END_REF].

Table 1 summarizes the complexity of broadcast imple-draft OPODIS '18 mentations that handle asynchronous and dynamic systems. To the best of our knowledge, all causal broadcast implementations use an underlying reliable broadcast in order to forbid multiple delivery. Their local space complexity comprises O(N ) where N is the number of processes that ever broadcast a message. Compared to preventive causal broadcast [START_REF] Nédelec | Breaking the Scalability Barrier of Causal Broadcast for Large and Dynamic Systems[END_REF], PRC-broadcast slightly increases the delivery execution time, and doubles the number of control message per added link. In turns, PRC-broadcast keeps a constant overhead on broadcast message, and changes the terms of local space complexity. Most importantly, the local space consumed does not monotonically increase anymore.

CONCLUSION

In this paper, we proposed a causal broadcast implementation that provides a novel trade-off between speed, memory, and traffic. Our approach exploits causal order to improve on the space complexity of the implementation that forbids multiple delivery. The local space complexity of this protocol does not monotonically increase and depends at each moment on the number of messages still in transit and the degree of the communication graph. The overhead in terms of number of control messages depends on the dynamicity of the system and remains low upon the assumption that the overlay network allows a form of routing. This advantageous trade-off makes causal broadcast a lightweight and efficient middleware for group communication in distributed systems.

As future work, we plan to investigate on ways to retrieve the partial order of messages out of PRC-broadcast. Applications may require more than causal order, they also may need to identify concurrent messages [START_REF] Sun | Context-based operational transformation in distributed collaborative editing systems[END_REF]. PRC-broadcast discards a lot of information by ignoring multiple receipts altogether. Analyzing the receipt order could provide insight on the partial order. The cost could depend on the actual concurrency of the system.

Definition 7 (

 7 Link memory). Assuming a link (A, B), Process B remembers among its delivered messages those that draft Process B and Process C receive b. They do not expect other copies. Process C delivers and forwards b. Process A receives its last expected copy of b. The message b is completely removed from the system.

Figure 1 :

 1 Figure 1: Link memory allows to safely remove obsolete control information in static systems.

  The delivery d B (m) implies a prior receipt r B (m) → d B (m). Assuming that each link carries each messages once, and this receipt comes from link (A, B), then Process B cannot receive, hence deliver, m from (A, B) again: m, r BA (m) → d B (m) ∧ d B (m) → r BA (m) ∧ r BA (m) → d BA (m). If this receipt comes from any other link (C, B), C = A, Process B remembers m on other links, and among others, on link (A, B): ∀m, r BC (m) → remember BA (m).

  in-view is tagged with b, meaning this is a first receipt. It tags the other link in its in-view with b and forwards b to its out-view. In Figure1c, Process B receives the awaited copy of b from Process A. It removes the corresponding entry. The broadcast protocol at Process B does not consume space anymore. Process C receives b. It detects a first receipt so it delivers and forwards b. It does not tag any link, for the only link from its in-view is the link from which it just received b. In Figure1d, the last process to await a copy of b finally receives it. None of processes remembers about b. No copy of b travels in the system. This implementation forbids multiple delivery in static systems while safely removing obsolete control information.However, implementing link memory becomes more challenging in dynamic systems where processes can start sending messages to any other process at any time. Any process can receive an already forgotten message from any other process. Figure2illustrates the issue. In Figure2a, Process A broadcasts a. It expects a copy from both Process B and Pro-Process A broadcasts a and expects a copy from both Process B and Process C. Process C receives, delivers, and forwards a. It does not expect additional copies. Process B adds a link to Process C. Then it receives, delivers, and forwards a. Process C receives and mistakes a for a new message. It delivers, and forwards a.

Figure 2 :

 2 Figure 2: Causal broadcast (Algorithm 1) fails to forbid multiple delivery in dynamic systems.

Figure 3 :

 3 Figure 3: Initializing the link memory from Process A to Process B. Control messages α, β, π, and ρ are delivered after all preceding messages while B β is not. At receipt of B β , Process B classifies the messages: B β ∩ (B α ∪ B π ) = B 2 ∪ A 3 are messages to ignore; B β \ B α \ B π = A 3 \ A 3 are messages to deliver; B π \ B β = B 3 are messages to expect from Process A.

c 1 b 1 ( 2 b 2 c2ρ

 122 Process B adds a link to Process C. PRCbroadcast ensures its safety. Process B sends a first control message α to Process C using Process A as mediator. Process C receives α and answers by sending β to Process B using Process A as mediator. Then, Process C broadcasts c1 and registers it in Bα. Process A receives β and routes it to Process B. Process A receives c1 and forwards it to both its neighbors. e) Process C receives and discards c1. Process B receives β and replies π to Process C using Process A as mediator. Process B receives c1 and forwards it to its neighbor. Process B broadcasts b1. It registers c1 and b1 in B β . Process A receives c1 and discards it. Process A receives π and routes it to Process C. Process A receives b1 and forwards it to its neighbors. Process C broadcasts c2 and registers it in Bα. A B B β : [c1, b1, b2] C π Bα : {c1, c2} Bπ : {b1, c3} c b1 c3 (g) Process A receives c2 and forwards it to its neighbors. Process B broadcasts b2 and registers it in B β . Process C receives π and replies ρ to Process B using Process A as mediator. Then it receives and forwards b1. Then it broadcasts c3. It registers b1 and c3 in Bπ. Process A receives and discards b1. Process A receives and routes ρ to Process B. Process A receives and forwards b2 then c3. Process B receives, forwards, and registers c2. Then Process B receives ρ and sends B β to Process C using the new link. Once Process A sent B β , the new link is safe. Process C receives B β . Process C does not deliver c1, b1 and c2, for it already delivered them. Process C delivers b2 and expects another copy from Process A, for it constitutes a new message. Process C expects to eventually receive c3 from Process B.

Figure 4 :' 18 Algorithm 2 : 11 foreach 12 if receivedπ then Bπ ← Bπ ∪ m 13 else Bα ← Bα ∪ m 14 15 upon open o (to) 16 Qo ← Qo \ to 17 send 18 upon open i (f rom) 19 Qi ← Qi \ f rom 20 upon 21 B[to] ← ∅ 22 send-π(f rom, to) 23 upon 24 S 40 Qi ← Qi ∪ f rom 41 upon closeo(to) 42 B ← B \ to 43 upon closei(f rom) 44 S ← S \ f rom 45 E

 41821112131415161718192021222324404142434445 Figure 4: Using buffers and control messages, PRC-broadcast provides reliable causal broadcast.

  Local space overhead (number of control information about broadcast messages in all buffers).

  Generated traffic overhead (number of control messages transiting in the system including routed messages).

Figure 5 :

 5 Figure 5: Overhead of PRC-broadcast required to ensure causal order and forbid multiple delivery in dynamic systems with varying latency.

ACKNOWLEDGEMENTS

This work was partially funded by the French ANR projects O'Browser (ANR-16-CE25-0005-01), and Descartes (ANR-16-CE40-0023).