P Šauli

S G Roux

P Abry

J Boška
email: boska@ufa.cas.cz

Acoustic-gravity waves during solar eclipses: detection, characterization and modeling using wavelet transforms

Keywords: Acoustic-Gravity Wave, Vertical Ionospheric Sounding, F-Layer, Wavelet Transform, Wave Packet Characterization

In the present contribution, we first propose a methodology that enables to detect wave like structures propagating in Ionosphere, by tracking the local maxima of the modulus continuous wavelet transform coefficients through heights. From the derivation of the phases of the wavelet transform, we measure the corresponding propagating parameters. These tools are applied to measurements collected by vertical ionospheric sounding at high-time resolution sampling regime (sampling periods ranged from 1 to 3 min) in the observatory Průhonice (49.9N, 14.5E, Czech Republic). The aim of these experiments is to analyze the changes in the ionospheric plasma induced by three different solar eclipse events (total solar eclipses, 11 August 1999, 29 March 2006, and annular solar eclipse, 3 October 2005) and to detect and analyze the propagation of the generated acoustic gravity waves. Second, injecting wave vector components measured from the data into the acoustic gravity wave propagation equations, we obtain a full description of the propagation of the waves. This enables us to differentiate acoustic gravity waves from others and to discuss similarities and differences of the waves detected during these three particular events. These procedures also enabled us to detect acoustic waves. We believe that the methodology proposed here brings significant improvement in detecting, characterizing and modeling acoustic gravity wave propagations from empirical data and can be readily used in the ionosphere community.

1 Introduction Acoustic Gravity Waves in Atmosphere. Terrestrial atmosphere shows high variabilities over a broad range of periodicities, which mostly consist of wave-like perturbations characterized by various spatial and temporal scales. Amongst atmospheric waves, acoustic gravity waves (AGW), whose periodicities range from minutes (pure acoustic waves) to few hours (gravity waves), constitute the source of most of the short-time ionospheric variabilities. Acoustic gravity waves play an important role in the dynamics and energetics of Atmosphere and Ionosphere. For instance, they are responsible for momentum and energy transfers from high latitudes to low latitudes and from lower to upper Atmosphere. Because acoustic gravity waves spread energy between atmospheric regions, they significantly contribute to the global circulation, temperature and compositional structure of Mesosphere, Thermosphere and Ionosphere. Gravity waves are hence an important component of the atmospheric motion field. Acoustic gravity wave propagation also have a significant impact on radio wave propagation conditions. Therefore, analyzing and understanding wave generation mechanisms with respect to specified sources constitutes a major goal to improve our knowledge of atmospheric dynamics. Acoustic gravity wave theory (e.g. ?) in terrestrial Atmosphere has been developed in the sixties and then further extended by various authors (e.g. ?, ?, ?). The first experimental observations refer to acoustic gravity waves generated by explosive sources and earthquakes ?, ?, and acoustic gravity waves in Earth Atmosphere have been widely studied empirically since. The interests of scientists range from the analysis of the climatology of the gravity waves to case studies of acoustic gravity wave occurrences related to particular events acting as wave sources, such as meteorological systems, geomagnetic storm, solar eclipse etc. Various radio techniques (including ionosonde) were used around the globe to analyze the climatology and case events of acoustic gravity waves. Numerous measurements and campaigns were conducted aiming at relating the observed gravity waves to their sources (e.g. HIRAC campaign ? amongst others). However, the description, interpretation and understanding of the mechanisms underlying acoustic gravity wave generation and propagation still remain incomplete. This is mostly due to severe difficulties in analyzing real measurements. For instance, it is difficult to decide whether the observed wave characteristics are due to the properties and positions of the acoustic gravity wave sources or to interactions between the propagating waves and the mean flow (convection, tides, planetary waves etc.), see e.g., by ?, ?, ? or ? for detailed reviews.

Acoustic Gravity Waves and Solar Eclipses. It has been proposed by ? that solar eclipses can act as sources for acoustic gravity waves. During a solar eclipse, Ionosphere strongly reacts to the break of ionization. The lu-nar shadow is moving within Ionospheric heights at a supersonic speed. The sharp border between sunlit and eclipsed regions, defined by strong gradients in temperature and ionization flux, moves throughout Ionosphere and drives it into a non-equilibrium state. The photoionization cut-off, together with the cooling of the neutral Atmosphere over a limited area, creates waves that tend to drive Ionosphere back to its equilibrium state. Model insights into processes occurring during solar eclipse in Thermosphere and Ionosphere is proposed by ?. Studies by ? suggest that perturbations generated by the eclipse induced ozone heating interruption may propagate upwards into the Thermosphere-Ionosphere system where they have an important influence. First experimental evidence of the existence of gravity waves in Ionosphere during solar eclipses were reported in ?, where waves with periods of 30-33 min were observed on ionosonde sounding virtual heights.

Goals of the present contribution. Various experimental studies of the 11 August 1999 solar eclipse (cf. e.g., ?, ?, ?, ?, ?) analyzed the relations between acoustic gravity wave generation mechanisms in Ionosphere and solar eclipse events. The present contribution aims at enlarging the scope of previously existing studies and at bringing new information about horizontal and vertical propagation characteristics. To do so, acoustic gravity waves detected during three different solar eclipses (11 August 1999, 3 October 2005and 29 March 2006) are studied and compared. Description of these eclipses and corresponding data are detailed in Section ?? and Table ??. Elaborating on tools proposed in ?, ? and ?, this contribution also develops a wavelet transform based methodology to detect wave packets (or structures) propagating at Ionospheric heights and to measure, from data, their time, period and height locations, their wave vectors, phase and packet velocities. Techniques based on Fourier transforms were previously proposed. However, by definition, Fourier transforms are averaging, and hence mixing information, along time. Therefore, wave parameters measured at a given frequency can potentially result from the contribution of different waves sharing the same characteristic frequency but existing at different time positions, hence producing poor or inaccurate characterization of the waves. Wavelet decompositions, thanks to their being joint time and frequency representations, enable to disentangle the contribution of different structures whose time or frequency supports partially overlap. Therefore, they enable to better identify and analyze wave structures, to more accurately decide whether they consists of acoustic gravity waves or not and finally to better measure their corresponding propagation parameters. Further developing this wavelet based approach, we inject measurements into the equations governing acoustic gravity wave propagation and, making use of an upper Atmosphere model (?), we fully characterize the propagating parameters of the detected structures. Acoustic gravity wave theory and the upper Atmosphere model are described in Section ??. Wavelet decomposition and wave packet detection and characterization are detailed in Section ??. In Section ?? we will discuss the results and conclude.

2 Solar Eclipses and Data Solar eclipse events. In the present contribution, we analyze three different solar eclipse events. Two of them, 11 August 1999 and 29 March 2006, represent total solar eclipses, while the third one, 3 October 2005, is an annular solar eclipse. All three solar eclipse events occurred during periods of low geomagnetic activity. Indeed, as shown in Fig. ??, Kp indices remained below or equal a maximum value of 3 (out of 9) for several consecutive days, indicating that Ionosphere remained in a quiet state. Therefore, we can consider that measurements reflect the variability due to the occurrence of the solar eclipses. The supersonic motion of the totality/ annularity footprint causes shock wave structures in Atmosphere, that are further reflected in ionospheric plasma. The parameters describing each solar eclipse are given in the Table ??, as observed from Průhonice ionospheric station.

Data Measurements and time series. In upper Atmosphere, acoustic gravity waves are observed directly as fluctuations of neutral gas or oscillations of the ionospheric plasma due to the coupling between the neutral and ionized components. Our measurements consists of vertical profiles of electron concentration. For the three eclipses, measurements were performed at the European mid-latitude ionospheric station Průhonice (Czech Republic; 49.9N, 14.6E), using vertical ionospheric sounding techniques. The 1999 solar eclipse was monitored using a classical ionosonde IPS 42 Kel Aerospace and data were collected with a 1-minute sampling period. This ionosonde was later (January 2004) replaced by the Digital Portable Sounder 4 (DP S4) hence used for the two latest solar eclipse events. For DPS4 measurements, lower resolution regimes were chosen to enable simultaneous record of ionograms and plasma drift. Hence data were collected with 2-minute and 3-minute sampling periods for the 2005 and 2006 events, respectively.

Real height vertical electron density profiles were derived from ionograms using two inversion techniques POLynomial ANalysis (?) and NHPC (?). Finally, from the real height electron density profiles, we obtain variations of the electron concentration X, as a function of time t, at fixed heights z:

X(t, z), t ∈ [T m , T M ], z ∈ Z. ( 1
)
where T m and T M denote the beginning and end of the measurement in UT.

The spatial sampling period is 5km, corresponding to heights Z = {155, 160, 165, . . . , 255} (in km). The time series for the three eclipses are shown in Fig. ??, left column. The acoustic gravity wave detection procedures described below are performed on these X(t, z) time series.

3 Acoustic gravity wave theory acoustic gravity Wave propagation At periods of minutes and larger, buoyancy effects become important due to atmospheric stratification and Atmosphere becomes dispersive and anisotropic. In such a medium, phase and energy no longer propagate along the same direction. Under an energy conservation assumption, the propagation of acoustic gravity waves is driven by the following ideal dispersion relation:

ω 4 -ω 2 ω 2 a -k 2 x C 2 (ω 2 -ω 2 g ) -C 2 ω 2 k 2 z = 0, (2)
where k x and k z stand for the horizontal and vertical components of the wave vector, C for the speed of sound, ω a for the angular acoustic cut-off frequency and ω g for the angular buoyancy (or Brunt-Väisälä) frequency. This dispersion relation accounts for a nonlinear and dispersive propagation. It indicates the existence of two propagation frequency ranges: acoustic modes, with characteristic frequencies larger than the acoustic cut-off ω a , gravity modes, with characteristic frequencies smaller than the Brunt-Väisälä ω g . An important property of the gravity mode consists of that fact that energy flows up when phase travels down and vice versa, while for acoustic mode both energy and phase propagate jointly, either upward or downward. The phase propagation angle Φ (measured from the vertical, clock-wise) indicates the phase velocity (or wave vector) direction while the energy propagation angle γ (measured from the wave vector direction, clock-wise) indicates the packet velocity direction:

