F Kiefer

J.-L Halbwachs

F Arenou

D Pourbaix

B Famaey

P Guillout

Y Lebreton

A Nebot Gómez-Morán

T Mazeh

J.-B Salomon

C Soubiran

L Tal-Or

Masses of the components of SB2 binaries observed with Gaia. III. Accurate SB2 orbits for 10 binaries and masses of HIP 87895 ⋆⋆

Keywords: binaries, spectroscopic, stars, fundamental parameters stars, individual, HIP 87895

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

Masses of the components of SB2 binaries observed with

Gaia. III. Accurate SB2 orbits for 10 binaries and masses of HIP 87895 Mass is the most crucial input in stellar internal structure modelling. It predominantly influences the luminosity of a star at a given stage of its evolution, and also its lifetime.

The knowledge of the mass of stars in a non-interacting binary system, together with the assumption that the components have same age and initial chemical composition, allows the age and the initial helium content of the system to be determined and therefore to characterize the structure and evolutionary stage of the components. Such modelling provides insights into the physical processes governing the ⋆ based on observations performed at the Observatoire de Haute-Provence (CNRS), France † E-mail: flavien@wise.tau.ac.il structure of the stars. Moreover provided masses are known with great accuracy [START_REF] Lebreton | The Three-Dimensional Universe with[END_REF], it gives constraints on the free physical parameters of the models. Therefore, modelling stars with extremely accurate masses (at the 1 % level), in different ranges of masses, would allow to firmly anchor the models of the more loosely constrained single stars.

This paper is the third in a series dedicated to the derivation of accurate masses of the components of doublelined spectroscopic binaries (SB2) with the forthcoming astrometric measurements from the Gaia satellite. In paper I (Halbwachs et al. 2014), we have presented our program to derive accurate masses from Gaia and from high-precision spectroscopic observations. We have selected a sample of 68 SB2s for which we expect to derive very precise inclination with Gaia, and M sin 3 i with the Spectrographe pour l'Observation des PHénomènes des Intérieurs Stellaires et des Exoplanètes (SOPHIE spectrograph, Haute-Provence Observatory). Our objective is to determine for these SB2 systems the masses of the two components with an accuracy about 1 %. We have been observing these stars since 2010 with SOPHIE. A first result of our program was the detection of the secondary component in the spectra of 20 binaries which were previously known as single-lined (paper I). A second result was the determination of masses for 2 SB2 with accuracy between 0.26 and 2.4 %, using astrometric measurements from PIONIER and radial velocities from SOPHIE (paper II).

Here, we present the accurate orbits measured for 10 SB2s (Table 1) with periods ranging from 37 to 881 days. After 5 years of observations with SOPHIE, we collected a total of 123 spectra. In addition, a large number of previously published measurements is available for each of them in the SB9 catalog (Pourbaix et al. 2004). Four of these targets are new SB2 identified in paper I, and previously known as SB1. Finally, we combined the radial velocity (RV) measurements of one star (HIP 87895) with existing interferometric measurements and derive the masses of the two components.

The observations are presented in Section 2. The method of measurements of radial velocities from SOPHIE's observations is explained in Section 3. We derive the orbital solutions in Section 4, discussing in particular the issue of the uncertainties when combining different datasets from different instruments. The derivation of the masses of HIP 87895 is discussed in Section 5. Finally, we summarize and conclude on our findings in Section 6.

OBSERVATIONS

The observations were performed at the T193 telescope of the Haute-Provence Observatory, with the SOPHIE spectrograph. SOPHIE is dedicated to the search of extrasolar planets, and, thanks to its high resolution (R∼75, 000), it enables accurate stellar radial velocities to be measured for SB2 components.

The spectra were all reduced through SOPHIE's pipeline, including localization of the orders on the frame, optimal order extraction, cosmic-ray rejection, wavelength calibration, flat-fielding and bias subtraction. The minimum signal-to-noise ratio (SNR) is 40 for the faintest stars of the sample, but it may be as large as 150 for a 6-magnitude star. Before each observation run ephemerides were derived from existing orbits provided by the SB9 catalogue (Pourbaix et al. 2004), and priority classes were assigned on the basis of the orbital phase. Four classes were used: the lowest priority corresponds to stars with expected RVs of primary and secondary component sufficiently different to permit accurate measurements, and the highest priority is reserved to the observations of the periastron of eccentric orbits.

Among all the observed SB2, we have selected those which were observed over at least one period, and which received a minimum of 11 observations. Table 1 summarizes this information. Given the very high quality of the measurements, an SB2 orbit could be derived in principle from only 6 of those observations, provided they were made at the most relevant phases. However, we show in Section 4 that 11 observations are necessary to validate the RV uncertainties, and to correct them when necessary.

RADIAL VELOCITY MEASUREMENTS

The radial velocities of the components are derived using the TwO-Dimensional CORrelation algorithm todcor (Zucker & Mazeh 1994;Zucker et al. 2004). It calculates the cross-correlation of an SB2 spectrum and two bestmatching stellar atmosphere models, one for each component of the observed binary system. This two-dimensional cross-correlation function (2D-CCF) is maximized at the radial velocities of both components. The multi-order version of todcor, named todmor (Zucker et al. 2004), determines the radial velocities of both components from the gathering of 2D-CCF obtained from each order of the spectrum.

All SOPHIE multi-orders spectra were corrected for the blaze using the response function provided by SOPHIE's pipeline; then for each of them, the pseudo-continuum was detrended using a p-percentile filter (paper II, or e.g. Hodgson et al. (1985)).

For both components of each binary, we determined a best-matching theoretical spectra from the PHOENIX stellar atmosphere models (Husser et al. 2013). We optimized the 2D-CCF with respect to effective temperature T eff , rotational broadening v sin i, metallicity [Fe/H], surface gravity log(g), and flux ratio at 4916 Å, α=F2/F1. Furthermore, each theoretical spectrum is convolved with the instrument line spread function, here modeled by a Gaussian, and pseudo-continuum detrended like the observed spectrum. The spectral parameters obtained through this method are given in Table 2. We determined spectral parameters from 4 spectra per binary on average, with the two components well individualized. The values and their uncertainties given in Table 2 are the average and standard deviation of the individual estimations. The 1σ uncertainties do not include known systematics of theoretical models with respect to real spectral types (see e.g. Torres et al. (2012)). ±0.04 ± 1 a A null value is given to V sin i with no error bar whenever found less than SOPHIE's typical pixel size ∼2km s -1 .

It is worth mentioning that the derived metallicity [Fe/H] is systematically subsolar. Optimizing the CCF of several spectra of the Sun obtained by observing Vesta and Ceres with SOPHIE gave spectral parameters consistent with the known values for the Sun except metallicity that was found to be -0.33 dex. However, we kept the values of metallicity that maximized the 2D-CCF, as given in Table 2.

We then applied todmor to all multi-order spectra of each target and determined the radial velocities of both components discarding all orders harboring strong telluric lines. For each of the non-discarded orders, we calculated a two dimensional cross-correlation function, and used the maximum of this function to derive radial velocities for the pri-mary and the secondary. Final velocities for each component are obtained by averaging these measurements and incorporating a correction for order-to-order systematics -typically 200-500 m s -1 . The final velocities are displayed in Table 3. They are used to derive the orbital solutions for the 10 SB2 in the next section.

DERIVATION OF THE ORBITS

The orbital solutions for the 10 SB2 are derived by combining the new measurements presented in this paper with previously published RVs (references in Table 4).

Since several datasets coming from different instruments are used together to derive a common orbital solution, realistic errors should be attributed to each dataset properly. It is explained in the following section. This process guarantees that each dataset receives the proper weight with respect to all others, including the new SOPHIE measurements presented here.

Correction of uncertainties

Uncertainties of previously published measurements, when provided, are usually underestimated. On the other hand, many lists of RV measurements do not include uncertainties, but only weights (W). Therefore, two different procedures are applied to attribute correct uncertainties to these retrieved measurements. They are both based on the calculation of the F2 estimator of the goodness-of-fit (see Paper II, equation 1, or Stuart & Ord 1994):

