Olivier Nier

Denis Rideau

Antoine Cros

Frédéric Monsieur

Gérard Ghibaudo

Raphael Clerc

Jean-Charles C Barbé

Clément Tavernier

Hervé Jaouen

Effective field and universal mobility in high-k metal gate UTBB-FDSOI devices

Keywords: FDSOI, universal mobility, effective field, coefficient η. I

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

INTRODUCTION

Ultra-Thin Body and Box Fully Depleted SOI (UTBB-FDSOI) device is considered as one of the best alternative solution to overcome conventional planar Bulk CMOS limitations [START_REF] Fenouillet-Beranger | FDSOI devices with thin BOX and ground plane integration for 32nm node and below[END_REF][START_REF] Planes | 28nm FDSOI technology platform for high-speed lowvoltage digital applications[END_REF]. Transport properties in UTBB-FDSOI have been extensively studied and many issues have been reported concerning both, the definition of the effective field (E eff ) [START_REF] Ohata | Impact of back-gate biasing on effective field and mobility in ultrathin silicon-on-insulator metal-oxide-semiconductor field-effect-transistors[END_REF] and the universal behavior of the mobility [START_REF] Cristoloveanu | Why the universal mobility is not[END_REF]. This paper aims at reviewing important experimental and theoretical aspects of the universal behavior of the mobility with respect to the effective field. The parameter η, characterizing the effective field, has been extracted from split-CV mobility measurements for n-and ptype UTBB-FDSOI devices. These extractions have been performed for a large range of Back gate Voltages (VB), temperatures and for devices with various Interfacial oxide (IL) Equivalent Oxide Thicknesses (EOT).

II. EXPERIMENTAL OBSERVATIONS

Devices have been processed on 300 mm SOI wafers with a 25 nm thick BOX. The final channel thickness is 7.5 nm and the oxide stack is made of a 1.8 nm thick layer of HfSiON high-k oxide deposited on top of a SiON interfacial layer (IL) with various physical thicknesses (T inv ranging from 1.3 to 4.0 nm for both n-and p-FDSOI devices). The effective mobility has been characterized using split-CV method on 0.9 x 0.9 µm² devices (measurements at V DS =50 mV) for a large range of VB (-10 V<VB<10 V) and temperatures (T=233 K, 300 K and 450 K). The impact of the VB on the capacitance and the drain current is shown in figure 1 for various temperatures. Figures 2 and3 demonstrate a non monotonic behavior and an improvement of the mobility in the forward regime (VB>0 V for nFDSOI and VB<0 V for pFDSOI devices) which is a direct consequence of the back gate inversion, as previously observed in [START_REF] Rideau | Mobility in High-K Metal Gate UTBB-FDSOI Devices: from NEGF to TCAD perspectives[END_REF][START_REF] Nier | Multi-scale strategy for high-k/metal-gate UTBB-FDSOI devices modeling with emphasis on back bias impact on mobility[END_REF]. The extractions have been corrected from access resistances of R access =2  60 Ω.µm. This resistance has been extracted using the R on (L) method [START_REF] Sheu | A capacitance method to determine channel lengths for conventional and LDD MOSFET's[END_REF], i.e. from the intersect of the curve Vds/Ion vs L at L=0. In figure 2, the mobility has been plotted as a function of the inversion charge for two different values of R access indicating that the effect on mobility is more pronounced in the back inversion regime and emphasing the importance of an accurate deembedding of R access . The variation of the capacitance and the threshold voltage (VTH) for all devices are shown in figures 4 and 5 respectively. It demonstrates that the VTH can be shifted by -.5 V to 1 V for VB ranging from -10 V to 10 V. The mobility degradation observed in figure 6 in the thinner EOT device is attributed to remote coulomb scattering due to the presence of charges at high-k/IL interface [START_REF] Nier | Multi-scale strategy for high-k/metal-gate UTBB-FDSOI devices modeling with emphasis on back bias impact on mobility[END_REF]. x 10 The mobility extracted at fixed inversion charge as a function of VB (figure 7) exhibits a bell-shaped behavior [START_REF] Nier | Multi-scale strategy for high-k/metal-gate UTBB-FDSOI devices modeling with emphasis on back bias impact on mobility[END_REF]. In the next section, we show that this behavior can be further highlighted representing the mobility versus the effective field rather than as a function of the inversion density as in figure 2.

-3 VOLTAGE [V ] CAPACITANCE (F/m 2 ) T=233 K T=300 K T=450 K VB=0 V VB=10 V VB=-10 V VB=-10 V VB=0 V VB=10 V 0 0.5 1 1.5 2

III. DEFINITION OF THE EFFECTIVE FIELD IN FDSOI

TRANSISTORS AND EXTRACTION OF PARAMETER.

A transverse average electric field can be defined from the local concentration n(x) and the transverse field E z (x) as:

∫ ( ) ( ) ∫ ( ) (1)
This later equation can be approximated by the following simplified equation in UTBB-FDSOI MOSFETs [START_REF] Sherony | SOI MOSFET effective channel mobility[END_REF]:

with , the inversion charge, the depletion charge ( ) and 1.5 nm accounts for the ground plane accumulation or depletion. In order to match equations (1) and ( 2), η has to be taken equal to η = 0.5 for both n-and pMOS devices in bulk [START_REF] Sabnis | Characterization of the electron mobility in the inverted< 100> Si surface[END_REF] as well as in FDSOI structures [START_REF] Esseni | An experimental study of mobility enhancement in ultrathin SOI transistors operated in double-gate mode[END_REF]. conditions. This also provides an efficient way to calibrate parameters T si , ε ox , IL EOT, T BOX from experiments. Another effective field E eff (not to be confused with the average transverse average electric field) based on Eq.2 is usually used to get the universal mobility curve [START_REF] Takagi | On the universality of inversion layer mobility in Si MOSFET's: Part I-effects of substrate impurity concentration[END_REF]. In this case, η is used as an empirical parameter and is extracted from experiments. In the case of bulk devices, this parameter has been found equal to η = 0.5 for bulk nMOSFET and η = 0.33 for bulk pMOSFET [START_REF] Takagi | On the universality of inversion layer mobility in Si MOSFET's: Part I-effects of substrate impurity concentration[END_REF].

K VB > 0V VB = 0V VB < 0V VB < 0V VB > 0V VB = 0V VB > 0V VB = 0V VB < 0V T=233 K -2 -1 0 1 2 -0.005 0 0.005 0.01 0.015 0.02 0.025 VOLTAGE [V ] CAPACITANCE (F/m 2 ) -2 -1 0 1 2 -0.005 0 0.005 0.01 0.015 0.02 0.025 VOLTAGE [V ] Tinv=4.0 nm Tinv=3.3 nm Tinv=2.65 nm Tinv=1.3 nm VB =0 V VB = -10 V VB = -10 V VB =0 V VB =10 V nMOS pMOS VB =10 V -10 -5 0 5 10 -2 -1.5 -1 -0.5 0 0.5 1 1.5 VB [V] VTH(VB) - VTH(VB=0V) [V]
In high-k UTBB-FDSOI (T inv ranging from 1.3 to 4 nm), it has been demonstrated [START_REF] Rideau | Mobility in High-K Metal Gate UTBB-FDSOI Devices: from NEGF to TCAD perspectives[END_REF][START_REF] Nier | Multi-scale strategy for high-k/metal-gate UTBB-FDSOI devices modeling with emphasis on back bias impact on mobility[END_REF] that the main mechanisms responsible of the mobility degradation are remote coulomb (due to the presence of charges at high-k/IL interface), phonons and surface roughness scatterings. From theoretical mobility calculation, we have shown in a previous work [START_REF] Rideau | Mobility in High-K Metal Gate UTBB-FDSOI Devices: from NEGF to TCAD perspectives[END_REF] that, in the back inversion regime or for devices with thick EOT (T IL > 2.0 nm), the remote coulomb component does not play a significant role in the total mobility. It is thus interesting to study the impact of remote coulomb scattering on mobility curves changing VB, temperatures or IL EOT. Using values extracted in bulk devices, the experimental mobility has been plotted in the case of FDSOI devices as a function of the effective field for various VB ranging from -10 V to 10 V (figure 9). First of all, it can be noticed that the effective field spans a much larger range of values when sweeping VB. However, it is clear from this figure that the mobility does not follow a universal trend, in particular in the back inversion regime. Effective field calculated using Eq.2 (η=0.5 for nFDSOI and η=0.33 for pFDSOI). Tinv= 2.65 nm. T=300 K.

A recent paper has shown that the value of η in FDSOI devices may be different from bulk values [START_REF] Bennamane | Method for extraction of η parameter characterising μ eff against E eff curves in FD-SOI Si MOS devices[END_REF]. This raises the question of the extraction of this parameter. η is usually extracted by adjusting experimental curves in order to get the best universal trend. However, an alternative technique has been recently proposed, deducing η from the following formula [START_REF] Van Den Daele | Detailed investigation of effective field, hole mobility and scattering mechanisms in GeOI and Ge pMOSFETs[END_REF]:

( )| ( )| (3)
This method (Eq.3) has been used to extract η at VB=0 V for various temperatures (figure 10), leading to η = 0.42 and 0.36 for n-and p-FDSOI devices respectively. A slight decrease of the coefficients has been observed for increasing temperatures.

This can also be seen in figure 11 where η has been characterized for devices with various IL EOT. Figure 11: Extracted value of parameter η using Eq. 3 in nand pFDSOI devices with various Tinv (devices of figure 4). T=300 K.VB=0 V.