tan Φ = k x /k z , (3)
tan γ = ω a ω 2 sin Φ cos Φ / 1 - ω a ω 2 sin 2 Φ (4)
The modulus of the wave vector, the phase velocity and the vertical and horizontal components of the packet velocity are defined as:

k = k 2 x + k 2 z , (5)
v φ = ω k , (6)
v p,x = C 2 k x (ω 2 -ω 2 g ) / ω(2ω 2 -ω 2 a -C 2 k 2 ) , (7)
v p,z = C 2 k z ω 2 / ω(2ω 2 -ω 2 a -C 2 k 2 ) . (8)
Eqs. (??) to (??) are derived in e.g., ? or ?.

Neutral Atmosphere parameters. For a practical use of Eqs. (??) to (??), it is necessary to set the values of ω a , ω g and C that reflect the properties of the background neutral Atmosphere. In our analysis, we consider that the upper Atmosphere is well described by the Australian Standard Atmosphere model 2000 (U ASA2000). The U ASA2000 model is based on U.S. Standard Atmosphere, 1976 (U SSA1976), and has been modified in the upper Atmosphere, above 86km (?). The U ASA2000 model provides the scale height and acceleration due to gravity that are necessary to compute the speed of sound.

The ratio between the specific heats at constant pressure and constant volume is a key factor in adiabatic processes and in determining the speed of sound in a gas. This ratio takes the value γ = 1.66 for an ideal mono-atomic gas and γ = 1.4 for a diatomic gas. Because Earth Atmosphere is predominantly a diatomic gas, we use this latter approximation (?, ?).

4 Acoustic gravity wave detection and modeling

Wavelet Transform

• Wave packet description and Fourier decomposition.

The goal is to extract wave propagation information from the data X(z, t) sampled in time and space. In the literature, this has been addressed by performing a wave packet expansion of the data by means of Fourier Transform:

X(z, t) = ω 0 (z)+∆ω ω 0 (z)-∆ω X 0 (ω, z) exp ı(ωt-) dω, (9)
where X 0 (ω, z) denotes the amplitude of the wave, obtained as the Fourier transform of X(z, t) with respect to the time variable t, ω 0 (z) and ∆ω stand respectively for the central frequency and characteristic frequency width of the wave packet at altitude z. A methodology originally introduced in ??, proposed to derive some of the Acoustic gravity wave parameters such as the characteristic frequency, the z-components of the wave vector and of the phase and packet velocities by tracking the evolution of extrema in amplitude and phase of X 0 (ω, z) along z.

Elaborating on ?, we extend this original idea to the wavelet framework. By replacing the Fourier transform with the wavelet transform, we obtain a description of the data T X (ω, t, z) both along time and frequency. As detailed in Section ??, a joint time and frequency representation enables more accurate detections and analyzes of wave structures.

• Wavelet Transform.

Let ψ 0 (t) denote an elementary pattern, referred to as the mother-wavelet. It is required to have fast decreases both in the time and frequency domains, and to be a band-pass filter (i.e., to have zero mean): R ψ 0 (u)du, ≡ 0.

(10)

One defines a family of analyzing functions as translated and dilated templates of the mother-wavelet:

ψ a,t (u) = 1 √ a ψ 0 u -t a , a > 0, z ∈ Z. ( 11
)
The coefficients of the continuous wavelet transform are obtained by comparisons, by means of inner product, of the data X(t, z) against the ψ a,t :

T X (a, t, z) = R X(u, z)ψ a,t (u)du. ( 12
)
Because wavelets are band-pass filters, we can relabel, with a little abuse of notation, the wavelet coefficients T X (a, t, z) ≡ T X (ω, t, z) using the usual scale-frequency conversion: ω = ω ψ /a, where ω ψ is the central pulsation of the chosen mother-wavelet, defined as

ω ψ = 2π +∞ 0 ν|Ψ 0 (ν)| 2 dν +∞ 0 |Ψ 0 (ν)| 2 dν , (13)
Ψ 0 standing for the Fourier transform of ψ 0 .

Because we choose to use complex mother-wavelet, the wavelet coefficients T X (ω, t, z) are complex numbers. Let {|T X (ω, t, z)|, φ(ω, t, z)} denote their modulus and phase. Scalograms (also called wavelet power spectra) consist of the plots of |T X (ω, t, z))| as a function of time t and period P = 2π/ω = 2πa/ω φ . Therefore, the scalograms |T X (ω, t, z))| can be given the meaning of energy content of X, at height z, around time position t and around frequency ω = ω ψ /a. Examples of scalograms obtained on electron concentration data are shown in Figs. ?? and ??.

In the present work, we make use of Morlet and Paul (complex) motherwavelets, defined as:

Morlet : ψ 0,µ (t) = (πσ 2 ) -1 4 exp(- t 2 2σ 2 ) exp(ı2πν 0 t), µ = 2πσν 0 , (14)
Paul :

ψ 0,µ (t) = 2 N ı N N ! π(2N )! (1 -ıt) -(N +1) , µ = N, (15)
where µ provides a degree of freedom that can be easily tuned to a given purpose. For instance, in the present work, it enables us to select the size of the time support of the mother wavelet. For these two chosen mother-wavelets, we have numerically computed ω ψ from Eq. (??) above.

For a thorough introduction to wavelet transforms, the reader is referred e.g., to [START_REF] Mallat | A Wavelet Tour of Signal Processing[END_REF]. In the present work, we adapted the wavelet decomposition Matlab toolbox provided by Torrence and Compo (cf. ?) to our purposes (Morlet wavelets with parameters µ = 6 and 4 and Paul wavelets with parameters µ = 4 and 2, were used).

Structure detection

The structure detection scheme we propose is organized in three key major steps:

(1) Data preprocessing and wavelet decomposition, (2) Energy concentration detection at each altitude and maxima line tracking along altitude, (3) Wave parameter measurements.

They are detailed below. For explanation purposes, the behavior of the entire detection/characterization/modeling procedure will be illustrated on a specific example structure, (corresponding to a superb gravity wave) occurring during the August, 11th, 1999 eclipse (GW1, in Table ??). The corresponding data are shown in Fig. ??(a).

• Data preprocessing and wavelet decomposition.

For each altitude z independently, a high-pass filter is applied to the time series {X(t, z), t ∈ [T m , T M ]} z∈Z to suppress periods larger than 90min and focus on short term oscillations. Detrended time series are shown Fig. ??(b). Then, complex wavelet coefficients are computed on these detrended data according to Eq. (??). Examples of scalograms are presented in Fig. ??.

• Wave packet detection.

First, for each scalogram |T X (ω, t, z))| independently, local energy maxima are detected and their time position, period, amplitude and phase recorded. Second, local maxima that exist jointly over a continuous range of heights z, within a same time-period neighborhood are connected together to form maxima lines. When different maxima exist in a same time-period neighborhood, the chaining operation is conducted to favor smooth evolutions along z of the local maxima parameters. Each of these maxima lines correspond to the detection of a wave packet (or wave structure), and consists of the following collection of information:

(1) Altitude range z ∈ [z, z] within which the structure is detected;

(2) Precise time position t 0 (z) and pulsation ω 0 (z) of the occurrence of the maximum at each height z and the corresponding amplitude X 0 (z) = X(t 0 (z), z); (3) Modulus |T X (ω, t, z))| and phase φ(ω, t, z) of the wavelet coefficients in the time-period neighborhood around the maxima position. The selected structure is marked by the use of a '• '.

• Wave packet characterisation.

From the information collected for each wave packet, we derive the following collection of attributes.

(1) Mean time and pulsation defined as:

t 0 = t 0 (z) z , ω 0 = ω 0 (z) z , (16)
where • z means that average is taken over the range of altitude z ∈ [z, z].

(2) Components of the Wave vector, phase and packet velocities are measured as:

k z (ω, t, z) = ∂φ(ω, t, z)/∂z, k 0,z (z) = k(ω, t, z) t 0 (z),ω 0 (z) , v (z) φ (ω, t, z) = ω/k z (ω, t, z), v (z) φ,0 (z) = v (z) φ (ω, t, z) t 0 (z),ω 0 (z) , v p,z (ω, t, z) = ∂ω/∂k z (ω, t, z), v p,0,z (z) = v p,z (ω, t, z) t 0 (z),ω 0 (z) ,              (17)
where • t 0 (z),ω 0 (z) denote that we take the median within a narrow timepulsation neighborhood centered around t 0 (z) and ω 0 (z).

(z) = 2π/ω 0 (z), k 0,z (z), X 0 (z), v (z)
φ,0 (z) and v p,0,z (z) measured according to the procedure described above for the chosen example structure.

This theoretically simple procedure calls for two important practical comments. Comment 1 Computing the quantities above involves derivation. This is performed using a third-order or fifth-order finite difference procedure, depending on the range of heights available in the structure and border effects are taken care of. Note that the computation of v p,z (ω, t, z) requires a double derivation and is actually computed as the inverse of ∂/∂ω(∂φ(ω, t, z)/∂z). This is numerically poorly conditioned and may lead to inaccurate results. This is further discussed in Section ?? where an acoustic wave is analyzed. Comment 2 From ionospheric vertical sounding measurements, one only has access to vertical profiles of electron density and hence to the vertical components of the wave vector, phase and packet velocities. Therefore, in Eq. (??) above k z and v p,z stand for the vertical components of the corresponding vectors. For the phase velocity, the situation is even more involved. In ???, v (z) φ has been incorrectly associated to the z component of the phase velocity v φ,z . However,

v φ = ω/k = ω/k z • k z /k = v (z) φ cosΦ, while v φ,z = v φ cosΦ, hence, v φ,z = v (z)
φ cos 2 Φ. When the phase propagation direction is close to the vertical direction, the error is negligible, this is however not the case for close to horizontal phase propagation.

Structure modeling

No further information can be extracted from the data themselves. To decide whether a detected wave packet corresponds or not to the propagation of an acoustic gravity wave, it can be compared to the theoretical acoustic gravity wave propagation model recalled in Section ??, making use of the upper Atmosphere model.