• When the uncertainties are provided, a noise is quadratically added to the original uncertainties, in order to get exactly F2=0 for the SB1 orbit of each component. Since the original uncertainties are underestimated, this results in decreasing the variations of the relative weights of the measurements of a given component.

• When only weights are given, they are first converted to uncertainties (σ = 1/W ). Then they are scaled in order to get F2=0 for the SB1 orbit of each component.

After this transformation, the SB2 orbit is derived, and F2 is considered again. The final uncertainties are obtained by multiplying the ones derived above with a factor chosen in order to get F2=0. All these operations result in applying the following formulae:

σ corr RV,1 = ϕ1 × σ 2 RV,1 + ε 2 1 (1) σ corr RV,2 = ϕ2 × σ 2 RV,2 + ε 2 2 (2)
Table 4 lists the derived values of the correction terms ϕ1, ϕ2, ε1 and ε2 for all stars of our sample.

The same procedure is applied to the uncertainties derived by todmor for the new measurements. For two binaries (HIP 67195 and HIP 100321), the SB1 orbit of the secondary component leads to a negative value of F2, implying that the uncertainties are slightly overestimated. In order to get F2=0, we prefered to keep the relative weights fixed, and simply multiply the uncertainties by a coefficient ϕ2 lower than 1.

Table 3. New radial velocities from SOPHIE and obtained with todmor. Outliers are marked with an asterisk ( * ) and are not taken into account in the analysis.

HIP 12081 BJD RV 1 σ RV 1 RV 2 σ RV 2 O 1 -C 1 O 2 -C 2 -2400000 km s -1 km s -1 km s -1 km s -1 km s -1 km
σ RV 1 RV 2 σ RV 2 O 1 -C 1 O 2 -C 2 -2400000 km s -1 km s -1 km s -1 km s -1 km s -1 km
BJD RV 1 σ RV 1 RV 2 σ RV 2 O 1 -C 1 O 2 -C 2 -2400000 km s -1 km s -1 km s -1 km s -1 km s -1 km s
BJD RV 1 σ RV 1 RV 2 σ RV 2 O 1 -C 1 O 2 -C 2 -2400000 km s -1 km s -1 km s -1 km s -1 km s -1 km
BJD RV 1 σ RV 1 RV 2 σ RV 2 O 1 -C 1 O 2 -C 2 -2400000
km s -1 km s -1 km s -1 km s -1 km s -1 km s

BJD RV 1 σ RV 1 RV 2 σ RV 2 O 1 -C 1 O 2 -C 2 -2400000
km s -1 km s -1 km s -1 km s -1 km s -1 km s HIP 95575

BJD RV 1 σ RV 1 RV 2 σ RV 2 O 1 -C 1 O 2 -C 2 -2400000 km s -1 km s -1 km s -1 km s -1 km s -1 km s
BJD RV 1 σ RV 1 RV 2 σ RV 2 O 1 -C 1 O 2 -C 2 -2400000 km s -1 km s -1 km s -1 km s -1 km s -1 km
BJD RV 1 σ RV 1 RV 2 σ RV 2 O 1 -C 1 O 2 -C 2 -2400000
km s -1 km s -1 km s -1 km s -1 km s -1 km s

σ RV 1 RV 2 σ RV 2 O 1 -C 1 O 2 -C 2 -2400000
km s -1 km s -1 km s -1 km s -1 km s -1 km s All the RV measurements and the uncertainties used in the derivation of the orbits will be available through the SB9 Catalogue (Pourbaix et al. 2004), which is accessible on-line 1 .

Derivation of the orbital elements

For each binary, we fitted an SB2 orbital model to the previously published datasets combined with the new SO-PHIE observations. The parameters were optimized using a Levenberg-Marquard method.

The final orbital solution consists in the following orbital elements: the period, P , the eccentricity, e, the epoch of the periastron, T0, the longitude of the periastron for the primary component, ω1, the RV semi-amplitudes of each component, K1 and K2, and the RV of the barycentre, V0.

We also added 3 supplementary parameters, which are: a systematic offset between the measurements previously published and the new ones, dn-p, and the offsets between the RVs of the primary and of the secondary component, d p 2-1 and d n 2-1 . The offset d p 2-1 is usually due to 1 http://sb9.astro.ulb.ac.be/ the fact that the published RVs were obtained from templates which are not specifically adapted to each component. For instance, a spectrovelocimeter like CORAVEL (Baranne, Mayor & Poncet 1979) was working by projecting any spectrum on a mask representing the spectrum of Arcturus. The offset between the primary and secondary RVs derived with todmor, d n 2-1 is expected to be null, but it is significant for some stars, since the spectra of the PHOENIX library do not perfectly represent the actual ones.

Results

Even with a correction, the uncertainties of the measurements from SOPHIE remain small and have weights much larger than the others. Therefore, incorporating the published datasets in the calculation essentially improved the accuracy of the period determined. Conversely, the significant precision of the new SOPHIE measurements allowed us to reach a very good accuracy on all other orbital parameters, especially the minimum masses.

The derived orbital elements for the 10 SB2 are given in Table 5. Among the 20 component stars, 15 of them have M sin 3 i determined with an accuracy better than 0.7 %, Table 5. The orbital elements derived from the previously published RV measurements and from the new ones. The radial velocity of the barycentre, V 0 , is in the reference system of the new measurements of the primary component. The minimum masses and minimum semi-major axes are derived from the true period (Ptrue = P × (1 -V 0 /c)). a The 3 first measurements in Griffin (2006) were discarded.