Using these extracted values η = 0.42 and 0.36, the experimental mobility has been plotted as a function of the effective field (figure 12). Also in this case, it turns out that the mobility does not follow a universal trend. Effective field calculated using Eq.2 (η=0.42 for nFDSOI and η=0.36 for pFDSOI). Tinv= 2.65 nm. T=300 K.

It ought to be notified that Eq.3 is valid only when the front interface is in the strong inversion regime [START_REF] Van Den Daele | Detailed investigation of effective field, hole mobility and scattering mechanisms in GeOI and Ge pMOSFETs[END_REF]. However it can be interesting to apply this equation with reverse VB (VB>0 V for nFDSOI and VB<0 V for pFDSOI devices) since at high gate voltages, the front channel is also inverted. In figures 13 and 14, η has been extracted for VB varying from -10 V to 10 V in n-and p-FDSOI devices. In the front inversion regime, η converge to the previously extracted values while in the back inversion regime, an increase of the coefficients with VB can be observed. As expected when the front channel is not inverted, Eq. 3 is not valid and the extraction of η is not relevant.

Figure 13: Extracted value of parameter η using Eq. 3 in a nFDSOI device for various VB ranging from -10 V to 10 V. Tinv= 2.65 nm. T=300 K. In the front inversion regime (VB<0), η 0.42 while in the forward regime (VB>0), η varies significantly with VB.

Figure 14: Extracted value of parameter η using Eq.3 in a pFDSOI device for various VB ranging from -10 V to 10 V. Tinv= 2.65 nm. T=300 K. In the front inversion regime (VB>0), η 0.36 while in the forward regime (VB<0), η varies significantly with VB. 4). η extracted using Eq.3. T=300K. Extractions have been done at VG=2.5V for devices with Tinv=2.65, 3.3 and 4.0 nm and at VG=1.2V for devices with Tinv=1.3 nm.

Figure 15: Extracted value of parameter η as a function of VB in n-and p-FDSOI devices with various IL EOT (devices of figure

In figure 15, extracted values of parameter η have been represented as a function of VB for n-and p-FDSOI devices with various IL EOT (devices of figure 4). It can be noticed that the three thicker IL EOT devices have roughly similar values for η while in the thinnest devices, where the remote coulomb scattering plays a significant role, lower values can be observed.

In figure 16, η has been extracted for nand pFDSOI devices (T inv =4.0 nm) at various temperatures. As previously observed in figure 10, the coefficients is not affected significantly by the temperature.

Figure 16: Extracted value of parameter η as a function of VB in n-and pFDSOI devices for three different temperatures (T=233, 300 and 450 K). η extracted using Eq.3. Tinv=4.0 nm. Extractions have been done at VG=2.5V.

There is another aspect to mention concerning the key assumption behind Eq.3. It ought to be notified that this equation is based on the assumption that [START_REF] Van Den Daele | Detailed investigation of effective field, hole mobility and scattering mechanisms in GeOI and Ge pMOSFETs[END_REF]:

( )| ( )| (4)
In order to check the validity of this formula, in figures 17, 18 and 19, the mobility has been plotted with respect to the effective field sweeping VB at fixed VG and sweeping VG at VB=0 V. First of all, in figure 17, bulk values for η are used (0.5 for n-and 0.33 for pFDSOI devices) and the condition described in Eq.4 is not satisfied at high Eeff. However, the same conclusions can be obtained from figure 18 when using values extracted from Eq.3 (η = 0.42 and 0.36 for n-and pFDSOI devices respectively). In order to get a better agreement, η also has been re-extracted by brute-force numerical fitting, leading to the value of η=0.62 for nFDSOI and η=0.5 for pFDSOI devices. Results are shown in figure 19.

It can be notified incidentally that the behaviors shown in figure 17, 18 and 19 have been reproduced using a Kubo-Greenwood solvers (not shown here) [START_REF] Rideau | Mobility in High-K Metal Gate UTBB-FDSOI Devices: from NEGF to TCAD perspectives[END_REF].

(cm 2 /V/s) EFFECTIVE FIELD (MV/cm) VB sweep @ VG=1.0V VG sweep @ VB=0V VB sweep @ VG=1.5V VB sweep @ VG=2.0V VB sweep @ VG=2.5V VG sweep @ VB=0V VB sweep @ VG=-2.5V VB sweep @ VG=-1.5V VB sweep @ VG=-1.0V nMOS pMOS VB sweep @ VG=-2.0V
Figure 18: n-and p-FDSOI experimental effective mobility as a function of the effective field sweeping the back terminal or the gate terminal. Eq.2 have been used for the evaluation of the effective field with η=0.42 for nFDSOI and η=0.36 for pFDSOI devices. Tinv= 2.65 nm. T=300 K.

Figure 19: n-and p-FDSOI experimental effective mobility as a function of the effective field sweeping the back terminal or the gate terminal. Eq.2 have been used for the evaluation of the effective field with η=0.62 for nFDSOI and η=0.5 for pFDSOI devices. Tinv= 2.65 nm. T=300 K.

The variation of the mobility with respect to the effective field has been plotted for VB ranging from -10 V to 10 V in figure 20 (n-and p-FDSOI devices). In these cases, a much better universal trend is observed, although not perfect, in particular in the forward regime, as expected from the results shown in figures 13 and 14. Effective field calculated using Eq.2 (η=0.62 for nFDSOI and η=0.5 for pFDSOI). Tinv= 2.65 nm. T=300 K.

The mobility has been plotted as a function of effective field for n-(figure 21) and p-FDSOI (figure 22) devices with Tinv=4.0 and 1.3 nm. We can notice that for the thinnest device (Tinv= 1.3 nm), where remote coulomb scattering plays a significant role, the mobility curves with respect to Eeff does not follow an unique trend even in the front inversion regime. The impact of remote coulomb scattering is further depicted in figure 23 where the mobility has been plotted for VB=-8V, 0 V and 8 V for the nFDSOI devices with various IL EOT. This is also noticeable in pFDSOI devices where the remote coulomb scattering contribution to the total mobility is less pronounced. Effective field calculated using Eq.2 (η=0.62).T=233 K and 450 K. Measurements have been performed at zero VB (line), but also for VB>0 (dashed lines) and VB<0 (dotted lines).

Figure 22: pFDSOI experimental effective mobility as a function of the effective field in devices with Tinv=4.0 nm (left) and Tinv=1.3 nm (right). Effective field calculated using Eq.2 (η=0.62).T=233 K and 450 K. Measurements have been performed at zero VB (line), but also for VB<0 (dashed lines) and VB>0 (dotted lines). These results confirm the difficulties to define a unique effective field in UTBB-FDSOI devices. Indeed, contrary to bulk devices, depending on gate and back voltages, carriers are not confined in a single inversion layer. The existence of multiple channels and the difference between the quality of the two interfaces (front and back) is most likely the cause of the difficulties to have a "perfect" universal trend in the whole range of effective field.

IV. CONCLUSIONS

In this paper, we have reviewed the important aspect of the effective field and mobility in UTBB-FDSOI devices. We have demonstrated that a nearly universal trend for the mobility with respect to Eeff can be obtained only in a limited range of VB. Indeed, we showed that in forward VB conditions, a single value of η does not make universal the mobility versus the effective field. The coexistence of multiple channels and the difference of interfaces (front and back) quality make difficult to apply the same procedure than in bulk devices for the full range of gate and back voltages.

Figure 1 :

 1 Figure 1: Gate capacitance (left) and drain current (right) as a function of the gate voltage for VB=-10, 0 and 10 V and for various temperatures (T=233, 300 and 450 K) in a nFDSOI device: Tinv= 2.65 nm.

Figure 2 :

 2 Figure 2: Effective experimental mobility as a function of the inversion chargefor various VB (-10V, 0V, 10V) corrected from access resistances (not corrected, 2 60 Ω.µm and 2*100 Ω.µm). nFDSOI device : Tinv= 2.65 nm. T=300 K.

Figure 3 :

 3 Figure 3: Effective experimental mobility as a function of the inversion charge for various VB ranging from -10 V to 10 V in steps of 2 V. nFDSOI device : Tinv= 2.65 nm. T=233, 300 and 450 K.

Figure 4 :

 4 Figure 4: Gate capacitance as a function of the gate voltage for VB=-10, 0 and 10 V in n-(left) and p-(right) FDSOI devices with Tinv=1.3 nm, 2.65 nm, 3.3 nm and 4.0 nm. T=300 K.

Figure 5 :

 5 Figure 5: Threshold voltage variation (reference at VB=0 V) as a function of VB in n-(left) and p-(right) FDSOI devices. Devices of figure 4.T=300 K.

Figure 6 :

 6 Figure 6: n-and p-FDSOI experimental effective mobility as a function of the inversion charge. Devices of figure 4.T=300 K; VB=0 V.

Figure 7 :

 7 Figure 7: n-(left) and p-(right) FDSOI experimental effective mobility as a function of VB extracted for Ninv=5e12 cm -2 and 1e13 cm -2 . Two structures: Tinv=1.3 nm and 4.0 nm. T=300 K.

Figure 8 :

 8 Figure 8: n-(left) and p-(right) FDSOI average electric field (Eq.2) assuming η = 0.5 compared to the simulated theoretical average field (Eq.1). VB from -10 V to 10 V in steps of 2V. Tinv= 2.65 nm; T=300 K.

Figure 8

 8 Figure8demonstrates that the approximated average field from Eq.2 reproduces accurately the numerical one (Eq.1) calculated using a self-consistent Poisson-Schrödinger solver for all biases

Figure 9 :

 9 Figure 9: n-(left) and p-(right) FDSOI experimental effective mobility as a function of the effective field. VB ranging from -10 V to 10 V in steps of 2 V.Effective field calculated using Eq.2 (η=0.5 for nFDSOI and η=0.33 for pFDSOI). Tinv= 2.65 nm. T=300 K.

Figure 10 :

 10 Figure 10: Extracted value of parameter η using Eq. 3 in n-and pFDSOI devices for various temperatures (T=233, 300 and 450 K). nFDSOI device : Tinv= 2.65 nm. The domain of validity corresponds to the strong front inversion regime.

Figure 12 :

 12 Figure 12: n-(left) and p-(right) FDSOI experimental effective mobility as a function of the effective field. VB ranging from -10 V to 10 V in steps of 2 V.Effective field calculated using Eq.2 (η=0.42 for nFDSOI and η=0.36 for pFDSOI). Tinv= 2.65 nm. T=300 K.

Figure 17 :

 17 Figure17: n-and p-FDSOI experimental effective mobility as a function of the effective field sweeping the back terminal or the gate terminal. Eq.2 have been used for the evaluation of the effective field with η=0.5 for nFDSOI and η=0.33 for pFDSOI devices. Tinv= 2.65 nm. T=300 K.

Figure 20 :

 20 Figure 20: n-(left) and p-(right) FDSOI experimental effective mobility as a function of the effective field. VB ranging from -10 V to 10 V in steps of 2 V.Effective field calculated using Eq.2 (η=0.62 for nFDSOI and η=0.5 for pFDSOI). Tinv= 2.65 nm. T=300 K.

Figure 21 :

 21 Figure 21: nFDSOI experimental effective mobility as a function of the effective field for VB in devices with Tinv=4.0 nm (left) and Tinv=1.3 nm (right).Effective field calculated using Eq.2 (η=0.62).T=233 K and 450 K. Measurements have been performed at zero VB (line), but also for VB>0 (dashed lines) and VB<0 (dotted lines).

Figure 23 :

 23 Figure 23: nFDSOI experimental effective mobility as a function of the effective field. Effective field calculated using Eq.2. (η=0.62). T=300 K. Devices of figure 4.


Achour Mostéfaouil

Michel Raynal

A Mostéfaoui

Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2 ) Messages, O(1) Time, and no Signature