First, from the Atmosphere model, we derive the values of ω a (z), ω g (z) and C(z), for all z ∈ [z, z]. Comparing the measured w 0 (z) to ω a (z) and ω g (z) enables to check whether the detected structure packet consists of a gravity or acoustic waves. Second, for all z ∈ [z, z] and all t and ω in the time-period neighborhood associated to the studied structure, we derive k x (ω, t, z) from the dispersion relation in Eq. (??) by plugging-in the measured k z (ω, t, z) and the calculated ω a (z), ω g (z) and C(z). Third, making use of Eqs. (??) to (??), we derive the phase and energy propagation angles Φ(ω, t, z) and α(ω, t, z) = Φ(ω, t, z) + γ(ω, t, z), respectively, measured clockwise from the vertical direction. Then, we compute the wave vector k(ω, t, z) and the phase velocity v φ (ω, t, z) from Eqs. (??) to (??). Combining previous results yields the phase velocity components v φ,z (ω, t, z) = v φ (ω, t, z) cos Φ(ω, t, z), v φ,z (ω, t, z) = v φ (ω, t, z) sin Φ(ω, t, z). To finish with, Eqs. (??) to (??) provide the packet velocity components v p,x (ω, t, z) and v p,z (ω, t, z). Fourth, from these quantities, we compute the median • t 0 (z),ω 0 (z) (as defined in Section ?? above) for each quantity hence obtaining Wave Vector k 0,x (z) = k x (ω, t, x) t 0 (z),ω 0 (z) ,

k 0 (z) = k x (ω, t, x) 2 + k z (ω, t, z) 2 t 0 (z),ω 0 (z) , Wavelength λ 0 (z) = 2π/k 0 (z), Phase Angle Φ 0 (z) = Φ(ω, t, z) t 0 (z),ω 0 (z) , Energy Angle α 0 (z) = α(ω, t, z) t 0 (z),ω 0 (z) , Phase velocity v φ,0 (z) = v φ (ω, t, z) t 0 (z),ω 0 (z) , v φ,0,z (z) = v φ,z (ω, t, z) t 0 (z),ω 0 (z) , v φ,0,x (z) = v φ,x (ω, t, z) t 0 (z),ω 0 (z) , Packet velocity v p,0,z (z) = v p,z (ω, t, z) t 0 (z),ω 0 (z) , v p,0,x (z) = v p,z (ω, t, x) t 0 (z),ω 0 (z) , v p,0 (z) = v p,x (ω, t, z) 2 + v p,z (ω, t, z) 2 t 0 (z),ω 0 (z) ,                                                                        (18)
Fig. ?? shows, for the chosen example structure, the quantities computed according to the procedure described above. Also, it compares the computed v φ,0,z (z)/cos 2 Φ 0 (z) with the measured v (z) φ,0 as well as the computed and measured z-component of the packet velocities. Both for detection and modeling, the central point of our procedures consists of the fact that all quantities are computed for each triplet (ω, t, z) independently and that a local median is performed a posteriori over a narrow time-pulsation neighborhood. Moreover, it is a remarkable fact that all the calculations related to the wave modeling require the use of a single quantity measured from data: k z (ω, t, z) = ∂φ(ω, t, z)/∂z.

Wavelet based acoustic-gravity wave detection and modeling toolbox

All procedures and programs used to detect and characterize acoustic gravity wave were written and implemented in Matlab, by ourselves. A graphical user interface of this toolbox is implemented for a friendly use and allow easy selection of the structures. This toolbox is available upon request.

Results and discussions

Wave activity

The three solar eclipses are characterized by an increase of the wave-like oscillation in the acoustic-gravity period range during and after the event. This finding is in agreement with other experimental studies ?, ?, ? related to observation of the August 11, 1999 event. However, the amplitudes of the oscillations do not remain at the same level during the whole solar eclipse event. c) and (e)). After removal of these global trends, the residual oscillations are analyzed using the wave detection procedures described above. This reveals that numerous wave-packets are detected propagating within the ionospheric plasma, before, during and after the solar eclipse events. Most observed waves are characterized by periods ranging from 20 minutes to 70 minutes and all of them but one consist of gravity waves. All the detected and analyzed waves are listed in Table ??. They are sorted according to their occurrence time (with respect to the phases of the solar eclipse event). Within data we detected also several waves before the solar eclipse events. These waves we do not report in the paper since they are very probably not related to the solar eclipse. Due to the fact that all three events occur during morning hours and because the performed measurements cover also sunrise hours, such waves can have their origin the Solar Terminator movement. Therefore, waves appearing before first contact of each eclipse event are not presented and further discussed.

Gravity waves

Let us analyze in details three of the detected waves that occur as first propagating structures within the studied height range.

11 August 1999: Gravity wave 1. This is the wave chosen to illustrate the behaviors of the detection and modeling procedures described in Section ?? and in Fig. ). An important property of gravity waves lies in the fact that the phase propagates downward while the wave is moving upward or vice versa. Fig. ?? shows the wavevectors and the vertical components of the phase and packet velocities measured from the data. The positive sign of the packet velocity together with the negative sign of the phase velocity confirm that a gravity wave is found, that propagates upward from altitude 200km. Conversely, the gravity wave propagates downward below 200km. Fig.

?? shows all the wave parameters -wave vector, wavelength, phase and packet velocities, phase and energy angles -characterizing the propagations and derived from acoustic gravity wave theory. The validation for the detection of a gravity wave is highlighted by the difference between energy (α) and phase (Φ) angle which is around 90 degrees. Moreover one notices that these waves propagates along directions close to the diagonals. Characteristic wavelength is found to be around 200 km.

In this case, as in most cases, we find an extremely satisfactory agreement between the z-components of the phase and packet velocities measured from the data and derived from the model. This agreement takes into account Comment 1, made in Section ?? regarding the discrepancy between the measured quantity v z φ and the z-component of the phase velocity v φ,z . These agreements provide us with clear indications confirming the validity of the detection of a gravity wave and a clear validation of the relevance of our combination of measurements made from data and modeling obtained from equations. shows an excellent agreement between estimated and modeled vertical components of the phase velocity. The measured and modeled vertical packet velocities do not match perfectly in the whole range (for reasons discussed in Section ??), however, there is a reasonable agreement with respect to sign and magnitude.

Discussion. Equivalent analyses and plots for each of the detected structures mentioned in Table ?? are available upon request or can be found at http://www.ufa.cas.cz/html/climaero/sauli.html. The study of these structures yields the following comments. The gravity wave activity increases after a notably larger delay for the annular solar eclipse compared to the total solar eclipses: waves are found during maximum phase only for the former while they occur during the initial phase for the latter. This difference in gravity waves generation/occurrence can likely be explained by differences in the terrestrial atmosphere cooling: the border between sunlit and eclipsed region is much sharper in the case of total eclipse. Analyzing wave propagations, we observe predominantly upward propagating structures. The wave structure that propagate upward and downward from the source region located around 200 km height consists of an exceptional case related to the solar eclipse of August 11, 1999. Such a situation does not repeat in any of the two other analyzed events, when the coverage of the solar disk is much lower. This finding might reflect that for the two later events, we mostly observe signatures of the shock wave. For all the detected gravity waves, the values of the energy propagation angles α (Fig. ??, ?? (f) and Fig. ?? (f)) indicate an oblique propagation direction. The difference between energy (α) and phase (Φ) angles, close to 90 degrees, confirm the gravity wave nature of the detected waves. The wave characterisation procedures developed here enable us to discriminate between the waves occurring before the solar eclipses, for instance waves produced by the Solar Terminators at sunrise (?,?), and those induced by the solar eclipse.

Acoustic wave

During the initial phase of the August, 11, 1999 event, we found a line of maxima existing over a large range of heights z and with a period ranging from 3 to 4 minutes (cf. Fig. ??). The identical signs of packet and phase velocities (cf. Fig. ??), together with the propagation period range suggest that this is an acoustic wave. Fig. ?? shows the characteristics of the wave as derived from the model. For this wave, while the agreement between the measured and derived z-components of the phase velocity is very satisfactory, this is not the case for the packet velocity (cf. Fig. ??(e) and (f)). This can be easily understood as the measured packet velocity involves taking an empirical double derivative, at periods (3 -4 minutes) which are extremely close to the sampling period (1 min): this is hence a ill-conditioned numerical operation. This points out a major difficulty in detecting and characterizing acoustic waves: detecting waves, whose periods are of the order of a few minutes, from data collected at sampling rates commonly used, above 1 min, is barely possible and even meaningless ; a relevant tracking of acoustic waves requires the use of sampling periods well below the minute. However, in the 1999 event, the combined use of a wavelet-based time-frequency representation, together with the exceptionally low 1-min sampling period, enables us to unambiguously detect an acoustic wave, which, as far as we know, has very rarely been achieved. Moreover, the use of the equation-based modeling that we proposed here allows us to accurately identify its propagating parameters. For instance, we find that the energy and phase angles are close one from the other as opposed to what is found for gravity waves. For this wave, we also find that the value of the energy angle indicate an oblique propagation of the wave. Hence, despite this sampling rate issue, the modeling of the acoustic wave proposed proves valid and gives satisfactory results.

Conclusions

In the present contribution, we showed that, taking advantage of the excellent joint time and frequency localization properties of the wavelet transform, we are able to detect and characterize wave structures. The detection relies on the identification of a collection of local modulus maxima, occurring simultaneously through a continuous range of heights. From the (derivation) of the phase of the complex wavelet coefficients, we managed to measure the z-components of the wave, phase and packet velocity vectors. Furthermore, making use of the acoustic gravity wave propagation equations, we managed to fully characterize the corresponding propagating parameters. This modeling part only relies on the use of the measured z-component of the wave vector. A key point in our approach lies in the use of sequences of vertical profiles of electron concentration and in the derivation of vertical and horizontal characteristics of the propagating pulse. Making use of this tools, we were able to identify numerous gravity waves and one acoustic wave. Hence, our analysis confirms the occurrence and production of acoustic gravity waves, at ionospheric heights, during solar eclipses. Notably, we observed that for strong amplitude total eclipses AGW occur extremely quickly after the beginning of the event. Also, we highlighted the difficulties in acoustic wave detection and modeling as well as the need for much higher sampling rate when acoustic waves are targeted. We believe that the use of the toolbox proposed here brings significant improvements and benefits with respect to efficient wave detections and can hence be easily used by the ionospheric community.

  Scalograms, corresponding to different altitudes, showing local maxima marked with ('•') are displayed in Fig. ??(a),(c) and (e). The practitioner can make use of a set of tools for visual inspection of the scalograms and for the manual selection of the structure (or maxima line) he wants to analyze. Then, he can zoom in the scalograms around the time and period locations of the chosen structure. This is illustrated in Fig. ??(b),(d) and (f) for the same altitude.