HIP P T 0 (BJD) e V 0 ω 1 K 1 M 1 sin 3 i a 1 sin i N 1 d n-p σ(O 1 -C 1 )p,n HD K 2 M 2 sin 3 i a 2 sin i N 2 d p 2-1 , d n 2-1 σ(O 2 -C 2 )p,n (d) 2400000+ (km s -1 ) ( o ) (km s -1 ) (M ⊙ ) (Gm) (km s -1 ) (km
while only 5 stars have minimum mass accuracies between 1 and 1.2%.

A comparison between the standard deviation of the residuals of the previous measurements and of the new ones also illustrates the improvements due to SOPHIE. It results from the last column of Table 5 that σ(O -C)p is between 2.3 and 239 times larger than σ(O -C)n, with a median around 30.

The orbital solutions, including previously published measurements, are displayed on Fig. 1. The (O -C) residuals are included in Table 3 and are plotted on Fig. 2. We do not observe any drift for any of the 10 SB2.

COMBINED ORBITAL SOLUTION AND MASSES FOR HIP 87895

HIP 87895 is the close visual binary (VB) MCA 50. Among the many observations recorded in the on-line Fourth Catalogue of Interferometric Measurements of Binary Stars2 , we found 3 very accurate long-base interferometric measurements performed with the Palomar Testbed Interferometer (PTI). Since the RV measurements are already providing parameters common to the spectroscopic and to the visual orbits, three 2-dimension measurements are quite sufficient to derive the remaining ones, which are: the orbital inclination, i, the position angle of the nodal line, Ω, and the ap- parent semi-major axis or the trigonometric parallax (both may equally be used). These measurements and the rescaled error ellipsoids provided by Muterspaugh et al. (2010) are taken into account simultaneously with our RV measurements, in order to directly derive the masses of the components and the trigonometric parallax of the system.

The results are given in Table 6, and in Fig. 3. We derived the two masses with accuracies of 1.2 and 0.98 %, respectively.

SUMMARY AND CONCLUSION

We obtained for 10 SB2 new radial velocity measurements from spectra taken with SOPHIE, among which four new SB2 identified in paper I. The todmor algorithm was used to separate the two components in each spectrum. All ten systems had previously published measurements in archive, which we added to our measurements to calculate the orbital solutions. We also derived estimations of stellar parameters obtained by optimizing the two dimensional crosscorrelation obtained with todmor.

We achieved the objective of deriving minimum mass with an accuracy better than 1% for 15 of the 20 stars of our SB2 sample. Moreover, all ten binaries have the minimum mass of both components estimated with relative uncertainties lower than 1.2%. This is a great achievement of the combination of todmor and SOPHIE. Especially it did very well in extreme configurations such as with small SNR (∼40), and very small flux ratio (α<0.05) between the two components.

We combined our RV measurements of HIP 87895 with 3 relative positions derived from long-based interferometric observations, and we obtained new mass estimate of the components, M1=1.132±0.014 M⊙ and M2=0.7421±0.0073 M⊙. On the basis of speckle observations, McAlister et al. (1995) previously derived M1=1.16±0.12 M⊙ and M2=0.77±0.05 M⊙, i.e. with relative errors of 10 and 6 %. Therefore, our measurements refine profitably to the 1% level the confidence range on the masses of HIP 87895.

Added to the systems observed with Pionier, we have now 3 binaries observed with SOPHIE which may be used to check the masses that will be derived from Gaia.

ACKNOWLEDGMENTS

This project was supported by the french INSU-CNRS "Programme National de Physique Stellaire" and "Action Spécifique Gaia". We are grateful to the staff of the Haute-Provence Observatory, and especially to Dr F. Bouchy, Dr H. Le Coroller, Dr M. Véron, and the night assistants, for their kind assistance. We made use of the SIMBAD database, operated at CDS, Strasbourg, France. This research has received funding from the European Community's Seventh Framework Programme (FP7/2007-2013) under grant-agreement numbers 291352 (ERC). The authors are very thankful to the anonymous reviewer for his help to improve the quality of this paper.

F

  . Kiefer, J.-L. Halbwachs, Frédéric Arenou, Dimitri Pourbaix, B. Famaey, P. Guillout, Y. Lebreton, A. Nebot Gómez-Morán, Tsevi Mazeh, J.-B. Salomon, et al. To cite this version: F. Kiefer, J.-L. Halbwachs, Frédéric Arenou, Dimitri Pourbaix, B. Famaey, et al.. Masses of the components of SB2 binaries observed with Gaia. III. Accurate SB2 orbits for 10 binaries and masses of HIP 87895. Monthly Notices of the Royal Astronomical Society, 2016, 458 (3), pp.3272-3281. 10.1093/mnras/stw545. hal-01291148 1 INTRODUCTION

Figure 1 .Figure 2 .

 12 Figure1. The spectroscopic orbits of the 10 SB2; the circles refer to the primary component, and the triangle to the secondary; the large filled symbols refer to the new RV measurements obtained with SOPHIE. For each SB2, the RVs are shifted to the zero point of the SOPHIE measurements of the primary component.

Figure 3 .

 3 Figure 3. The visual part of the combined orbit of HIP 87895.Upper panel: the visual orbit; the circles are the 3 positions obtained from long-base interferometry; the node line is in dashes. Middle panel: the residuals along the semi-major axis of the error ellipsoid. Lower panel: the residuals along the semi-minor axis of the error ellipsoid.

Table 1 .

 1 The ten SB2 analyzed in this paper. The time span is the total span of observation epochs, counted in number of periods. d SNR is the median signal-to-noise ratio of each sample.

	HIP	HD	V	Period a N	spec	b	Time span c SNR d
			(mag.) (day)			(period)
			Previously published SB2
	12081 15850	7.72	443.49	11		3.3	80
	17732 23626	6.27	277.89	11		5.5	120
	56275 100215 7.99	47.88	13		30.7	80
	87895 163840 6.33	880.78	14		2.1	120
	95575 183255 8.05	166.36	13		11.9	75
	100321 195850 7.02	37.94	11		45.3	80
	SB2 identified in paper I, previously published as SB1
	13791 18328	8.87	48.71	13		28.8	40
	61727 110025 7.58	54.88	12		28.3	80
	62935 120005 8.53	139.00	11		10.6	40
	67195 120005 6.50	39.28	14		37.3	120

a The period values are taken from the SB9 catalog

(Pourbaix et al. 2004

). b Nspec gives the number of spectra collected with SOPHIE. c

Table 2 .

 2 The stellar parameters determined by optimization of the 2D-CCF obtained with todmor. Explanations in Section 3.

	HIP HD	T eff,1 T eff,2 (K)	log g 1 log g 2 (dex)	V 1 sin i 1 a V 2 sin i 2 a (km s -1 )	[Fe/H] (dex)	α (flux ratio)
	12081	6290	4.24	11.9	-0.37	0.635
	15850	± 23	±0.05	±0.1	±0.01	±0.012
		6003	4.30	6.5
		± 13	±0.01	±0.1
	13791	6173	4.31	5.5	-0.34	0.034
	18328	± 6	±0.01	±0.1	±0.01	±0.001
		4953	5.09	0
		± 95	±0.01
	17732	6030	3.34	9.4	-0.71	0.258
	23626	± 7	±0.03	±0.1	±0.01	±0.004
		6051	3.84	0
		± 18	±0.01
	56275	6889	3.93	20.6	-0.33	0.036
	100215	± 36	±0.11	±1	±0.01	±0.002
		4906	4.33	0
		± 75	±0.01
	61727	6461	3.82	9.8	-0.48	0.070
	110025	± 31	±0.15	±0.1	±0.06	±0.007
		5256	4.31	7.7
		± 168	±0.14	1.4
	62935	5818	4.03	4.9	-0.27	0.054
	112138	± 85	±0.08	±0.4	±0.01	±0.015
		4378	4.40	0
		± 115	±0.13
	67195	6411	4.29	13.6	-0.21	0.027
	120005	± 29	±0.13	±0.2	±0.03	±0.002
		4478	4.72	4.5
		± 418	±0.21	±0.1
	87895	5970	4.33	4.7	-0.19	0.036
	163840	± 1	±0.01	±0.1	±0.01	±0.004
		4385	4.81	0
		± 134	±0.04
	95575	4908	4.75	3.4	-0.88	0.431
	183255	± 5	±0.03	±0.1	±0.01	±0.008
		4088	4.51	0
		± 5	±0.03
	100321	6485	4.17	14.2	-0.39	0.207
	195850	± 6	±0.05	±0.2	±0.01	±0.011
		5558	4.39	5.5
		± 62

Table 3 .

 3 Continued.

	s -1

c 2015 RAS, MNRAS 000, 1-9

Table 4 .

 4 Correction terms applied to the uncertainties of the previous and of the new RV measurements. The composition of these terms into a uncertainty correction is explained in Section 4.1, eqs. 1 and 2.

	-1

Table 6 .

 6 The combined VB+SB2 solutions of HIP 87895; For consistency with the SB orbits and with the forthcoming astrometric orbit, ω refer to the motion of the primary component. (km s -1 ) 0.456 ± 0.047d 2-1 p (km s -1 ) -0.754 ± 0.608 d 2-1 n (km s -1 ) 0.320 ± 0.056 σ (o-c) V LT I (mas) 0.086 σ (o-c) RV p (km s -1 )0.841, 1.211 σ (o-c) RV n (km s -1 ) 0.035, 0.209

		HIP 87895
	P (days)	881.628 ± 0.064
	T 0 (BJD-2400000)	55650.39 ± 0.38
	e	0.4165 ± 0.0010
	V 0 (km s -1 )	-32.347 ± 0.014
	ω 1 ( o )	135.46 ± 0.16
	Ω( o ; eq. 2000)	175.32 ± 0.44
	i ( o )	72..83 ± 0.47
	ex a (mas)	80.64
	M 1 (M ⊙ )	1.132 ± 0.014
	M 2 (M ⊙ )	0.7421 ± 0.0073
	̟ (mas)	36.35 ± 0.20
	d n-p

c 2015 RAS

c 2015 RAS, MNRAS 000, 1-9

http://ad.usno.navy.mil/wds/int4.html c 2015 RAS, MNRAS 000, 1-9


Camila Chovet
email: camila.chovet@etu.univ-valenciennes.fr

Marc Lippert

Laurent Keirsbulck

Bernd R Noack

Jean-Marc Foucaut

MACHINE LEARNING CONTROL FOR EXPERIMENTAL TURBULENT FLOW TARGETING THE REDUCTION OF A RECIRCULATION BUBBLE

Keywords: Machine learning control, experimental flow control, recirculation zone

We experimentally control the turbulent flow over backwardfacing step (Re H = 31500). The goal is to modify the internal (Xr) and external (Lr) recirculation points and consequently the recirculation zone (Ar). A model-free machine learning control (MLC) is used as control logic. As benchmark, an optimized periodic forcing is employed. MLC generalizes periodic forcing by a multi-frequency actuation. In addition, a sensor-based control and a non-autonomous feedback, open-and closed-loop laws, were use to optimize the control. The MLC multi-frequency forcing outperforms, as expected, periodic forcing. The nonautonomous feedback brings a further improvement. The unforced and actuated flows have been investigated in real-time with a TSI particle image velocimetry (PIV) system. The current study shows that a generalization of multi-frequency forcing and sensor feedback significantly reduces the turbulent recirculation zone, far beyond optimized periodic forcing. The study suggests that MLC can effectively explore and optimize new feedback actuation mechanisms and we anticipate MLC to be a game changer in turbulence control.

INTRODUCTION

Flow with separation and reattachment has long been a subject of fundamental fluid dynamics research. This flow gives rise to unsteadiness, pressure fluctuations, structure vibrations and noise [START_REF] Chun | Visualization of a locallyforced separated flow over a backward-facing step[END_REF]. The flow over a backward-facing step (BFS) is a common separating/reattaching flow found in nature. Therefore is deeply studied both numerically and experimentally (see [START_REF] Chun | Visualization of a locallyforced separated flow over a backward-facing step[END_REF][START_REF] Hung | Direct numerical simulation of turbulent flow over a backward-facing step[END_REF][START_REF] Beaudoin | Three-dimensional stationary flow over a backwardsfacing step[END_REF][START_REF] Aider | Large-eddy simulation applied to study the influence of upstream conditions on the time-dependant and averaged characteristics of a backward-facing step flow[END_REF]). The control of separated and reattaching flows is an essential issue for practical applications. Periodically perturbing the shear layer at the separation location using synthetic jet actuator was found to be an effective tool to control these flows [START_REF] Chun | Control of turbulent separated flow over a backward-facing step by local forcing[END_REF][START_REF] Yoshioka | Turbulence statistics of periodically perturbed separated flow over a backward-facing step[END_REF][START_REF] Yoshioka | Organized vortex motion in periodically perturbed turbulent separated flow over a backward-facing step[END_REF][START_REF] Dejoan | Large eddy simulation of periodically perturbed separated flow over a backwardfacing step[END_REF]. Bhattacharjee et al. [START_REF] Bhattacharjee | Modification of Vortex Interactions in a Reattaching Separated[END_REF] claimed that the most effective non-dimensional forcing frequency, so called Strouhal Number (St H = f * H U 0 ), was between 0.2 and 0.4. Closed-loop control offers further possibilities to improve the actuation efficiency by adapting the control to different flow conditions. There are two main ways to generate the closed-loop control laws. The first one is to compute the model using previous knowledge of the physics of the flow [START_REF] Sipp | Dynamics and control of global instabilities in open flows: a linearized approach[END_REF]. But, these models, obtained from the derivation of the NavierStokes equations, are of very high order and require reduction before they can be used in a realistic settings [START_REF] Gautier | Closed-loop separation control using machine learning[END_REF]. The challenges of model-based control design have led us to inclined to model-free control strategies using machine learning methods such as genetic programming (GP). GP is a powerful regression method which can detect and exploit nonlinear actuation mechanisms in an unsupervised manner, as evidenced in several shear flow control experiments [START_REF] Gautier | Closed-loop separation control using machine learning[END_REF][START_REF] Debien | Closed-loop separation control over a sharp-edge ramp using genetic programming[END_REF][START_REF] Parezanovic | Frequency selection by feedback control in a turbulent shear flow[END_REF].

The goal of this study is to use the performance benefits of machine learning control MLC in active flow control to find a cost effective control law. The control objective is to reduce the recirculation zone downstream of a backward-facing step (BFS). Particle image velocimetry PIV will be employed to the physical mechanisms of turbulent unperturbed and perturbed flows.

EXPERIMENTAL APPARATUS AND TECHNIQUES Description of the test facility and the step

The experiments were conducted in an optically accessible closed-loop wind tunnel. The test section is 2m wide, 2m high and 10m long. The free stream velocity is U 0 = 5.7m s, Re H = 31500 (δ = 0.68H, Re δ = 21500). The air is conditioned in a settling chamber to minimize free stream turbulence through a contoured converging nozzle. The model is mounted in the middle of the test section. The step height of the backwardfacing step is H = 83mm and corresponds to an expansion ratio of 1.04, i.e. negligible inference of the upper wall. An effectively nominally two-dimensional flow is provided by the large span of 2000mm yielding an aspect ratio of 24 [START_REF] De Brederode | Influence of the side walls on the turbulent centerplane boundary-layer in a square duct[END_REF]. The array of actuators was placed at the middle the test section width and is 5H long (20%), leaving a free space of 800mm between the control area and the test section walls. This prevents flow interactions between the corner of the test section and the backward facing step. The origin of the coordinate system is located at the edge of the step. The flow is described in a Cartesian coordinate system with x, y, z representing streamwise, spanwise (or lateral) and transverse (or normal to ground) directions, respectively. The setup described above is illustrated in a 3D view in FIG. 1.

Actuation system

The actuation system is driven by 20 piezoelectric devices (Murata micro-blowers, see FIG. 2(a)) which distribute the air flow through micro-nozzles (micro-pulsed jets). The distance between two neighboring micro-nozzles is 20 mm. The location of the actuators was chosen in agreement with literature and previous works [START_REF] Gautier | Closed-loop separation control using machine learning[END_REF] The micro-jets axes are perpendicular to the wall as seen in FIG. 1.

Contrary to other classical pulsed jets devices, Murata micro-blowers only need a power supply of 5 to 20 Volts. The mean jet velocity (u jet ) provided by each micro-blower is expected to range between 0 m/s to 30 m/s and is proportional to the voltage command up to 100Hz.The jet velocity can be commanded over a wide range of frequencies with large accuracy, avoiding, for instance, dynamic overshoots citeCHO16. As an example FIG. 2(b) shows the actuator re-sponse to a complex input voltage signal. These actuators have unique advantages for closed-loop flow control applications.

Pressure Measurements

Recirculation length reduction is highly correlated with the pressure from which the control performance can be quantified. A set of 25 static pressure taps were distributed downstream of the back-facing step in the freestream direction. The pressure tabs were mounted starting at 25mm with an interval between each other of 50 mm (x i H = 0.6), as shown in FIG. 1. In addition, a second set of 25 sub-miniature piezo-resistive Kulite XCQ-062 sensors with a nominal measurement range of 35 kPa. Flush-mounted Kulite transducers were placed in parallel and at the same x i location as the static ones. Thus, the 25 unsteady and static pressure sensor arrays extents up to 14.75H in the streamwise direction.

Velocity measurements

Velocity measurements were performed downstream of the step by the use of standard two-component TSI particle image velocimetry (PIV). The PIV field is of view is about 7.3H × 1.8H on the xy plane passing through center of the backward facing step. This large field spans the whole wake containing entirely the recirculating flow domain. The flow is seeded with oil particles using a jet atomizer upstream the stagnation chamber. The atomizer location allows homogenous dispersion of the particles throughout the test section.

The system consists of a double-pulse laser system and two cameras (2000 × 2000 pixels charge-coupled-device Powerview with a 50 mm optical lens). The frequency-doubled laser (Qswitched Nd:YAG operating at 532 nm; dual-head BigSky) emits laser pulses with a maximum energy of 200 mJ. The resolution is 19.2 pixels/mm for the employed cameras. The dynamic range is approximately 30 pixels and the velocity vectors are processed with an interrogation window 16 × 16 pixels with an overlap of 50%. For every flow/actuation configurations, 2000 doubleframe pictures are recorded to ensure the velocity fields statistics convergence. The PIV time-uncorrelated snapshots are recorded with a repetition rate of 7 Hz. The velocity measurements are sampled at 10kHz and latter filtered at 3kHz.

GENETIC PROGRAMMING CONTROL

Duriez et al. [START_REF] Duriez | Machine Learning Control -Taming Nonlinear Dynamics and Turbulence[END_REF] formulated a generic, model-free, approach to open-and closed-loop control of nonlinear systems called Machine learning control (MLC) . The control design is formulated as a regression problem: find the control law which optimizes a given cost function. An initial population of control law candidates (b (2) i is then evolved from the previously evaluated one by genetic operators , leading to new cost functions J

(2) i . Without loss of generality, the control laws of the n-generation are ordered

J (n) 1 ≤ J (n) 2 ≤ ... ≤ J (n)
100 . This learning process will continue until some stopping criterion is met. In the present study a the number of generations was set to 12, which was the minimum amount of generations required to converge toward the best individual. The targeted optimal control law is the best individual of the last generation. This individual is taken as MLC law. This marks the end of the learning phase. This process is summarized in FIG. 3.

Three different approaches for control laws are considered. First, multi-frequency control b = k(h j ) generalizes periodic forcing using three sine signals at 14Hz, 15Hz and 16Hz; St H of 0.211, 0.226 and 0.241, as inputs. These frequencies correspond to the best periodic forcing frequencies obtained in previous experiences. Second, in sensor-based control b = k(P j ), the pressure probes are used to generate the control laws. Finally, multi-frequency forcing and sensor-based feedback is generalized in the non-autonomous law b = k(P j ,h j ), i.e., a combination of harmonic and sensor-based inputs is taken.

As the main goal is to reduce the external separation point (L r ), The cost function J = L E r +λ < b > was based on an estimated L E r from a quadratic fit of the spatial pressure fluctuation distribution Cp rms . This was achieved using four pressure probes (P 7 , P 8 , P 10 & P 13 ) with an evaluation time of T e =15s. The penalization parameter prioritize either the separation length reduction (λ < 1) or the actuation cost (λ > 1). A penalization λ = 0.1 was set based on the low energy consumption of the row of micro-blower.

RESULTS AND DISCUSSION

To obtain the external and internal reattachment lengths and consequently the recirculation area, Simpsons et al. estimates the points where the backward flow probability (BFP) reaches a value of 50% [START_REF] Simpson | Aspects of turbulent boundary-layer separation[END_REF]. To actively control the flow of the backwardfacing step, experiments were carried out varying the frequency ( f ) of the periodic actuation commands (b = U jet Sin(2pi f t)), where U jet is the velocity actuation amplitude set constant at 25m s (see FIG. 5(h of the present study are consistent with those obtained in previous experiments [START_REF] Chun | Control of turbulent separated flow over a backward-facing step by local forcing[END_REF][START_REF] Yoshioka | Turbulence statistics of periodically perturbed separated flow over a backward-facing step[END_REF][START_REF] Bhattacharjee | Modification of Vortex Interactions in a Reattaching Separated[END_REF][START_REF] Li | Effect of the periodic perturbations on the wall pressure downstream of a backward facing step[END_REF]. PIV measurements were performed at the optimal frequency, the BFP obtained is shown in FIG. 5(d). This corroborates the effectiveness of pulsing jet injection with forcing frequency to reduce the separation length [START_REF] Nadge | High Reynolds number flow over a backward-facing step: structure of the mean separation bubble[END_REF]. MLC studies were carried out to discover new and more effective closed-loop separation control laws. Three cases were studied: multi-frequency open-loop, sensor-based and nonautonomous control laws. After 12 generations with 100 individuals, PIV measurements were carried out for the optimal control; represented in FIG. 5(g),(i) and (j) for sensor-based, multifrequency open-loop and non-autonomous, respectively. The BFP values extracted at the vicinity of the wall (y H = 0.07) are plotted in FIG. 5(a) for: unforced (dot-dashed gray line), periodic forcing (solid gray line), multi-frequency open-loop (dashed black line), sensor-based (dashed gray line) and non-autonomous control (solid black line). The increase of the internal separation length and the decrease of the external separation point are clearly seen from the unforced flow (dot-dashed gray line) to the non-autonomous control (solid black line). It is interesting to note that multi-frequency open-loop (dashed black line) out-performs the periodic forcing, but the sensor-based (dashed gray line) control law is the least efficient. Moreover, to better understand the effects of the different control laws over the flow, the BFP fields for all cases are presented in FIG. 5(bf). Periodic forcing BFP field is seen in FIG. 5(d

CONCLUSION

Experimental flow control in a separated shear layer using micro-pulsed jets was done. The control target was to modify key turbulent flow parameters such as: internal separation point, external separation point and recirculation area, more specifically increase the first parameter and reduce the others. Periodic forcing, open-and closed-loop machine learning control strategies were used in order to compare and obtain the best control law. Periodic forcing was able to significantly decrease the external separation point and the recirculation area, and to move up the internal separation point. Machine learning control was employed to search for new and more effective closed-loop control laws. Three MLC cases were studied: multifrequency open-loop, sensor-based and non-autonomous. Only twelve generations with 100 individuals were needed to converge towards a control law which outperforms periodic forcing. Non- autonomous control showed to be the best control law strongly modifying all analyzed parameters. The resulting flows were investigated with real-time PIV. The study suggests that MLC can effectively explore and optimize new feedback actuation mechanisms and we anticipate MLC to be a game changer in turbulence control.

ACKNOWLEDGMENT

This work was carried out within the framework of the CNRS Research Federation on Ground Transports and Mobility, in articulation with the ELSAT2020 project supported by the European Community, the French Ministry of Higher Education and Research, the Hauts de France Regional Council. The authors gratefully acknowledge the support of these institutions.

FIGURE 2 .

 2 FIGURE 2. ACTUATION SYSTEM. a) PULSED JET SCKETCH; b) VELOCITY RESPONSE TO AN ARBITRARY SIGNAL

( 1 )

 1 i (s j )), called individuals, is generated randomly by combining user-defined functions, constants and sensors s j (or signals); like in a Monte-Carlo method. Each individ-ual is graded in the experiment (inner loop) and a cost function J(1) 1 is attributed to them. Each generation is made of 100 individuals to assure variability. A new population of individuals b

  )). Both internal (Xr) and external (Lr) separation points and the separation area (Ar) as a function of the Strouhal Number St H = f * H U 0 are shown in Fig. 4. The reattachment lengths and area are normalized by those of the unperturbed experiment. Xr increases while Lr and Ar decreased with increasing St H reaching positive and negative peaks at St H = 0.226, respectively. From results, the best forcing frequency was observed at f = 15Hz, St H = 0.226 and is associated with the shedding phenomena. Xr increases up to 38.4% while Lr and Ar decrease to 4.8% and 19.0%, respectively. The results