Keywords: Asynchronous message-passing system, Broadcast abstraction, Byzantine process, Consensus, Distributed algorithm, Intrusion tolerance, Multivalued consensus, Optimal resilience, Randomized binary consensus, Signature-free algorithm Système à passage de messages, Processus byzantin, consensus binaire, consensus multivalué, réduction algorithmique

This paper presents a new algorithm that reduces multivalued consensus to binary consensus in an asynchronous message-passing system made up of n processes where up to t may commit Byzantine failures. This algorithm has the following noteworthy properties: it assumes t < n/3 (and is consequently optimal from a resilience point of view), uses O(n 2 ) messages, has a constant time complexity, and does not use signatures. The design of this reduction algorithm relies on two new all-to-all communication abstractions. The first one allows the non-faulty processes to reduce the number of proposed values to c, where c is a small constant. The second communication abstraction allows each non-faulty process to compute a set of (proposed) values such that, if the set of a non-faulty process contains a single value, then this value belongs to the set of any non-faulty process. Both communication abstractions have an O(n 2 ) message complexity and a constant time complexity. The reduction of multivalued Byzantine consensus to binary Byzantine consensus is then a simple sequential use of these communication abstractions. To the best of our knowledge, this is the first asynchronous messagepassing algorithm that reduces multivalued consensus to binary consensus with O(n 2 ) messages and constant time complexity (measured with the longest causal chain of messages) in the presence of up to t < n/3 Byzantine processes, and without using cryptography techniques. Moreover, this reduction algorithm tolerates message reordering by Byzantine processes.

Introduction

Consensus in asynchronous Byzantine systems The consensus problem lies at the center of fault-tolerant distributed computing. Assuming that each non-faulty process proposes a value, its formulation is particularly simple, namely, each non-faulty process decides a value (termination), the non-faulty processes decide the same value (agreement), and the decided value is related to the proposed values (validity); the way the decided value is related to the proposed values depends on the failure model. Consensus is binary when only two values can be proposed by the processes, otherwise it is multivalued.