Fig. ? ?

 ? Fig. ?? shows t 0 (z), P 0(z) = 2π/ω 0 (z), k 0,z (z), X 0 (z), v

  Fig. ??(b) shows much larger amplitudes of the fluctuation during the initial phase compared to those occurring after the maximum solar disk occultation. Figs. ??(d) and ??(f) indicate completely different situations: Larger electron concentration oscillation amplitudes are observed after the eclipse maximum and remain present after the fourth contact. Moreover, the two most recent eclipses are characterized by significantly lower magnitudes compared to that of the first one. The decrease of the solar radiation flux is proportional to the magnitude of the eclipse and is reflected in the depletion of the electron concentrations at all ionospheric heights (compare Fig. ??, left column, plot (a) against (

  ??. It was obtained with Paul wavelet (µ = 4). Shortly after the first contact around 9h 20min UT, an upward propagating structure with period about 30 minutes and a downward traveling wave with period about 15 minutes are found. Both of them have a source region located at height 200km. Fig. ?? reports the measurements obtained from the data characterizing these waves. One notices that the downward wave slightly precedes the upward wave (Fig. ?? (a)) and that the maximum amplitude of the upward wave is located around 240km (see Fig. ?? (c)

3

  October 2005: Gravity wave 1. For the 3 October 2005 event, the first detected wave structure occurs at 9h 12min, close to the eclipse maximum (see Fig. ??(a)), computed using Paul wavelet (µ = 6). This gravity wave with period about 43 minutes (Fig. ??(b)) propagates upward between 155 km and 200 km (as seen from the positive packet velocity and negative phase velocities (cf. Fig. ??(e) and (f))). Wave amplitude maximum appears to be at height 180 km. Fig. ?? illustrates the complete propagation characteristics of the gravity wave. Its wavelength is found to be around 200 km (Fig. ??(d)). 29 March 2006: Gravity wave 1. For the 29 March 2006, inspection of the wavelet power spectrum (computed using Paul wavelet (µ = 6), cf. Fig. ??(a)) indicates that a well developed structure is observed 14 minutes only after the first contact. This structure propagates through the lower part of the analyzed ionospheric region, from 160 km up to 205 km, with a period around 30 minutes (Fig. ??(b)). It reaches its maximum amplitude at height around 190 km (Fig. ??(c)).

  Fig. ??(d) shows the vertical component of the wave vector. The values of the z-components of the phase (negative) and packet (positive) velocities obtained from the data indicate that we observe an upward propagating gravity wave (cf. Fig. ??(e) and (f)). The complete set of propagation parameters is illustrated in Fig. ??(a)-(f).

  Fig. ??(b)

Fig. 1 .Fig. 2 .Fig. 3 .Fig. 4 .Fig. 5 .Fig. 6 .Fig. 7 .Fig. 8 .Fig. 9 .

 123456789 Fig. 1. 3-hour Kp index. Geomagnetic activity during three solar eclipses events. The grey shaded areas indicate occurrences time of the eclipses.

Fig. 10 .Fig. 11 .Fig. 12 .

 101112 Fig. 10. Scalograms, 11 August 1999. Examples of three scalogram plots at three consecutive heights 200km (a) and (b); 195 km (c) and (d); and 190 km (e)and (f). In left column, the time range is selected to cover the initial solar eclipse phase. Local maxima line are marked with "•".. Between 10h UT and 10h20min UT, there is well developed local maxima ,marked with a "• ", that coincides in time and period over a significant range of heights zs. Panels (b), (d) and (f) represent the focus on this maxima in the acoustic mode period range 2-6 minutes around 10H15min UT.

  Parameters of the solar eclipse events. parameters as observed above Průhonice ionospheric station, (According to NASA database, time is given in UT).

	Event	First contact Fourth contact Maximum Magnitude
	11 Aug 1999	09:22	12:04	10:42	0.952
	3 Oct 2005	08:01	10:32	09:15	0.539
	29 Mar 2006	09:46	11:50	10:48	0.486
	Table 1

Table 2

 2 Detected waves. List of the detected and analyzed waves with occurrence period and time (with respect to the eclipse phase). Period of the wave denotes dominant period of the structure.

	Event	name	Period	Occurrence	Propagation
		GW1 15 min, 30 min	Initial	upward/downward
	11 August 1999	AW1	3-4 min	Initial	upward/downward
		GW2	22 min	After	upward
		GW1	43min	Maximum	upward
		GW2	20min	Recovery	upward
	3 October 2005	GW3	65min	After	upward
		GW4	30min	After	upward
		GW5	32min	After	upward
		GW6	22min	After	upward
	29 March 2006	GW1	30min	Initial	upward
		GW2	40min	After	upward

Acknowledgment : This work has been supported by the Grant 205/06/1619 of the Grant Agency of the Czech Republic, Grant IAA300420504 of the Grant Agency ASCR and the joint Grant from French CNRS and Czech ASCR 18098).


Victorien Elvinger
email: victorien.elvinger@loria.fr

Gérald Oster

François Charoy

Prunable Authenticated Log and Authenticable Snapshot in Distributed Collaborative Systems

Keywords: Authenticated log, Prunable log, Authenticated snapshot, Distributed collaborative systems, Dynamic group, Consistency, Convergence, Causal Stability, View-Fork-Join-Causal

In distributed collaborative systems, participants maintain a replicated copy of shared documents. They edit their own copy and then share their modifications without any coordination. Copies follow successions of divergence and convergence. Convergence is a liveness property of collaborative systems. Some malicious participants may find an advantage to make the collaboration fail. To that end, they can preclude convergence of the copies.

To protect convergence of copies, participants can exploit an authenticated log of modifications. New participants have to retrieve the entire log in order to contribute. Unfortunately, the cost of joining a collaboration increases with the size of this log. Causal Stability allows to prune authenticated logs in a static collaborative group without any malicious participants.

In this paper, we first tailor Causal Stability to dynamic groups in presence of malicious participants. We then propose a mechanism to verify the consistency of a pruned log and a mechanism to authenticate a snapshot from a pruned log.

I. INTRODUCTION

Modern collaborative systems enable participants to coauthor shared documents. They rely on optimistic replication algorithms [START_REF] Saito | Optimistic Replication[END_REF] which support concurrent and conflicting edits of these documents. Participants hold their own copy of documents. They edit it locally before sharing their modifications with others. Thus, we witness successions of divergence and convergence between copies [START_REF] Dourish | The Parting of the Ways: Divergence, Data Management and Collaborative Work[END_REF]. Convergence of copies confirms the propagation of the participants' modifications. It guarantees the progression of the collaboration. Hence, convergence is a liveness property for collaborative systems. If the system is unable to ensure convergence of copies, the collaboration is prone to failure. Sometimes, participants to a collaborative endeavor can find an advantage to make it fail. They could achieve that by making sure that two groups of participants maintain divergent views on a document. We need to ensure that it is not possible at a cost that is sustainable for the different stakeholders.

A solution used in operation-based replication is to authenticate the log of operations. Participants compare their respective logs to figure out which contributions they miss. Thus, honest participants will eventually get the same set of contributions and convergent logs. Combined with a concurrency and conflict resolver [START_REF] Saito | Optimistic Replication[END_REF][START_REF] Shapiro | Conflict-Free Replicated Data Types[END_REF][START_REF] Ellis | Concurrency control in groupware systems[END_REF], copies of honest participants will eventually converge. In collaborative systems, new participants can join at any time. In order to obtain the current document state and contribute on it, they have to retrieve an authenticated log from a participant and verify its authenticity. Thus, the cost of joining a collaboration linearly grows with the size of the log. Furthermore, all participants have to store the log to be able to invite new participants in the group. Performance degrades as the size of the log increases. Reducing the footprint of authenticated logs in dynamic collaborative groups remains an important problem. One way to achieve that is to prune the log to maintain the cost at an acceptable level. Authenticated logs rely on consistency models [START_REF] Viotti | Consistency in non-transactional distributed storage systems[END_REF] which define how contributions can be related to each other. Causal Stability [START_REF] Baquero | Making Operation-Based CRDTs Operation-Based[END_REF] enables us to safely prune causal-consistent logs in static groups. Once a contribution is stable, participants have the guarantee that all participants included it in their log. They cannot issue a new contribution concurrently to a stable one.

In this paper, we propose to adopt the same strategy but with dynamic groups and in presence of an active adversary. To this end, we first adapt Causal Stability to dynamic groups. Then, we propose a consistency model that enables stabilization. Our consistency model is specified under the perspective of a log and relies on View-Fork-Join-Causal (VFJC) consistency model [START_REF] Mahajan | Consistency, Availability, and Convergence[END_REF]. In the literature, VFJC is considered the strongest achievable consistency model in a distributed collaborative system with an active adversary. We define when a contribution is stable in our Stabilizable VFJC log. We design a mechanism to check the consistency of a pruned log. To illustrate the value of our stabilizable and prunable log, we propose a mechanism to authenticate a document snapshot from a pruned log.

II. SYSTEM AND ADVERSARY MODELS

In this section, we introduce distributed collaborative systems along with basic notations. Then, we model the adversary of the system. Next, we present the definition of VFJC under the perspective of an authenticated log. Last, we illustrate the use of a VFJC log by the means of an example.

A. Distributed collaborative systems

Distributed collaborative systems support collaborative activities without a central server. A collaborative activity involves a group of participants that contribute to a common work. A group has a finite and evolving number of participants. They can leave and join the collaboration at any time. We denote P the set of participants. P = {P 1 , . . . , P i , . . . , P N }. Each participant owns an asymmetric signing key pair [START_REF] Salomaa | Public-Key Cryptography[END_REF].

P is partitioned when there is no network connection between subsets of participants. A participant in a singleton is said to be offline. Subsets evolve depending on the status of their connection. The system is always-available [START_REF] Mahajan | Consistency, Availability, and Convergence[END_REF] such that every participant can contribute to the common work at all time. To this end, each participant holds a copy of shared data. This is a sticky availability model [START_REF] Guerraoui | Trade-offs in Replicated Systems[END_REF]. S i t denotes the state of the copy held by a participant P i at a discrete time t.

Participants apply contributions such as insertions and deletions on their own copy. c i j denotes the j-th contribution of P i . c i denotes any contribution of P i . Participants eventually share their contributions to the rest of the group via an asynchronous network [START_REF] Lynch | Distributed Algorithms[END_REF] without any coordination.

Always-availability leads to concurrent contributions and then conflicts [START_REF] Mens | A State-of-the-Art Survey on Software Merging[END_REF]. As previous works [START_REF] Weilbach | Decoupling Conflicts for Configurable Resolution in an Open Replication System[END_REF][START_REF] Mahajan | Consistency, Availability, and Convergence[END_REF], we delegate the handling of concurrencies and conflicts to the application [START_REF] Saito | Optimistic Replication[END_REF][START_REF] Shapiro | Conflict-Free Replicated Data Types[END_REF][START_REF] Ellis | Concurrency control in groupware systems[END_REF]. Causality tracking [START_REF] Lamport | Time, Clocks, and the Ordering of Events in a Distributed System[END_REF] exposes concurrencies between contributions. Instead of tracking every causal relation, we can only expose immediate dependencies [START_REF] Prakash | An Adaptive Causal Ordering Algorithm Suited to Mobile Computing Environments[END_REF][START_REF] Pomares Hernández | The Immediate Dependency Relation: An Optimal Way to Ensure Causal Group Communication[END_REF][START_REF] Pomares | The Minimal Dependency Relation for Causal Event Ordering in Distributed Computing[END_REF]. Definition 1 introduces related notations. We assume that the contributions are causally delivered. Although the application decides how to resolve conflicts, we assume strong convergence [START_REF] Viotti | Consistency in Non-Transactional Distributed Storage Systems[END_REF][START_REF] Shapiro | Conflict-Free Replicated Data Types[END_REF]: Two participants who play the same set of contributions get an identical state without any further coordination.

Definition 1 (Causality). We write a → b, if and only if a (causally) precedes b. We also said that b depends on a. "→" is a strict partial order. Two contributions a and b are concurrent, denoted a b, if and only if neither precedes the other. b immediately depends on a, denoted a ↓ b, if and only if there does not exist a contribution c such that a precedes c and c precedes b.

a ↓ b ⇐⇒ a → b ∧ ( c • a → c → b) (Immediate Dep.) a b ⇐⇒ a = b ∧ a → b ∧ b → a (Concurrency)

B. Adversary model

We consider a Byzantine adversary [START_REF] Lamport | The Byzantine Generals Problem[END_REF]. The adversary controls an unbounded number of malicious participants. They can collude together. The adversary has also an extended control over network. She is able to alter, discard, duplicate, or reorder messages. She can partition the set of honest participants. However we assume the following limitations:

• She has limited resources, both in time and computational power. These resources are not sufficient to break the cryptographic primitives used, such as collision-resistant hash functions and digital signatures. • She cannot prevent an honest participant from authenticating the public key of another honest participant. • She is not able to prevent honest participants from eventually exchanging an unbounded number of messages. The adversary aims at permanently prevent honest participants from eventually converging to the same state of shared data.

C. VFJC log as threat mitigation

Authenticated logs [START_REF] Mahajan | Depot: Cloud Storage with Minimal Trust[END_REF][START_REF] Truong | Authenticating Operationbased History in Collaborative Systems[END_REF] make misbehaviors evident. An authenticated log contains all participants' contributions along with their dependencies. Each contribution embeds the identifiers of its immediate dependencies. To make the log tamper-evident, the identifier of a contribution includes its collision-resistant hash and a contribution is digitally signed with the private key of its author.

H i t denotes the append-only log of a participant P i at a discrete time t. For all t, H i t is a sublog of H i t+1 . Figure 1 presents a representation of an authenticated log. If there exists a directed edge from a first contribution to a second one, then the second contribution immediately depends on the first one.

c A 1 c A 2 c B 1 c B 2 Figure 1. Authenticated log of Alice (P A ). Alice generates a first contribution c A 1 at discrete time t = 1. H A 1 = c A 1 . Then, she generates c A 2 such that c A 2 depends on c A 1 . H A 2 = c A 1 ↓ c A 2 .
Alice receives and delivers c B 1 , the first contribution of Bob (P B ). c B 1 is concurrent to c A 2 and depends on c A 1 .

H A 3 = c A 1 ↓ c A 2 , c A 1 ↓ c B 1 .
Then, she receives and delivers c B 2 , the second contribution of Bob.

H A 4 = c A 1 ↓ c A 2 , c A 1 ↓ c B 1 , c A 2 ↓ c B 2 , c B 1 ↓ c B 2 .
Given an authenticated log, any honest participant can figure out who misbehaves from a set of rules. At the log level, the rules are summarized with a consistency model [START_REF] Viotti | Consistency in non-transactional distributed storage systems[END_REF]. It restricts how contributions can be related. In the literature, VFJC is the strongest achievable consistency model in an always-available and convergent system in presence of a Byzantine adversary.

In VFJC, a participant is considered malicious only if she issues two or more contributions that are concurrent with themselves. To distinguish them from allowed concurrent contributions, i.e. those authored by distinct authors, we refer to them as non-linear1 . Definition 2 defines when a participant is provably malicious. Definition 2 (Provably malicious). If a VFJC-consistent log has at least two non-linear contributions, then their author is provably malicious. Given a contribution c, provablyMalicious(c) gives all provably malicious participants in the sublog that only includes c and all contributions that precede c.

provablyMalicious(c) = P k | ∃(c k l c k m ) → c
By issuing non-linear contributions, a malicious participant creates concurrent branches of contributions called forks [START_REF] Viotti | Consistency in Non-Transactional Distributed Storage Systems[END_REF][START_REF] Mazières | Building Secure File Systems out of Byzantine Storage[END_REF]. The acceptance of forks in a log may raise difficult conflicts to resolve. VFJC limits the number of accepted forks according to the number of malicious participants.

Definition 3 presents VFJC under the abstraction of a log. Each honest participant maintains a VFJC log. This definition is different from the original one in the following aspects:

• VFJC was specified for distributed storage systems where several data are concurrently modified. In our system model, participants collaboratively edit a single data. • VFJC consistency model uses real-time dates to prevent a past contribution from depending on a future one. We assume that the causal delivery layer enforces this.

Definition 3 (VFJC log). Let a VFJC log H i t = (Contrib i t , →) from an honest participant P i at a discrete time t. H i t is a locally finite partially ordered set (poset). Contrib i t is the set of accepted contributions for P i at time t. '→' is a strict partial order with the following extra properties: L1 (per-participant linear ordering) P i , the owner of H i t , linearly orders her own contributions.

∀c i k ∀c i l • c i k → c i l ⇐⇒ k < l L2 (
proper generation -causality tracking) Every contribution of P i , the owner of H i t , depends on all contributions of the log in which it was appended.

∀c i ∃t • H i t +1 -H i t = c i ∧ ∀x ∈ H i t •
x → c i L3 (sharing with no provably malicious) If there exists an immediate dependency relation between two contributions, then none of these contributions is authored by a provably malicious participant in the sublog that only contains them and all contributions that precede them.

∀c k ↓ c l • P k , P l ∈ provablyMalicious(c l )

L4 (appendable -sharing with no provably malicious)

There does not exist a pair of non-linear contributions such that one is among the latest contributions.

∀c k l • c k m c k l ∧ c k m ∈ latest i t where latest i t = {x | y • x → y} D. Motivating example
Suppose a team of volunteers, including Alice and Mallory, who organize an event. Alice creates a shared document and invites few team members to contribute to it. Each year, opponents try to disturb the event. Since the organizing team is open, malicious people, such as Mallory, can join the team. In order to protect convergence against misbehaviors, the document is secured thanks to a VFJC log.

Alice, Mallory, and other members participate in several editing sessions. The document contains minutes, reports, and a poll to know who is coming on the 4th of May, the date of the event. The log grows and all participants get a convergent log. Alice invites Bob in the editing group.

Figure 2 represents the part of the log of the collaboration when Bob is invited and can join the group. Alice (P A ) invites Bob (P B ) and ask collaborators to fill the poll. c A 1 sums up these actions. Bob joins the group thanks to Mallory (P M ). Mallory attempts to mislead Bob about the date. She modifies the date to the 8th of March and only shares this modification c M 2 with Bob. In the meantime, she confirms with c M 1 her availability on the 4th of May to Alice. Bob has the wrong date and then confirms with c B 1 his attendance on the 8th of March. Upon reception of c B 1 , Alice is aware that Bob has not the same causal context as hers. Given c M 2 , she figures out the misbehavior of Mallory. At the end of the depicted session, honest participants, Alice and Bob, get a convergent log and stop communicating with Mallory. Note that they stop communicating with Mallory as soon as they figure out her misbehavior: upon delivery of c B 1 for Alice, and c A 2 for Bob.

P A P M P B c A 1 c M 1 c M 2 c B 1 c A 2 c B 2 (a)
Dashed arrows are transmissions of one or more contributions.

c A 1 c M 1 c A 2 c M 2 c B 1 c B 2 (b)
A VFJC log with a fork junction at c B 2 . Figure 2. (a) A collaborative session and (b) the VFJC log of honest participants (Alice P A and Bob P B ) after their convergence. Mallory (P M ) issues two non-linear contributions (c M 1 c M 2 ). She is provably malicious.

In their respective VFJC log, honest participants linearly order their own contributions (property L1) and expose the dependencies of their contributions (property L2). The linear order matches the order of generation, and the dependencies of a contribution are all contributions observed before the time of its generation. Since they send their contributions along with their dependencies, these orders are preserved. Hence, in any VFJC log, the contributions of every honest participant are linearly ordered and expose their dependencies. In the example,

c A 1 precedes c A 2 (c A 1 → c A 2 ) and c B 1 precedes c B 2 (c B 1 → c B 2 ). c B 1
depends on c A 1 and c M 2 ; while c B 2 depends on all contributions. Although c B 1 is received before the generation of c A 2 , c A 2 does not depend on it. According to the log, c A 2 depends only on c A 1 and c M 1 . We explain this behavior in following paragraphs. Mallory authors two non-linear contributions c M 1 c M 2 and thus breaks with property L1. From the point of view of an honest participant, another participant is not known to be malicious until misbehaviors are observed. Indeed, Alice and Bob do not know the misbehavior of Mallory when they receive respectively c M 1 and c M 2 . Since they have no proof that the received contribution is a non-linear one, they optimistically append it to their log. Alice and Bob hold two distinct forks.

Upon reception of c B 1 , Alice figures out the misbehavior of Mallory. Since Bob is not known to be malicious, Alice unavoidably accepts the fork c M 2 ↓ c B 1 . However, if Alice appends this fork to her current log, she risks compromising her availability. Indeed, under L3, Alice is not able to directly join two forks, i.e. her next contribution cannot both depend on non-linear contributions (c M 1 and c M 2 ) and immediately depends on one of them (c M 1 ). However, in accordance with L2, a contribution must properly expose its dependencies and then must depend on c A 1 , c B 1 , and the two non-linear contributions c M 1 and c M 2 . This contradiction leads to an impossibility to author new contributions.

L4 avoids this availability issue. Following L4, it is not possible to have two non-linear contributions such that one of them is at the end of the log. Since it is not conceivable to demand that Alice contribute each time that the situation is met, VFJC introduces special contributions called views. Before the integration of c

M 2 ↓ c B 1 , a view c A 2 is appended. Upon reception of c A 2 , Bob accepts the fork c M 1 ↓ c A 2 .
L4 is fulfilled and then he does not need to issue a view. Bob's next contribution joins the two forks. All contributions that depend on a fork junction, including the junction itself, act as a proof of knowledge. Given such a contribution, we deduce that its author agrees on the fact that Mallory misbehaved. No more contributions of Mallory can be honestly accepted. Mallory is thus evicted of the group.

III. LOG STABILITY

In this section, we explore the concept of log stabilization. The log is divided into a stable part and an unstable part. The stable part includes only stable contributions. A contribution is stable once no more contributions concurrent to the included contributions can be appended to the log.

This section proposes to seek stability in dynamic groups and in presence of the adversary. We first assume the absence of an active adversary and tailor Causal Stability to dynamic groups. Then, we show that VFJC is not stabilizable in presence of malicious participants. Based on VFJC, we define a stabilizable log and View-Fork-Join-Causal Stability (VFJCS).

As stable contributions remain stable forever, they can be safely dropped from the log, we will make use of VFJCS to define a log pruning mechanism in the next section.

A. Provable Causal Stability in dynamic group

Causal stability [START_REF] Baquero | Making Operation-Based CRDTs Operation-Based[END_REF] was defined in the context of static group and in absence of an adversary. Here, we tailor this concept to dynamic groups and we assume that all participants are honest.

A contribution is causally stable once all participants of the group have provably observed it. A participant provably observes a contribution if and only if she issues at least one contribution that depends on it. A convenient way to infer causal stability of a contribution is to show that no more concurrent contributions can be accepted. In dynamic group, participants join and leave the group at any time. A participant has an uncertain knowledge of the group composition. When a contribution is generated, it is therefore not possible to know all participants who are able to issue concurrent contributions.

In order to join and contribute to a collaboration, a newcomer has first to retrieve the log from another participant. Following L2, the newcomer inherits of all observations of that participant. If the participant has already observed a given contribution, then the newcomer cannot issue concurrent contributions. Conversely, if the participant has not already observed a contribution, then the newcomer may issue a concurrent contribution.

To determine who sent her log to a newcomer, we add a tracking mechanism based on invitations. To invite a newcomer, a participant issues an invitation. An invitation is a special type of contribution. invitedIn(c) gives all participants invited in c. An invitation embeds public keys of the invited participants. For convenience, we introduce previouslyInvited H :

previouslyInvited H (c) = {invitedIn(x) | x → c}
A newcomer cannot contribute if he was not invited. To enforce this rule, we require that the author of a contribution had been invited in a preceding contribution. This rule does not apply for the initiator of the collaboration. Indeed, she issues a first contribution in which she is self-invited. It follows that every contribution, except the first one, has at least one immediate dependency. The log is bounded-below and its bottom element ⊥ is the first contribution.

∀c k = ⊥ • P k ∈ invitedIn H (c k ) (self-invited) ∀c k = ⊥ • P k ∈ previouslyInvited H (c k ) (previously invited)
If the invitation of a new participant depends on a given contribution, then this participant can only issue contributions that depend on it. Conversely, if an invitation of a new participant precedes or is concurrent to a given contribution, then the participant may issue concurrent contributions. Participants who may issue concurrent contribution to a given contribution are required observers of the contribution. If all required observers of a contribution observe it, then the contribution is causally stable.

However required observers of a contribution can leave the collaboration. They may never observe the contribution. The contribution would never be stable. We need to take departures into account. A participant can leave the collaboration by requesting to be evicted. In order to evict someone, a participant issues an eviction. An eviction is a special type of contribution. evictedIn(c) gives all participants evicted in c. Definition 4 names the participant evicted in a contribution c and in preceding evictions, the known evicted of c. Definition 4 (Known evicted). Let a contribution c from a VFJC log H i t . A participant is a known evicted in c if and only if she is provably malicious or she is evicted in the sublog that contains only c and predecessors of c.

evicted H (c) = {evictedIn(x) | x → c ∨ x = c} ∪ provablyMalicious(c)
The acceptance of contributions whom the author was evicted follows consistency rules adapted from L3 and L4:

∀c k ↓ c l • P k , P l ∈ evicted H (c l ) (sharing with no evicted) ∀c k , c j ∈ latest i t • P k ∈ evicted H (c j ) (appendable)
An evicted participant cannot issue a contribution that depends on contributions that know her eviction. Thus known evicted of c are not required observers of c.

Required observers of a contribution can also be evicted in concurrent or following contributions. For the sake of simplicity, we consider only known evicted participants in following contributions. Only participants who have not yet provably observed a contribution e in which participants are known as evicted can directly accept contributions from these evicted participants. If all required observers of e have provably observed it, then it is no longer possible to accept contributions of known evicted participants of e. e is causally stable. All known evicted participants in a causally stable contribution are no longer required observers. Definition 5 summarizes which participants are required observer of a contribution.

Definition 5 (Required observer). Let a contribution c from a VFJC log H i t . A required observer of c is either a participant invited in an invitation that precedes c or a participant invited in a concurrent invitation of c. All known evicted participants in c and in provably causally stable contributions that follow c are not required observers.

requiredObs H (c) = {invitedIn(x) | x c} ∪ previouslyInvited H (c) -evicted H (c) -{evicted H (x) | c → x ∧ isProvablyCausallyStable(x)}
Under L1, honest participants linearly order their contributions. Thus if a participant issues a contribution which depends on another one, then she cannot issue a new contribution concurrent to these contributions. Thus a contribution is causally stable as soon as there exists proofs that its required observers have observed it.

The original definition of Causal Stability takes the implicit observation of the owner of the log into account. Thus, it is possible to have two identical logs in which the set of causally stable contributions is not identical. Since new participants retrieve and verify the log from other participants, it is important to define the stability of a contribution regardless of the initial owner of the log. We discuss more about this in section IV. Definition 6 defines Provable Causal Stability (PCS) which tailors Causal Stability to dynamic groups and removes implicit observations. Figure 3 shows how invitations interact with the provable causal stability status of a contribution. Definition 6 (Provable Causal Stability). In a VFJC log H i t , a contribution is provably causally stable if and only if all required observers have provably observed it.

isProvablyCausallyStable H (c) = requiredObs H (c) ⊆ provablyObs(c) where provablyObs(c j ) = {P j } ∪ P k | ∃ c k • c j → c k B. Stabilizable-View-Fork-Join-Causal log
A malicious participant can issue a new contribution that is non-linear with one of her past contributions. If all participants provably observed past contributions, then following L3 and L4, they cannot honestly accept this new contribution.

However, any participant can invite someone. A malicious participant can issue an invitation which is non-linear with The participation of newcomers in a fork leads to its acceptance by honest participants. Thus, it is always possible to have a concurrent contribution to another one. Log stabilization implies that at some point, contributions become stable, i.e. it is no longer possible to accept contributions that are concurrent to them. Hence, a VFJC log is not stabilizable in a dynamic group and in presence of malicious participants.

c A 1 c A 2 c B 1 c B 2 c C 1 pcs pcs {P A , P B } {P C } {P D } Figure 3. Upon generation of c A 2 ,
To stabilize a VFJC log, we have to reject forks that include only contributions of provably malicious participants and those of participants invited in the fork. This includes transitively invited participants. To simplify the expression of this property, we disable concurrent invitations of an identical participant. This can be obtained by including the collision-resistant hash of the invitation in the generated identifier of the participant. e.g. in Figure 3, the identifier of Carol consists in her public key and the hash of c B 1 . The owner of the public key can still be concurrently invited. He is attached to several participants.

A convenient way to reject these forks is to accept only contributions whom the author is known as participant both in concurrent branches of the contribution and in its immediate dependencies. In Figure 4, Franck is not known to participate in c B 20 . c B 20 is the latest contribution of a branch that is concurrent to c F 1 . Thus c F 1 is not acceptable. To accept a contribution whom the author is unknown in concurrent branches, honest participants have first to accept the contribution that invites him. In our example, honest participants have to accept c M 2 . Following L3 and L4, they cannot accept the non-linear contribution c M 2 . Thus, they cannot accept the fork c M 2 ↓ c F 1 . Definition 7 (Known participants). Let a contribution c from a VFJC log H i t . participants(c) gives all invited participants in the sublog that includes only c and all contributions that precede c. Evicted participants in this sublog are not included.

participants H (c) = previouslyInvited H (c) ∪ invitedIn(c) -evicted H (c)
∀c • evictedIn(c) ⊂ {participants H (x) | x ↓ c}
L6 (sharing with no evicted) If there exists an immediate dependency relation between two contributions, then neither is authored by an evicted participant in the sublog that contains only them and all contributions that precede them (Implies L3).

∀c k ↓ c l • P k , P l ∈ evicted H (c l )
L7 (sharing with known participants) The author of c has to be known as participant in immediate dependencies of c. The author of an immediate dependency of c has to be known as participant in every immediate dependency of c.

∀c k ↓ c l ∀c j ↓ c l • P l , P k ∈ participants H (c j )

L8 (appendable -sharing with known participants)

The author of every latest contribution has to be known as participant in all latest contributions. The owner of the log has to be a known participant of all latest contributions. This also excludes contributions whom the author is evicted.

∀c k , c j ∈ latest i t • P i , P k ∈ participants H (c j ) where latest i t = {x | y • x → y}
To illustrate the addition of SVFJC, we consider Figure 5 as an example. Under L8, an honest participant cannot accept a contribution in which the author is not known as participant in latest contributions of her log or a contribution which does not include in its known participants the authors of latest contributions. c A 2 does not include Carol in its known participants. Under L8, it is not possible to maintain a log such that both are latest contributions. 3 fulfills these requirements. To enable stabilization, SVFJC logs reject forks in which new participants have contributed. This limits the availability of the system for these new participants. The application can use additional consistency rules to mitigate this issue. For instance, an invitation could be consistent only if it is accepted by a subset of trusted participants (author of the document, moderators, . . . ). This is out of scope of this paper.

c A 1 c A 2 c B 1 c C 1 c A 3 {P A , P B } {P C } (a) Alice's SVFJC log. c A 1 c A 2 c B 1 c C 1 c B 2 {P A , P B } {P C } (b) Bob's SVFJC log.

C. View-Fork-Join-Causal Stability

In presence of malicious participants, Provable Causal Stability is insufficient to stabilize a SVFJC log. Figure 6 shows a scenario in which a contribution is provably causally stable, when in the meantime, another honest participant accepts a contribution that is concurrent to this contribution.

Only participants that have not provably observed a contribution c can directly accept a non-linear contribution of c. Hence, it is not possible to accept a non-linear contribution of c when c is provably causally stable. We say that the author of c is a provably linear observer of the sublog that contains only c and all contributions that precede c. Definition 9 defines the provably linear observers of a given contribution. Definition 9 (Provably linear observer). Let a contribution c of a SVFJC log H i t . A provably linear observer of c is a participant who is the author of at least one provably causally stable contribution that depends on c. isProvablyCausallyStable H (c k )}

provablyLinearObs H (c) = {P k | ∃c k = c ∨ c → c k • c A 1 c B 1 c M 1 c A 2 pcs pcs {P A , P B , P M } (a) Alice's SVFJC log. c A 1 c B 1 c M 2 c B
In a SVFJC log, a contribution is stable once it is no longer possible to honestly accept contributions that are concurrent to it. Hence, a contribution is stable if and only if all required observers of the contribution are also provably linear observers. Definition 10 names a stable contribution, a view-fork-joincausally stable contribution. Figure 7 illustrates how the collaboration of Figure 6 may evolve.

Definition 10 (View-Fork-Join-Causal Stability). In a SVFJC log H i t , a contribution is view-fork-join-causally stable if and only if all required observers are provably linear observers.

isVFJCStable H (c) = requiredObs H (c) ⊆ provablyLinearObs H (c) c A 1 c B 1 c M 1 c A 2 c M 2 c B 2 c A

IV. PRUNED LOG

In this section we describe how to prune the log and to verify its consistency. We first augment contributions in order to reduce the scope in which honest participants perform consistency verifications. Then we analyze which contributions can be dropped without hurting consistency verifications.

A strategy to prune the log is to remove as much as possible contributions. Only the contributions that are necessary to maintain the future consistency of the log must be kept. If an honest participant receives or generates a contribution, she must be capable of verifying its consistency with the log.

Before appending a contribution to her log, an honest participant verifies that properties L4, L5 (implies L3), L6, L7, and L8 hold. This verification requires the entire log or a sublog that includes the contribution and its predecessors. To remove contributions of the log, we have to reduce the size of the sublog in which its properties are verifiable.

These properties rely directly or indirectly on the functions evicted H and previouslyInvited H . We propose to embed their result in every contribution. In practice, authenticated logs enable these data to be efficiently stored. evicted h and previouslyInvited h are the embedded versions of these functions. These changes enable the verification of all properties and the verification of the stability of a contribution in a sublog that contains only the appended contribution, its immediate dependencies, and all branches that are concurrent to at least one immediate dependency.

As seen in subsection III-C, a participant cannot honestly accept a concurrent contribution to a stable (view-fork-joincausally stable) contribution. It follows that we can remove every stable contribution, except when an unstable contribution may depend on it. For example, in Figure 7,c A 1 and c M 2 precede stable contributions. They are thus removable.

Definition 11 (SVFJC pruned log). A log h i

t is a SVFJC pruned log if and only if: P1 (stable base) Every contribution of the base of the pruned log is stable.

∀ c k ∈ base(h) • isVFJCStable h (c k ) where base(h) = x ∈ h | ∃y ∈ deps(x) ∧ y ∈ h j t P2 (well-formed unstable contributions) Every unstable contribution is well-formed. ∀ ¬ isVFJCStable h (c k ) • isWellFormed (c k ) P3 (per-participant linear ordering) Similar to L1 ∀c i k ∀c i l • c i k → c i l ⇐⇒ k < l P4 (proper generation) Adaptation of L2 ∀ ¬ isVFJCStable h (c i ) ∃t • h i t +1 -h i t = c i ∧ ∀x ∈ latest i t • x ↓ c i
P5 (appendable -sharing with no provably malicious) Similar to L4

∀c k l • c k m c k l ∧ c k m ∈ latest i t P6 (appendable -sharing with known participants) Adaptation of L8 ∀c k , c j ∈ latest i t • P i , P k ∈ participants h (c j )
Definition 12 enumerates all consistency verifications that are locally performed on a contribution. Based on this definition, Definition 11 defines the consistency of a pruned log. deps(c) provides the identifiers of the immediate dependencies of c. Definition 12 (Well-formed contribution). Let a SVFJC pruned log h i t from a SVFJC log H i t with ⊥ the bottom contribution. A well-formed contribution c k (we write isWellformed (c k )) respects the following properties: W1 (bottom identity) The contribution is either the bottom element or an intermediate contribution. An intermediate contribution has at least one dependency.

c k = ⊥ ∨ deps(c k ) = ∅
W2 (no transitive dependencies) The contribution exposes only its immediate dependencies. ∀x, y ∈ deps(c k ) • x y W3 (known evicted) Previously evicted participants, new evicted participants, and new provably malicious participants are the only known evicted participants of the contribution.

evicted h (c k ) = evicted h (x) | x ∈ deps(c k ) ∪ evictedIn(c k ) ∪ provablyMalicious(c k )
W4 (sharing with no evicted participants) Authors of the contribution and of its immediate dependencies are not known as evicted in the contribution.

∀c j ∈ deps(c k ) • P j , P k ∈ evicted h (c k )
W5 (Previously invited) Previously invited participants in c k correspond to previously invited participants and newly invited participants in all immediate dependencies of the contribution.

previouslyInvited h (c k ) = {previouslyInvited h (x) ∪ invitedIn(x) | x ∈ deps(c k )}
W6 (sharing with known participants) The author of c k is known as participant in all immediate dependencies. The author of every immediate dependency of c k is known as participant in all immediate dependencies of c k .

∀c j , c l ∈ deps(c k ) • P l , P k ∈ participants h (c j )
W7 (evicting only existing participants)

evictedIn(c k ) ⊂ participants h (x) | x ∈ deps(c k )
An honest participant is able to prune her log without hurting its future consistency or its availability. She can receive a new contribution and verify its consistency. She can also generate new consistent contributions. Because we define stability such that it is independent of the owner of the log, any participant can verify the consistency of a pruned log. Thus new participants can retrieve a pruned log and verify its consistency. Because contributions are missing, they cannot verify whether all contributions are well-formed. They have to trust verifications carried out by other participants. Every stable contributions are considered well-formed. If a new participant retrieves a pruned log, he is not able to obtain the current state of the document. Next, we propose to retrieve a pruned log with an untrusted snapshot and to authenticate the snapshot from the pruned log.

V. AUTHENTICATED SNAPSHOT

In this section we propose to authenticate an untrusted snapshot of the document with a SVFJC pruned log. To do that we augment invitations with state fingerprints.

When a collaboration starts, the log contains a single contribution. This first contribution ⊥ is an invitation that invites the first participants. Each time a contribution is appended to the log, the contribution is played on the local copy of the shared document. Some contributions, such as views, invitations, and evictions, make no change to the state.

We say that a state S i t and a log H i t are consistent if and only if the causal execution of every contribution of H i t on the empty state S 0 gives S i t . Note that there exists several sequences of causal execution when the log contains concurrent contributions. In subsection II-A we assume strong convergence [START_REF] Viotti | Consistency in Non-Transactional Distributed Storage Systems[END_REF][START_REF] Shapiro | Conflict-Free Replicated Data Types[END_REF]. This guarantees that every sequence of causal execution produces the same state. undo(Contrib, S) causally undoes a set of contributions Contrib on a state S.

Under L8, the latest contributions of a SVFJC log must include the owner of the log as known participants. An honest newcomer accepts only SVFJC-consistent pruned logs. Thus he must be a known participant in every latest contribution of the log. As long as a participant has not contributed to the collaboration, the contribution that invites him is unstable. Consistent pruned log includes all unstable contributions. It follows that the contribution that invites this newcomer is part of a consistent pruned log.

We are certain that an honest newcomer will observe the contribution that invites him. We can embed information to authenticate a snapshot in this contribution. When a participant invites a newcomer, she computes the fingerprint of the current state of the document and embeds it in the invitation. This fingerprint is a collision-resistant hash. fingerprint(c) gives the embedded fingerprint if c is an invitation.

To verify whether the embedded fingerprint of an invitation c is correct, a participant has to produce the state observed by c. The participant first duplicates the current local state and undoes every concurrent and following contributions of c. Then she computes the fingerprint of the obtained state. If the computed fingerprint matches the embedded one, then the embedded fingerprint is correct. computedFingerprint(S) is the function that computes the fingerprint of a state S.

To ensure that only correct fingerprints are embedded in invitations, in Definition 13 we extend the definition of wellformed contributions.

(c k ) = ∅ =⇒ fingerprint(c k ) = computedFingerprint(S ) where S = undo( x ∈ h i t | x c k ∨ c k → x , S i t )
New participants retrieve a pruned log and a snapshot from a participant. By verifying the consistency of the pruned log, they also verify the consistency between the log and the snapshot. Thus, if the pruned log is SVFJC-consistent, then the snapshot is considered authentic.

A malicious participant can forge a state and embed the fingerprint of this state in one of her invitations. If the pruned log does not contain an invitation issued by an honest participant, then the new participants are not able to detect that the snapshot is not authentic. As seen in subsection III-B, the application can mitigate this using additional consistency rules. Another possibility is to embed the state fingerprint in more contributions. This is out of scope of this paper.

VI. RELATED WORK

Distributed storage systems store and atomically update several objects. The knowledge of the latest update of every object is sufficient to get the actual state. Based on this observation, ASTRO [START_REF] Mahajan | ASTRO: Autonomous and Trustworthy Data Sharing[END_REF] proposes to sum up the older updates in order to shrink the log. In addition to securely tracking causal dependencies, honest participants have to maintain a balanced Merkle tree [START_REF] Merkle | Secrecy, Authentication, and Public Key Systems[END_REF] in which the leaves are their own updates. Instead of directly signing an update, honest participants sign the root of their own Merkle tree. Every signature is a summary of one or more updates of a participant. ASTRO respects a weaker consistency model than VFJC. It does not limit the number of accepted forks. A malicious participant can conceal non-linear contributions in a summary. It is not possible for an honest participant to determine if a summary is well-formed. Our consistency model limits the number of accepted forks.

Based on the same observation, Depot [START_REF] Mahajan | Depot: Cloud Storage with Minimal Trust[END_REF] proposes a checkpoint mechanism to discard old updates. Periodically, a client suggests update removals. An honest client needs the approval of every client in order to garbage collect the suggested updates. A malicious client can prevent the garbage collection since a consensus is required. In contrast, we propose to prune the log without any coordination and extra communications; honest participants incrementally prune their log. Like in Depot, a malicious participant can prevent the garbage collection. However, in practice, we can evict inactive participants while Depot cannot determine if a disagreement to a consensus is honest or dishonest. To perform consistency checks, Depot includes enough information in the checkpoints. We design augmented contributions in order to perform consistency checks in a pruned log. Our proposition could be adapted to Depot.

Instead of sending the entire log, SPORC [START_REF] Feldman | SPORC: Group Collaboration Using Untrusted Cloud Resources[END_REF] propose the transmission of a snapshot. Periodically, a participant publishes a signed snapshot on a central server. Participants trust each other, thus the snapshot is considered authentic if the signature is correct. Under our adversary model, this approach is not secured: a malicious participant can freely tamper the snapshot.

Zhao et al. [START_REF] Zhao | Byzantine Fault Tolerance for Collaborative Editing with Commutative Operations[END_REF] introduces an optimistic Byzantine Fault-Tolerant (BFT) approach for collaborative editing. Unlike common agreement-based BFT systems, their approach first applies the execution step and runs the agreement step ondemand. Indeed, honest server replicas execute and broadcast updates to client replicas as soon as they are received. When an honest client does not receive enough matching updates, it demands an agreement among the pool of server replicas. The paper describes a mechanism to join a collaboration using a snapshot of the document. To add a new client, a server replica runs an agreement over the clients. Once accepted, honest clients send an identical snapshot. A majority of matching snapshot is enough to consider a snapshot authentic. If the number of active clients is not enough, the application gives up safety in profit of liveness. In contrast, we propose an invitation mechanism that enables us to asynchronously accept newcomers. Our joining process requires a single snapshot. We rather abort a joining process than sacrifice safety.

VII. DISCUSSIONS

A. Causal stability

The usefulness of our proposal relies on the assumption that the size of the stable part of the log is close to the entire log.

Our adversary model assumes that two honest participants can eventually exchange messages and does not limit how long eventually is. Thereby, messages could not be delivered before the end of the collaboration. Participants could be disconnected for a long period time. As long as they are disconnected, the stabilization of the log is not possible.

Although the selected model is worthy for the design of secure mechanisms, it is not relevant for their assessments. Indeed, a system where participants have poor interactions is likely not a collaboration. In practice, inactive participants can be evicted from the group after a given period. With such a mechanism, stabilization can be enforced. Only contributions shared between inactive participants could be lost.

B. Availability vs Consistency

Distributed systems make a trade-off between consistency and availability. Availability is a usability requirement and then cannot be traded for strong consistency guarantees [START_REF] Mahajan | Consistency, Availability, and Convergence[END_REF][START_REF] Mahajan | Depot: Cloud Storage with Minimal Trust[END_REF]. Weak consistency guarantees are not suitable for every application [START_REF] Terry | Replicated Data Consistency Explained Through Baseball[END_REF]. As mitigation, we build on VFJC [START_REF] Mahajan | Consistency, Availability, and Convergence[END_REF], the strongest achievable consistency guarantees in an alwaysavailable and convergent system.

VIII. CONCLUSION AND FUTURE WORK

Distributed collaborative systems rely on replication algorithms to support concurrent modifications of shared documents in presence of network partitions. Convergence of document copies determines the liveness of a collaboration and can be protected with authenticated logs against an active adversary.

The cost of joining a collaboration linearly grows with the size of the authenticated log.

We have shown that it is possible to protect convergence of document copies with a pruned version of the authenticated log. We designed a mechanism based on the authentication of snapshots of the document using a prunable authenticated log of the contributions.

To this end, we extended Causal Stability to dynamic groups (in which members can join and leave for their convenience) and in presence of an active adversary. Our proposal relies on an adaptation of the View-Fork-Join-Causal (VFJC) consistency model to a stabilizable version of the log of contributions. We also showed that the log can be pruned without threatening its future consistency. To illustrate the value of our stabilizable and prunable log, we proposed to authenticate a snapshot from a pruned log. The maintenance of a pruned log and its transmission along with a snapshot reduce the footprint of authenticated logs when new participants join the collaboration.

To enable stabilization, our authenticated log rejects forks in which new participants have contributed. This limits the availability of the system for these new participants. A future work could explore extensions to offer more guarantees to these participants. For instance, we could add time-based or trust-based rules to accept an invitation under conditions.

Our system model elevates partitioning as a feature: partitions can independently collaborate. A future work could explore log stabilization in partitions.

Figure 5 .

 5 Figure 5. Bob (P B ) invites Carol (P C ) in his contribution c B 1 . Carol issues c C 1 which depends on c B 1 . In the meantime Alice (P A ) issues c A 2 which is concurrent with Bob's and Carol's contributions. Alice receives c B 1 and c C 1 , when Bob receives the contribution of Carol before the contribution of Alice. (a) and (b) respectively depicts the SVFJC log of Alice and Bob.

2 pcs

 2 {P A , P B , P M } (b) Bob's SVFJC log.

Figure 6 .

 6 Figure 6. Alice (P A ) starts a collaboration with Bob (P B ) and Mallory (P M ). Mallory issues two non-linear contributions c M 1 and c M 2 . (a) In the log of Alice, c B 1 is provably observed by Mallory and Alice. From the point of view of Alice, c B 1 is provably causally stable (pcs). (b) Because Bob has not yet observed c M 1 , he accepts c M 2 in his log. Thus there exists a concurrent contribution to c B 1 which was honestly accepted.

Figure 7 . 3 .

 73 Figure 7. Mallory (P M ) is provably malicious. She is known as evicted in c A 3 . Since c A 3 is provably causally stable (pcs), then Mallory is no longer a required observer of any contributions. c B 2 precedes c A 2 and are pcs. Thus Alice (P A ) and Bob (P B ) are provably linear observers of c B 2 and all preceding contributions. These contributions have only Alice and Bob as required observers. They are thus view-fork-join-causally stable (vfjcs).

  Alice knows that her (P A ) and Bob (P B ) are in the group. Thus, Bob and Alice are required observers of c A 2 . Upon delivery of c B 1 , Alice knows that Bob invited Carol. Since c B 1 is concurrent to c A 2 , Carol (P C ) could issue concurrent contributions to c A 2 . Hence, Carol is also a required observer of c A 2 . Upon delivery of c B 2 , Alice has a proof of observation of c A 2 from Bob and she is aware of the invitation of Dave (P D ).

	Since, c B 2 depends on c A 2 , Dave is not a required observer of c A 2 . Delivery of c C 1 gives a proof of observation of c A 2 from Carol. All required observers have observed c A 2 . Thus c A 2 becomes provably causally stable (pcs).
	her past delivered contributions. If the invited participant
	contributes to the collaboration, then he issues a contribution
	that depends on this invitation. He is not provably malicious.
	Following L3 and L4, honest participants have to accept his
	contribution and by extension the fork. Figure 4 illustrates this
	scenario.
	c A 1	. . .	c M 20	c B 20
	c M 21 {P 21 that invites Franck (P F ) c F 1 and is non-linear with her past delivered contributions c M 1 , . . . , c M 20 . Franck issues c F 1 . c F 1 depends on c M 21 . Since Franck is not provably malicious, honest participants accept the fork c M 21 ↓ c F 1 . The log is VFJC-consistent.

A , P B , P M } {P F }

Figure 4. Alice (P A ), Bob (P B ), and Mallory (P M ) honestly issue contributions. Then Mallory issues an invitation c M

  W8 (correct fingerprint) If the contribution is an invitation, then the embedded fingerprint matches the computed fingerprint on the state observed by the contribution.

	invitedIn
	Definition 13 (Well-formed contribution and fingerprints). Let
	a SVFJC log H i t and its attached state S i t . Let a SVFJC pruned log h i t from H i

t . A well-formed contribution c k ∈ h i t fits:

Mahajan et al. [7] refers to them as non-serial

ACKNOWLEDGEMENTS

We would like to thank Matthieu Nicolas, Olivier Perrin, Alizée Dulliand, Rado Randrianomanana, Alexandre Merlin, and anonymous reviewers for their meaningful comments.