FIGURE 3 .FIGURE 4 .

 34 FIGURE 3. GENETIC PORGRAMMING CONTROL LOOP SKETCH

  ). For the multi-frequency open-loop case (Fig.5(e)), a higher reduction of the external separation point (L r = 5.18H), compared to the best forcing frequency, is observed and an increase in the internal separation point X r = 1.42H can be seen. On the contrary, for the sensor-based case (FIG.5(c)), the internal and external separation point did not change significantly. We obtained L r = 5.55H and X r = 0.95H. As expected, the best case combines sensor-based feedback and open-loop forcing. The resulting non-autonomous feedback (FIG.5(f)) gave a strong reduction of the external separation point up to 8.6% (L r = 5.13H) and an increase of 70.6% of the internal separation point X r = 1.48H. Same results are seen for the recirculation area, where the best control law is the MLC non-autonomous reducing this region up to 40.7%. The current study shows that a generalization of multifrequency forcing and sensor feedback control law significantly reduces the turbulent recirculation zone. A summary of all the results is presented in FIG.6. The key enabler is MLC for optimizing the control laws. The study indicates that MLC can effectively explore and optimize new feedback actuation mechanisms in numerous experimental applications.

FIGURE 5 .

 5 FIGURE 5. BACKWARD FLOW PROBABILITY. (a) BFP PRO-FILE EXTRACTED AT y/H=0.07, FLOW PROBABILITY FIELD: (b) UNFORCED FLOW: DOT-DASHED GRAY LINE IN FIG.(a), (c) MLC SENSOR-BASED: DASHED GRAY LINE IN FIG.(a), (d) OP-TIMAL PERIODIC FORCING: SOLID GRAY LINE IN FIG.(a), (e) MLC MULTI-FREQUENCY: DASHED BLACK LINE IN FIG.(a), (f) MLC NON-AUTONOMOUS: SOLID BLACK LINE IN FIG.(a), (g) CONTROL LAW SIGNAL MLC SENSOR-BASED, (h)CONTROL LAW SIGNAL OPTIMAL PERIODIC FORCING, (i) CONTROL LAW SIGNAL MLC MULTI-FREQUENCY,(j) CONTROL LAW SIG-NAL MLC NON-AUTONOMOUS.

