Mohammad Esmail Alikhani

Laurent Manceron
email: laurent.manceron@synchrotron-soleil.fr

The copper carbonyl complexes revisited: why are the infrared spectra and structures of copper mono and dicarbonyl so different?

Keywords: CuCO, Cu(CO) 2, far infrared, infrared spectrum, structure, bonding analysis, Renner-Teller effect

New Infrared absorption data have been obtained using isolation in solid argon and neon on copper carbonyl molecules, CuCO and Cu(CO) 2 , two very reactive molecules. For CuCO, all three fundamentals are now observed and it presents an unusually large matrix effect, in line with former results indicating a weak metal carbon interaction and a large total dipole moment. With help of isotopic effects, new data indicates unambiguously that Cu(CO) 2 is linear and presents a notably stronger metal-carbon interaction than CuCO. Quantum chemical calculation have been carried out at the CCSD(T) level for determining energies and structural properties, as well as spectroscopic observables. The results enable an assessment of the high stability of the Cu(CO) 2 molecule (first bond dissociation energy of 66 kJ/mole) which suggest that observation at room temperature is possible and give a first evidence of Renner effect on a penta-atomic molecule.

Introduction

One chief application of rare gas matrix isolation (MI) is the trapping of reactive or unstable species, as large amounts (µmole range) of radicals or transient species can be stabilized in solid solution within a thin solid rare gas slab, enough to permit the use of a combination of various spectroscopic techniques [1]. Among the pioneers in the field [START_REF]Chemistry and Physics of Matrix-Isolated Species[END_REF] who developed co deposition of metal atoms with small molecules to model various reactions, M. Jacox was among the first to use alkali atoms to generate molecular anions by charge transfer mechanisms [START_REF] Andrews | [END_REF]4]. Among many contributions, she was one of the first to implement a variety of spectroscopic techniques, including far infrared spectroscopy, taking advantage of the fact that these reactive species are trapped and made longlived. In more recent years, with the generalization of ab initio and DFT quantum chemical (QC) calculations and the improvement of its predictive power for spectroscopic properties, M. Jacox warned against the danger of relying solely on apparent matches between QC-predicted vibrational frequencies for making definite species identifications or transitions assignments and advocated combining and cross-checking these with extensive isotopic effects [5]. These principles have been an inspiration to many and in particular to us here.

Neutral copper carbonyl complexes have been the object of many studies and came across to be intriguing objects, laboratory models for a number of concepts. For the copper mono-carbonyl after several conflicting studies, a consensus has emerged that it is a weakly bound, quite floppy species and a non-conventional, bent structure [6][7][8][9]. The situation for the di-carbonyl species is quite different: experimental data are much scarcer and all theoretical studies converge in predicting a much more strongly bound species with a linear structure. It has been observed in three separate infrared absorption MI studies, following the brief initial report of Ogden [10], the more complete work on binary copper carbonyl complexes by Huber and coworkers [11] who detected a very intense CO stretching fundamental vibration and, more recently, in the work by Andrews and coworkers [12] on the isolation of neutral and ionic copper carbonyls and the frequencies for this mode re-measured in solid argon and neon. On the basis of isotopic effects and of the inactivity of the second, symmetrical CO stretching, it was concluded that this species should be centrosymmetrical, presumably linear. Remarkably, it was not observed in two separate ESR MI studies by Kasai and Jones [13] and Chenier and coworkers [14], in samples where the other binary carbonyls (CuCO and Cu(CO) 3 ) were observed. This negative result was interpreted as a proof that this molecule is, indeed, linear and having a 2 Π ground state, in which case it is expected to be ESR-silent. In 1995, V. Barone, using various DFT-based calculations, predicted the electronic structures, energies, geometries and some spectroscopic vibrational properties of the CuCO, Cu(CO) 2 and Cu(CO) 3 series [15], predicting remarkably well the bent structure of CuCO and that Cu(CO) 2 should revert to linearity with a 2 Π ground state. Even more recently, Cerón and Mendizabal examined in detail for the first time using high level ab initio methods, ranging from MP2 to CCSD(T), the reasons for the change in bonding strength when going from CuCO to Cu(CO) 2 [16] . In particular, they showed that the low stability of the copper-monocarbonyl [17] could be perfectly explained by calculating the induction and dispersion contributions, at the highest level of theory. In a parallel publication, Wu et al. reached quite similar conclusions [18] and compared the performances of several DFT methods. None of these theoretical studies confronted their predictions, however, to the available experimental data on the low frequency metal-ligand stretching and bending modes [19], most sensitive to the nature of the bonding and the chosen QC method.

In the course of studies devoted to the observation of the low frequency stretching and bending modes of transition metal carbonyls, new data pertaining to Cu(CO) 2 and Cu(CO) 3 were observed in our laboratory. If the data concerning the Cu(CO) 3 complex match reasonably well the former DFT predictions [15] and are readily understandable in terms of a vibrational spectrum of a trigonal, D 3h symmetry species, the data concerning Cu(CO) 2 present specific features which cannot be readily understood in terms of a purely vibrational spectrum of a linear species. In fact, with a 2 Π ground state, Cu(CO) 2 constitutes a rare example of five-atomic molecule with a Renner-Teller effect. The goal of this contribution is thus three-fold: make use of the unique possibilities of MI to investigate the IR spectroscopy of a linear five-atomic molecule with a Renner-Teller effect, give spectroscopic indicators of the bonding strength in Cu(CO) 2 and describe the specific features of the bonding with topologic arguments at the required level of theory.

Experimental details.

Samples containing copper carbonyl complexes were formed by co-condensing Cu vapor and dilute CO-Ar or Ne mixtures (0.5-16% CO/Ar or 200-2000ppm O 2 /Ne), onto one of six flat, highly polished, Rh-plated copper mirrors maintained between 3 and 15K using a pulse-tube, closed-cycle cryogenerator (Cryomech PT405, Syracuse, USA), the experimental procedures are described in Reference 20.

Copper wire (99.998% purity, Alpha Aesar) was wrapped around a tungsten filament, and heated at 800-900°C to generate the Cu metal vapour. The metal deposition rate was carefully monitored with the aid of a quartz microbalance and was varied from 1 to 10 nanomol/min. High purity Neon or Argon (Air Liquide, France; 99,995%), carbon monoxide (Air Liquide, France; 99,998%), 13 O) were used to prepare the gas mixtures. Survey absorption spectra were recorded between 10000 and 50 cm -1 on the same samples using a Bruker 120 FT spectrometer with 0.1 cm -1 resolution and different beam splitter/sources/detector/window combinations covering the far infrared to near infrared range, as detailed in Ref. 20. For selected spectral ranges, high resolution scans were acquired with 0.02 cm -1 resolution. Diffusion experiments were performed by annealing the samples to 9 -10K (neon) or 25-30 K (argon) in the dark, the sample facing an 80K radiation shield.

Computational details:

Geometrical optimizations, vibrational frequency and Natural Bonding Orbital (NBO) calculations have been performed using the Gaussian 09 quantum chemical package [21]. Optimized molecular structures and harmonic vibrational frequency of CO, CuCO, and Cu(CO) 2 compounds were determined by means of the coupled-cluster single and doubles and with perturbative triples [CCSD(T)] method with the 6-311+G(2d) Pople's basis set, as implemented in Gaussian 09 package. Additional optimization and harmonic vibrational frequency computations were carried out with the popular B3LYP functional.

The NBO figures have been obtained using the Multiwfn Version 3.3.5 software [START_REF] Lu | Multiwfn: A Multifunctional Wavefunction Analyzer[END_REF].The nature of chemical bonding has been investigated in the framework of the AIM ("Atoms In Molecul" of Bader [START_REF] Bader | Atoms in Molecules: A Quantum Theory[END_REF]) topological approach with help of the AIMAll code [START_REF] Aimall | TK Gristmill Software[END_REF].

We recall that the "wfx" files, necessary to the AIM calculations, were obtained with a CCSD/6-311+G(2d) single-point calculation at the CCSD(T)/6-311+G(2d) optimized geometry and using the "Density=Current".

Experimental Results

Figure 1 presents the infrared spectra observed for CuCO isolated in solid argon and neon. As noted earlier, the ν 2 and ν 3 metal-ligand bending and stretching fundamentals of this species are at low frequency [19]. Also, notably, while the ν 1 mode experiences a small blue shift from 2010 to 2034 cm-1 ( 1.2%) from argon to neon, the low frequency modes experience a very large redshift (322.7 to 294.9 cm-1, thus -9.7%, and 207.5 to 176.7 cm-1, thus -17%). These latter values indicate an anomalously large matrix effect. For most rigid molecules, the compilation of matrix results by M. Jacox indicates an average gas-to matrix shift of -2% for argon and less than 0.4% for neon [1]. A large matrix effect for argon is expected when a highly polar molecule is embedded in this polarizable medium, especially for weakly bonded species [START_REF] Jacox | [END_REF]. In solid neon, much less polarizable, more reliable data are obtained and the frequencies observed here can serve as better reference point for QC calculations.

Remarkably, the known Cu(CO) 2 absorptions present only a slight argon to neon blue shift (0.8 to 0.1%, +0.4% on average), characteristic for a rigid, more covalently bound molecule, thus confirming that the bonding evolves markedly by adding a second carbonyl group (see theoretical section below).