Byzantine failures were introduced in the context of synchronous distributed systems [START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Pease | Reaching agreement in the presence of faults[END_REF][START_REF] Raynal | Fault-tolerant agreement in synchronous message-passing systems[END_REF], and then investigated in the context of asynchronous distributed systems [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Lynch | Distributed algorithms[END_REF][START_REF] Raynal | Communication and agreement abstractions for fault-tolerant asynchronous distributed systems[END_REF]. A process has a Byzantine behavior (or commits a Byzantine failure) when it arbitrarily deviates from its intended behavior: it then commits a Byzantine failure (otherwise we say it is non-faulty). This bad behavior can be intentional (malicious) or simply the result of a transient fault that altered the local state of a process, thereby modifying its behavior in an unpredictable way.

Several validity properties have been considered for Byzantine consensus. This paper considers the following one: a decided value is a value that was proposed by a non-faulty process or a default value denoted ⊥. Moreover, to prevent trivial or useless solutions, if all the non-faulty processes propose the same value, ⊥ cannot be decided. As these properties prevent a value proposed only by faulty processes to be decided, such a consensus is called intrusion-tolerant Byzantine (ITB) consensus [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].

Solving Byzantine consensus Let t denote the model upper bound on the number of processes that can have a Byzantine behavior. It is shown in several papers (e.g., [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF][START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Pease | Reaching agreement in the presence of faults[END_REF][START_REF] Toueg | Randomized Byzantine agreement[END_REF]) that Byzantine consensus cannot be solved when t ≥ n/3, be the system synchronous or asynchronous, be the algorithm allowed to use cryptography or not, or be the algorithm allowed to use random numbers or not.

As far as asynchronous systems are concerned, it is well-known that there is no deterministic consensus algorithm as soon as one process may crash [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF], which means that Byzantine consensus cannot be solved either as soon as one process can be faulty. Said another way, the basic asynchronous Byzantine system model has to be enriched with additional computational power. Such an additional power can be obtained by randomization (e.g., [START_REF] Ben-Or | Another advantage of free choice: completely asynchronous agreement protocols[END_REF][START_REF] Correia | From consensus to atomic broadcast: time-free Byzantine-resistant protocols without signatures[END_REF][START_REF] Friedman | Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems[END_REF][START_REF] Mostéfaoui | Signature-free asynchronous Byzantine consensus with t < n/3 and O(n 2 ) messages[END_REF][START_REF] Rabin | Randomized Byzantine generals[END_REF]), assumption on message delivery schedules(e.g., [START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF][START_REF] Toueg | Randomized Byzantine agreement[END_REF]), failure detectors suited to Byzantine systems (e.g., [START_REF] Friedman | ✸Pmute-based consensus for asynchronous Byzantine systems[END_REF][START_REF] Kihlstrom | Byzantine fault detectors for solving consensus[END_REF]), additional -deterministic or probabilistic-synchrony assumptions (e.g., [START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF][START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF][START_REF] Alvizi | Fast Byzantine consensus[END_REF]), or restrictions on the vectors of input values proposed by the processes (e.g., [START_REF] Friedman | Distributed agreement problems and their connection with errorcorrecting codes[END_REF][START_REF] Mostéfaoui | Conditions on input vectors for consensus solvability in asynchronous distrbuted systems[END_REF]). A reduction of atomic broadcast to consensus in the presence of Byzantine processes is presented in [START_REF] Milosevic | On the reduction of atomic broadcast to consensus with Byzantine faults[END_REF].

Finally, for multivalued Byzantine consensus, another approach consists in considering a system model enriched with an algorithm solving (for free) binary Byzantine consensus. This reduction approach has been first proposed in the context of synchronous systems [START_REF] Turpin | Extending binary Byzantine agreement to multivalued Byzantine agreement[END_REF]. Recent works for such synchronous systems can be found in [START_REF] King | Breaking the O(n 2 ) bit barrier: scalable Byzantine agreement with an adaptive adversary[END_REF][START_REF] Liang | Error-free multi-valued consensus with Byzantine failures[END_REF][START_REF] Patra | Error-free multi-valued broadcast and Byzantine agreement with optimal communication complexity[END_REF]. Reductions for asynchronous systems where the communication is by message-passing can be found in [START_REF] Ch | Secure and efficient asynchronous broadcast protocols[END_REF][START_REF] Correia | From consensus to atomic broadcast: time-free Byzantine-resistant protocols without signatures[END_REF][START_REF] Mostéfaoui | From binary consensus to multivalued consensus in asynchronous message-passing systems[END_REF]. The case where communication is by read/write registers is investigated in [START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF]. This reduction approach is the approach adopted in this paper to address multivalued Byzantine consensus.

Contributions of the paper

Considering asynchronous message-passing systems, this paper presents a new reduction from multivalued Byzantine consensus to binary Byzantine consensus, that has the following properties:

• It tolerates up to t < n/3 Byzantine processes,

• Its message cost is O(n 2 ),

• Its time complexity is constant,

• It tolerates message re-ordering by Byzantine processes,

• It does not use cryptography techniques.

A simple and efficient Byzantine Binary consensus algorithm has recently been proposed in [START_REF] Mostéfaoui | Signature-free asynchronous Byzantine consensus with t < n/3 and O(n 2 ) messages[END_REF]. This algorithm, which is based on Rabin's common coin, is signature-free and round-based, requires t < n/3, has an O(n 2 ) message complexity per round, and its expected number of rounds is constant. It follows that, when the reduction algorithm proposed in this paper is combined with this binary consensus algorithm, we obtain a Byzantine multivalued consensus algorithm that has the four properties listed previously. To our knowledge, this is the first Collection des Publications Internes de l'Irisa c IRISA Byzantine multivalued consensus algorithm that is signature-free, optimal with respect to resilience (t < n/3), has an O(n 2 ) expected message complexity and a constant expected time complexity.

The design of the reduction algorithm is based on two new communication abstractions, which are all-to-all communication abstractions. The first allows the non-faulty processes to reduce the number of values they propose to k ≤ c values where c is a known constant. More precisely, c = 6 when t < n/3 (worst case), c = 4 when n = 4t, and c = 3 when t < n/4. The second communication abstraction allows each non-faulty process to compute a set of (proposed) values such that, if the set of a non-faulty process contains a single value, then this value belongs to the set of any non-faulty process. Both communication abstractions have an O(n 2 ) message complexity and a constant time complexity.

The structure of the resulting Byzantine multivalued consensus algorithm is as follows. It first uses the first communication abstraction to reduce the number of proposed values to a constant. Then, it uses sequentially twice the second communication abstraction to provide each non-faulty process with a binary value that constitutes the value it proposes to the underlying binary Byzantine consensus algorithm. Finally, the value decided by a non-faulty process is determined by the output (0 or 1) returned by the underlying binary Byzantine consensus algorithm. Thanks to the communication abstractions, this reduction algorithm is particularly simple (which is a first class design property).

Roadmap

The paper is composed of 6 sections. Section 2 presents the computing model, and define the multivalued ITB consensus problem. Section 3 defines the first communication abstraction (called RD-broadcast) that reduces the number of proposed values to a constant, presents an algorithm that implements it, and proves it correct. Section 4 defines the second communication abstraction (called MV-broadcast), presents an algorithm that implements it, and proves it correct. Section 5 presents the algorithm reducing multivalued consensus to binary consensus in the presence of Byzantine processes.

Computing Model and Intrusion-Tolerant Byzantine Consensus

Distributed computing model

Asynchronous processes

The system is made up of a finite set Π of n > 1 asynchronous sequential processes, namely Π = {p 1 , . . . , p n }. "Asynchronous" means that each process proceeds at its own pace, which may vary arbitrarily with time, and remains always unknown to the other processes.

Communication network

The processes communicate by exchanging messages through an asynchronous reliable point-to-point network. "Asynchronous" means that a message that has been sent is eventually received by its destination process, i.e., 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 there is a bi-directional communication channel between each pair of processes. Hence, when a process receives a message, it can identify its sender.

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 a message by executing the primitive "receive()".

The operation broadcast TAG(m) is a macro-operation which stands for "for each j ∈ {1, . . . , n} send TAG(m) to p j end for".This operation is usually called unreliable broadcast (if the sender commits a failure in the middle of the for loop, it is possible that only an arbitrary subset of processes receives a message).

Failure model Up to t processes may exhibit a Byzantine behavior. A Byzantine process is a process that behaves arbitrarily: it may crash, fail to send or receive messages, send arbitrary messages, start in an arbitrary state, perform arbitrary state transitions, etc. Hence, a Byzantine process, which is assumed to send a message m to all the processes, can send a message m 1 to some processes, a different message m 2 to another subset of processes, and no message at all to the other processes. Moreover, Byzantine processes can collude to "pollute" the computation. A process that exhibits a Byzantine behavior is also called faulty. Otherwise, it is non-faulty.

Let us notice that, as each pair of processes is connected by a channel, no Byzantine process can impersonate another process. Byzantine processes can modify the message delivery schedule, but cannot affect network reliability. More generally, the model does not assume a computationally-limited adversary.

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. Let us observe that this does not prevent multiple copies of the first message TAG() to be received and processed. Notation This computation model is denoted BAMP n,t [∅]. In the following, this model is restricted with the constraint on t < n/3 and is consequently denoted BAMP n,t [n > 3t].

Measuring time complexity

When computing the time complexity, we consider the longest sequence of messages m 1 , . . . , m z whose sending are causally related, i.e., for each x ∈ [2..z], the reception of m x-1 is a requirement for the sending of m x . The time complexity is the length of this longest sequence. Moreover, we implicitly consider that, in each invocation of an all-to-all communication abstraction, the non-faulty processes invoke the abstraction simultaneously.

Multivalued Intrusion-tolerant Byzantine Consensus

Byzantine consensus This problem has been informally stated in the Introduction. Assuming that each nonfaulty process proposes a value, each of them has to decide on a value in such a way that the following properties are satisfied.

• C-Termination. Every non-faulty process eventually decides on a value, and terminates.

• C-One-shot. A non-faulty process decides at most once.

• C-Agreement. No two non-faulty processes decide on different values.

• C-Obligation (validity). If all the non-faulty processes propose the same value v, then v is decided.

Intrusion-tolerant Byzantine (ITB) consensus

In Byzantine consensus, if the non-faulty processes do not propose the same value, they can decide any value. As indicated in the Introduction, we are interested here in a more constrained version of the consensus problem in which a value proposed only by faulty processes cannot be decided. This consensus problem instance is defined by the C-Termination, C-One-shot, C-Agreement, and C-Obligation properties stated above plus the following C-Non-intrusion property (which is a validity property), where ⊥ is a predefined default value, which cannot be proposed by a process.

• C-Non-intrusion (validity). A value decided by a non-faulty process is a value proposed by a non-faulty process or ⊥.

The fact that no value proposed only by faulty processes can be decided gives its name (namely intrusion-tolerant) to that consensus problem instance 1 .

Remark on the binary consensus Interestingly, binary Byzantine consensus (only two values be can be proposed by processes) has the following property.

Property 1. The ITB binary consensus problem is such that if a value is decided by a non-faulty process, this value can always be a value proposed by a non-faulty process.

Proof It follows from the C-obligation property that any non-faulty process decides b when all the non-faulty processes proposed b. Otherwise, at least one non-faulty process proposed g, and then any value b or g may be decided by a non-faulty process without violating the C-Non-intrusion property.

✷ P roperty 1
This means that, when considering the ITB binary consensus, ⊥ can be safely replaced by any of b or g.

1 Directing the non-faulty processes to decide a predefined default value -instead of an arbitrary value, possibly proposed only by faulty processes-in specific circumstances, is close to the notion of an abortable object as defined in [START_REF] Hadzilacos | On deterministic abortable objects[END_REF][START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF] where an operation is allowed to abort in the presence of concurrency. This notion of an abortable object is different from the notion of a query-abortable object introduced in [START_REF] Aguilera | Abortable and query-abortable objects and their efficient implementation[END_REF].

Collection des Publications Internes de l'Irisa c IRISA 3 The Reducing All-to-All Broadcast Abstraction

Definition

The reducing broadcast abstraction (RD-broadcast) is a one-shot all-to-all communication abstraction, whose aim is to reduce the number of values that are broadcast to a constant. RD-broadcast provides the processes with a single operation denoted RD_broadcast(). This operation has an input parameter, and returns a value. It is assumed that all the non-faulty processes invokes this operation.

When a process p i invokes RD_broadcast(v i ) we say that it "RD-broadcasts" the value v i . When a process returns a value v from an invocation of RD_broadcast(), we also say that it "RB-delivers" a value (or a value is RB-delivered). The default value denoted ⊥ rd cannot be RB-broadcast but can be RB-delivered. RD-broadcast is defined by the following properties.

• RD-Termination. Every non-faulty process eventually RD-delivers a value.

• RD-Integrity. No non-faulty process process RD-delivers more than one value.

• RD-Justification. The value RD-delivered by a non-faulty process is either a value RD-broadcast by a nonfaulty process, or the default value ⊥ rd . • RD-Obligation. If the non-faulty processes RD-broadcast the same value v, none of them RD-delivers the default value ⊥ rd . • RD-Reduction. The number of values that are RD-delivered by the non-faulty processes is upper bounded by a constant c.

An RD-broadcast algorithm

An algorithm implementing the RD-broadcast abstraction is described in Figure 1. This algorithm assumes t < n/3. The aim of the local variable rd_del i is to contain the value RD-delivered by p i ; this variable is initialized to "?", a default value that cannot be RD-delivered by non-faulty processes. When a process p i invokes RD_broadcast MSG(v i ), it broadcasts the message INIT(v i ), and waits until it is allowed to RD-deliver a value (line 1). During this waiting period, p i receives and processes the messages INIT() or ECHO() sent by the algorithm. let rd_pseti(x) denote the set of processes from which pi has received INIT(x) or ECHO(x).

operation RD_broadcast(vi) is (1) broadcast INIT(vi); wait(rd_deli = "?"); return(rd_deli).

when INIT(v) or ECHO(v) is received do (2) if (v = vi) ∧ (INIT(v) received from (n -2t) different processes) ∧ (ECHO(v) never broadcast) (3) then broadcast ECHO(v) (4) end if; (5) if ∃ x = vi : |rd_pseti(x)| ≥ t + 1 then rd_deli ← ⊥ rd end if; (6) if ∃ x : |rd_pseti(x)| ≥ n -t then rd_deli ← x end if; (7) let w be the value such that, ∀ x received by pi: |rd_pseti(w)| ≥ |rd_pseti(x)|; (8) if | ∪x rd_pseti(x)| -|rd_pseti(w)| ≥ t + 1 then rd_deli ← ⊥ rd end if. Figure 1: An algorithm implementing RD-broadcast in BAMP n,t [n > 3t]
The behavior of a process p i on its server side, i.e. when -while waiting-it receives a message INIT(v) or ECHO(v), is made up of two phases.

• Conditional communication phase (lines 2-4). If the received value v is different from the value v i it has RD-broadcast, and INIT(v) has been received from "enough" processes (namely (n -2t)), p i broadcasts the message ECHO(v) if not yet done. Let us notice that, as n -2t ≥ t + 1, this means that INIT(v) has been received from at least one non-faulty process.

• Try-to-deliver phase (lines 5-8). Then, for any value x, a process p i computes first the set rd_pset i (x) composed of the processes from which p i has received a message INIT(x) or ECHO(x). If there is a value x, different from v i , that has been received from (t + 1) different processes, if it is non-faulty, p i knows that at least two different values have been RD-broadcast by non-faulty processes (its own value v i , plus another one). In this case, p i RD-delivers the default value ⊥ rd (line 5 and line 1). The RD-delivery of a value by p i terminates its invocation of the RD-broadcast.

If the predicate of line 5 is not satisfied, p i checks if there is a value v received from at least (nt) distinct processes (line 6). Let us notice that, in this case, it is possible that v has been RD-broadcast by all correct processes. Hence, p i RD-delivers this value. As no value w ′ = w has been received more than w, the claim is also true for any such value w ′ . So, the predicate of line 6 will never be satisfied at p i , and consequently p i RD-delivers the default value ⊥ rd .

Remark The predicate of line 6 could be strengthened as follows:

∃ x : (|rd_pset i (x)| ≥ n -t) ∧ (INIT(x) received from ≥ n -2t different processes).
This predicate is more constraining than the predicate (∃ x : |rd_pset i (x)| ≥ nt) used to RD-deliver values at p i . Consequently, it can reduce the number of values which are RD-delivered at p i .

Proof of the RD-broadcast algorithm

All the proofs assume t < n/3. Let us now consider the case n = 4t + α ≥ 4t, where α ≥ 0. In this case n -2t = 2t + α ≥ 2t. As the broadcast by p i of a message ECHO(v) requires the reception of INIT(v) from at least 2t + α different processes, it is possible that there is such a value v. On the other side, as a process p i receives at most one message INIT() from each other process, it is not possible for a process p i to receive n -2t ≥ 2t messages carrying a value w, different from both v and v i . It follows that (n/4 ≥ t) ⇒ (nb_echo ≤ 1), which concludes the proof of the lemma.

Lemma

✷ Proof Let us consider a "worst" execution, i.e., an execution in which t processes are Byzantine. Let us call "vote" (for a value v = ⊥ rd ) a message INIT(v) or ECHO(v) sent by a process.

To be RD-delivered by a non-faulty process p i , a value (different from ⊥ rd ) must be received from (nt) different processes (line 6). Due to Lemma 1, a non-faulty process can vote for at most three distinct values, while a Byzantine process can vote for any number of values. To maximize the total number of values that can be RD-delivered by the set of non-faulty processes, we consider the worst case where (a) there are t Byzantine processes, and (b) if a non-faulty process p i RD-delivers a value v (line 6) it has received for this value (n -2t) votes from non-faulty processes, and a vote from each of the Byzantine processes. In this way, we have to consider the maximal number of votes that can be sent by the non-faulty processes and the fact that only (n -2t) of them are needed to RD-deliver a value. There are three cases.

Case n > 3t. At most 3(n-t) votes can be sent by the non-faulty processes. It follows that the total number of different values that can be RD-delivered by the set of non-faulty processes is (where the "<" comes from n > 3t):

3(n -t) n -2t = 3n -6t + 3t n -2t = 3 + 3t n -2t < 3 + 3t 3t -2t = 6.
Hence the total number of RD-broadcast values that can be returned by the whole set of non-faulty processes is at most 5. When adding the default value ⊥ rd , we obtain c = 6.

Case n > 4t. It then follows from Lemma 1 that there are at most 2(nt) votes sent by non-faulty processes. With the same reasoning as before we obtain (where "<" comes from n > 4t):

2(n -t) n -2t = 2n -4t + 2t n -2t = 2 + 2t n -2t < 2 + 2t 4t -2t = 3.
Hence the total number of RB-broadcast values that can be returned by the whole set of non-faulty processes is at most 2. When adding the default value ⊥ rd , we obtain c = 3.

Finally, for n = 4t we have 2(n-t) n-2t = 6t 2t = 3. Hence, at most c = 4 different values can be returned by the whole set of non-faulty processes when n = 4t.

✷ Lemma 2

Theorem 1. The algorithm described in Figure 1 implements the RD-broadcast abstraction in the computing model

BAMP n,t [n > 3t].
Proof The proof of the RD-Integrity property (a non-faulty process RD-delivers at most one value) follows directly from the text of the algorithm. The proof of the RD-Reduction property follows from Lemma 2.

To prove the RD-Justification property we show that a value RB-broadcast only by Byzantine processes cannot be RD-delivered by a non-faulty process p i . Let us assume the worst case, namely, there are t Byzantine processes and all of them RB-broadcast the same value v. As n > 3t, no non-faulty process can receive INIT(v) from n -2t ≥ t + 1 different processes. Hence, no non-faulty process broadcasts ECHO(v) at line 3. If follows that no non-faulty process receives messages INIT(v) or ECHO(v) from (nt) different processes. Hence, the predicate |rd_pset i (v)| ≥ nt (line 6) cannot become satisfied at a non-faulty process p i , which concludes the proof of the RD-Justification property.

To prove the RD-Obligation property, let us assume that all the non-faulty processes RD-broadcast the same value v. We have to show that no non-faulty process RD-delivers ⊥ rd , i.e., executes the statement rd_del i ← ⊥ rd at line 5 or line 8. Let us first observe that, even if all Byzantine processes propose the same value w = v, the predicate of line 5 cannot be satisfied for w. Finally, as the (at least nt) non-faulty processes RD-broadcast the same value v, whether the (at most t) Byzantine processes have sent the same or different values in INIT() or ECHO() messages, it is not possible for the predicate of line 8 to become satisfied.

To prove the RD-Termination property, we consider two cases. Let us first consider that some value v is RDbroadcast by at least n -2t ≥ t + 1 non-faulty processes. If follows from line 2 that each other non-faulty process broadcasts ECHO(v). Hence, each non-faulty process p i receives messages INIT() or ECHO() messages, carrying the value v, from at least (nt) processes. Consequently, the predicate of line 6 becomes eventually satisfied at every non-faulty process, and -if not yet done-each of them RD-delivers a value.

Let us now consider the case where there is no value v that is RD-broadcast by n -2t non-faulty processes. Considering a non-faulty process p i , let us assume that the predicates of line 5 and line 6 are never satisfied. We show that the predicate of line 8 becomes then eventually satisfied. Let v be the value that p i received the most often from different processes. By assumption it received this value from g non-faulty processes where g < n-2t, and from b Byzantine processes, where 0 ≤ b ≤ t. As g + b < (n -2t) + b, at most (n -2t -1) + b processes have sent the value v to p i . Moreover, as p i does not terminate at line 5 or line 6, it receives a message from each nonfaulty process, i.e., from at least (nt) processes, from which we conclude that p i eventually receives messages from at least (nt) + b different processes. It follows that at least

(n -t + b) -((n -2t -1) + b) = t +

RD-Broadcast vs Byzantine k-Set Agreement

In the k-set agreement problem, each process proposes a value, and at most k different values can be decided by the non-faulty processes. It is shown in [START_REF] Prisco | On k-set consensus problems in asynchronous systems[END_REF] that the solvability of k-set agreement in the presence of Byzantine processes depends crucially on the validity properties that are considered. As the reader can easily check, the specification of the RD-broadcast abstraction defines an instance of the Byzantine c-set agreement problem, where c is the constant defined in Lemma 2. It follows that the algorithm presented in Figure 1 solves this Byzantine k-set agreement instance for any k ≥ c in the system model BAMP n,t [t < n/3]. (Let us remind that t < n/3 is the lower bound on t to solve Byzantine consensus in a synchronous system.)

The Multivalued Validated All-to-All Broadcast Abstraction

Definition

The RD-broadcast abstraction reduces the number of values sent by processes to at most five values plus a default value denoted ⊥ rd , while keeping the number of messages exchanged by non-faulty processes in O(n 2 ).

Differently, assuming that each non-faulty process broadcasts a value, and at most k different values are broadcast (where k does not need to be known by the processes), the aim of the one-shot multivalued validated all-to-all broadcast abstraction (in short MV-broadcast) is to provide each non-faulty process with an appropriate subset of values (called validated values), which can be used to solve multivalued ITB consensus. To that end, the fundamental property of MV-broadcast that is used is the following: if a non-faulty process returns a set with a single value, the set returned by any other non-faulty process contains this value. Moreover, from an efficiency point of view, an important point that has to be satisfied is that the message cost of an MV-broadcast instance has to be O(kn 2 ).

To MV-broadcast a value v i , a process p i invokes the operation MV_broadcast(v i ). This invocation returns to p i a non-empty set a values, which consists of validated values, plus possibly a default value denoted ⊥ mv . This default value cannot be MV-broadcast by a process. Similarly to RD-broadcast, when a process invokes MV_broadcast(v), wee say that it "MV-broadcast v". MV-broadcast is defined by the following properties.

• MV-Obligation. If all the non-faulty processes MV-broadcast the same value v, then no non-faulty process returns a set containing ⊥ mv . • MV-Justification. If a non-faulty process p i returns a set including a value v = ⊥ mv , there is a non-faulty process p j that MV-broadcast v. • MV-Inclusion. Let set i and set j be the sets returned by two non-faulty processes p i and p j , respectively.

(set i = {w}) ⇒ (w ∈ set j ) (let us notice that w can be ⊥ mv ).

• MV-Termination. An invocation of MV_broadcast() by a non-faulty process terminates (i.e., returns a nonempty set).

The following property follows directly from the MV-Inclusion property.

• MV-Singleton. Let set i and set j be the sets returned by two non-faulty processes p i and p j , respectively.

[(set i = {v}) ∧ (set i = {w})] ⇒ (v = w).
let mv_pset1i(x) denote the set of processes from which pi has received MV_VAL1(x); mv_val2i is a set of pairs process index, value , initially empty.

operation MV_broadcast MSG(vi) is (1) broadcast MV_VAL1(vi); wait ∃ v such that |mv_pset1i(v)| ≥ 2t + 1 ; % v can be ⊥mv % (2) broadcast MV_VAL2(v); wait |mv_val2i| ≥ n -t ; (3) return ({x | -, x ∈ mv_val2i}).
when MV_VAL1(y) is received do % y can be ⊥mv % ( 4)

if (|mv_pset1i(y)| ≥ t + 1) ∧ (MV_VAL1(
) not yet broadcast) then broadcast MV_VAL1(y) end if;

(5) let w be the value such that, ∀ x received by pi:

|mv_pset1i(w)| ≥ |mv_pset1i(x)|; (6) if (| ∪x mv_pset1i(x)| -|mv_pset1i(w)| ≥ t + 1) ∧ (MV_VAL1(⊥mv) never broadcast) (7) then broadcast MV_VAL1(⊥mv) (8) end if; when MV_VAL2(x) is received from pj do % x can be ⊥mv % (9) wait(|mv_pset1i(x)| ≥ 2t + 1); (10) mv_val2i ← mv_val2i ∪ j, x .

An MV-broadcast algorithm

A two-phase algorithm implementing the MV-broadcast abstraction is described in Figure 2. It assumes t < n/3, and -as we will see-its message complexity is O(kn 2 ).

To be validated, a value must have been MV-broadcast by at least one non-faulty process. Hence, for a process to locally know whether a value is validated, it needs to receive it from (t + 1) processes.

Each process p i manages a local variable mv_val2 i , which is a set (initially empty). Its aim is to contain pairs j, x , where j is a process index and x a validated value. The behavior of a non-faulty process p i is as follows.

• In the first phase (line 1) a process p i broadcasts its initial value by sending the message MV_VAL1(v i ). It then waits until it knows (a) a validated value v (hence it has received MV_VAL1(v) from at least (t + 1) different processes), (b) and this value v is eventually known by all non-faulty processes. This is captured by the following waiting predicate "the message MV_VAL1(v) has been received from at least (2t + 1) different processes" used at line 1. From then on, p i will champion this value v for it to belong to the sets returned by the non-faulty processes.

On it server side concerning the reception of a message MV_VAL1(y), a process p i does the following (line 4). If p i knows that y is a validated value (i.e., the message MV_VAL1(y) was received from least (t + 1) processes), (if not yet done) p i broadcasts the very same message to help the validated value y to be known by all non-faulty processes.

Then, according to its current knowledge of the global state, p i checks if there is a possibility that no value at all be present enough to be validated. It there is such a possibility, p i broadcasts MV_VAL1(⊥ mv ) in order no set returned by a non-faulty process be empty. To that end (as at lines 6-7 of the RD-broadcast algorithm, Figure 1), p i computes the value w most received from different processes (lines 5). If at least (t + 1) processes have broadcast values different from w, p i broadcasts MV_VAL1(⊥ mv ), if not yet done (lines 6-8); p i sends the default value because it sees too may different values, and it does not know which ones are from non-faulty processes.

• When it enters the second phase (line 2), a process champions the validated value v it has previously computed with the waiting predicate of line 1. This is done by broadcasting the message MV_VAL2(v). It then waits until the set mv_val2 i contains at least (nt) pairs j, x , and finally returns the set of values contained in these pairs (line 3). Let us remind that those are validated values.

On its server side, when a process p i receives a message MV_VAL2(x) from a process p j , it waits until it has received a message MV_VAL1(x) from at least (2t + 1) different processes. This is needed because Byzantine processes can send spurious messages MV_VAL2(x) while they have not validated the value x. More precisely, let us notice that the waiting predicate (|mv_pset1 i (x)| ≥ 2t + 1) used by p i at line 9 is the same as the one used at line 2 by p j -if it is non-faulty-to champion the value x. Hence, in case p j is not non-faulty, p i waits until the same validation predicate (|mv_pset1 i (x)| ≥ 2t + 1) becomes true before accepting to process the message MV_VAL2(x) sent by p j .

Remark Let us notice that this algorithm is tolerant to message duplication. Moreover, while a non-faulty process is not allowed to MV-broadcast the default value ⊥ mv , a Byzantine process can do it. Let us also remark that ⊥ mv is the only default value associated with the MV-broadcast abstraction. Hence, for MV-broadcast, ⊥ rd is a "normal" value, which can be MV-broadcast, as any value different from ⊥ mv .

Proof of the MV-broadcast algorithm

As previously, all the proofs assume t < n/3.

Lemma 3.

The waiting predicate (∃ v such that |mv_pset1 i (v)| ≥ 2t + 1) (used at line 1) is eventually satisfied at any non-faulty process p i .

Proof Let us consider the the following predicate P : "There is a value v and a finite time after which at least (t + 1) non-faulty processes have sent the message MV_VAL1(v)". We consider two cases.

Case 1: The predicate P is satisfied. In this case, it follows from line 4 that every non-faulty process eventually broadcasts MV_VAL1(v). As there are at least nt ≥ 2t + 1 non-faulty processes, the predicate (∃ v such that |mv_pset1 i (v)| ≥ 2t + 1) becomes eventually true at every non-faulty process. Consequently, no non-faulty process can block forever at line 1.

Case 2: The predicate P is not satisfied. Let p i be a non-faulty process. Let vmr i be the most often received value by p i , from different processes (as defined at line 5). Let c be the number of non-faulty processes that sent MV_VAL1(vmr i ). As P is not satisfied, c ≤ t.

As there are at least (nt) non-faulty processes, p i receives at least (nt) messages MV_VAL1(). More precisely, p i receives these messages from (nt + b) different processes, where b ∈ [0..t] is the additional number of -non-faulty or Byzantine-processes that sent a message to p i . Among these (n-t+b) processes, at most (c+b) messages MV_VAL1() carry the value vmr i (the upper bound (c + b) is attained when the b additional processes are Byzantine and sent MV_VAL1(vmr i ) to p i ). It follows that at least (nt + b) -(c + b) = ntc of them sent to p i values different from vmr i . As c ≤ t and n > 3t, we have ntc ≥ n -2t ≥ t + 1. It follows that the predicate of line 6 is eventually satisfied, and p i broadcasts then the message MV_VAL1(⊥ mv ) (line 7). This reasoning applies to any non-faulty process p i (possibly with values different from vmr i ). Hence, each non-faulty process p i eventually receives MV_VAL1(⊥ mv ) from at least (nt) processes. Finally, as nt ≥ 2t + 1, the predicate (|mv_pset1 i (⊥ mv )| ≥ 2t + 1) is eventually satisfied at each non-faulty process p i , which concludes the proof of the second case.

✷ Before a non-faulty process p j returns a set set j , it added (nt) different pairs to mv_del2 j . As a non-faulty process processes at most one message MV_VAL2() from every other process (see the discarding of erroneous messages from Byzantine processes in section 2.1), it follows that p j has received and processed messages MV_VAL2() from (nt) different processes, i.e, from at least n -2t ≥ t + 1 non-faulty processes.

As (n-t)+(t+1) > n, it follows that there is a non-faulty process p k that sent the same message MV_VAL2() to both p i and p j . Hence, it sent MV_VAL2(w) to p j , and the pair k, w is a pair of mv_val2 j , which concludes the proof of the lemma. ✷ Lemma 7

Theorem 3. The algorithm described in Figure 2 Proof As far as the messages MV_VAL1() are concerned we have the following. Each non-faulty process broadcasts its initial value v i (line 1), broadcasts at most once any value v = v i it receives (line 4), and broadcasts at most once the default value ⊥ mv (line 7). It follows that these broadcasts issued by the non-faulty processes generate at most (k + 1)n 2 MV_VAL1() messages. As each non-faulty process broadcasts a message MV_VAL2() at most once (line 2), it follows that at most n 2 MV_VAL2() messages are sent by the non-faulty processes. Hence, the total number of messages sent by non-faulty processes belongs to O(n 2 ).

As there are only two message types, a message has to carry a single bit of control information.

As far as the time complexity is concerned, we have the following. A message MV_VAL1() sent by a non-faulty process at line 1 entails at most one forwarding of the same message at line 4 by a non-faulty process. Moreover, the sending of a message MV_VAL2() by a non-faulty process at line 2 is entailed by "enough" reception of messages MV_VAL1(). It follows that the longest sequence of causally related messages is 3.

✷ T heorem 4

Multivalued Intrusion-Tolerant Byzantine Consensus

The multivalued intrusion-tolerant Byzantine (ITB) consensus problem was defined in Section 2.3. A signaturefree algorithm that solves it despite up to t < n/3 Byzantine processes is described in this section. This algorithm is such that the expected number of messages exchanged by the non-faulty processes is O(n 2 ), and its expected time complexity is constant.

Enriched computation model for multivalued ITB consensus

In the following, as announced in the introduction, we consider that the additional computational power that allows multivalued ITB consensus to be solved in BAMP n,t [t < n/3] is an underlying Byzantine binary consensus (BBC) algorithm. Let BAMP n,t [t < n/3, BBC] denote the system model BAMP n,t [t < n/3] enriched with a BBC algorithm. BBC algorithms are described in several papers (e.g., [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Correia | From consensus to atomic broadcast: time-free Byzantine-resistant protocols without signatures[END_REF][START_REF] Friedman | Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems[END_REF][START_REF] Mostéfaoui | Signature-free asynchronous Byzantine consensus with t < n/3 and O(n 2 ) messages[END_REF][START_REF] Toueg | Randomized Byzantine agreement[END_REF]).

To obtain a multivalued ITB consensus algorithm with an O(n 2 ) expected message complexity and a constant expected time complexity, we implicitly consider that the underlying BBC algorithm is the one presented in [START_REF] Mostéfaoui | Signature-free asynchronous Byzantine consensus with t < n/3 and O(n 2 ) messages[END_REF].

An efficient algorithm solving the multivalued ITB consensus problem

The algorithm is described in Figure 3. The multivalued consensus operation that is built is denoted mv_propose(), while the underlying binary consensus operation it uses is denoted bin_propose(). Extremely simple, this algorithm can be decomposed in four phases. The first three phases are communication phases, while the last phase exploits the result of the previous phases to reduce multivalued Byzantine consensus to BBC.

The second and the third phases are two distinct instances of the MV-broadcast abstraction. Not to confuse them, their corresponding broadcast operations are denoted MV_broadcast 1 (), and MV_broadcast 2 (), respectively. Similarly, their default values are denoted ⊥ mv1 and ⊥ mv2 . It is assumed that the default values ⊥ rd , ⊥ mv1 , ⊥ mv2 , and ⊥ (the consensus default value) are all different. The four phases are as follows, where C _PROP denotes the set of values proposed by the non-faulty processes.

Collection des Publications Internes de l'Irisa c IRISA The fact that expected time complexity is constant follows directly from the fact that the time complexities of both the RB-broadcast and MV-Broadcast abstraction are constant (Theorem 2 and Theorem 4), and the underlying BBC algorithm has an expected time complexity that is constant.

✷ T heorem 6

Remark Let us remark that, if we suppress the invocation of the RD-broadcast abstraction, and replace line 1 by the statement "rd_val i ← v i ", the multivalued ITB consensus remains correct. This modification saves the two communication steps involved in the RD-broadcast, but loses the O(n 2 ) message complexity, which is now O(kn 3 ), where k ∈ [1.

.n] is the number of distinct values broadcast by correct processes.

Conclusion

This paper presented an asynchronous message-passing algorithm which reduces multivalued consensus to binary consensus in the presence of up to t < n/3 Byzantine processes (n being the total number of processes). This algorithm has the following noteworthy features: its message complexity is O(n 2 ), its time complexity is O(1), and it does not rely on cryptographic techniques. As far as we know, this is the first consensus reduction owning all these properties, while being optimal with respect to the value of t. This algorithm relies on two new all-toall communication abstractions. These abstractions consider the values that are broadcast, and not the fact that "this" value was broadcast by "this" process. This simple observation allowed us to design an efficient reduction algorithm. (An n-multiplexing of a one-to-all broadcast abstraction would entail an O(n 3 ) message complexity.) Interestingly, this reduction algorithm tolerates message re-ordering by Byzantine processes. When combined with the binary Byzantine consensus algorithm presented in [START_REF] Mostéfaoui | Signature-free asynchronous Byzantine consensus with t < n/3 and O(n 2 ) messages[END_REF], we obtain the best algorithm known so far (as far as we know) for multivalued Byzantine consensus in a message-passing asynchronous system (where "best" is with respect the value of t, the message and time complexities, and the absence of limit on the computational power of the adversary).

Lemma 1 Lemma 2 .

 12 At most c different values can be RD-delivered by the non-faulty processes, where c = 6 when n/3 > t, c = 4 when n = 4t, and c = 3 when t > n/4.

Figure 2 :

 2 Figure 2: An algorithm implementing MV-broadcast in BAMP n,t [n > 3t]

  Finally, if p i has not yet assigned a value to rd_del i , it computes the value w that, up to now, it has received the most often in an INIT() or ECHO() message (line 7). If there are at least (t + 1) different processes that sent INIT() or ECHO() messages with values different from w (this is captured by the predicate of line 7), it is impossible for p i to have in the future the same value received from (nt) distinct processes. This claim is trivially true for w, because at least (t + 1) processes sent values different from w.

  1 different processes have sent to p i values different from v. Consequently, the predicate of line 8 is eventually satisfied and p i RD-delivers ⊥ rd . ✷ T heorem 1 Proof It follows from Lemma 1 that a non-faulty process echoes at most two INIT() messages. This means that, it broadcast at most three messages (its own INIT() message, plus two ECHO() messages). As a broadcast costs n messages, the total number of messages sent by the non-faulty processes is 3n 2 . A single bit of control is required to differentiate INIT() and ECHO() messages. As far as the time complexity is concerned, a message ECHO() can only be sent when a message INIT() is received. Hence, the time complexity is 2.

	Theorem 2. The number of messages sent by the non-faulty processes is upper bounded by O(n 2 ). Moreover, in
	addition to a value sent by a process, a message carries a single bit of control information. The time complexity is
	O(1).

✷ T heorem 2

  Lemma 4. The waiting predicate (|mv_val2 i | ≥ nt) (used at line 2) is eventually satisfied at any non-faulty process p i .Proof It follows from Lemma 3 that no non-faulty process blocks forever in the wait statement of line 1. Hence, each non-faulty process p i broadcasts a message MV_VAL2(w i ) at line 2, where the value w i is such that (|mv_pset1 i (w i )| ≥ 2t + 1). If follows from this predicate that at least (2t + 1) processes sent MV_VAL1(w i ) to p i from which we conclude that the message MV_VAL1(w i ) has been broadcast by at least (t + 1) non-faulty processes. It consequently follows from line 4 that (if not yet done) each non-faulty process broadcasts the message MV_VAL1(w i ). Hence, at each non-faulty process p j , we eventually have |mv_pset1 j (w i )| ≥ 2t + 1. Finally, it follows from the predicate of line 9 that, at line 10, every non-faulty process p j adds i, w i to its local set mv_val2 j .As there are (nt) non-faulty processes, it follows that we eventually have |mv_pset1 i (w i )| ≥ nt at every non-faulty process, and the predicate of line 2 becomes eventually satisfied, which concludes the proof of the lemma. If all non-faulty processes MV-broadcast the same value v, no non-faulty process returns a set containing ⊥ mv .Proof To prove the MV-Obligation property, let us assume that all non-faulty processes broadcast MV_VAL1(v) at line 1. If follows from the predicate of line 4 that, even if all the Byzantine processes broadcast the same value w = v, no non-faulty process broadcasts w at line 4, and consequently at most t values different from v can be broadcast in MV_VAL1() messages. Let us consider a non-faulty process p i in a worst case execution, which occurs when all the Byzantine processes broadcast the same value w = v. Let us notice that |mv_pset1 i (v)| monotonically increases from 0 to (nt), and |mv_pset1 i (w)| monotonically increases from 0 to t. There are two cases.• If, during the execution, there are periods where|mv_pset1 i (w)| ≥ |mv_pset1 i (v)|,due to the range of |mv_pset1 i (w)|, the predicate |mv_pset1 i (v)| -|mv_pset1 i (w)| ≥ t + 1 returns false when it is evaluated by p i . It follows that, when |mv_pset1 i (w)| ≥ |mv_pset1 i (v)|, p i cannot broadcast MV_VAL1(⊥ mv1 ) at line 7. • During the period where |mv_pset1 i (v)| ≥ |mv_pset1 i (w)| (this necessarily occurs, and eventually remains true forever), due to the range of |mv_pset1 i (v)| and |mv_pset1 i (w)|, and similarly to the previous case, the predicate |mv_pset1 i (w)| -|mv_pset1 i (v)| ≥ t + 1, returns false when it is evaluated by p i , and, as before, p i cannot broadcast MV_VAL1(⊥ mv ) at line 7.It follows that no non-faulty process broadcasts MV_VAL1(⊥ mv ). As only (at most t) Byzantine processes may broadcast MV_VAL1(⊥ mv ), the predicate (|mv_pset1 i (⊥ mv )| ≥ 2t + 1) evaluated at line 9 can never be satisfied at a non-faulty process p i . Hence, the set mv_val2 i of a non-faulty process p i cannot contain a pair -, ⊥ mv , and consequently p i cannot return a set including ⊥ mv , which concludes the proof the MV-Obligation property.Proof To prove the MV-Justification property, we show that a value MV-broadcast only by Byzantine processes cannot be added to the set mv_val2 i of a non-faulty process p i . Let us consider the worst case where there are t Byzantine processes and all broadcast MV_VAL1(v), where v, is not MV-broadcast by non-faulty processes. Due to the predicate of line 4, no non-faulty process p i echoes the value v. Hence, v can be received only from the t Byzantine processes. It follows that the predicate (|mv_pset1 i (v)| ≥ 2t + 1) of line 9 cannot be satisfied at a non-faulty process p i , and consequently -, v cannot be added to mv_val2 i . Let set i and set j be the sets returned by two non-faulty processes p i and p j , respectively. (set i = {w}) ⇒ (w ∈ set j ). If a non-faulty process p i returns set i = {w}, it follows from the predicate of line 2 that mv_val2

		✷ Lemma 4
	Lemma 5. ✷ Lemma 6
	Lemma 7. Proof	Lemma 3

✷ Lemma 5 Lemma 6. If the set returned by a non-faulty process p i contains a value v = ⊥ mv , then v has been MV-broadcast by a non-faulty process. i contains (nt) different pairs process index,w . Hence, p i has received the message MV_VAL2(w) from (nt) different processes.

  implements the MV-broadcast abstraction in the computing model BAMP n,t [t < n/3]. Let us assume that at most k different values are MV-broadcast by the processes. The number of messages sent by the non-faulty processes is upper bounded by O(kn 2 ). A message needs to carry a single bit of control information. The time complexity is O(1).

	Proof The proof follows from Lemmas 3 and 4 (MV-Termination), Lemma 5 (MV-Obligation), Lemma 6 (MV-
	Justification), and Lemma 7 (MV-Inclusion).	✷ T heorem 3
	Theorem 4.

Collection des Publications Internes de l'Irisa c IRISA

operation mv_propose(vi) is [START_REF] Aguilera | Abortable and query-abortable objects and their efficient implementation[END_REF] rd_vali ← RD_broadcast(vi); % - -------------------------------------(2) set1i ← MV_broadcast 1 (rd_vali); % pi, pj non-faulty: (|set1i| = 1) ∧ (|set1j| = 1) ⇒ (set1i = set1j) % [START_REF] Ben-Or | Another advantage of free choice: completely asynchronous agreement protocols[END_REF] if (set1i = {w}) then auxi ← w else auxi ← ⊥ end if; % - -------------------------------------(4) set2i ← MV_broadcast 2 (auxi); % pi, pj non-faulty: (set2i = {w}) ⇒ (w ∈ set2j) % % - -------------------------------------(5)

if (set2i = {w}) ∧ (w / ∈ {⊥ rd , ⊥mv1, ⊥mv2, ⊥}) then bpi ← 1 else bpi ← 0 end if; [START_REF] Ch | Secure and efficient asynchronous broadcast protocols[END_REF] bdeci ← bin_propose(bpi); [START_REF] Correia | From consensus to atomic broadcast: time-free Byzantine-resistant protocols without signatures[END_REF] if (bdeci = 1) then return(w) such that w ∈ set2i and w / ∈ {⊥ rd , ⊥mv1, ⊥mv2, ⊥} [START_REF] Prisco | On k-set consensus problems in asynchronous systems[END_REF] else return(⊥) [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF] end if. • The first phase consists of an RB-broadcast instance. Each non-faulty process p i invokes RD_broadcast(v i ), where v i is the value it proposes to consensus, and stores the returned value in its local variable rd_val i (line 1). Due to properties of the RD-broadcast abstraction, we have

and (due to Lemma 2) |RD_VAL| ≤ 6. Moreover, the message cost of this phase is the one of the RDbroadcast, i.e., O(n 2 ). • The second phase (lines 2 and 3) consists of the first MV-broadcast instance, namely, a process p i invokes MV_broadcast 1 (rd_del i ) from which it obtains the non-empty set set1 i . Due to the properties of the MVbroadcast abstraction, we have

Moreover, due to the MV-singleton property, we also have

Then, according to the value of set1 i , p i prepares a value aux i it will broadcast in the second MV-broadcast instance. If set1 i = {w}, aux i = w, otherwise aux i = ⊥ (the consensus default value).

Let AUX = ∪ i∈C {aux i }, where C denotes the set of non-faulty processes. While preserving the O(n 2 ) message complexity, the aim of the lines 2 and 3 is to ensure the following property

Let us notice that, thanks to the MV-Justification property, the set AUX cannot contain a value proposed only by Byzantine processes. • The third phase (line 4) is a second instance of the MV-broadcast abstraction. The values MV-broadcast by the non-faulty processes are values of the set AUX . So, the set set2 i returned by a non-faulty process p i is such that

and, due to the MV-Inclusion property, the sets returned to any two non-faulty processes p i and p j are such that (set2 i = {w}) ⇒ (w ∈ set2 j ).

• The last phase (lines 5-9) is where the underlying BBC algorithm is exploited. If set2 i contains a single value, that is not a default value, p i proposes 1 to the underlying BBC algorithm. Otherwise, it proposes 0. Then, according to the value bdec i returned by the BBC algorithm, there are two cases. If bdec i = 1, p i return the value of set2 i which is not a default value (line 7). Otherwise, bdec i = 0 and p i returns the default value ⊥.

Proof of the multivalued ITB consensus algorithm

Theorem 5. The algorithm described in Figure 3 solves the multivalued ITB consensus problem in the computing model BAMP n,t [t < n/3, BBC].

Proof The C-termination property follows from the following properties.

• The RD-termination property (line 1).

• The MV-Termination property applied to both instances of MV-broadcast (lines 2 and 4).

• The C-Termination property of the underlying BBC algorithm.

• The fact that, when BBC returns 1:

-at least one non-faulty process p i proposed 1 to BBC, and this process is such that set2 i = {w} where w / ∈ {⊥ rd , ⊥ mv1 , ⊥ mv2 , ⊥}, and -due to the MV-inclusion property of MV_broadcast 2 (), the set set2 j of any non-faulty process p j contains w, and this is the only non-bottom value in set2 j .

Proof of the C-Obligation property. Let us consider the case where all non-faulty processes propose the same value v. It follow from the RD-Obligation property that they all return v from their invocation of RD_broadcast(v) (line 1). Hence, they all invoke MV_broadcast 1 (v) (line 2), from which, due to the MV-Obligation and MV-Justification properties, they all obtain the set set1 i = {v}. It follows that they all MV_broadcast 2 (v), from which (for the same reason) they still obtain the same set set2 i = {v} (line 4). Consequently all non-faulty processes propose 1 to the underlying BBC algorithm and (due to its C-Obligation property) they all decide 1 (line 6). Hence, they all return v at line 7.

Proof of the C-Non-intrusion property. To show that a value proposed only by Byzantine processes cannot be decided, let us consider the worst case, namely, there are t Byzantine processes and all of them propose a value w, which is not proposed by a non-faulty process. It follows from the RD-Justification of the RD-broadcast abstraction that no non-faulty process p i obtains w from its invocation of RD_broadcast() (line 1). Similarly, due to the MV-Justification of the MV-broadcast abstraction, no non-faulty process p i can obtain w from its invocations of MV_broadcast 1 () (line 2) and MV_broadcast 2 () (line 4). As v / ∈ set2 i , a non-faulty process p i cannot decided v.

Proof of the C-agreement property. If the value decided by the underlying BBC algorithm is 0, all non-faulty processes decide ⊥ (line 8). If the value 1 is decided, and all non-faulty processes proposed 1, all their sets set2 i are singletons, which -due to the MV-singleton property-contain the same value w. It follows from lines 5 and 7 that all non-faulty processes decide w.

Let us now consider the last case, where the value 1 is decided by the underlying BBC algorithm, while two non-faulty processes p i and p j are such that p i proposed 1 and p j proposed 0. As p i has proposed 1 we have set2 i = {w}, where w is not a default value. As both p i and p j are non-faulty, it follows from the MV-Inclusion property of the second MV-broadcast that w ∈ set2 j . Moreover, as non-faulty processes can MV-broadcast only w or ⊥ at line 4, it follows from the MV-Inclusion property that w is the only non-default value in set2 j . Consequently, p j decides w at line 7.

✷ T heorem 5 Theorem 6. Let us assume an underlying BBC algorithm whose expected message complexity is O(n 2 ) and expected time complexity is constant (e.g., the one presented in [START_REF] Mostéfaoui | Signature-free asynchronous Byzantine consensus with t < n/3 and O(n 2 ) messages[END_REF]). When considering the non-faulty processes, the expected message complexity of the multivalued ITB consensus algorithm described in Figure 3 is O(n 2 ), and its expected time complexity is constant.

Proof It follows from Theorem 2 that the number of messages sent by the non-faulty processes at line 1 is O(n 2 ). Due to the RD-reduction property of the RD-broadcast abstraction, there is constant c (where c ≤ 6, see Lemma 2) such that at most c different values are RD-delivered by the RD-broadcast abstraction. It then follows from Theorem 4 that the number of messages sent in the two MV-broadcasts (lines 2 and 4) by the non-faulty processes is O(n 2 ). Finally, as the expected number of messages sent by the non-faulty processes in the BBC algorithm is O(n 2 ), the multivalued ITB consensus algorithm inherits this message complexity. It follows that the expected number of messages sent by the non-faulty processes belongs to O(n 2 ).