FIGURE 6 .

 6 FIGURE 6. SUMMARY OF SEPARATION POINT AND REGION FOR ALL STUDIED CASES. ◇ INTERNAL SEPARATION POINT Xr, ◇ EXTERNAL SEPARATION POINT Lr, ◆ RECIRCULATION AREA Ar. VARIATIONS ARE IN %


Grégoire Bonin

Achour Mostéfaoui

Matthieu Perrin

Does the operational model capture partition tolerance in distributed systems?

In large scale distributed systems, replication is essential in order to provide availability and partition tolerance. Such systems are abstracted by the waitfree model, composed of asynchronous processes that communicate by sending and receiving messages, and in which any process may crash. Complexity in local memory has already been studied for several objects, including sets, databases and collaborative editors. However, the literature has focused on a subclass of algorithms, called the operational model, in which processes can only broadcast one message per update operation and the read operation incurs no communication.

This paper tackles the following question: are the operational model and the wait-free model equivalent from the complexity point of view?

We show that update consistency allows implementations in the wait-free model that require strictly less local memory than their counterparts in the operational model.

Introduction

In distributed systems, shared objects are used to simplify the implementation of distributed applications, and provide fault tolerance by replication. Problems arise with replication as consistency has to be maintained between the different replicas.

The most natural and intuitive abstraction for the user would be to view a distributed/replicated object as if it is a single physical object shared by all the processes. This means that all the operations on the object, possibly concurrent or interleaving, appear as if they have been executed atomically and sequentially. Such an abstraction has to respect a correctness condition called strong consistency. Unfortunately, the CAP Theorem [START_REF] Gilbert | Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services[END_REF] states that this property is unrealizable in most systems, as it is impossible to combine strong consistency, availability and partition tolerance in asynchronous systems. Eventual consistency was introduced to overcome this issue. It states that, after update operations stop taking place, the different replicas will eventual converge to an identical state.