As noted by earlier workers, the Cu(CO) 2 and Cu(CO) 3 species are favored in samples with relatively high CO content (typically 2 to 4 % in argon) and can be easily discriminated in the CO stretching vibration region, between 2100 and 1850 cm-1, from CuCO absorption with stepwise CO concentration increase (figure 1 of reference 19), with Cu(CO) 2 growing after CuCO, and Cu(CO) 3 appearing next. It is thus straightforward to discriminate and group infrared absorptions pertaining to Cu(CO) 2 and Cu(CO) 3 from their growth behavior. All absorptions observed in argon present a multiple trapping site pattern, common for the medium [1,[START_REF]Chemistry and Physics of Matrix-Isolated Species[END_REF]. For the sake of simplicity, we will only quote further the main trapping site frequencies. In neon, the absorptions are quite sharp and present a single trapping site after deposition. In this study, we observed nine new bands for various isotopic precursors of Cu(CO) 2 (table 1) and ten new bands for Cu(CO) 3 (table 2). The new data observed emerged mainly in two spectral regions: the mid-to near infrared above 2500 cm -1 and the mid-to far infrared between 800 and 100 cm -1 . For each band observed with a single isotopic precursor characteristic patterns emerge with 12 CO + 13 CO isotopic mixtures : triplets for Cu(CO) 2 and quartet for Cu(CO) 3 (Figures 234567), as expected for species with two, respectively three, carbonyl groups.

The data for Cu(CO) 3 (table 2) are only mentioned here and will not be discussed further as this molecule is not the objective of this work.

For Cu(CO) 2 , the near infrared features must involve overtones or combinations involving the high frequency carbonyl stretching modes. From simple symmetry consideration only ν 1 +ν 3 , ν 2 +ν 3 , ν 1 + ν 4 can produce IR active transitions for the stretching motions, while combination of ν 3 +ν 5 , ν 1 + ν 6 (with ν 5 and ν 6 being the trans-and cis-Cu-C=O bending modes , respectively (figures 2 and 3). The frequencies for the various isotopic species for the strong ν 3 antisymmetrical CO stretching mode are known, and our experiments show here a weaker band at 2031.0 cm -1 , belonging to the dicarbonyl molecule, which also indicate that of the ν 1 symmetrical stretching for the Cu(CO)( 13 CO) species (figure 4) for which the inversion center is no longer present and this motion slightly IR activated. This band is observed with an intensity ratio of about 0.034 (9) with respect to the strongest, ν 3 antisymmetrical CO stretching mode at 1865.9 cm -1 . Thus, assignments of the bands at 3914.9, 2542.5 and 2297 cm -1 to the ν 1 +ν 3 , ν 2 +ν 3 and ν 1 + ν 4 transitions are fairly straightforward. This implies an X 11 and X 13 anharmonicity coefficients of 40.2 and 14.4 cm -1 , somewhat larger but in line with Ni(CO) 2 , a comparable example [26]. Note that the relationship X 11 / X 13 = 4 , true in the limit of the local mode model developed by Mills and Robiette [27], holds here only approximately, showing that ν 1 and ν 3 are not purely carbonyl stretching motions, but vibrations in which carbonyl and metalcarbon stretching motions are notably coupled. This also shows when examining the isotopic effects on ν 3 , with a 12 C/ 13 C shift larger than the 16 O/ 18 O one, in spite of a smaller change in reduced mass, another sign of coupling [28]. Assignment of the weak band at 2542.5 cm -1 to the ν 1 + ν 4 transition would place the ν 4 , Σ u symmetry band around 490 cm -1 . In fact, in the low frequency region, a very weak band is observed near 493 cm-1 (figures 5 and 7), with a notably larger 16 O/ 18 O shift ( -10.7 cm -1 ) than 12 C/ 13 C (-3.5 cm -1 ) , which can thus be assigned to the ν 4 mode. Further below, a much stronger band is observed near 247 cm -1 , with a large 12 C/ 13 C (-7.2 cm -1 ) and a small 16 O/ 18 O (-1.9 cm -1 ) isotopic effects, as expected for a Cu-C=O bending mode, which must involve the cis-C-C=O bending coordinate. Another band is, however, observed near 610 cm -1 with the same isotopic behaviour and, yet, about 15% of the intensity of the former, thus very unusually strong for a combination or overtone transition. Another very weak band is observed near 888 cm -1 with isotopic shifts comparable in absolute value (about -1.9 cm -1 16 O/ 18 O shift and cm -1 -9,7 cm -1 12 C/ 13 C shift), but very different in relative magnitude (-0.2% and -1%, respectively). This finds no simple explanation in a purely vibrational picture. To substantiate these considerations, Table 3 presents the results of a semi-empirical force field for calculations of the purely vibrational isotopic effects. Comparison is made with the frequencies observed for all four Σ u and Σ g stretching modes and the Π u mode for the strong band at 247.4 cm -1 . The remaining Π g modes are first fitted to the values proposed by Barone [15]. These results confirm that the proposed assignments for the stretching modes are fully consistent with the observed isotopic shifts. It is also possible to compute the intensity ratio, predictable with a zero order bond moment approximation, between the ν 1 symmetrical and the ν 3 antisymmetrical CO stretching modes. The value of 0.024 is consistent with experimental results. The model also indicate an important increase in the Copper-carbon bond force constant, from about 1 N/m in CuCO [19] to more than 2.5 N/m in Cu(CO) 2 , a value characteristic for strong coordination bonds, close to that deduced for Ni(CO) 2 [26], but different from the smooth decrease from NiCO to Ni(CO) 2 and Ni(CO) 4 [30][31][32]. This is followed only by a moderate decrease in the CO bond force constant, from 16.6 to 15.2 N/m, and a qualitative change in geometry. These elements clearly indicate that a drastic change in the copper-carbonyl bonding nature takes place with the addition of a second carbonyl group. This motivates an examination of the bonding nature with the appropriate theoretical methods.

Theoretical Results

In their theoretical paper on the mono-and dicarbonyl, Ceron and Mendizabal showed that the stability of the copper-monocarbonyl could be perfectly explained by calculating the induction and dispersion contributions [16]. Consequently, the causes of the failure of the density functional -based methods, not taking into account correctly the dispersion energy, can be understood.

Accordingly, in order to investigate the Cu(CO) 2 , the conclusions of reference 16 were followed and the CCSD(T) method retained. Theoretical geometrical, energetic and vibrational data are gathered in Table 1. For CuCO and Cu(CO) 2 , the binding energy is calculated with respect to CO + Cu and CO + CuCO partners, respectively. The Cu-C bond length decreases by 0.14Å from mono-to dicarbonyl of copper. In parallel, we observe a very small increase in the C-O distance (0.004Å) from free CO to CuCO. However, addition of a second CO leads to a significant lengthening of the C-O bond length (0.011Å). Accordingly, we can easily conclude that the dispersion contribution is not the main cause of the Cu(CO) 2 stability.

Bonding analysis. In order to complete the NBO analysis of Mendizabal, we provide here the plot of the orbitals involving in the bonding between carbon monoxide and copper atom. They are displayed in Figure 8 and9.

In the bent Cu-CO, the bonding interaction of carbon monoxide with copper consists of a concerted electron delocalization over orbitals of σ and  character. We note that the overlapping between σ(Cu) and two *(CO) and σ*(CO) antibonding orbitals is different from zero, owing to the bent structure of Cu-CO. The two bonding driving forces are synergistic and stabilize the complex (D 0 = -10.6 kJ/mol). However, as shown in Table 4, the net charge of Cu is very small (+0.017 e), but enough to polarize substantially the complex (with a dipole moment of 2.14 D calculated at CCSD/6-311+G(2d)//CCSD(T)/ 6-311+G(2d) level, using the Density=Current" keyword).

The AIM topological properties have been listed in Table 2. Changes in the Cu atomic charge and in the charge density at C-O and Cu-C bond critical points are in line with the NBO analysis. For instance, the charge density at the C-O bond critical point decreases by 0.005 and 0.019 e/Å 3 from free CO to CuCO, and to Cu(CO) 2 . The most notable change occurs at the Cu-C bond critical point when we compare CuCO to Cu(CO) 2 : it increases by 40%.

NBO and AIM analyses of Cu(CO) 2 evidenced the simultaneous existence of two phenomena: the formation of the Cu-C electron-shared bonds and the weakening of the CO bond. Thus, in the copper dicarbonyl molecule, copper forms a σ(Cu-C) covalent bond with each carbon monoxide leading to a high energetic stability (D 0 = -66.9 kJ/mol). The CO bonds weaken upon formation of the dicarbonyl copper molecule, owing to the back-donation from lone pair (Cu) to the antibonding *(CO) orbital. These drastic changes in the bonding nature also improve considerably the abilities of DFT-based method for describing the bonding and predicting the spectroscopic properties.

Vibrational frequencies and IR spectrum. As discussed above, Cu(CO) 2 could be, in contrast to CuCO, well described by the density functional bases method. In Table 5 are listed harmonic vibrational frequencies and some force constants calculated at the CCSD(T)/6-311+G(2d), and also some results calculated with B3LYP)/6-311+G(2d) method for CO and Cu(CO) 2 compound. The B3LYP results are reported in parentheses. The results presented here are in good agreement with experimental findings for all four stretching modes and deserve no further special comment, except to note the exceptionnaly high predicted IR intensity for the ν 3 Σ u -symmetry stretching mode, predicted near 2000cm-1 (vs. 1904 (neon) and 1891(argon) cm-1) ( with near 4000 Km/mole), which explains its easy detection in early matrix work [10,11] and targets this mode for possible gas phase observation. The other Σ u -symmetry stretching mode, ν 4 , is predicted very weak, in line with the present experimental data (table 1).

A closer look at the situation indicates that, with a 2 Π u ground state, the molecule should present a Renner-Teller situation [33], corresponding to case (A) as described in ref. [34] (figure 10) with the total energies of both electronic components of the degenerate state increasing as the molecular frame bends, resulting in changes in the bending vibrational frequencies for the vibronic states. In fact, in this case, QC calculations give in this case two different frequency values corresponding to the vibrations in the xz and yz planes (with z the molecular axis). This is caused by the fact that the potential surface for the 2 Π u ground state splits upon bending into two components, with one corresponding to the plane for the unpaired electron of the electronic wave function. These frequencies are, however, different from the observables. A model for handling Renner-Teller effect in linear penta-atomic molecules has been developed by Peric and coworkers [35] in a thorough approach for the general case and applied to one vibronic transition of C 5 -. Our data are, of course, not sufficient to permit extraction of the seven parameters needed for attempting a reliable assignment, namely the frequencies ω T (for the Cu-C=O trans-bending motion) , ω c1 (for the Cu-C=O cis-bending motion) , ω c2 (for the C-Cu-C=O bending motion) , ε T , ε C1 , ε C2 and ε C12 the four Renner parameters (one for each of the bending and one connecting the two cis-bending motions, which can couple by symmetry). Noting that the second cis-C-Cu-C bending mode lies at much lower frequency than the other, Cu-C=O ones and that its Renner splitting seems small from QC calculations, we consider here only a first, very crude approximation: the C-Cu-C is considered rigid and the spin-orbit effect neglected. From the more reliable CCSD(T) calculations, ω T = 343 cm -1 , ω c1 = 320 cm -1 , ε T = -0.41 and ε C1 = 0.19 can be estimated using well-known approximations [36]. From this values and truncating the energy expressions developed in reference 35, we can compute energies of 310 cm -1 for the first transition to the( v c =1, v T =0) vibronic state and energies of 609 and 623 cm -1 to the ( v c =1, v T =1)and ( v c =2, v T =0) levels. Given the general overestimation of the frequencies in our QC calculations, we would thus suggest assignment of the observed transitions near 247 and 610 cm-1 to the transitions from ground to v c = 1 and 2 states. In this simple picture, the very weak transitions observed near 888 cm-1 is not assigned and obviously requires a complete treatment of all vibronic effects.

Conclusions.

In this work new infrared absorption data have been observed for CuCO and Cu(CO) 2 molecules, produced by spontaneous reaction of copper atoms and carbon monoxide in solid argon and neon.

For CuCO, an important matrix effect and a very low copper-carbon stretching frequency both confirm the prediction that this species in a very weakly bound, polar complex. For Cu(CO) 2 ,the matrix effects are very small (less than 0.4% on average) indicating a strongly bound and non-polar species, following the trends noted by M. Jacox [1,[START_REF] Jacox | [END_REF]. Isotopic data on nine new bands, combined with semi-empirical and quantum chemistry calculations at the CCSD(T) level enable assignment of all stretching modes and a discussion of the transitions in the far infrared associated with bending motions. This study thus confirms former predictions that the molecule is linear and far-infrared data give evidence of a much stronger metal-carbon interaction. Also, a set of low-lying transitions cannot be explained in a purely vibrational picture, and is assigned to vibronic transitions caused by Renner-Teller effect, as predictable for a 2 Π u ground state. To our knowledge, this is the first example of spectroscopic data on a neutral penta-atomic molecule with a Renner effect and illustrates the possibility of matrix-isolation to enable a first approach of these phenomena. Experimental and theoretical data converge in indicating a much stronger copper-carbon bond in the di-carbonyl than in the mono carbonyl and the bonding nature in both molecules is analyzed with topological methods. Finally, the relatively high stability (66 kJ/mole estimated here for the first bond dissociation energy) and the very high IR absorption intensity predicted for the ν 3 Σ u -symmetry stretching mode, observed near 1904 cm-1 in solid neon, in a favourable IR domain might facilitate observation of the Cu(CO) 2 molecule in the gas phase, in a cold discharge experiment, for instance. -Cu(CO) 2 a strongly bound and non-polar species.

Tables

-Vibrational data for all stretching modes of Cu(CO) 2 -Vibronic effects for bending modes due to Renner effect.

  = 2.52, F CO,CO = 1.18, F CuC,CuC = 0.32, F CuC,CO = 0.3 mdyne Å -1 ; F CuCO = 0.235, F CCuC = 0.1, F CuCO,CuCO = -0.092, F CuCO,CCuC = 0.0 mdyne Å rad 2 ; R CuC = 1.73 Å, R CO = 1.15 Å, Θ CCuC = Θ CuCO = 180°. b -Set to the QC value, the same as predicted in this work. c -Deduced from combination band and semi-empirical calculation.

 3 (

 3 CuC str./ OCCu bend) = 159, F CuC = 0) 2 ν 1 (g) = 2072 (2111, 0) ν 3 ( u )=2007 (1996, 4880) ν 4 ( u ) = 489 (485, 1) ν 2 ( g ) = 406 (388, 0) F CO = 15.8 (15.65), F CuC = 3.2(3.1) ν cis-XZ = 380 (379,1), ν trans-XZ =309 (303, 0), ν c-Cu-C-XZ = 67 (66, 1) ν cis-YZ = 246 (243, 23) ν trans-YZ =374 (354,0), ν c-Cu-C-YZ = 70 (72

Figure 1 .

 1 Figure 1. Comparison of vibrational spectra for CuCO isolated in sold argon (top) and neon (bottom).

Figure 2 .

 2 Figure 2. Comparison of vibrational spectra in the 2600-2440 cm -1 ν 1 + ν 4 combination region of Cu(CO) 2 for various isotopic precursor in solid argon.

Figure 3 .

 3 Figure 3. Comparison of vibrational spectra in the 4400-3800 cm -1 ν 1 + ν 3 combination region of Cu(CO) 2 and for various isotopic precursor in solid argon. The asterisk designates the V=0-2 transition of 13 C 18 O isotopic impurity.

Figure 4 .

 4 Figure 4. Comparison of vibrational spectra in the 2100-1800 cm -1 region of CuCO, Cu(CO) 2 , Cu(CO) 3 for various isotopic precursor in solid argon. The asterisk designates absorptions due to the 13 C 18 O isotopic impurity.

Figure 5 .

 5 Figure 5. Comparison of vibrational spectra in the 700-100 cm -1 region of CuCO, Cu(CO) 2 , Cu(CO) 3 for various concentrations in solid argon. Cu/CO/Ar = 0.25/0.5/100 (a), 0.25/1/100 (b), 0.4/4/100 (c).

Figure 6 .

 6 Figure 6. Comparison of vibrational spectra in the 280-220 cm -1 region of Cu(CO) 2 for various isotopic precursor in solid argon.

Figure 7 .

 7 Figure 7. Comparison of vibrational spectra in the 670-470 cm -1 region of Cu(CO) 2 for various isotopic precursor in solid argon. The asterisks designates a CuO 2 impurity band.

Figure 8 .

 8 Figure 8. Natural bonding orbitals evolving in the donation (from the occupied σ(C) to the unoccupied σ*(Cu) orbital) and back-donation (from the occupied σ(Cu) to the unoccupied *(CO) and σ *(CO) orbitals) bonding modes in the bent Cu-CO molecule.

Figure 9 .

 9 Figure 9. Natural bonding orbitals evolving in the formation of two σ(Cu-C) covalent bonds and in the back-donation (from the occupied (Cu) to the unoccupied *(CO) orbital) bonding modes in the linear Cu(CO) 2 molecule.

Figure 10 .

 10 Figure 10. Schematic representation of the Renner-Teller potential energy surface for Cu(CO) 2 with 2 Π u ground state.

Figure 1 Figure 2

 12 Figure 1

Figure 3 Figure 4

 34 Figure 3

Figure 5 Figure 6

 56 Figure 5

Figure 7 Figure 8 Figure 9

 789 Figure 7

Figure 10 Highlights-

 10 Figure 10

Table 1 -

 1 Vibrational frequencies (cm -1 ) and relative intensities of the IR absorption bands observed for various isotopic species of Cu(CO) 2 isolated in solid argon (italics for solid neon values).

	Assignment a	Cu( 12 CO) 2	Cu( 12 CO)( 13 CO)	Cu( 13 CO) 2	Cu( 12 C 18 O) 2
	2 1		4021.8
	 1 +  3	3914.9 b 3939.3 (50) c	3872.1	3824.0	3830.8
	 1 +  4	2542.5 2562.0 (2.5)	2520.0	2491.1	2488.3
	 2 +  3	2297 2309.8 (0.8)	2262.8	2237.8	2232.8
	 1	-	2031.0	-	-
	 3	1890.9 1904.5 (4880)	1865.9	1847.2	1850.1
	?	888.4 (0.5)	-	878.7	886.3
	 cis bend	609.8 610.6 (10)	600.8	592.0	603.3
	 4	493 (1)	-	489.5	482.3
	 cis bend	247.4 247.8 (65)	243.5	240.2	245.2
	a-Approximate description with  g -modes: ν 1 CO stretch. and ν 2 Cu-CO stretch,  u -modes: ν 3 CO stretch.
	and ν 4 Cu-CO stretch,  g -modes: ν 5 Cu-CO symmetrical bend,  u -modes: ν 6 , ν 7 Cu-CO, C-Cu-C
	asymmetrical bend.
	b-Argon value for the main trapping site, in italics for solid neon.
	c-Relative intensities with respect to the 493 cm

Table 2 -

 2 Vibrational frequencies (cm -1 ) and relative intensities of the IR absorptions of Cu(CO) 3 isolated in solid argon.

	Assignment a	Cu(CO) 3	Cu(CO) 2 ( 13 CO)	Cu(CO)( 13 CO) 2	Cu( 13 CO) 3	Cu(C 18 O) 3
	 1 +  4	4061.4 (w) b			4022.7	3971.5
	2 4	3943.0 (vw)			3853.8	-
	 1 +  5	2545.6 (vw)			2489.1
	 1 +  8	2479.0 (vw)			2368.5
	 1 +  6	2420.5 (vw)	2408.6		2432
	 4 +  8	2354 (vw)			2297
	 4	1975.5 (s)	1956.5	1942.5	1930.7	1930.8
	 6	630.9 (w)			611.8
	 5	443.5 (w)	440		437.6
	 8	378.5 (s)	374	370	368	374.5
	 6	321.4(s)	322	318	312.1	319.4
	a-Tentative assignment. A' 1 modes: CO, Cu-CO stretching modes (ν 1 ,ν 2 ), A' 2 modes: Cu-C=O in-plane
	deformation (ν 3 ), A" 2 modes: Cu-C=O, C-Cu-C out-of-plane deformations (ν 8, , ν 9 ), IR-active, E' modes:
	C=O, Cu-CO stretch., Cu-C=O, C-Cu-Cu deformations (ν 4 , ν 5 , ν 6, ,ν 7 ) IR-active, E" modes: Cu-C=O out-of-
	plane deformations (ν 10 ).
	b-S=strong, m=medium, w=weak, vw=very weak.

Table 3 -

 3 Comparison of experimental and calculated a harmonic frequencies for various isotopic species of Cu(CO) 2 .

		63 Cu(CO) 2	65 Cu(CO) 2	63 Cu( 13 CO) 2	63 Cu(C 18 O 2 )	Cu(CO) 13 (CO)
		exp	calc	exp	calc	exp	calc	exp	calc	exp	calc
	ν 1 ( g )	2049.0 c 2052.1	-	2052.1 2001.8 c 2003.2 2005.7 c 2007.2 2031.0 2031.0
	ν 3 ( u )	1890.9 1891.1	-	1891.1 1847.2 1846.5 1850.1 1849.4 1865.9 1865.4
	ν 4 ( u )	493.5	494.2	-	490.6	489.5	490.3	482.3	484.4	489	492.3
	ν 2 ( g )	406.6 c 407.0	-	407.0	395.1 c 400.6	382.2 c 392.3	393.7 c 403.7
	ν 5 (Π g ) b	-	338.0	-	338.0	-	327.6	-	333.7	-	333.0
	ν 6 (Π u )	247.4	247.5	-	247.2	240.0 240.2	245.2	245.5	243.5	243.5
	ν 7 (Π u ) b	-	70.2	-	69.8	-	69.4	-	68.7	-	69.8
	a -F CO = 15.22, F CuC

Table 4 .

 4 Some energetic, geometrical and electronic parameters at CCSD(T) structure.  and  2  are given in e/Å 3 and e/ Å 5 . Distances are in Å, angle in degree, binding energy (D e at equilibrium structure and D 0 corrected for the vibrational frequencies) is in kJ/mol. Q net = net charge, BCP = bond critical point.

	Species	QTAIM topological analysis	Geometrical parameters Binding energy

Table 5 .

 5 Harmonic vibrational frequencies (in cm -1 ) and some force constants (in mdyne/Å) obtained at CCSD(T)/6-311+G(2d) level, compared to experimental frequencies in neon . For Cu(CO) 2 , harmonic vibrational frequencies and intensities (Km/mole) calculated at B3LYP/6-311+G(2d) are also reported in parentheses.

		Calculated vibrational frequencies	Experimental
	CO	 CO =2146 (2211) F CO =36.5(38.7)	2143.2 (gas) , 2142.2 (Ne)
	CuCO	 1 (CO stretching) = 2072 , F CO =17.0
		 2 (CuC str./ OCCu bend)= 262


Zohir Bouzid

Achour Mostéfaoui

Michel Raynal

Minimal Synchrony for Asynchronous Byzantine Consensus

Keywords: Adopt-commit, Asynchronous message-passing, Byzantine process, Consensus, Distributed algorithm, Eventual timely channel, Feasibility condition, Lower bound, Optimal resilience, Reliable broadcast, Signature-free algorithm, Synchrony assumption. Consensus Byzantin avec Synchronisme Minimal Système à passage de messages, Processus byzantin, Synchronie minimale

Solving the consensus problem requires in one way or another that the underlying system satisfies some synchrony assumption. Considering an asynchronous message-passing system of n processes where (a) up to t < n/3 may commit Byzantine failures, and (b) each pair of processes is connected by two uni-directional channels (with possibly different timing properties), this paper investigates the synchrony assumption required to solve consensus, and presents a signature-free consensus algorithm whose synchrony requirement is the existence of a process that is an eventual t+1 bisource. Such a process p is a correct process that eventually has (a) timely input channels from t correct processes and (b) timely output channels to t correct processes (these input and output channels can connect p to different subsets of processes). As this synchrony condition was shown to be necessary and sufficient in the stronger asynchronous system model (a) enriched with message authentication, and (b) where the channels are bidirectional and have the same timing properties in both directions, it follows that it is also necessary and sufficient in the weaker system model considered in the paper. In addition to the fact that it closes a long-lasting problem related to Byzantine agreement, a noteworthy feature of the proposed algorithm lies in its design simplicity, which is a first-class property.

Introduction

Byzantine consensus A process has a Byzantine behavior when it behaves arbitrarily [START_REF] Pease | Reaching agreement in the presence of faults[END_REF]. This bad functioning can be intentional (malicious behavior, e.g., due to intrusion) or simply the result of a transient fault that altered the local state of a process, thereby modifying its execution in an unpredictable way.

We are interested here in the consensus problem in message-passing distributed systems prone to Byzantine process failures whatever their origin. Consensus is an agreement problem in which each process first proposes a value and then decides on a value [START_REF] Pease | Reaching agreement in the presence of faults[END_REF]. In a Byzantine failure context, the consensus problem is defined by the following properties: every non-faulty process decides (termination), no two non-faulty processes decide differently (agreement), and the decided value is not arbitrary, i.e., it is related in one way or another to values proposed by non-faulty processes (validity).

Context of the paper A synchronous distributed system is characterized by the fact that both processes and communication channels are synchronous (or timely) [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Lynch | Distributed algorithms[END_REF][START_REF] Raynal | Fault-tolerant agreement in synchronous message-passing systems[END_REF]. This means that there are known bounds on process speed and message transfer delays. Let t denote the maximum number of processes that can be faulty in a system made up of n processes. In a synchronous system, consensus can be solved (a) for any value of t (i.e., t < n) in the crash failure model, (b) for t < n/2 in the general omission failure model, and (c) for t < n/3 in the Byzantine failure model [START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Pease | Reaching agreement in the presence of faults[END_REF]. Moreover, these bounds are tight.

Differently, when all channels are asynchronous (i.e., when there is no bound on message transfer delays), it is impossible to solve consensus even if we consider the weakest failure model (namely, the process crash failure model) and assume that at most one process may be faulty (i.e., t = 1) [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF]. It trivially follows that Byzantine consensus is impossible to solve in a failure-prone asynchronous distributed system.

As Byzantine consensus can be solved in a synchronous system and cannot in an asynchronous system, a natural question that comes to mind is the following "When considering the synchrony-to-asynchrony axis, which is the weakest synchrony assumption that allows Byzantine consensus to be solved in a message-passing system?" This long-lasting question is the issue addressed in this paper. To that end, the paper considers a synchrony assumption capturing the structure and the number of eventually synchronous channels among correct processes.

Related work

Several approaches to solve Byzantine consensus have been proposed. We consider here only deterministic approaches 1 . One consists in enriching the asynchronous system (hence the system is no longer fully asynchronous) with a failure detector, namely, a device that provides processes with (possibly unreliable) hints on failures [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. Basically, in one way or another, a failure detector encapsulates synchrony assumptions. Failure detectors suited to Byzantine behavior have been proposed and used to solved Byzantine consensus (e.g., [START_REF] Doudou | Muteness failure detectors: specification and implementation[END_REF][START_REF] Friedman | Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems[END_REF][START_REF] Kihlstrom | Byzantine fault detectors for solving consensus[END_REF]).

Another approach proposed to solve Byzantine consensus consists in directly assuming that some channels satisfy a synchrony property ("directly" means that the synchrony property is not hidden inside a higher level abstraction such as a failure detector). This approach, which relies on the notion of an 3 x + 1 bisource (read "3" as "eventual"), was introduced in [START_REF] Aguilera | Consensus with Byzantine failures and little system synchrony[END_REF]. Intuitively, this notion states that there is a correct process that has x input channels from correct processes and x output channels to correct processes that are eventually timely [START_REF] Delporte-Gallet | Algorithms for extracting timeliness graphs[END_REF][START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF] (the "+1" comes from the fact that it is assumed that each process has a "virtual" input/output channel from itself to itself, which is always timely).

Considering asynchronous systems with Byzantine processes without message authentication, it is shown in [START_REF] Aguilera | Consensus with Byzantine failures and little system synchrony[END_REF] that Byzantine consensus can be solved if the system has an 3 nt bisource (all other channels being possibly fully asynchronous). Moreover, the process that is the 3 nt bisource can never be explicitly known by the whole set of processes. Considering systems with message authentication, a Byzantine consensus algorithm is presented in [START_REF] Moumen | Byzantine consensus with few synchronous links[END_REF] that requires an 3 t + 1 bisource only. As for Byzantine consensus in synchronous systems, all these algorithms assume t < n/3. Finally, it has been shown in [START_REF] Baldellon | A necessary and sufficient synchrony condition for solving Byzantine consensus in symmetric networks[END_REF] that the "3 t + 1 bisource" synchrony assumption is a necessary and sufficient condition to solve Byzantine consensus in asynchronous bi-directionnal message-passing systems, enriched with message authentication.

Content of the paper This paper presents a Byzantine consensus algorithm for signature-free asynchronous messagepassing systems, which requires only the two assumptions: t < n/3 and the existence of an 3 t + 1 bisource. As these assumptions are necessary and sufficient to solve Byzantine consensus in the asynchronous model enriched with message authentication [START_REF] Baldellon | A necessary and sufficient synchrony condition for solving Byzantine consensus in symmetric networks[END_REF], it follows that (a) the existence of an 3 t + 1 bisource is necessary and sufficient to solve Byzantine consensus in an asynchronous signature-free system, and (b) the proposed algorithm is optimal with respect to underlying synchrony assumptions.

The proposed algorithm is round-based. To attain its goal, it relies on a modular construction involving two communication abstractions and two distributed objects. More precisely, we have the following.

• The communication abstractions are the one-to-all reliable broadcast (RB) abstraction introduced in [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF], and a very simple new communication abstraction that we call cooperative broadcast (CB). As suggested by its name, it is an all-to-all broadcast abstraction. This abstraction, which uses RB as an underlying subroutine, is particularly simple. It actually captures important cooperation properties, which make easier the design of upper layer distributed agreements. • The two distributed objects are the following ones (the implementation of each of them use the underlying CB broadcast abstraction).

-The first object is a message-passing version of the adopt-commit (AC) object (introduced in [START_REF] Gafni | Round-by-round fault detectors: unifying synchrony and asynchrony[END_REF]) appropriately modified to cope with up to t < n/3 Byzantine processes. Each round of the consensus algorithm uses a specific AC object. The aim of these objects is to prevent the consensus safety property from being violated.

-The second object is a round-based object called eventual agreement (EA) object. It aims is to ensure the consensus termination property. Hence, its implementation relies on the 3 t + 1 bisource assumption.

It is important to emphasize that, when designing the algorithm presented in the paper, modularity and simplicity were considered as first class design criteria. The algorithm presented is only the last step of a long quest: "Simplicity does not precede complexity, but follows it" (Alan Perlis, First Turing Award).

Road map

The paper is made up of 7 sections. Section 2 presents the basic underlying asynchronous Byzantine computation model, the RB broadcast abstraction and the new CB broadcast abstraction. Section 3 presents an AC object suited to message-passing systems prone to Byzantine failures. Then, Section 4 presents the 3 t + 1 bisource behavioral assumption. Section 5 presents the round-based eventual agreement object. Section 6 pieces together the previous abstractions to obtain the synchrony-optimal Byzantine consensus algorithm. Finally, Section 7 concludes the paper.

2 Basic Model, Reliable Broadcast, and Cooperative Broadcast

Communication network

The processes communicate by exchanging messages through an asynchronous reliable point-to-point network. "Asynchronous" means that there is no bound on message transfer delays. "Reliable" means that the network does not loss, duplicate, modify, or create messages. "Point-to-point" means that any pair of processes is connected by two uni-directional channels (one in each direction). Hence, when a process receives a message, it can identify its sender. Moreover, as there is no message loss, all message transfer delays are finite.

A process p i sends a message to a process p j by invoking the primitive "send TAG(m) to p j ", where TAG is the type of the message and m its content. To simplify the presentation, it is assumed that a process can send messages to itself. A process receives p i a message by executing the primitive "receive()". Then then say that the message is received by p i .

Failure model Up to t processes can exhibit a Byzantine behavior. A Byzantine process is a process that behaves arbitrarily: it can crash, fail to send or receive messages, send arbitrary messages, start in an arbitrary state, perform arbitrary state transitions, etc. Moreover, Byzantine processes can collude to "pollute" the computation (e.g., by sending messages with the same content, while they should send messages with distinct content if they were non-faulty).

A process that exhibits a Byzantine behavior is called faulty. Otherwise, it is correct or non-faulty. Given an execution, C denotes the set of processes that are correct in this execution.

Let us notice that, as each pair of processes is connected by a channel, no Byzantine process can impersonate another process. Moreover, it is assumed that the Byzantine processes do not control the network (they can neither corrupt the messages sent by non-faulty processes, nor modify the message reception schedule).

Discarding messages from Byzantine processes If, according to its algorithm, a process p j is assumed to send a single message TAG() to a process p i , then p i processes only the first message TAG(v) it receives from p j . This means that, if p j is Byzantine and sends several messages TAG(v), TAG(v ′ ) where v ′ = v, etc., all of them except the first one are discarded.

Unreliable (best effort) broadcast This simple broadcast is defined by a pair of operations denoted broadcast() and receive(), where broadcast TAG(m) is used as a shortcut for for each j ∈ {1, . . . , n} send TAG(m) to p j end for. This means that a message broadcast by a correct process is received at least by all the correct processes. Differently, while it is assumed to send the same message to all the processes, a faulty process can actually send different messages to distinct processes and no message to others.

Notation The notation BZ_AS n,t [∅] is used to denote the previous basic Byzantine asynchronous message-passing computation model.

Reliable broadcast abstraction

This broadcast abstraction (in short, RB-broadcast) was proposed by G. Bracha [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF]. It is a one-shot one-to-all communication abstraction, which provides processes with two operations denoted RB_broadcast() and RB_deliver(). When p i invokes RB_broadcast() (resp., RB_deliver()), we say that it "RB-broadcasts" a message (resp., "RB-delivers" a message). An RB-broadcast instance where process p x is the sender is defined by the following properties.

• RB-Validity. If a non-faulty process RB-delivers a message m (from p x ), then, if p x is correct, it RB-broadcast m.

• RB-Unicity. A correct process RB-delivers at most one message from p x .

• RB-Termination-1. If p x is non-faulty and RB-broadcasts a message m, all the non-faulty processes eventually RB-deliver m from p x . • RB-Termination-2. If a non-faulty process RB-delivers a message m from p x (possibly faulty) then all the nonfaulty processes eventually RB-deliver the same message m from p x .

The RB-Validity property relates the output to the input, while RB-Unicity states that there is no message duplication. The termination properties state the cases where processes have to RB-deliver messages. The second of them is what makes the broadcast reliable. It is shown in [START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF] that t < n/3 is an upper bound on t when one has to implement such an abstraction. For self-containment of the paper, an algorithm implementing RB-broadcast is described in Appendix B (this algorithm is from [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF]).

Collection des Publications Internes de l'Irisa c IRISA Notation The basic computing model strengthened with the additional constraint t < n/3 is denoted BZ_AS n,t [t < n/3]. RB-broadcast can consequently be implemented in this model.

Cooperative broadcast abstraction

Definition This new communication abstraction (in short CB-broadcast) is a one-shot all-to-all broadcast defined by an operation, denoted CB_broadcast(), plus a read-only per process p i , denoted cb_valid i . "All-to-all" means that it is assumed that all correct processes invoke CB_broadcast(). When a process p i invokes CB_broadcast(v), we say that "it cb-broadcasts v".

An invocation of CB_broadcast() by a process p i has an input parameter, namely the value that p i wants to broadcast, and returns a value, which is a value CB-broadcast by a correct process. The CB-broadcast abstraction is formally defined by the following properties.

• CB-Operation Termination. The invocation of CB_broadcast() by a correct process terminates.

• CB-Operation Validity. If the invocation of CB_broadcast() returns v to a correct process p i , v ∈ cb_valid i .

• CB-Set Termination. The set cb_valid i of a correct process p i is eventually non-empty.

• CB-Set Validity. The set cb_valid i of any correct process p i contains only values cb-broadcast by correct processes.

• CB-Set Agreement. The set cb_valid i and cb_valid j of any two correct processes p i and p j are eventually equal.

Feasibility condition in the presence of up to t Byzantine processes Let m be the number of different values that can be cb-broadcast by correct processes. It follows from the previous specification that, even when the (at most) t Byzantine processes propose a same value w, not proposed by a correct process, w can neither be returned, nor belong to the set cb_valid i of a correct process p i . This can be ensured if and only if there is a value cb-broadcast by at least (t + 1) correct processes. This feasibility condition is captured by the predicate nt > mt. (A proof of this feasibility condition can be found in [START_REF] Herlihy | Distributed computing through combinatorial topology[END_REF]). Hence, we assume in the following that at most m ≤ ⌊ n-(

⌋ different values can be cb-broadcast by the set of correct processes, and the corresponding abstraction is called an m-valued CB-broadcast.

An algorithm implementing CB-broadcast A simple algorithm implementing CB-broadcast is described in Figure 1. When p i invokes CB_broadcast(v i ), it first invokes RB_broadcast CB_VAL(v i ) for all correct processes to be eventually aware of v i (line 1). Then, it waits until its set cb_valid i becomes non-empty (line 2). When this occurs, p i takes any value from cb_valid i and returns it (line 3). Finally, p i adds to cb_valid i all the values it RB-delivers from (t + 1) different processes (i.e., v was RB-broadcast by at least one correct process). It is important to notice that, after the predicate cb_valid i = ∅ became satisfied, new values can still be added to cb_valid i .

operation CB_broadcast(vi) is (1) RB_broadcast CB_VAL(vi); (2) wait (cb_validi = ∅); (3) return (any value in cb_validi). when CB_VAL(v) is RB_delivered from pj do (4) if (v RB_delivered from (t + 1) diff. processes) then add v to cb_validi end if. Figure 1: An algorithm implementing m-valued CB-broadcast in BZ_AS n,t [t < n/3] Theorem 1. The algorithm described in Figure 1 implements the m-valued CB-broadcast abstraction in BZ_AS n,t [t < n/3].
Proof Proof of the CB-Termination properties. It follows from the feasibility condition, that there is a value v that is proposed by at least (t + 1) correct processes. Hence, these processes RB-broadcast CB_VAL(v). It then follows from line 4 and the RB-termination property that v will be added to the set cb_valid i of each correct process p i . Hence, the CB-Set Termination property is satisfied, and no correct process can be blocked forever at line 2, from which follows the CB-Operation Termination property.

Proof of the CB-Validity properties.

To prove the CB-Set Validity property, let us consider a value v cb-broadcast only by Byzantine processes. It follows that a correct process p i can RB-deliver v from at most t different processes. Hence, p i cannot add v to cb_valid i at line 4, which proves the property. The CB-Operation Validity property is then a trivial consequence of the CB-Set Validity property.

Proof of the CB-Set Agreement property. Let us consider a value v ∈ cb_valid i . This means that p i RB-delivered the message CB_VAL(v) from (t + 1) different processes (line 4). It then follows from the RB-termination property of RB-broadcast that each correct process p j RBdelivers these (t + 1) messages CB_VAL(v). Consequently, any correct process p j adds v to its local set cb_valid j , which concludes the proof.

2 T heorem 1

Adopt-Commit in the Presence of Byzantine Processes

This object was introduced in [START_REF] Gafni | Round-by-round fault detectors: unifying synchrony and asynchrony[END_REF] in the context of read/write communication. Here we slightly modify its definition to cope with Byzantine processes (which by definition can decide anything).

Definition An adopt-commit (AC) is a one-shot object which encapsulates the safety part of agreement problems. It provides processes with a single operation denoted AC_propose(). This operation takes a value as input parameter (we say that the invoking process proposes this value), and returns a pair d, v (we say that the invoking process decides d, v ), where d is a control tag and v a value. An AC object is defined by the following properties.

• AC-Termination. An invocation of AC_propose() by a correct process terminates.

• AC-Validity. This property is made up of two parts.

-AC-Output domain. If a correct process decides d, v , d ∈ {commit, adopt}, and v is a value that was proposed by a correct process. -AC-Obligation. If all the correct processes propose the same value v, only the pair commit, v , can be decided. • AC-Quasi-agreement. If a correct process decides commit, v , no other correct process can decide -, v ′ where v ′ = v.

Implementations of an AC object in the presence of process crash failures can be found in [START_REF] Gafni | Round-by-round fault detectors: unifying synchrony and asynchrony[END_REF][START_REF] Mostéfaoui | Solving consensus using Chandra-Toueg's unreliable failure detectors: a general quorum-based approach[END_REF]. The implementation of [START_REF] Gafni | Round-by-round fault detectors: unifying synchrony and asynchrony[END_REF] is for asynchronous systems where any number of processes may crash and communication is by atomic read/write registers. The implementation of [START_REF] Mostéfaoui | Solving consensus using Chandra-Toueg's unreliable failure detectors: a general quorum-based approach[END_REF] is for asynchronous message-passing systems where a minority of processes may crash.

It follows from the AC-Output domain property, that a value proposed only by Byzantine processes cannot be decided by a correct process. This means that an AC object has the same feasibility condition as CB-broadcast (let us also notice that this is independent from the fact that an AC object can be built on top of CB-broadcast). Hence, we assume that at most m ≤ ⌊ n-(t+1) t ⌋ values can be proposed by the correct processes, and the corresponding object is called an m-valued adopt-commit object.

Collection des Publications Internes de l'Irisa c IRISA Implementation of an m-valued adopt-commit object A distributed algorithm implementing an AC object in the presence of up to t < n/3 Byzantine processes is described in Figure 2, for a correct process p i . This algorithm is based on an underlying CB-broadcast, which means that each process has a read-only local set cb_val i (initially empty).

operation AC_propose(vi) is (1) esti ← CB_broadcast AC_PROP(vi);

(2) RB_broadcast AC_EST(esti);

(3) wait (AC_EST(est) messages have been RB-delivered from (nt) different processes, and their est values belong to cb_validi); (4) mfv i ← most frequent value in the previous (nt) AC_EST() messages;

(5) if (each of the previous (nt) AC_EST() messages carries mfv i ) [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] then return ( commit, mfv i ) [START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF] else return ( adopt, mfv i ) (8) end if. When a process p i invokes AC_propose(v i ), it first issues CB_broadcast AC_PROP(v i ) from which it obtains a value that it saves in est i (line 1). It then RB-broadcasts the message AC_EST(est i ) (line 2), and waits until (a) it has RBdelivered messages AC_EST() from (nt) different processes, and (b) the values carried by these messages belong to the set cb_valid i supplied by CB-broadcast (line 3). Let us remember that, after the predicate cb_valid i = ∅ became satisfied, new values can still be added to cb_valid i .

When this predicate becomes satisfied, p i computes the most frequent value mfv i carried by the previous (nt) AC_EST() messages (line 4). If there are several "most frequent" values, p i takes any of them. Finally, if all the messages who made satisfied the predicate of line 3 carried the same value mfv i , p i returns the pair commit, mfv i ) (line 6); otherwise it returns the pair adopt, mfv i ) (line 7).

Theorem 2. Assuming that all the correct processes invoke AC_propose(), the algorithm described in Figure 2

imple- ments an m-valued adopt-commit object in BZ_AS n,t [t < n/3].
Proof Proof of the AC-termination property. Due to the CB-Operation termination property, no correct process blocks forever at line 1. So, we have only toshow that no correct process can block forever at line 3. It follows from CB-Set Termination and CB-Set Validity that the sets cb_valid i of the correct processes are eventually not empty and contain only values proposed by correct processes. As (i) the value RB-broadcast by each correct process at line 2 is a value of its set cb_valid i , (ii) there are at least (nt) correct processes, and (iii) the sets cb_valid i of the correct processes are eventually equal (CB-Set Agreement property), it follows that the predicate of line 3 is eventually satisfied at each correct process, which concludes the proof of ACtermination property.

Proof of the AC-Output domain property. Let us first observe that a correct process can decide only commit, v or adopt, v (lines 6-7). Hence, we have only to show that v is a value proposed by a correct process. A value v decided by a correct process p i was RB-delivered in a message AC_EST(v). It follows from the predicate of line 3 that v ∈ cb_valid i . Finally, if follows from the CB-Set Validity property that v is a value proposed by a correct process.

Proof of the AC-Obligation property. If all correct processes propose the same value v, it follows from the CB-Set (Termination, Validity, and Agreement) properties that the set cb_valid i of each correct process p i is eventually equal to {v}. Hence, each correct process RBbroadcasts the message AC_EST(v) at line 2. It then follows from the predicate of line 3 that no value different from v can be decided.

Proof of the AC-Quasi-agreement property. Let p i and p j be two correct processes such that p i decides commit, v while p j decides -, v ′ . As p i decides commit, v , it follows from line 3 that it RB-delivered the message AC_EST(v) from (nt) different processes. As, due to the RB-Unicity and RB-Termination-2 properties, no two correct processes RB-deliver different values from the same process, it follows that, among the (nt) messages AC_EST() RB-delivered by p j , at most t of them may carry a value different from v, i.e., at least n -2t ≥ t + 1 carry the value v. It follows that v is the most frequent value RB-delivered by p j , and consequently v ′ = v.

2 T heorem 2

4 The 3 t + 1 Bisource Assumption

Definitions

These notions were introduced in [START_REF] Aguilera | Consensus with Byzantine failures and little system synchrony[END_REF][START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF] (see also Appendix A).

Eventually timely channel Let us consider the channel connecting a process p i to a process p j . This channel is eventually timely if there is a finite time τ and a bound δ, such that any message sent by p i to p j at time τ ′ is received by p j by time max(τ, τ ′ ) + δ. Let us observe that neither τ , nor δ, is known by the processes. As already indicated, there is an input/output channel from each process to itself.

3[k]sink, 3[k]source, and 3[k]bisource A correct process p i is an 3[k]
sink if it has eventually timely input channels from k correct processes (including itself). This set of processes is denoted X - i . Similarly, a correct process is an 3[k]source if it has k eventually timely output channels to correct processes (including itself). This set of processes is denoted

X + i . An 3[k]bisource is a correct process p i that is both 3[k]sink and 3[k]source.
Let us remark that the timely input channels and the timely output channels do not necessarily connect p i to the same subset of processes.

Notation for system models The system model BZ_AS n,t [t < n/3] enriched with an 3 t + 1 bisource is denoted BZ_AS n,t [t < n/3, 3 t + 1 bisource].

Eventual Agreement Object

Motivation and definition

This object, which is round-based, will be used to ensure the termination of the consensus algorithm, namely, its aim is to allow the correct processes to eventually converge on a single value. To this end, it provides the processes with a single operation denoted EA_propose(r, v) where r is a round number and v is the value proposed at this round by the invoking process. Each invocation of EA_propose() by a correct process returns a value. It is assumed that each correct process invokes this operation once per round, and its successive invocations are done according to consecutive round numbers. When a process invokes EA_propose(r, v), we say that it "ea-proposes v at round r".

Definition An eventual agreement (EA) object is defined by the following properties.

• EA-Termination. For any r, if all correct processes invoke EA_propose(r, -), each of these invocations terminates.

• EA-Validity. For any r, if all correct processes invoke EA_propose(r, v) no correct process returns a value different from v.

Collection des Publications Internes de l'Irisa c IRISA

• EA-Eventual agreement. If the correct processes execute an infinite number of rounds, there is an infinite number of rounds r at which all the correct processes return the same value v, where v is such that a correct process invoked EA_propose(r, v).

It is important to notice that the EA-Validity property is particularly weak. More precisely, if, during a round r, two correct processes invoke ea_propose(r, v1) and EA_propose(r, v2), with v1 = v2, the invocation of EA_propose(r, -) by any correct process is allowed to return an arbitrary value (i.e., even a value proposed neither by a correct nor by a Byzantine process).

As the implementation that follows uses at every round an instance of CB-broadcast, we assume that at most m ≤ ⌊ n-(t+1) t ⌋ different values are ea-proposed by correct processes.

Implementation of an m-valued eventual agreement object

Definitions The algorithm presented below uses the following sets and functions.

• There are α = n n-t possible combinations of (nt) processes among the n processes p 1 , ..., p n . Let us call them F 1 . . . F α .

• Given any round number r ≥ 1:

coord(r) denotes the function (r -1) mod n + 1.

Given a round r, coord(r) defines its coordinator process. As we can see, if there is an infinite number of rounds, each process is infinitely often round coordinator. -F (r) denotes the function F index(r) , where index(r) = (⌈ r n ⌉ -1) mod α + 1. Hence, each set F (r) returns a set made up of (nt) processes. During each round, its coordinator strives to decide a value. To this end, it requires the help of the processes in F (r) to broadcast the value it champions. F 1 is used by the coordinators of the rounds 1 to n; F 2 is used by the coordinators of the rounds (n + 1) to 2n; ..., F α is used by the coordinators of the rounds ((α -1)n + 1) to αn; F 1 is used by the coordinators of the rounds ((αn + 1) to (α + 1)n; etc.

Considering an infinite sequence of rounds, it is important to notice that there is an infinite number of rounds r and r ′ such that (coord(r) = coord(r ′ )) ∧ F (r) = F (r ′ ) and an infinite number of rounds r and r ′ such that coord(r) = coord(r ′ ) ∧ F (r) = F (r ′ ) .

Local variables Each process p i manages the following local variables.

• timer i [1..] is an array of timers, such that timer i [r] is the timer used by p i for round r.

• CB [1..] is an array of CB-broadcast instances shared by all processes. CB [r] is the instance associated with round r. Hence, CB [r].cb_valid i is the set of values supplied to p i by CB [r].

To distinguish messages which have the same tag but are sent at different rounds, a message XXX() associated with round r is denoted XXX[r]().

Algorithm: first part of EA_propose() (Lines 1-5) The algorithm executed by a correct process p i is described in Figure 3. Let us remind that, it is assumed that each correct process invokes EA_propose() at every round.

When a correct process p i invokes EA_propose(r i , val i ) (r i is a round number and val i the value it ea-proposes at this round), it first invokes CB [r i ].CB_broadcast EA_PROP1(val i ), and saves the value returned in aux i (line 1).Then, p i broadcasts the message EA_PROP2[r i ](aux i ) (line 1) and waits until (a) it has received messages where v = ⊥ received from a process in F (ri) [START_REF] Ch | Random oracles in Constantinople: practical asynchronous Byzantine agreement using cryptography[END_REF] then return(v) [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF] else return(vali) (10) end if.

when EA_PROP2[r]() is received from a process in F (r) do [START_REF] Delporte-Gallet | Algorithms for extracting timeliness graphs[END_REF] if (i = coord(r) ∧ (EA_COORD[r]() not already broadcast) [START_REF] Doudou | Muteness failure detectors: specification and implementation[END_REF] then let w be the value carried by the message EA_PROP2[r](); [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF] broadcast EA_COORD[r](w) [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF]

end if. when EA_COORD[r](v) is received from p coord(r) or (timeri[r] expires) do (15) if (EA_RELAY[r]() not already broadcast) (16) disable timeri[r]; (17) if (timeri[r] expired) then v_coordi ← ⊥ else v_coordi ← v end if; (18) broadcast EA_RELAY[r](v_coordi) (19) end if. Figure 3: An algorithm implementing an m-valued EA object in BZ_AS n,t [t < n/3, 3 t + 1 bisource] CB-broadcast instance CB [r i ] (line 3
). If all these messages carry the same value v, p i returns v as result of its invocation EA_propose(r i , val i ) (line 4)2 . Otherwise, p i sets the timer associated with the round r i to the value r i (line 5) 3 .

Algorithm: message processing and role of the round coordinator (Lines 11-19) Each round r uses a round coordinator, defined by coord(r). As we have also seen, the set of (nt) processes denoted F (r) is associated with round r.

When p i is the coordinator of round r and receives for the first time a message EA_PROP2[r]() from a process in the set F (r), it champions the value w carried by this message to become the value returned by the invocations of EA_propose(r, -). To that end, it simply broadcasts the message EA_COORD[r](w) (lines [START_REF] Delporte-Gallet | Algorithms for extracting timeliness graphs[END_REF][START_REF] Doudou | Muteness failure detectors: specification and implementation[END_REF][START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF][START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF].

When a process p i receives a message EA_COORD[r](v) from the coordinator of round r, if not yet done, it broadcasts the message EA_RELAY[r](v) to inform the other processes that it has received the value v championed by the coordinator of round r. If the local timer associated with this round (timer i [r]) has already expired, p i broadcasts the message EA_RELAY[r](⊥), to inform the other processes that it suspects the coordinator of round r not to be an 3 t + 1 bisource (this suspicion can be due to the asynchrony of the channel connecting p coord(r) to p i , or the fact that -while p coord(r) is an 3 t + 1 bisource-the link from p coord(r) to p i is not yet synchronous, or the fact that p coord(r) has a Byzantine behavior). In all cases, as timer i [r] will no longer be useful, p i disables it. This behavior of p i is captured by the lines 15-19.

Algorithm: second part of EA_propose() (Lines 6-10) After it has set timer i [r i ] (line 5), p i waits until it has received a message EA_RELAY[r i ]() from (nt) different processes (line 6). When this occurs, the invocation of EA_propose(r i , val i ) by p i returns a value. This value is v = ⊥ if p i received a message EA_RELAY[r i ](v) from a process in the set F (r i ) (lines 7-8). Otherwise, no process of F (r i ) witnesses the value championed by the coordinator of round r. In this case, p i returns the value val i , i.e., the value it ea-proposed (line-9).

Proof

Let us remember that, by assumption, all correct processes invoke EA_propose(r, -), where r = 1. Moreover, they ea-propose at most m different values.

Lemma 1. For any r, if all correct processes invoke EA_propose(r, v) no correct process returns a value different from v.

Proof Since all correct processes invoke EA_propose(r, v), all of them invoke CB [r].CB_broadcast EA_PROP1(v) at line 1. It follows from the CB-Set Validity property that the set CB [r].cb_valid i of any correct process p i can contain only the value v. Therefore, the (nt) messages EA_PROP[r]() considered at line 3 carry necessarily the value v. Consequently, every correct process that executes line 4 necessarily returns v. That is, no other value can be returned by a correct process.

2 Lemma 1

Lemma 2. Let r ≥ 1. If all correct processes invoke EA_propose(r, -), then each of these invocation terminates.

Proof Let p i a correct process. Let us first observe that, due to the CB-Operation Termination property, p i cannot be blocked forever when it invokes CB [r].CB_broadcast EA_PROP1() at line 1. Hence, the proof consists in showing that p i cannot block forever at line 3 or line 6. The proof that p i cannot block forever at line 3 follows from the following observation. As a correct process cannot block forever at line 1, each correct process p j broadcasts the message EA_PROP2[r](aux j ) at line 2 where aux j was returned by its invocation of CB [r].CB_broadcastEA_PROP1() at line 1. It follows from the CB-Operation Validity property that aux j ∈ CB [r].cb_valid j . Moreover, according to the CB-Set Agreement property, aux j is eventually added to the set CB [r].cb_valid i of every correct process p i . Consequently, each correct process p i receives messages EA_PROP2[r]() from at least (nt) processes and the values carried by these messages eventually belong to its set CB [r].cb_valid i . Consequently no correct process remains blocked forever at line 3.

It remains to prove that p i cannot block forever at line 6. Let us observe that since timer i [r] is set to r, it follows that this timer expires at every correct process. Hence, the when condition preceding line 15 becomes true at every correct process and each of them broadcasts an EA_RELAY[r]() message if not already done. It follows that p i receives messages EA_RELAY[r]() from at least (nt) processes. Therefore, p i cannot be blocked forever waiting at line 6.

2 Lemma 2 Lemma 3. If the correct processes execute an infinite number of rounds, there is an infinite number of rounds r at which all the correct processes return the same value v, where v is such that a correct process invoked EA_propose(r, v).

Proof Let us define the following rounds:

• Let r 1 be the first round that is strictly greater than 2δ.

• Let p ℓ be an 3[t + 1]bisource. There exists a round r 2 such that in every subsequent round:

-Each message sent by any p x ∈ X - ℓ to p ℓ is received within an interval of at most δ time units. -Each message sent by p ℓ to any p y ∈ X + ℓ is received within an interval of at most δ time units. • Let r > max(r 1 , r 2 ) be any round coordinated by p ℓ such that X + ℓ ⊆ F (r) and F (r) ⊆ C. Let us notice that, due to the definition of F (r), an infinity of such rounds r exists.

Claim C. For every process p i ∈ X + ℓ , we have v_coord i = ⊥ in round r (line 18). Proof of claim C. Let p i be any process in X + ℓ . Let τ be the time at which p i sets the timer at line 5 of round r. At this moment, since p i finished executing line 4, there are at least (nt) processes from which p i received an EA_PROP2[r]() message. Since |X - ℓ | ≥ t + 1, it follows that among these (nt) processes, there is at least one, say p k , that belongs to X - ℓ . Observe that p k necessarily broadcast the message EA_PROP2[r]() before τ . Since r > r 2 , this message is received by p ℓ before time τ + δ.

Therefore, if p ℓ did not broadcast a message EA_COORD[r]() before receiving EA_PROP2[r]() from p k , as p k ∈ X - ℓ ⊆ F (r), the condition of line 11 and the when statement preceding it are both satisfied, and p ℓ broadcasts EA_COORD[r]() at line 13. Consequently, in all cases, p ℓ broadcasts a message EA_COORD[r]() by time τ + δ. Finally, since p i ∈ X + ℓ and r > r 2 , this message is received by p i before time τ + 2δ.

Let us recall that, as r > r 1 , it holds that r > 2δ, and consequently, since p i set timer i [r] to r (line 8) at time τ , the timeout occurs after time τ + 2δ. Therefore, p i receives the message EA_COORD[r]() from p ℓ before the timeout. Consequently, when evaluated by p i , the predicate of line 17 is necessarily false, and v_coord i = ⊥. This proves the claim.

We show in the following that all correct processes return the same value in round r. Let us first observe that every correct process broadcasts an EA_PROP2[r]() message that carries a value which was necessarily ea-proposed by a correct process. Therefore, since p ℓ is correct (and is the coordinator of r), the message EA_COORD[r]() it broadcasts in round r contains a value, say w, that was sent to it by a correct process. Therefore, since (due to the definition of r), the processes of F (r) are correct, the EA_RELAY[r]() messages broadcast by them carry either w or ⊥. Consequently, every correct process p i can either returns w or val i after executing the lines 7-10. To finish the proof, it remains to show that no correct process p i returns val i (if val i = w).

Let us observe that each correct process waits at line 6 until it receives (nt) EA_RELAY[r]() messages. Since |X + ℓ | > t, it follows that at least one of these messages was broadcast by a process in X + ℓ . Due to Claim C, this message cannot carry ⊥. It then follows from the predicate of line 7 that any correct process executes line 8 and returns w, which proves the lemma.

2 Lemma 3

Theorem 3. The algorithm described in Figure 3 implements an m-valued eventual agreement object in BZ_AS n,t [t < n/3, 3 t + 1 bisource].

Proof The proof follows from Lemma 1, Lemma 2, and Lemma 3. 2 T heorem 3

Looking for efficiency: Parameterized eventual agreement

Time complexity of the EA algorithm The aim of the previous algorithm was to attain a round r during which all correct processes return the same value (ea-proposed by one of them). Hence its time complexity can be measured by the value of this round number. As the underlying synchrony assumption is eventual, we only know that this number r is finite.

Hence, to eliminate the noise created by the "eventual" attribute, and consequently be able to compute a time complexity of the algorithm, let us replace the 3 t + 1 bisource synchrony assumption by the t + 1 bisource assumption, i.e., we consider that there is a t + 1 bisource from the very beginning. The corresponding system model is denoted

BZ_AS n,t [t < n/3, t + 1 bisource].
The uncertainty created by the "eventual" attribute is consequently eliminated, and the only uncertainty is the identity of the bisource and its associated input and output timely channels. As there are n processes and α = n n-t combinations for the sets F (r), it follows that the algorithm, which works in BZ_AS n,t [t < n/3, 3 t + 1 bisource], terminates in at most αn rounds when the system behaves as BZ_AS n,t [t < n/3, t + 1 bisource].

Collection des Publications Internes de l'Irisa c IRISA Improving the time complexity One way to improve the time complexity of the algorithm (as measured previously) is to consider a "tuning" parameter k, 0 ≤ k ≤ t, and use it in both the synchrony assumption and the size of the sets F (r), as follows.

• The assumption t + 1 bisource is replaced by the stronger assumption t + 1 + k bisource.

• Instead of (nt), the size of the sets F (r) is now nt + k.

An algorithm, parameterized with k, extending the basic algorithm of Figure 3 and based on the previous definition is described in Appendix C. Designed for the system model BZ_AS n,t [t < n/3, 3 t + 1 + k bisource], this algorithm has a time complexity of βn where β = n n-t+k when executed in BZ_AS n,t [t < n/3, t + 1 + k bisource]. As simple instances of this parameterized algorithm, let us consider two particular values of k. For k = 0, we obtain the basic algorithm. For k = t, the time complexity is n, which is the best that can be obtained with a round coordinator-based algorithm (up to n rounds can be needed to benefit from the t + 1 + k bisource).

6 Byzantine Consensus Algorithm m-Valued Byzantine consensus In the m-valued Byzantine consensus, the correct processes propose values from a set of at most m values. The corresponding object is a one-shot object, that provides the processes with a single operation denoted CONS_propose(v), where v is the value proposed by the invoking process. This operation returns a value to the invoking process. If p i obtains the value v, we say that it "decides" v. The consensus object is defined by the following properties.

• CONS-Termination. The invocation of CONS_propose() by a correct process terminates.

• CONS-Validity. If a correct process decides a value v, there is a correct process that invoked CONS_propose(v).

• CONS-Agreement. No two correct processes decide different values.

An algorithm solving m-valued Byzantine consensus Assuming m ≤ ⌊ n-(t+1) t ⌋, the algorithm described in Figure 4 implements an m-valued consensus object in BZ_AS n,t [t < n/3, t + 1 bisource]. This algorithm, which -thanks to the previous abstractions-is simple, uses the following underlying objects.

• Each process p i manages a round number r i (initialized to 0), and a current estimate of the decision value, denoted est i .

• EA_OBJECT is an m-valued eventual-agreement object shared by all processes. Its aim is to allow the processes to eventually converge to the same estimate value. Hence, the associated line 4 is mainly related to the CONS-Termination property. • AC _OBJECT [1..] is an unbounded array of m-valued adopt-commit objects, shared by all processes. AC _OBJECT [r] is the adopt-commit object used at round r. The aim of these objects (line 6) is to allow the correct processes to decide a value proposed by one of them, and to prevent them from deciding different values, i.e., to guarantee consensus safety. • CB [0] is a CB-broadcast instance, used at the very beginning to obtain a value proposed by a correct process and allow a process p i to use the associated set CB [0].cb_valid i to check the validity of the values returned by the EA_OBJECT object (i.e., to check if this value was proposed by a correct process).

When a correct process p i invokes CONS_propose(v i ), it first invokes CB [0].CB_broadcastVALID(v i ) to obtain a value for was proposed by a correct process (line 1) 4 . As already indicated, this invocation also ensures that the sets CB [0].cb_valid i of correct processes are eventually equal and contain values proposed only by correct processes. nt ≥ t + 1, the decision predicate of line 9 becomes eventually true at every correct process, which contradicts the initial assumption.

Proof of the CONS-Validity property.

Let us consider the first round. Let p i be a correct process. It follows from the CB-Operation Validity property of CB [0] that est i is a value proposed by a correct process. Moreover, it follows from the CB-Set Validity property, that CB [0].cb_valid i contains only values proposed by correct processes. It follows from these observations that, be or not est i modified at line 5, it contains a value proposed by a correct process when p i invokes AC _OBJECT [START_REF] Aguilera | Consensus with Byzantine failures and little system synchrony[END_REF].AC_propose(est i ) at line 6. It then follows from the AC-Validity property of AC _OBJECT [START_REF] Aguilera | Consensus with Byzantine failures and little system synchrony[END_REF] that the value assigned to est i at line 6 is a value proposed by a correct process. The same reasoning applies iteratively to all rounds, from which it follows that a value that is RB-broadcast by a correct process at line 7 is a value proposed by a correct process.

If a correct process p i decides a value v at line 9, it follows from the decision predicate used at this line that v was RB-broadcast at line 7 by at least one correct process p j . The previous paragraph has shown that such a value v was proposed by a correct process.

Proof of the CONS-Agreement property. Let us first observe that, if a correct process decides at line 9, it decides a value RB-broadcast by a correct process at line 7. Hence, the proof consists in showing that no two correct processes RB-broadcast different values at line 7.

Let r be the first round at which a correct process p i RB-broadcast a message DECIDE() at line 7. Let v the value carried by this message. It follows that, at line 6, p i obtained the pair commit, v from the object AC _OBJECT [r]. Let us consider another correct process p j . There are two cases.

• p j RB-broadcast the message DECIDE(w) at line 9 of round r. This means that it obtained commit, w from AC _OBJECT [r]. It then follows from the AC-agreement property of the object AC _OBJECT [r] that v = w. Moreover, p j proceeds to the next round with est j = v. • p j did not RB-broadcast the message DECIDE(w) at line 9 of round r. It then follows from the AC-agreement property of AC _OBJECT [r] that p j obtained the pair adopt, v . Hence, at line 6, p j assigned the value v to est j .

It follows that the estimate values of all the correct processes that progress to the next round are equal to v. Let p x be any correct process executing round (r + 1). It follows from the EA-Validity property of EA_OBJECT , that the invocation by p x of EA_OBJECT .EA_propose(r + 1, est x ) returns v, and from the AC-Obligation property of AC _OBJECT [r + 1] that this object returns -, v to p x . This means that the estimates of all the correct processes remain forever equal to v. Hence, no value different from v can be RB-broadcast at line 7 by a correct process during a round r ′ ≥ r.

T heorem 4 7 Conclusion

A variant To ensure that a value decided by a correct process is always a value that was proposed by a correct process, this paper has considered m-valued consensus, i.e., there is a value that is proposed by at least m correct processes.

To ensure that no value proposed only by Byzantine processes is ever decided, some Byzantine consensus algorithms (e.g., [START_REF] Correia | From consensus to atomic broadcast: time-free Byzantine-resistant protocols without signatures[END_REF][START_REF] Mostéfaoui | Signature-free broadcast-based intrusion tolerance: never decide a Byzantine value[END_REF]) do not have such an "m-valued" requirement. They instead allow the correct processes to decide a default value ⊥ when they do not propose the same value. The algorithms proposed in the paper can be modified to satisfy this different validity requirement.

The aim and the content of the paper This paper presented a consensus algorithm for asynchronous Byzantine message-passing systems, that is optimal with respect to the underlying synchrony assumption. This assumption is the existence of a process that is an eventual t + 1 bisource. Such a process p is a non-faulty process that eventually has (a) timely input channels from t correct processes and (b) timely output channels to t correct processes. Moreover these input and output channels can connect p to different subsets of processes.

In addition to a reliable broadcast abstraction, the design of the algorithm, which is very modular, is based on simple abstractions: a new broadcast abstraction called cooperative broadcast, adopt-commit objects that cope with Byzantine processes (hence, as far as we know, the paper presented the first implementation of such objects in the presence of Byzantine processes), and a new round-based object called eventual agreement, whose definition involves a pretty weak validity property.

This paper answered a long-lasting problem, namely, solving Byzantine consensus with the weakest underlying synchrony assumptions. Finally, as claimed in the introduction, and in addition to its optimality with respect to synchrony requirements, a very important first class property of the proposed algorithm lies in its design simplicity. "Simplicity ⇒ easy" is rarely true for non-trivial problems [START_REF] Aigner | Proofs from THE BOOK[END_REF].

operation RB_broadcast MSG(vi) is (1) broadcast INIT(i, vi).

when INIT(j, v) is received do (2) if first reception of INIT(j, -) then broadcast ECHO(j, v) end if.

when ECHO(j, v) is received do (3) if ECHO(j, v) received from more than n+t 2 different processes and READY(j, v) not yet broadcast [START_REF] Baldellon | A necessary and sufficient synchrony condition for solving Byzantine consensus in symmetric networks[END_REF] then broadcast READY(j, v) (5) end if.

when READY(j, v) is received do (6) if READY(j, v) received from (t + 1) different processes and READY(j, v) not yet broadcast [START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF] then broadcast READY(j, v) (8) end if; (9) if READY(j, v) received from (2t + 1) different processes and MSG(j, v) not yet RB-delivered [START_REF] Correia | From consensus to atomic broadcast: time-free Byzantine-resistant protocols without signatures[END_REF] then RB_deliver (j,MSG(v)) % RB-delivery of the message MSG(v) from pj % (11) end if.

C Parameterized Eventual Agreement Object

Let k such that 0 ≤ k ≤ t. The algorithm described in Figure 6 implements an EA object in the system model BZ_AS n,t [t < n/3, 3 t + 1 + k bisource]. As already indicated in Section 5.4, it also assumes that each set F (r) contains (nt + k) processes.

This algorithm is a simple extension of the basic EA algorithm of Figure 3. The lines with the same numbers are the exactly the same in both algorithms. The lines N1, N2, and N3, are new lines, and the lines 12.M1, 12.M2, 13.M1, and 13.M2, replace the lines 12 and 13 of Figure 3. Hence, the modifications are restricted to lines N1-N3 and lines 12.M1-13.M2.

• The first modification (lines N1-N3) is as follows. Before setting the timer of the current round (line 5), the processes executes an additional communication phase: each process p i broadcasts the message EA_PROP3[r i ](bag i ) where bag i contains the (nt) messages EA_PROP2[r i ]() that made true the predicate of line 3. Then, p i waits until it received a message EA_PROP3[r i ]() from (nt) processes. This wait is to not set the timer too early, and (as in Figure 3) makes its expiration dependent only of the message EA_COORD(r)() sent by the round coordinator at line 13.M1, and the messages EA_RELAY(r)() sent by the processes of F (r) at line 18. • As now |F (r)| = nt + k, it is possible that F (r) always contain k Byzantine processes. Consequently, the round cordinator waits until it obtains the same message EA_PROP2[r i ](w) (contained in a message EA_PROP3[r](), as defined at line N1) from (k + 1) processes in F (r) (lines 12.M1-12.M2). As at least one of these processes is correct, it follows that EA_PROP2[r](w) is from a correct process. Hence, when the t + 1+ k bisource coordinates a round, it selects and broadcasts (line 13.M1) a value w obtained from a correct process.

Remark When we consider the basic algorithm of Collection des Publications Internes de l'Irisa c IRISA

Figure 2 :

 2 Figure 2: An algorithm implementing an m-valued adopt-commit object in BZ_AS n,t [t < n/3]

Figure 5 :

 5 Figure 5: Implementing RB-broadcast in BZ_AS n,t [t < n/3] (from [6])

Figure 3 ,

 3 in addition to a CB-broadcast, an invocation of EA_propose() involves three sequential communication steps (messages EA_PROP2[r](), EA_COORD[r](), and EA_REALY[r]()). Differently, the algorithm of Figure 6 requires an additional communication step (messages EA_PROP3[r]()).

  EA_PROP2[r i ]() from (nt) different processes, and (b) the values carried by these messages belong to the set CB [r i ].cb_valid i supplied by operation EA_propose(ri, vali) is (1) auxi ← CB[ri].CB_broadcast EA_PROP1(vali); (2) broadcast EA_PROP2[ri](auxi); (3) wait (EA_PROP2[ri]() messages have been received from (nt) different processes, and their aux values belong to CB[ri].cb_validi); (4) if (the (nt) previous messages carry the same value v) then return(v) end if; (5) set timeri[ri] to ri;

	(6) wait (EA_RELAY[ri](aux) messages received from (n -t) different processes);
	(7) if EA_RELAY[ri](v)

Collection des Publications Internes de l'Irisa c IRISA

Let us remark that lines 1-3 of Figure

and lines 1-3 of Figure2differ only in the fact that an RB-broadcast is used at line 2 for the AC object, and a simple broadcast is used at line 2 for the EA object. These lines have not been encapsulated to define a higher level object because the messages EA_PROP2[ri]() are explicitly used in lines 11-14 of Figure3, while their counterparts in an AC object -messages AC_EST()-are not used by the upper layer.[START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF] The important point here is that the value of the timer increases; as ri increases at every round, it is used as a timeout value. More generally, it is possible to assign to timeri[ri] the value returned by an increasing function fi(ri), which can be specific to each process pi.Collection des Publications Internes de l'Irisa c IRISA

Even if, up to now, a process behaved "correctly", it may crash in the future and become then faulty. Hence, no process can a priori considers the value it proposes as a value proposed by a correct process.Collection des Publications Internes de l'Irisa c IRISA

Acknowledgments

This work has been partially supported by the French ANR project DISPLEXITY devoted to computability and complexity in distributed computing, and the Franco-German ANR project DISCMAT devoted to connections between mathematics and distributed computing.

operation CONS_propose(vi) is (1) esti ← CB [0].CB_broadcast VALID(vi); % safety: validity % (2) repeat forever [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF] ri ← ri + 1; (4) v ← EA_OBJECT .EA_propose(ri, esti); % liveness % [START_REF] Ben-Or | Another advantage of free choice: completely asynchronous agreement protocols[END_REF] if (v ∈ CB[0].cb_validi) then esti ← v end if; % safety: validity % [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] tag, esti ← AC _OBJECT [ri].AC_propose(esti); % safety: agreement % [START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF] if (tag = commit) then RB_broadcast DECIDE(esti) end if (8) end repeat.

when DECIDE(v) is RB-delivered do [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF] if (DECIDE(v) RB-delivered from (t + 1) diff. processes) then return(v) end if. Then process p i enters an infinite loop (lines 2-8). After it has entered its current round (line 3), process p i proposes its current estimate of the decision value est i to the to the EA object, namely, it invokes EA_OBJECT .ea_propose(r i , est i ) (line 4). If the value returned by this invocation is a value that it knows as proposed by a correct process, it adopts it as new estimate, otherwise it keeps its previous estimate (line 5).

Process p i proposes then the current value of est i to the adopt-commit object associated with the current round, from which it obtains a pair tag, est i (line 6). If the value of the tag is commit (line 7), p i RB-broadcasts the message DECIDE(est i ) to inform the other processes that the value of est i can be decided. Then, whatever the value of the tag, p i proceeds to the next round with its (possibly new) estimate value est i .

Finally, as soon as a process, that not yet decided, has RB-delivered the same message DECIDE(v) from (t + 1) different processes, it decides v and stops (line 9). Let us notice that at least one of these messages is from a correct process.

Theorem 4. The algorithm described in Figure 4 solves the m-valued Byzantine consensus problem in the system model

Proof We say that a process p i starts round r when it assigns value r to its local variable r i (line 3). Proof of the CONS-Termination property. If a process decides at line 9, it previously RB-delivered the message DECIDE(v) from (t + 1) different processes. Due to the RB-termination property of the corresponding (t + 1) RB-broadcasts, each correct process RB-delivers this message from the same set of (t + 1) processes, and consequently decides. So, let us assume by contradiction that no correct process decides at line 9.

Let us first observe that, due to the CB-Operation Termination property that no correct process p i blocks forever at line 1. Moreover, it follows from the CB-Operation Validity that CB [0].cb_valid i = ∅ when this invocation terminates.

As no correct process decides, and all correct processes invoke EA_propose(1, -), it follows from the EA-Termination and AC-Termination properties that they all terminate the first round, and consequently start the second. Moreover, if the estimate est i of a correct process p i is updated at line 5, its new value is a value proposed by a correct process. It follows that the correct processes start the second round with estimate values est i containing values proposed by correct processes. As no correct process decides, the same reasoning applies to all rounds r > 1.

Let us observe that the local variables CB [0].cb_valid i of the correct processes eventually converge to the same content (CB-Set Agreement and Termination properties of CB [0]). Hence, there is a round r 0 such that, for every correct process p i , the set CB [0].cb_valid i is never updated after it starts r 0 .

It then follows from the EA-Eventual Agreement property of EA_OBJECT , that there is a round r > r 0 during which all correct processes obtain the same value v at line 4, where v is a value proposed by a correct process. Hence, since r > r 0 , they all succeed the test of line 5 and adopt v as their new estimate est i . Therefore, all correct processes invokeAC _OBJECT [r].AC_propose(v) at line 6. Due to the AC-Obligation property of AC _OBJECT [r], all correct processes obtain commit, v at line 6. Consequently, they all RB-broadcast the same message commit, v at line 7. An

Collection des Publications Internes de l'Irisa c IRISA

A On the Definition of 3 t + 1 bisource

Our definition of an 3 t + 1 bisource is slightly different from the original definition introduced in [START_REF] Aguilera | Consensus with Byzantine failures and little system synchrony[END_REF]. The difference is that it considers only eventually timely channels connecting correct processes, while [START_REF] Aguilera | Consensus with Byzantine failures and little system synchrony[END_REF] considers eventually timely channels connecting a correct process to correct or faulty processes. Hence, an 3 t + 1 bisource is an 3 2t + 1 bisource in the parlance of [START_REF] Aguilera | Consensus with Byzantine failures and little system synchrony[END_REF]. We consider only eventually timely channels connecting pair of correct processes for the following reason: an eventually timely channel connecting a correct process and a Byzantine process can always appear to the correct process as being an asynchronous channel.

B An algorithm implementing RB-broadcast

The distributed algorithm described in Figure 5 implements the RB-broadcast abstraction. It is a simplified version of an algorithm due to G. Bracha [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF]. Its proof can be found in [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF].

When a process p i wants to RB-broadcast a message whose content is v i , it broadcasts the message INIT(i, v i ) (line 1). When a process p i receives a message INIT(j, -) for the first time, it broadcasts a message ECHO(j, v) where v is the data content of the INIT() message (line 2). If the message INIT(j, v) received is not the first message INIT(j, -), p j is Byzantine and the message is discarded. Finally, when p i has received the same message ECHO(j, v) from more than (n + t)/2 processes, it broadcasts the message READY(i, v i ) (line 4). The fact that ECHO(j, v) was received from more than (n + t)/2 processes ensures that no two correct processes can broadcast different messages READY(j, -), but it is still possible that correct processes broadcast such a message while other correct processes never broadcast a message READY(i, -).

The aim of lines 6-8) is to prevent deadlock. Finally, the aim of lines 9-11 is to ensure that all or none of the non-faulty processes RB-deliver the message MSG(j, v) from p j . To this end, the RB-delivery predicate requires that p i receives (2t + 1) copies of READY(j, v), which means at least (t + 1) copies from non-faulty processes (line 9).