In this context, Conflict-Free Replicated Data Types (CRDTs) [START_REF] Shapiro | Conflict-free replicated data types[END_REF] constitute a family of objects designed to achieve eventual consistency. Those are based on a theorem stating the equivalence between two kinds of objects: the Commutative Replicated Data Types (CmRDTs), in which all update operations commute, and Convergent Replicated Data Types (CvRDTs), whose states form a lattice. For example, the G-set (grow-only set) provides two different operations: an update operation that inserts an element and a query operation that reads if a specific element is in the set. On the CmRDT viewpoint, inserting x and inserting y commute. On the CvRDT viewpoint, the set inclusion is a lattice order on the states of the set. The operational model has been proposed to abstract the implementation of CRDTs. In the operational model, each replica maintains a local state on which the operations are done. An update operation is divided into two facets. First, the update operation is prepared locally by the replica where the update operation is issued and then a message is broadcast to inform all other replicas. Second, the local state of each replica is updated at reception of the update message. By the commutative effect all replicas converge to the same state when no update operation is in progress.

As only one message is broadcast per update operation, algorithms in the operational model are, by design, optimal in terms of the number of used messages. The amount of metadata that must be stored on each replica to ensure convergence is more problematic and has been widely studied for several objects including sets, counters and registers [START_REF] Burckhardt | Replicated data types: specification, verification, optimality[END_REF], data stores [START_REF] Attiya | Limitations of highly-available eventuallyconsistent data stores[END_REF] and collaborative editors [START_REF] Attiya | Specification and complexity of collaborative text editing[END_REF].

Despite the fact that algorithms from the operational model are naturally partition tolerant and minimize the number of messages needed in their implementation, the operational model imposes limitations on the form of its admissible algorithms. It is for example impossible to acknowledge or forward messages, to execute local steps without the reception of a message, or to propagate information during read operations. This prevents algorithms from using more advanced techniques like the message schemes used by checkpointing [START_REF] Randell | Reliability issues in computing system design[END_REF][START_REF] Baldoni | Characterization of consistent global checkpoints in large-scale distributed systems[END_REF]. Such algorithms are usually studied in the wait-free asynchronous message-passing distributed model, or simply the wait-free model, in which asynchronous processes communicate by sending and receiving messages. Any number of processes may crash, which also captures partition tolerance as it is impossible for a process to wait for an acknowledgement from any other process since all other processes may have crashed.

Problem statement

The wait-free model is strictly more general than the operational model, as any algorithm from the operational model can be naturally transformed into an algorithm in the wait-free model, but the converse does not hold. In particular, this means that the complexity results proven in the operational model may not hold in the wait-free model.

Therefore arises the following question: are the wait-free model and the operational model equivalent in terms of complexity ?

Approach In this paper, we consider objects specified by a sequential specification, that describes the behaviour of the object when processes access it sequentially, and a weak consistency criterion, namely update consistency [START_REF] Perrin | Update consistency for wait-free concurrent objects[END_REF]. Update consistency strengthens eventual consistency by stating that the convergence state must be obtainable in a sequentially consistent execution. In other words, it can be obtained by a sequential ordering of the update operations. On a computability viewpoint, it is possible to implement any object with this criteria in both computing models [7, ?].

Contributions We prove that there exists an object whose implementation in the wait-free model requires strictly less local memory than its operational model counterpart.

In Section 2, we present the shared objects that we consider for our proofs, and more particularly a new object, the Countdown-append, as well as the two consistency criteria we use. In Section 3, we present the state of the art of the two models and define our formalism to study the properties of the implementations of the two models. In Section 4, we present the algorithm type and the complexity that we use to compare the different models. In Section 5, we prove the difference between the two models under update consistency. In Section ??, we prove the equivalence of the two models under causal convergence.

Shared objects

In distributed systems, several kinds of shared objects have been proposed to provide the processes with higher-level abstractions. There are two main kinds of objects. On the one hand, one-shot objects like consensus and renaming are a generalization of functions in sequential systems, where each process proposes an input and decides an output. One-shot objects are specified by a binary relation that relates input vectors to the admitted output vectors. On the other hand, long-lived objects, such as registers and queues, are a generalization of data structures in sequential programming, aiming at storing and organizing data in memory. This paper only considers long-lived objects Long-lived objects are defined by three components: a sequential specification that describes its expected behaviour when operations are accessed sequentially (e.g. a queue or a stack), a consistency criterion that describes how concurrency affects the object (e.g. linearizability or eventual consistency), and a progress condition that enforces termination guarantees. The only progress condition we address in this paper is wait-freedom: all operations invoked by non-faulty processes terminate.

Sequential specifications

In order to keep close enough to the CRDTs, we suppose that shared objects are accessed by two distinct kinds of operations: updates, from a set U , modify the local state of the object but do not return a value, and queries, from a set Q, return a value in a set B that depends on the state of the object but do not modify it1 . The set of all operations is A = U ∪ (Q × B). A sequential history is a (finite or infinite) sequence of symbols in A.

The sequential specification of an object is the set of all sequential histories admitted by the object. It describes the behaviour of the object when it is used by a single process.

As an example, we now define the l-countdown-append object, where l ∈ N, that will be especially useful in Section 5. The l-countdown-append object exposes 4 update operations, a, b, c and d and one query operation, q. Figure 1 represents the behaviour of the object as an automaton. It is divided into two phases: during the first phase, the object counts the number of update operations, starting from l, down to 1, then ε (the empty word). In the second phase, the operation is concatenated at the end of the state. Finally, the query operation returns the local state of the objects each time it is executed.

l l -1 2 1 ε * * * * a b c d a b c d a b c d
aa ab ac ad . . . q q q q q q q q q q q q . . . q Fig. 1. Representation of a l-countdown-append object as an automaton.

Consistency criterion

A consistency criterion defines how concurrency affects the distributed behaviour of an object. Formally, it identifies which distributed histories are admissible for a given sequential specification.

A distributed history models a distributed executions of a program using a shared object. It is defined by a tuple H = (A, E, L, →) ∈ H, where:

-A is the set of operations of the object (the same set as in sequential histories); -E is a countable set of events; -L : E → A is a labelling function, that labels each event by an operation; -→∈ E 2 is the process order, a partial order such that e → e if e precedes e on the same process.

A sequential history is a linearization of a distributed history H if it contains the same operations as H, and the order of appearance of the operations is compatible with the process order between the events labelled by the operations. We now define formally the consistency criterion used in this paper: update consistency.

Update consistency: A history is update consistent [START_REF] Perrin | Update consistency for wait-free concurrent objects[END_REF] for an object O if, when all the processes stop executing update operations, they eventually converge towards a state resulting from a linearization of the update operations. Formally, a history H is update consistent if it is in one of the two following cases :

-The processes never stop updating, i.e. H contains an infinity of update operations. -It is possible to omit a finite number of query operations such that resulting history has a linearization in the sequential specification of O.

Computing models

We now present the two computing models used in this paper: the wait-free model and the operational model, as well as the definition of an execution in the wait-free model.

Wait-free model

The wait-free asynchronous message-passing system model, or simply wait-free model, is composed of n processes called p 1 , p n . The set of all processes is denoted by P . The number n of participating processes is bounded, although it may not be known by each of them. Processes are asynchronous, in the sense that there is no bound on their relative speed. Moreover, processes can fail by crashing: a faulty process executes correctly until it crashes, at which point it stops operating. A process that does not crash during an execution is called correct.

Processes can communicate by sending and receiving messages. Communication channels are reliable, as all sent messages are eventually received by correct processes. However, channels are asynchronous, in the sense that there is no bound on the time it takes for one message to be delivered. We suppose that all sent messages can be uniquely identified.

We assume that processes have access to the causal broadcast abstraction that provides them with an operation broadcast (m) operation and a receive (m) event, where m is a message, respecting the following properties.

-Validity: If a process delivers a message m, then m was broadcast by some process.

-Uniformity: If a process delivers a message m, then all correct processes deliver m.

-Termination: If a correct process p i attempts to broadcast m, then p i terminates its broadcast invocation and eventually delivers m. -Causal delivery: If a process delivers a message m and then broadcasts a message m , then all processes delivering m have previously delivered m

Note that causal broadcast can be easily implemented in the wait-free model [START_REF] Raynal | The causal ordering abstraction and a simple way to implement it[END_REF]. However, this implementation has a cost in local memory. We choose to include the primitive in the model to isolate the complexity needed to maintain consistency of the shared objects from the complexity needed to ensure complexity, and therefore reducing the noise of the complexity results we obtain in the next sections.

Operational model

The operational model allows algorithms of form of Algorithm 1. Each process maintains a local state. Query operations return a value that is locally computed based on the local state. Update operations are separated into a prepare function and an effect function. The prepare function computes locally a piece of information m based on the update function and the local state. Then, function ef f ect(m) is applied asynchronously on all processes.

Algorithm 1: operational model algorithmic form

There is a canonical injection that maps any algorithm A in the operational model into an algorithm op2wf (A) in the wait-free model, as illustrated by Algorithm 2. The local states of op2wf (A) are the same as the payload of A and the queries remain unchanged. In the update operations, the result of the prepare function is transmitted to the effect function as a single message forwarded on the network. Because of this, the operational model can be viewed as a restriction of the wait-free model, where additional constraints on the use of the messages have been added.

By a slight abuse of language, from now on, we will use the term "algorithm" (without precision), to refer to algorithms in the wait-free model. Further notions defined on algorithms are extended to algorithms from the operational model thanks to the canonical injection.

1 object A ∈ OM (T ) 2 localA ← ζ0; 3 operation α is 4 if α ∈ UT then

Complexity

We consider deterministic algorithms. This allows us to define a state by an execution or a history. In order to compare the local complexity of algorithms in the different models, we define the H-complexity that allows us to compare the efficiency of two algorithms when executing the same history. As the algorithms are deterministic, we can compare equivalent state in the two algorithms (if the states are defined by the same sub-history, then they are equivalent).

Definition 1 (H-complexity).

Let H be a history that contains a finite number of updates, and let Λ be an algorithm. Let S be the set of all local states reachable by any process executing Λ during an execution that can be abstracted by H.

We define the H-complexity of Λ as follows:

if S = ∅ (i.e. if H is not admitted by Λ), the H-complexity is 0; if S is infinite (i.e. if S contains states of unbounded size), the H-complexity is ∞; otherwise, the H-complexity is the maximal size of a state in S.

Update consistent countdown-append object

In this section, we prove that the two models are not equivalent under update consistency. To do so, we study implementations of the l-Countdown-append object in both models. More precisely, we compare the number of bits that can be needed to encode the local state of some process after it executes l update operations.

For all words v = u 1 ...u l ∈ {U l } consisting of l update operations of the lcountdown-append object, we denote by H v = (U, {1, ..., l}, i → u i , < |{1, ..., l}) the history in which one process performs all updates of v in their order of appearance.

We prove the following results. On the one hand, the H v -complexity of any algorithm in the operational model is at least l 2 -1 bits, for some v. On the other hand, there exists an algorithm in the wait free model with an H v -complexity in O(n log(nl)) bits for all v.

Intuitively, the reason for this difference comes from the fact that the information returned by the query operation changes between the countdown phase and the append phase of the object. Because of message reordering, it happens that the operations that form the return value in the second phase are already known (and misinterpreted) by some processes during the first phase. In the wait-free model, this information can be retrieved from other processes afterwards. This is not possible in the operational model, so processes have to store it locally.

Lower bound in the operational model

We now prove that any algorithm in the operational model has a H v -complexity of at least l 2 -1 bits for some v. Our proof follows the scheme introduced in [4]: we build a family of executions such that, at some point in the execution, process p i performing the operations of v is unable to distinguish between all these executions and an execution modeled by H v . Then, in a later stage of the execution, p i must be able to distinguish between enough of them in order to keep convergence possible.

P1 P2 u1,1 u2,1 u l-1,1 u l,1 u1,2 u2,2 u l-1,2 u l,2 q → ε q → ε q → sc q → sc U1 U2 Fig. 2.
Typical execution in the proof of Theorem 1 Theorem 1. For any deterministic algorithm Λ that implements an update consistent l-countdown-append object in the operational model, there exists v such that the H v -complexity of Λ is at least l 2 -1 bits. Proof. Let Λ be an algorithm in the operational model implementing an update consistent l-countdown-append object. For each pair of words of update operations (v 1 , v 2 ), where v 1 ∈ {a, b} l and v 2 ∈ {c, d} l , we define the execution X (v1,v2) , illustrated on Figure 2, as follows. Only two processes p 1 and p 2 take steps in X (v1,v2) . All other processes crash before the beginning of the execution. Initially, process p 1 (resp. p 2 ) executes sequentially, in order, the operations forming v 1 (resp. v 2 ). In accordance to the operational model, they broadcast a single message during each operation. In a later stage, they both receive the others' messages, respecting the FIFO ordering. Finally, both processes perform a query operation. We denote by X = {X (v1,v2) |v 1 ∈ {a, b} l ∧ v 2 ∈ {c, d} l } the set of all X (v1,v2) executions.

Let us first remark that update consistency imposes that both query operations returns the same value v c , that is a suffix of size l, of an interleaving of v 1 and v 2 . Let f (v 1 , v 2 ) be the number of c and d operations in v c . Note that f is well defined because Λ is deterministic.

We now distinguish the executions depending on which process has a majority of operations in the convergence state. We define

X 1 = {X (v1,v2) ∈ X : f (v 1 , v 2 ) ≥ l 2 } and X 2 = X \ X 1 .
As X 1 and X 2 form a partition of X which has a size 2 2l , we have

|X 1 | ≥ 2 2l-1 or |X 2 | ≥ 2 2l-1 . Without loss of generality, we suppose that |X 1 | ≥ 2 2l-1 .
We now partition X 1 based on the value of v 1 . For each word v 1 ∈ {a, b} l , let

X 1 (v 1 ) = {X (v,v2) ∈ X 1 : v = v 1 }. There exists a word v 1 such that |X 1 (v 1 )| ≥ |X1| |{a,b} l | = 2 2l-1 2 l = 2 l-1 . Let us fix such a v 1 .
Let v 2 and v 2 such that X (v1,v2) and X (v1,v 2 ) belong to X 1 (v 1 ). By definition of f , if X (v1,v2) and X (v1,v 2 ) converge to the same state, then v 2 and v 2 differ at most by their l -f (v 1 , v 2 ) ≤ l 2 first operations. Consequently, there are at least

2 l-1 2 l 2 = 2 l 2 -1 different values for v 2 for which X (v1,v2) lead to different convergence states. Let X be a subset of X 1 (v 1 ) of size 2 l 2 -1
, in which all convergence states are different.

In the operational model, the local state of process p 2 at the end of the execution only depends on its local state after executing its own l update operations, and the messages received from p 1 afterwards. In all the executions of X , the messages received by p 2 are the same in all executions because v 1 is fixed. Moreover, the local state of p 2 at the end of all executions is different. This means that the local state of p 2 after doing its updates is also different in all executions. Consequently, there is a word v 2 such that, after executing all update operations in v 2 (execution X), the local state of p 2 requires at least l 2 -1 bits.

Finally, let us consider the execution X in which only p 2 takes steps, executing a the sequence of update operations of v 2 . Just after executing its updates, p 2 cannot distinguish between executions X and X , so its local state in X also requires l 2 -1 bits. Moreover, X is modeled by H v2 . Therefore, the H v2 -complexity of Λ is at least l 2 -1 bits.

Upper bound in the wait-free model

We now prove there is an algorithm that implements an update consistent l-Countdown-append in the wait-free model with a lower H v -complexity, for any v. Our proof is based on Algorithm 3, based on the algorithm UQ 0 from [START_REF] Perrin | Distributed Systems: Concurrency and Consistency[END_REF]. Each process p i maintains four variables. Variables countdown i and append i represent the current local state at p i . If countdown i > 0, the l-countdownappend object is in the countdown phase. Otherwise it is in the append phase and its value is append i . Variable clock i is the equivalent of a version vector, such that clock i (j) that represents the number of operations done by p j that are taken into account into the current state of p i . As p i does not know the number of participants, it is encoded as an associative array, rather than a vector. Finally, variable leader i is the identifier of a process such that, clock i < clock leaderi or p i and p leaderi are in the same local state.

When a process invokes the query operation q, it computes locally the state of the object based on countdown i and append i .

When process p i invokes an update operation a, b, c or d, it increments its local clock clock i [i] and broadcasts a message mUpdate (Line 9). At reception of such a message, p i executes the operation (decrements countdown i if the countdown is not finished, or append the operation to append i ), and answers with a mUpdate message containing its version of the state and its current vector clock.

When receiving a correction message, the process checks if the message received is more recent according to the vector clock, and if that is the case, it replaces its own data with the received one.

In order to keep the paper as readable as possible, we only give a sketch of the correctness proof here. A more formal proof can be found in [START_REF] Perrin | Distributed Systems: Concurrency and Consistency[END_REF].

Lemma 1 (Update consistency). All distributed histories admitted by Algorithm 3 are update consistent for the l-countdown-append object.

Proof. Let H a history admitted by Algorithm 3. If H contains a finite number of queries or an infinite number of updates, it is update consistent by definition. Otherwise, at least the process performing updates is correct. Let us suppose that each process p i performs a finite number m i of updates. Let us pose m = n i=1 m i . After some finite time t 1 , all correct processes have received all messages mUpdate sent during the execution, and after some finite time t 2 , all correct processes have received all messages mCorrect sent during the execution.

If m ≤ l, after t 1 , all read operations return l -m (or ε when l = m), which is correct for update consistency. If m > l, all correct processes broadcast m -l messages mCorrect. Let us consider the process p j that broadcast m-l messages mCorrect, with the smallest identifier (it exists because at least one process is correct), and let mC = mCorrect(cl j , j, a j ) be its last message. Because of the causal broadcast, no process can receive a message mUpdate after mC. Moreover, the clock cl j is maximal and j is minimal, so by the condition of lines 18-19, all processes will adopt state a j at reception of mC and keep it afterwards. Finally, a j is corresponds to a state accessible by a linearization of the updates in H: the clock mechanism of lines 11 and 18-19 ensures that each update is applied Proof. By Lemmas 1, 2 and 3, Algorithm 3 is an example.

We can finally conclude on the non-equivalence between the two computing model in the implementation of update consistency.

Corollary 1. There exists an object O and an algorithm Λ wf implementing an update consistent O in the wait-free model, such that, for any algorithm Λ om implementing an update consistent O object in the operational model, there is a history H such that Λ wf has a strictly lower H-complexity than Λ om .

Proof. By Lemma 3, there exists a constant x > 1 such that, for any v, the H v complexity of Algorithm 3 is strictly lower than x log(nl) bits. Let l > 2 -1+x log n x . We have x log(nl) < l 2 -1. Let O be the l-countdown-append object, and let Λ om implementing an update consistent O in the operational model. By Theorem 1, there exists v such that the H v -complexity of Λ om is at least l 2 -1 bits. Therefore, Algorithm 3 has a strictly lower H v -complexity than Λ om .

Conclusion

In this paper we answered the following question: are the wait-free model and the operational model equivalent in terms of local complexity? We proved that the response to this question is no in the case of update consistency: we proved that there exists an object that has a different complexity in the two models: the lcountdown-append object. In the wait-free model, there is an algorithm for which the complexity required to encode a special state of the object is upper bounded by O(log(nl)) bits, whereas in the operational model, any algorithm requires at least l 2 -1 bits to encode the same state. This means that the operational model does not allow the optimal implementation for update consistency.

The result proposed in this papers shows that the question of whether the operational model is well suited to represent partition tolerance is not simple, especially in the context of determining the complexity in local memory required to implement shared objects. An interesting open question is whether the lower bounds proved for several objects in the operational model can be extended to the wait-free model.

8 m 9 effect(m) 10 P

 8910 is an information to be passed ayload ← τu(m, P ayload)

5 Send

 5 M (α) is received from 8 localA ← τα(localA); Algorithm 2: Wait-free model translation of the operational model algorithmic form

This hypothesis is only done for the sake of clarity and can be easily removed, like in[START_REF] Perrin | Distributed Systems: Concurrency and Consistency[END_REF].

1 var clocki ∈ Array(N, N) ← [i → 0]; 2 var leaderi ∈ N ← i; 3 var countdowni ∈ {0, ..., l} ← l; 4 var append i ∈ U ← ε; 5 operation q() 6 if countdowni = 0 then return append i ; 7 else return countdowni;

Algorithm 3: The countdown-append object in the wait-free model exactly once, and causal delivery ensures that the order between the updates is respected.

Lemma 2 (Wait-freedom). Algorithm 3 is wait-free.

Proof. This comes from the fact that it contains no loop.

Lemma 3 (Complexity). For all l ∈ N and v ∈ U l , Algorithm 3 has an H vcomplexity of O(log(nl)) bits.

Proof. Let l ∈ N and v ∈ U l . In any execution abstracted by H v , there is a process p i that performs all l update operations, and sends all messages mUpdate. At reception of any of these messages by any process p j , the condition of Line 13 is false, so no message mUpdate is ever sent.

For all processes p j and p k = p i , clock j [k] = 0 and clock j [i] ≤ l. If we encode clock i by a set of pairs j, clock i [j] , the encoding takes less than log(n) + log(l) = log(nl) bits; The process identifier leader i can be encoded in log(n) bits; countdown i can take at most l different values, so it can be encoded in log(l) bits; finally append i = ε is a constant value, so it has an encoding of constant size c. Theorem 2. There exists an algorithm Λ implementing an update consistent l-countdown-append object in the wait-free model such that, for all v ∈ U l , Λ has an H v -complexity of O(log(nl)) bits.