Tiago José

Santos Moraes

Mohamed Trabelsi
email: mohamed.trabelsi@ensam.eu.

Hussein Zahr
email: hussein.zahr@ensam.eu.

Eric Semail
email: eric.semail@ensam.eu.

T J D S Mores

Homopolar Current's Copper Losses Analysis for Different Modulations in Open-End Winding Five-Phase drives

 Abstract --This paper analyses the copper losses due to the homopolar current of a five-phase open-end winding machine supplied by a 10-leg inverter and a single DC voltage source. This topology can have non-null high frequency homopolar current components that can increase the machine's copper losses and result in overheating of the motor phase windings . Accordingly, different modulation strategies are compared with the goal of reducing the homopolar current and, consequently the resulting copper losses. The comparison study is achieved using Matlab/Simulink and a finite element model in order to evaluate these losses.

Index Terms--Eddy currents, Homopolar current, Integrated drive, Multiphase Permanent Magnet Synchronous machine (PMSM), Open-end winding, Proximity effects, Pulse width modulation (PWM), Skin effect, Space vector pulse width moduation (SVPWM). NTEGRATED drive main advantage is its potential high power drive density, especially because only one thermal cooling system is used for the machine and the Voltage Source Inverter (VSI). Other advantages are observed for this kind of drive such as elimination of AC cables, a better Electromagnetic Compatibility and a simplified packaging for use in complex systems such as hybrid automotive [START_REF] Burkhardt | Design and analysis of a highly integrated 9-phase drivetrain for EV applications[END_REF]- [START_REF] Morya | Applications of Wide Bandgap (WBG) devices in AC electric drives: A technology status review[END_REF]. Otherwise, the main concerns of this drive architecture are the thermal constraints, especially for the most delicate components of the drive such as the Si transistors and the magnets [START_REF] Burkhardt | Design and analysis of a highly integrated 9-phase drivetrain for EV applications[END_REF], [START_REF] Wang | Integrated Modular Motor Drive Design With GaN Power FETs[END_REF]. With wide-gap transistors SiC or GaN with maximum temperature of the same order as the windings, this constraint should be reduced in the future [START_REF] Burkhardt | Design and analysis of a highly integrated 9-phase drivetrain for EV applications[END_REF], [START_REF] El-Refaie | Integrated electrical machines and drives: An overview[END_REF]- [START_REF] Morya | Applications of Wide Bandgap (WBG) devices in AC electric drives: A technology status review[END_REF].

I. NOMENCLATURE

Nevertheless, it is likely that transistors fault occurrence will be higher than in the classical drives. This is the reason why fault tolerance of the drive is particularly interesting especially in transportation. As consequence, the multiphase machines are interesting candidates for the integrated drives [START_REF] Burkhardt | Design and analysis of a highly integrated 9-phase drivetrain for EV applications[END_REF], [START_REF] El-Refaie | Integrated electrical machines and drives: An overview[END_REF], [START_REF] Barrero | Recent Advances in the Design, Modeling, and Control of Multiphase Machines. Part I[END_REF], [START_REF] Rosen | Modeling and optimized control of fault-tolerant H-bridge fed multiphase drives[END_REF].

When the VSI-legs are inside the machine, the open-end winding drives is no longer a structure which increases the complexity of the external connections. On contrary, for an imposed DC bus voltage such as 48V, , the open-end windings solution allows to reduce the copper losses in comparison with a standard Y-connected drive, since in this case, the voltage on the windings is almost multiplied by two for a given power. Nevertheless, the open-end winding structure allows also the circulation of an homopolar current [START_REF] Bodo | A Space Vector PWM With Common-Mode Voltage Elimination for Open-End Winding Five-Phase Drives With a Single DC Supply[END_REF].

The homopolar currents are the common mode components that generate a pulsaing torque (null average torque), generating mostly copper losses. Supplying the machine with a null homopolar voltage does not ensure that the homopolar current is null. Low frequency homopolar current components can be generated by the rotor saliency of a permanent magnet rotor. In this case, the homopolar frequency currents (which order is a multiple of the number of phases) are coupled to the fundamental frequency current, the one that is controlled for torque generation. A high-frequency homopolar current component is also mostly generated by the non-linearity of the inverter. This shows why an homopolar current component is usually obtained at the switching frequency, even if its value is not a multiple of the number of phases [START_REF] Zhan | Analysis and Suppression of Zero Sequence Circulating Current in Open Winding PMSM Drives With Common DC Bus[END_REF].

The high-frequency homopolar current might generate more losses per Ampere due to the skin and proximity effects [START_REF] Iwasaki | Influence of PWM on the proximity loss in permanent magnet brushless AC machines[END_REF] respectively proportional to the frequency or its square. In an experimental set-up with a five-phase Permanent Magnet Synchronous Machine (PMSM) equipped with temperature sensors, the authors have verified that with different PWM modulation strategies, the winding temperatures can be, for a given torque and speed, multiplied by two in comparison with classical star coupling. This is the reason why this study compares different modulation strategies aiming to reduce the high frequency homopolar current. Thereafter, the copper losses for each modulation strategy are calculated using a finite element model allowing to take into account skin and proximity effects and then compared to a reference star-connected PMSM in which the homopolar current is null.

Section 3 presents the multiphase system under investigation. Section strategies which are analyzed. Section 5 presents the simulation results with a comparative analysis of the investigated PWM strategies based on the obtained results of the finite element losses analysis.

III. SYSTEM AND CONTROL'S DESCRIPTION

The considered topology in this study is shown in Fig. 2. It consists of two five-leg inverters VSI1 and VSI2, single DC voltage source and a five-phase open-end windings PMSM. The machine parameters are given in Table 1. The performance analysis is achieved in comparison to the reference topology using a five-phase star-connected machine, as depicted in Fig. 3.

The multiple reference frame concept has been successfully applied to the multiphase drives to deduce a simple control scheme [START_REF] Kestelyn | A vectorial approach for generation of optimal current references for multiphase permanent-magnet synchronous machines in real time[END_REF]. Based on this representation, it is possible to consider the five-phase PMSM as a set of two fictitious magnetically independent two-phase machines (main machine (MM) and secondary (SM)) and one fictitious homopolar one-phase machine (HM). Each equivalent fictitious machine (respectively, MM, SM and HM) is α-β frame, x-y frame and h frame). These frames are obtained by applying the linear Concordia transformation given in [START_REF] Burkhardt | Design and analysis of a highly integrated 9-phase drivetrain for EV applications[END_REF].

For the system under study, it is assumed that the electromagnetic torque is produced only by the low order harmonic components (1 st and 3 th harmonics). Consequently, the α-β current components are supposed to be sinusoidal. On the contrary, the x-y current components are supposed also to the contrary, the x-y current components are supposed also to exist since they can contribute for the torque production in the five-phase PMSM, when the back electromotive forces (Back-EMF) are not sinusoïdal. Taking this into account, those two bi-dimensionnal subspaces are independently controlled by PI controllers, as shown in the control scheme of Fig. 1.

The homopolar current component ih cannot generate a constant non-null torque. Because of that, this frame will be supplied by a null voltage reference. In practice, this does not ensure that the homopolar current is always null. As mentioned in the introductionrotor saliency and inverter's non-linearity can generate low and high frequency homopolar currents. Homopolar component would be null if there were two isolated electric sources supplying each inverter. However, industrial applications may impose only one electric source because of cost or technical issues due to the isolation of the two electric sources.

IV. INVESTIGATED MODULATION STRATEGIES

For the open-end wind five-phase PMSM under study, four modulation strategies were chosen to be analyzed. Three of them are classified as intersection modulation strategy in which the PWM signal is generated by comparing a reference voltage to a triangle carrier signal at switching frequency. The fourth strategy is a space vector PWM (SVPWM) strategy in which a combination of 8 voltage vectors is chosen to generate the PWM signals at each switching period, as it is explained further in this section.

A voltage vector is composed by the instantaneous voltage of the machine phase. As the studied system is a 5-phase open-end winding machine, this vector has 5 dimensions and each phase can be supplied by Those voltages depend on the state of the two inverter legs that supply the same phase. For an example, to supply motor phase a with +VDC the transistors T1 and T16 must be closed.

                C (1)
In order to supply a phase with 0V either upper transistors or bottom transistors of the two inverter legs supplying the same phase must be closed. In conclusion, 243 (3 5 ) voltage vectors are possible.

A. Two-level PWM strategy

The principle of this strategy is given in Fig. 4. It consists in giving inversed PWM signals to two inverter legs supplying the same phase. In this case, the phase voltages will be either

DC V  or DC V 
, reducing to 32 ( 52 ) the possible voltage reference vectors. Using the Concordia Transformation, it is possible to see that all 32 vectors have a non-null projection on the homopolar frame .

B. Three-level PWM simple modulation strategy

In comparison to the 2-level strategy, this one uses two triangle carrier signals, one for the positive voltage values and another to the negative values (Fig. 5). It reduces by almost half the number of commutations, which also generate losses in the inverter, but this aspect is not analyzed in this paper. Furthermore, all 243 vectors are used in this modulation strategy. The advantage of this strategy is the fact of using voltage vectors which the homopolar voltage is low or even null and also vectors which value is closer to the referencevoltage vectors one. For example, if the reference vector is [0.1 -0.5 0.9 -0.7 0.3] VDC , a combination of the vectors as [0 -1 1 -1 0]VDC and others can be used in order to obtained reference voltages.

C. Three-level PWM double modulation strategy

This strategy is similar to the previous one. There are also two triangle carrier signals, the first one is the same of the 2level PWM and the second is its mirror (Fig. 6). As the 3level PWM simple modulation strategy, all 243 vectors are used. But, there are as many commutations as the 2-level PWM strategy.

D. Eight-vector Z-SVPWM strategy

The 8-vector Z-SVPWM strategy (Fig. 7) is the most complex one since it involves only some specific vector of the possible 243 ones to supply the machine. Many criterions can be used to select the vectors that will be implemented. In this study, as the homopolar current is the main issue, the select vectors are the ones which the homopolar projection is null. 51 vectors correspond to this criterion. By only using these vectors, the homopolar current is theorically null.

Analyzing the select vectors in the α-β frame, it is possible to see that 10 vectors ( l V ) have the highest amplitude (1,94 DC V ), allowing to supply the phases with a higher voltage. However, those 10 vectors have a non-null projection on x-y frame. This might generate a torque ripples, because the third harmonic of the Back-EMF is not null. That is why 10 other vectors ( s V ) will be also used in order to compensate the voltage projection on x-y frame.

Being chosen the 20 vectors that will be used to supply the machine, the modulation strategy will work as follows: with the voltage reference projection on the main subspaces the four closest vectors will be used to generate reference vector projection. Then every vector will have its own activation duration

2 2 1 1   j s s s l l s s s l l j ref e T V T V T T V T V T e V     (2)
In order to compensate the projection of the vectors on x-y frame, the relation of the equation ( 3) must be respected. This is made for the four vectors that will generate the voltage reference on the α-β frame. With the same principle, four other vectors will be chosen to generate the voltage reference on the x-y frame, totalizing thus eight vectors as indicated in the strategy name.

For every commutation period the activation durations of all eight vectors must be recalculated.

V. CO-SIMULATION RESULTS AND COMPARISON

This section presents a summary of the main cosimulation results conducted on the finite elements (FE) cosimulation software presented in Fig. 1. The simulation software has been set up by using Matlab/SimuLink. Regardless the used modulation technique, the motor-inverter set has been modeled with a toolbox model of the power switches and of the by-pass diodes with data from the supplier. A dead time of 1 µs has been introduced to prevent supplier. All tests have been carried out in permanent operating conditions.

The obtained motor phase currents derived from Matlab/SimuLink have been then used to fed a FE model (ANSYS Maxwell 2D) of the five-phase machine, generating thus the losses density map of the machine. The parameters of the five-phase PMSM are given in Table. I.

A. Machine control simulation

Simulations are carried out for every modulation strategy for a 1000 rpm as rotation speed. The delivered torque is 20 N.m and the resulting power is 2.1 kW . The fundemental frequency is of 116 Hz and the third harmonic of 350 Hz. The results are depicted on Fig. 8 to Fig. 13. As annouced above, the aim of this work is to apply a modulation technique for the five-phase PMSM giving the same harmonic components as those obtained for a star-connected PMSM, as depicted in Fig. 8.

Considering open-end windings configuration, for each modulation strategy, high frequency components (at switching frequency) are visible on the motor phase currents but the highest values are obtained for a 2-level PWM strategy, as illustrated in Fig. 9. These results are in accordance with previous addressed works in this subject. In fact, the harmonic content of the current presents high frequency components at the switching frequency (10kHz) with an amplitude of 14% compared to the fondamental current amplitude.

Regarding the two 3-level strategies (simple or double modulation), the double modulation has the lowest highfrequency components. Moreover, the double modulation induces high-frequency components at the double of the PWM switching frequency.

Even if the Z-SVPWM has theorically the best performance regarding high frequency homopolar components supression, it is not what is obtained in simulation with an almost perfect VSI. This happens mostly because of the low activation duration of the vectors controlling the current in the x-y frame and the transistors dead-time. As a consequence, some low-frequency harmonics appear. By analyzing the time-domain waveforms of the homopolar currents (see Fig. 13) for each modulation strategy, the observations above are confirmed. The 2-level PWM strategy is the one presenting the highest value of the homoplar current compoenent at switching frequency. However, the next analysis will verify if the two 3-level PWM strategies are already effective enough on heat dissipation reduction. It should be highlighed that the temperatures experimentaly obtained in the different windings with both 3-level PWM strategies are of the same order as the ones obtained with a star connection topology.

B. Finite Model co-simulation

The obtained currents from simulation stage are introduced to the FE model using ANSYS Maxwell software.

As the low-frequency harmonic components have really low impact on skin and proximity effects [START_REF] Młot | Analysis of the proximity and skin effects on copper loss in a stator core[END_REF]- [START_REF] Thomas | Proximity loss study in high speed flux -switching permanent magnet machine[END_REF] in the motor phase windings, their RMS values are used instead. The FE simulation is achieved over two PWM periods. The obtained results regarding the copper losses cartographies are illustrated on Fig. 14 to Fig. 19. The average copper losses in all windings of the five-phase PMSM are depicted in Table .  II.

From the obtained results, as expected, the high frequency homopolar current components result in a copper losses increase of almost 50% in the case of the 2level PWM strategy applied in comparison to the starconnected PMSM considered as a reference basis. The two other strategies (3-level simple modulation PWM and Z-SVPWM) have similar behavior concerning the copper losses, which are about 27 % higher than those obtained with the star-connected PMSM, as summarized in Table .  II. On the contrary, copper losses obtained for the 3-level double modulation PWM is similar to the ones obtained with the star connected five-phase PMSM.

Regarding the efficiency, the 3-level simple modulation PWM and the Z-SVPWM have the same efficiency (96.7%) since they have the same level of copper losses as observed in Table II. The 3-level double modulation has the higher efficiency (97.2%) since the copper losses are the lowest. On the contrary, the 2-level PWM strategy has the worst efficiency (96%) among the studied strategies, since the significant level of losses in windings. Beyond this, there are other particular effects that must be taken into account for analysis like as the skin and proximity effects. As expected by the FE model, the results illustrated in Fig. 14 to Fig. 18 allow the visualization of high copper losses (almost 6 times more) located at the coils conductors close to the rotor. Consequently, this can result in hotspots formation in such conductors. In Fig. 19, the normalized copper losses in some rotor-side conductors in the coils are given for the four PWM strategies. It is observed that are the most impacted by the proximity effect and have the majority of contribution in the overall copper losses. In future works, the thermal behavior of the five-phase PMSM for each strategy will be investigated, in order to prove the variability of the given conclusions here.

VI. CONCLUSION

If open-end windings machines are attractive for integrated drives, it appears that important losses due to high frequency homopolar current components can be induced. In this paper, different modulation strategies are compared in order to reduce the copper losses. The 2-level PWM strategy is the one presenting the highest dissipation among all strategies. In order to simplify the modulation, this strategy reduces the number of voltage vectors supplying the machine without taking into account the homopolar current generation. The

Fig. 2 .

 2 Fig. 2. Configuration of the open-end winding five-phase PMSM topology supplied by two 5-leg inverters and a single dc voltage source.

Fig. 3 .

 3 Fig. 3. Configuration of star-connected 5-phase PMSM topology.

Fig. 1 .

 1 Fig. 1. Control and co-simulation scheme.

Fig. 4 .

 4 Fig. 4. 2-level PWM Strategy

  the equation (2):

5

 5

Fig. 8 .

 8 Fig. 8. Obtained current of phase A and its reference, with the current harmonics spectrum for star-connected 5-phase PMSM.

Fig. 9 .

 9 Fig. 9. Obtained current of phase A and its reference, with the current harmonics spectrum for 2-level PWM.

Fig. 10 .

 10 Fig. 10. Obtained current of phase A and its reference, with the current harmonics spectrum for 3-level simple modulation.

Fig. 11 .

 11 Fig. 11. Obtained current of phase A and its reference, with the current harmonics spectrum for 3-level double modulation.

Fig. 12 .

 12 Fig. 12. Obtained current of phase A and its reference, with the current harmonics spectrum for 8-vector Z-SVPWM.

Fig. 13 .

 13 Fig. 13. Homopolar current obtained for each modulation strategy.

Fig. 14 .

 14 Fig. 14. Copper losses cartography for the star-connected configuration.

Fig. 15 .

 15 Fig. 15. Copper losses cartography for 2-level PWM strategy.

Fig. 16 .

 16 Fig. 16. Copper losses cartography for 3-level simple modulation PWM strategy.

Fig. 17 .

 17 Fig. 17. Copper losses cartography for 3-level double modulation PWM strategy.

Fig. 18 .

 18 Fig. 18. Copper losses cartography for Z-SVPWM strategy.

TABLE I PARAMETERS

 I OF THE USED FIVE-PHASE MACHINE

	Technical data	Sinusoidal PMSM
	Resistance R (Ω)	0.0011
	Inductance Lp (µH)	118.5
	Inductance LS (µH)	51.4
	Inductance Lh (µH)	110
	Number of pole pairs p	7
	Fundamental harmonic E1 at 1rd/s (V)	0.1358
	Third harmonic amplitude in (%) of E1	10 %
	five harmonic amplitude in (%) of E1	1.1 %

TABLE . II

 . AVERAGE COPPER LOSSS PER TOPOLOGY AND PER MODULATION STRATEGY FOR THE FIVE-PHASE PMSM other three strategies present similar results with copper losses very similar to the ones obtained for a star-connected machine. The lowest homopolar current is obtained when the 3-level PWM with double modulation is applied. The double modulation generates harmonics on a frequency that is the double of the commutation frequency of each transistor. Even though the Z-SVPWM strategy theoretically eliminates the homopolar current, in practice this strategy is very sensitive to effects as the transistor's dead-time, for example. Consequently, low and high frequency harmonics might appear increasing then the copper loss VII. ACKNOWLEDGMENT This work has been achieved within the framework of CE2I project. CE2I is co-financed by European Union with the financial support of European Regional Development Fund (ERDF), French State and the French Region of Hautsde-France.

	Topology	Modulation	Total copper	Motor
		Strategy	losses (PU)	efficiency(%)
	Star-connected		1.0	97.2
		2-level PWM	≈1.5	96
		3-level PWM
		simple	≈1.27	96.7
		modulation
	Open-end winding	3-level PWM
		double	≈1.0	97.2
		modulation
		8-vector Z-SVPWM	≈1.27	96.7

VIII. REFERENCES

 This work has been achieved within the framework of CE2I project. CE2I is co-financed by European Union with the financial support of European Regional Development Fund (ERDF), French State and the French Region of Hauts-de-France.


Damien Imbs
email: damien.imbs@lif.univ-mrs.fr

Achour Mostéfaoui
email: achour.mostefaoui@univ-nantes.fr

Matthieu Perrin
email: matthieu.perrin@univ-nantes.fr

Michel Raynal
email: raynal@irisa.fr

Set-Constrained Delivery Broadcast: Definition, Abstraction Power, and Computability Limits

Keywords: CCS Concepts C.2.4 [Computer-Communication Network]: Distributed Systems -distributed applications, network operating systems, D.4.1 [Operating Systems] -concurrency, D.4.5 [Operating Systems] Reliability, -fault-tolerance, F.1.1 [Computation by Abstract Devices]: Models of Computation -Computability theory Algorithms, Reliability, Theory Abstraction, Asynchronous system, Communication abstraction, Conflict-free replicated data type, Design simplicity, Distributed task, Linearizability, Message-passing system, Process crash, Read/write atomic register, Snapshot object

This paper introduces a new communication abstraction, called

Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an asynchronous message-passing system prone to process crash failures. This abstraction allows each process to broadcast messages and deliver a sequence of sets of messages in such a way that, if a process delivers a set of messages including a message m and later delivers a set of messages including a message m ′ , no process delivers first a set of messages including m ′ and later a set of message including m.

After having presented an algorithm implementing SCDbroadcast, the paper investigates its programming power and its computability limits. On the "power" side it presents SCD-broadcastbased algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data), and distributed tasks. On the "computability limits" side it shows that SCD-broadcast and read/write registers are computationally equivalent.

INTRODUCTION

Programming abstractions. Informatics is a science of abstractions, and a main difficulty consists in providing users with a "desired level of abstraction and generality -one that is broad enough to encompass interesting new situations, yet specific enough to address the crucial issues" as expressed in [START_REF] Fischer | Appraising two decades of distributed computing theory research[END_REF]. When considering sequential computing, functional programming and object-oriented programming are well-know examples of what means "desired level of abstraction and generality".

In the context of asynchronous distributed systems where the computing entities (processes) communicate -at the basic level-by sending and receiving messages through an underlying communication network, and where some of them can experience failures, a main issue consists in finding appropriate communication-oriented abstractions, where the meaning of the term "appropriate" is related to the problems we intend to solve. Solving a problem at the send/receive abstraction level is similar to the writing of a program in a low-level programming language. Programmers must be provided with abstractions that allow them to concentrate on the problem they solve and not on the specific features of the underlying system. This is not new. Since a long time, high level programming languages have proved the benefit of this approach. From a synchronization point of view, this approach is the one promoted in software transactional memory [START_REF] Shavit | Software transactional memory[END_REF], whose aims is to allow programmers to focus on the synchronization needed to solve their problems and not on the way this synchronization must be implemented (see the textbooks [START_REF] Herlihy | The Art of Multiprocessor Programming[END_REF][START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF]).

If we consider specific coordination/cooperation problems, "matchings" between problems and specific communication abstractions are known. One of the most famous examples concerns the consensus problem whose solution rests on the total order broadcast abstraction 1 . Another "matching" example is the causal message delivery broadcast abstraction [START_REF] Birman | Reliable communication in the presence of failures[END_REF][START_REF] Raynal | The causal ordering abstraction and a simple way to implement it[END_REF], which allows for a very simple implementation of a causal read/write memory [START_REF] Ahamad | Causal memory: definitions, implementation and programming[END_REF].

Aim of the paper. The aim of this paper is to introduce and investigate a high level communication abstraction which allows for simple and efficient implementations of concurrent objects and distributed tasks, in the context of asynchronous messagepassing systems prone to process crash failures. The concurrent objects in which we are interested are defined by a sequential specification [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF] (e.g., a queue). Differently, a task extends to the distributed context the notion of a function [START_REF] Biran | A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor[END_REF][START_REF] Moran | Extended impossibility results for asynchronous complete networks[END_REF]. It is defined by a mapping from a set of input vectors to a set of output vectors, whose sizes are the number of processes. An input vector I defines the input value I [i] of each process p i , and, similarly, an output vector O defines the output O[j] of each process p j . Agreement problems such as consensus and k-set agreement are distributed tasks. What makes the implementation of a task difficult is the fact that each process knows only its input, and, due to net effect of asynchrony and process failures, no process can distinguish if another process is very slow or crashed. The difficulty results in an impossibility for consensus [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF], even in a system in which at most one process may crash.

Content of the paper: a broadcast abstraction. The SCDbroadcast communication abstraction proposed in the paper allows a process to broadcast messages, and to deliver sets of messages (instead of a single message) in such a way that, if a process p i delivers a message set mset containing a message m, and later delivers a message set mset ′ containing a message m ′ , then no process p j can deliver first a set containing m ′ and later another set containing m. Let us notice that p j is not prevented from delivering m and m ′ in the same set. Moreover, SCD-broadcast imposes no constraint on the order in which a process must process the messages it receives in a given message set.

After having defined SCD-broadcast, the paper presents an implementation of it in asynchronous systems where a minority of processes may crash. This assumption is actually a necessary and sufficient condition to cope with the net effect of asynchrony and process failures (see below). Assuming an upper bound ∆ on message transfer delays, and zero processing time, an invocation of SCD-broadcast is upper bounded by 2∆ time units, and O(n 2 ) protocol messages (messages generated by the implementation algorithm).

Content of the paper: implementing objects and tasks. Then, the paper addresses two fundamental issues of SCDbroadcast: its abstraction power and its computability limits. As far as its abstraction power is concerned, i.e., its ability and easiness to implement atomic (linearizable) or sequentially consistent concurrent objects [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF][START_REF] Lamport | On interprocess communication, Part I: basic formalism[END_REF] and read/write solvable distributed tasks, the paper presents, on the one side, two algorithms implementing atomic objects (namely a snapshot object [START_REF] Afek | Atomic snapshots of shared memory[END_REF][START_REF] Anderson | Multi-writer composite registers[END_REF], and a distributed increasing/decreasing counter), and, on the other side, an algorithm solving the lattice agreement task [START_REF] Attiya | Atomic snapshots using lattice agreement[END_REF][START_REF] Faleiro | Generalized lattice agreement[END_REF].

The two concurrent objects (snapshot and counter) have been chosen because they are encountered in many applications, and are also good representative of the class of objects identified in [START_REF] Aspnes | Wait-free data structures in the asynchronous PRAM model[END_REF]. The objects of this class are characterized by the fact that each pair op1 and op2 of their operations either commute (i.e., in any state, executing op1 before op2 leads to the same state as executing op2 before op1, as it is the case for a counter), or any of op1 and op2 can overwrite the other one (e.g., executing op1 before op2 leads to the same state as executing op2 alone). Our implementation of a counter can be adapted for all objects with commutative operations, and our implementation of the snapshot object illustrates how overwriting operations can be obtained directly from the SCD-broadcast abstraction. Concerning these objects, it is also shown that a slight change in the algorithms allows us to obtain implementations (with a smaller cost) in which the consistency condition is weakened from linearizability to sequential consistency [START_REF] Lamport | How to make a multiprocessor computer that correctly executes multiprocess programs[END_REF].

In the case of read/write solvable tasks, SCD-broadcast shows how the concurrency inherent (but hidden) in a task definition can be easily mastered and solved.

Content of the paper: the computability limits of SCDbroadcast. The paper also investigates the computability power of the SCD-broadcast abstraction, namely it shows that SCD-broadcast and atomic read/write registers (or equivalently snapshot objects) have the same computability power in asynchronous systems prone to process crash failures. Everything that can be implemented with atomic read/write registers can be implemented with SCDbroadcast, and vice versa.

As read/write registers (or snapshot objects) can be implemented in asynchronous message-passing system where only a minority of processes may crash [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF], it follows that the proposed algorithm implementing SCD-broadcast is resilience-optimal in these systems. From a theoretical point of view, this means that the consensus number of SCD-broadcast is 1 (the weakest possible).

Roadmap. The paper is composed of 8 sections. Section 2 defines the SCD-broadcast abstraction. Section 3 presents a resilienceoptimal algorithm implementing SCD-broadcast in asynchronous message-passing systems prone to process crash failures, while Then, Sections 4-6 present SCD-broadcast-based algorithms for concurrent objects and tasks. Section 7 focuses on the computability limits of SCD-broadcast. Finally, Section 8 concludes the paper. Due to page limitations, proofs are not given in the article, but they can be found in [START_REF] Imbs | Set-Constrained Delivery Broadcast: Definition, Abstraction Power, and Computability Limits[END_REF].

THE SCD-BROADCAST COMMUNICATION ABSTRACTION

Process model. The computing model is composed of a set of n asynchronous sequential processes, denoted p 1 , ..., p n . "Asynchronous" means that each process proceeds at its own speed, which can be arbitrary and always remains unknown to the other processes. A process may halt prematurely (crash failure), but it executes its local algorithm correctly until it crashes (if it ever does). The model parameter t denotes the maximal number of processes that may crash in a run r . A process that crashes in a run is said to be faulty in r . Otherwise, it is non-faulty.

Definition of SCD-broadcast. The set-constrained delivery broadcast abstraction (SCD-broadcast) provides the processes with an operation scd_broadcast(m) that takes a message m to broadcast as parameter, and triggers the event scd_deliver(mset) that provides the process on which it was triggered with a non-empty set of messages mset. Using a classical terminology, when a process invokes the operation scd_broadcast(m), we say that it "scd-broadcasts a message m". Similarly, when the event scd_deliver(mset) is triggered on this process, we say that it "scd-delivers the set of messages mset". By a slight abuse of language, when we are interested in a message m, we say that a process "scd-delivers the message m" when actually it scd-delivers the message set mset containing m. SCD-broadcast is defined by the following set of properties, where we assume -without loss of generality-that all the messages that are scd-broadcast are different. 2 • Validity. If a process scd-delivers a set containing a message m, then m was scd-broadcast by a process. • Integrity. A message is scd-delivered at most once by each process. • MS-Ordering. Let p i be a process that scd-delivers first a message set mset i and later a message set mset ′ i . For any pair of messages m ∈ mset i and m ′ ∈ mset ′ i , no process p j scd-delivers first a message set mset ′ j containing m ′ and later a message set mset j containing m.

• Termination-1. If a non-faulty process scd-broadcasts a message m, it terminates its scd-broadcast invocation and scddelivers a message set containing m. • Termination-2. If a process scd-delivers a message m, every non-faulty process scd-delivers a message set containing m.

Termination-1 and Termination-2 are classical liveness properties (found for example in Uniform Reliable Broadcast [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Raynal | Communication and agreement abstractions for fault-tolerant asynchronous distributed systems[END_REF]). The other ones are safety properties. Validity and Integrity are classical communication-related properties. The first states that there is neither message creation nor message corruption, while the second states that there is no message duplication.

The MS-Ordering property is new, and characterizes SCDbroadcast. It states that the contents of the sets of messages scddelivered at any two processes are not totally independent: the sequence of sets scd-delivered at a process p i and the sequence of sets scd-delivered at a process p j must be mutually consistent in the sense that a process p i cannot scd-deliver first m ∈ mset i and later m ′ ∈ mset ′ i mset i , while another process p j scd-delivers first m ′ ∈ mset ′ j and later m ∈ mset j mset ′ j . Let us nevertheless observe that if p i scd-delivers first m ∈ mset i and later m ′ ∈ mset ′ i , p j may scd-deliver m and m ′ in the same set of messages.

Let us remark that, if the MS-Ordering property is suppressed and messages are scd-delivered one at a time, SCD-broadcast boils down to the well-known Uniform Reliable Broadcast abstraction [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF][START_REF] Raynal | Communication and agreement abstractions for fault-tolerant asynchronous distributed systems[END_REF]. Differently, if all message sets contain exactly one message, SCD-broadcast is equivalent to the Atomic Broadcast abstraction.

An example. Let m 1 , m 2 , m 3 , m 4 , m 5 , m 6 , m 7 and m 8 be messages that have been scd-broadcast by different processes. The following scd-deliveries of message sets by p 1 , p 2 and p 3 respect the definition of SCD-broadcast:

• at p 1 : {m 1 , m 2 }, {m 3 , m 4 , m 5 }, {m 6 }, {m 7 , m 8 }. • at p 2 : {m 1 }, {m 2 , m 3 }, {m 4 , m 5 , m 6 }, {m 7 }, {m 8 }. • at p 3 : {m 1 , m 2 , m 3 }, {m 4 , m 5 }, {m 6 , m 7 }, {m 8 }.
Differently, due to the scd-deliveries of the sets including m 2 and m 3 , the following scd-deliveries by p 1 and p 2 do not satisfy the MS-broadcast property:

• at p 1 : {m 1 , m 2 }, {m 3 , m 4 , m 5 }, ... • at p 2 : {m 1 , m 3 }, {m 2 }, ... 2
The unicity of messages is not restrictive in practice, as one can assume the broadcast operation tags messages with a unique identifer. This way, messages can be unique even if their applicative content is not.

A containment property. Let mset ℓ i be the ℓ-th message set scd-delivered by p i . Hence, at some time, p i scd-delivered the sequence of message sets mset 1 i , . . . ,

mset x i . Let MSet x i = mset 1 i ∪ . . . ∪ mset x i .
The following Containment property follows directly from the MS-Ordering and Termination-2 properties: ∀ i, j, x, y:

(MSet x i ⊆ MSet y j ) ∨ (MSet y j ⊆ MSet x i ).
Partial order on messages created by the message sets. The MS-Ordering and Integrity properties establish a partial order on the set of all the messages, defined as follows. Let → i be the local message delivery order at process p i defined as follows: m → i m ′ if p i scd-delivers the message set containing m before the message set containing m ′ . As no message is scd-delivered twice, it is easy to see that → i is a partial order (locally know by p i ). The containment property implies that there is a total order (which remains unknown to the processes) on the whole set of messages, that complies with the partial order →= ∪ 1≤i ≤n → i . This is where SCD-broadcast can be seen as a weakening of total order broadcast.

IMPLEMENTATION OF SCD-BROADCAST

This section shows that the SCD-broadcast communication abstraction is not an oracle-like object (oracles allow us to extend our understanding of computing, but cannot be implemented). It describes an implementation of SCD-broadcast in an asynchronous send/receive message-passing system in which any minority of processes may crash. This system model is denoted CAMP n,t [t < n/2] (where CAMP n,t stands for "Crash Asynchronous Message-Passing" and t < n/2 is its restriction on failures). As t < n/2 is the weakest assumption on process failures that allows a read/write register to be built on top of an asynchronous message-passing system [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF] 3 , and SCD-broadcast and read/write registers are computationally equivalent (as shown in Sections 4 and 7), the proposed implementation is optimal from a resilience point of view.

Underlying communication network

Send/receive asynchronous network. Each pair of processes communicate through two uni-directional channels on which they send and receive messages. Hence, the communication network is a complete network: any process p i can directly send a message to any process p j (including itself). A process p i invokes the operation "send type(m) to p j " to send to p j the message m, whose type is type. The operation "receive type() from p j " allows p i to receive from p j a message whose type is type. Each channel is reliable (no loss, corruption, nor creation of messages), not necessarily FIFO, and asynchronous (while the transit time of each message is finite, there is no upper bound on message transit times). Let us notice that, due to process and message asynchrony, no process can know if another process crashed or is only very slow.

Uniform FIFO-broadcast abstraction. To simplify the presentation, and without loss of generality, we consider that the system is equipped with a FIFO-broadcast abstraction. Such an abstraction can be built on top of the previous basic system model without enriching it with additional assumptions (see e.g. [START_REF] Raynal | Communication and agreement abstractions for fault-tolerant asynchronous distributed systems[END_REF]). It is defined by the operations fifo_broadcast() and fifo_deliver(), which satisfy the properties of Uniform Reliable Broadcast (Validity, Integrity, Termination 1, and Termination 2), plus the following message ordering property.

• FIFO-Order. For any pair of processes p i and p j , if p i fifodelivers first a message m and later a message m ′ , both from p j , no process fifo-delivers m ′ before m.

Algorithm

This section describes Algorithm Then, qdplt .cl[x] will contain the sequence number associated with m by p x when it broadcast the message forward_msg(msд.m, -, -, -, -). This last field is crucial in the scd-delivery by the process p i of a message set containing m.

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

• buffer i : buffer (init. empty) where are stored quadruplets containing messages that have been fifo-delivered but not yet scd-delivered in a message set. • to_deliver i : set of quadruplets containing messages to be scd-delivered. • sn i : local logical clock (initialized to 0), which increases by step 1 and measures the local progress of p i . Each application message scd-broadcast by p i is identified by a pair ⟨i, sn⟩, where sn is the current value of sn i .

• clock i [1.
.n]: array of logical dates; clock i [j] is the greatest date x such that the application message m identified ⟨x, j⟩ has been scd-delivered by p i .

Protocol message. The algorithm uses a single type of protocol message denoted forward_msg(m, sd, sn, f , sn f ). Such a message is made up of five fields: the first field is an associated application message m, the second and third form a pair ⟨sd, sn⟩ that is the identity of the application message and the fourth and fifth form a pair ⟨f , sn f ⟩ that describes the local progress (as captured by sn f ) of the forwarder process p f when it forwarded this protocol message to the other processes by invoking fifo_broadcast forward_msg(m, sd, sn sd , f , sn f ) (line 11).

Operation scd_broadcast(). When p i invokes the operation scd_broadcast(m), where m is an application message, it sends the protocol message forward_msg(m, i, sn i , i, sn i ) to itself (this simplifies the writing of the algorithm), and waits until it has no more message from itself pending in buffer i , which means it has scddelivered a set containing m (lines 19 and 20).

Uniform fifo-broadcast of a message forward_msg. When a process p i fifo-delivers a protocol message forward_msg(m, sd, sn sd , f , sn f ), it first invokes the internal operation forward(m, sd, sn sd , f , sn f ). In addition to other statements, the first fifo-delivery of such a message by a process p i entails its participation in the uniform reliable fifo-broadcast of this message (lines 5 and 11). In addition to the invocation of forward(), the fifo-delivery of forward_msg() invokes also try_deliver(), which strives to scd-deliver a message set (lines 4).

The core of the algorithm. Expressed with the relations → i , 1 ≤ i ≤ n, introduced in Section 2, the main issue of the algorithm is to ensure that, if there are two message m and m ′ and a process p i such that m → i m ′ , then there is no p j such that m ′ → j m.

To this end, a process p i is allowed to scd-deliver a message m before a message m ′ only if it knows that a majority of processes p j have fifo-delivered a protocol message forward_msg(m, -, -, -, -) before a protocol message forward_msg(m ′ , -, -, -, -); p i knows it either (i) because it fifo-delivered from p j a message forward_msg(m, -, -, -, -) but not yet a message forward_msg(m ′ , -, -, -, -), or (ii) because it fifo-delivered from p j both forward_msg(m, -, -, -, snm) and forward_msg(m ′ , -, -, -, snm ′ ) and the sending date smn is smaller than the sending date snm ′ . The MS-Ordering property follows then from the impossibility that a majority of processes "sees m before m ′ ", while another majority "sees m ′ before m".

Internal operation forward(). This operation can be seen as an enrichment (with the fields f and sn f ) of the reliable fifo-broadcast implemented by the protocol messages forward_msg(m, sd, sn sd , -, -). Considering such a message forward_msg(m, sd, sn sd , f , sn f ), m was scd-broadcast by p sd at its local time sn sd , and relayed by the forwarding process p f at its local time sn f . If sn sd ≤ clock i [sd], p i has already scd-delivered a message set containing m (see lines 18 and 20). If sn sd > clock i [sd], there are two cases defined by the predicate of line 6.

• No quadruplet qdplt in buffer i is such that qdplt .msд = m.

In this case, p i creates a quadruplet associated with m, and adds it to buffer i (lines 8-10 Internal operation try_deliver(). When a process p i executes try_deliver(), it first computes the set to_deliver i of the quadruplets qdplt containing application messages m which have been seen by a majority of processes (line 15). From p i 's point of view, a message has been seen by a process p f if qdplt .cl[f ] has been set to a finite value (line 7).

As indicated in a previous paragraph, if a majority of processes received first a message forward_msg carrying m ′ and later another message forward_msg carrying m, it might be that some process p j scd-delivered a set containing m ′ before scd-delivering a set containing m. Therefore, p i must avoid scd-delivering a set containing m before scd-delivering a set containing m ′ . This is done at line 16, where p i withdraws the quadruplet qdplt corresponding to m if it can not deliver m ′ yet (i.e. the corresponding qdplt ′ is not in to_deliver i ) or it does not have the proof that the situation cannot happen, i.e. no majority of processes saw the message corresponding to qdplt before the message corresponding to qdplt ′ (this is captured by the predicate

|{ f : qdplt .cl[f ] < qdplt ′ .cl[f ]}| ≤ n 2 )
. If to_deliver i is not empty after it has been purged (lines 16-17), p i computes a message set to scd-deliver. This set mset contains all the application messages in the quadruplets of to_deliver i (line 20). These quadruplets are withdrawn from buffer i (line 18). Moreover, before this scd-delivery, p i needs to updates clock i [x] for all the entries such that x = qdplt .sd where qdplt ∈ to_deliver i (line 18). This update is needed to ensure that the future uses of the predicate of line 17 are correct. .m] of atomic read/write registers which provides the processes with two operations, denoted write(r , -) and snapshot(). The invocation of write(r , v), where 1 ≤ r ≤ m, by a process p i assigns atomically v to REG[r ]. The invocation of snapshot() returns the value of REG [1..m] as if it was executed instantaneously. Hence, in any execution of a snapshot object, its operations write() and snapshot() are linearizable.

The underlying atomic registers can be Single-Reader (SR) or Multi-Reader (MR) and Single-Writer (SR) or Multi-Writer (MW). We consider only SWMR and MWMR registers. If the registers are SWMR the snapshot is called SWMR snapshot (and we have then m = n). Moreover, we always have r = i, when p i invokes write(r , -). If the registers are MWMR, the snapshot object is called MWMR.

Implementations based on read/write registers. Implementations of both SWMR and MWMR snapshot objects on top of read/write atomic registers have been proposed (e.g., [START_REF] Afek | Atomic snapshots of shared memory[END_REF][START_REF] Anderson | Multi-writer composite registers[END_REF][START_REF] Imbs | Help when needed, but no more: efficient read/write partial snapshot[END_REF][START_REF] Inoue | Linear time snapshots using multi-writer multi-reader registers[END_REF]). The "hardness" to build snapshot objects in read/write systems and associated lower bounds are presented in the survey [START_REF]How hard is it to take a snapshot[END_REF]. The best algorithm known ( [START_REF] Attiya | Atomic snapshots in O (n log n) operations[END_REF]) to implement an SWMR snapshot requires O(n log n) read/write on the base SWMR registers for both write() operation snapshot() is (1) done i ← false; scd_broadcast sync(i); wait(done i );

(2) return(reg i [1..m]).

operation write(r, v) is (3) done i ← false; scd_broadcast sync(i); wait(done i ); (4) done i ← false; scd_broadcast write(r, v, ⟨tsa i [r ].dat e + 1, i ⟩); wait(done i ).

when the message set { write(r j 1 , v j 1 , ⟨dat e j 1 , j 1 ⟩), . . . , write(r jx , v jx , ⟨dat e jx , j x ⟩), sync(j x +1 ), . . . , sync(j y ) } is scd-delivered do (5) for each r such that write(r, -, -) ∈ scd-delivered message set do [START_REF] Attiya | Atomic snapshots using lattice agreement[END_REF] let ⟨dat e, wr it er ⟩ be the greatest timestamp in the messages write(r, -, -); [START_REF] Attiya | Atomic snapshots in O (n log n) operations[END_REF] if (tsa i [r ] < t s ⟨dat e, wr it er ⟩) [START_REF] Attiya | Sequential consistency versus linearizability[END_REF] then let v the value in write(r, -, ⟨dat e, wr it er ⟩); [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF] r eд i [r ] ← v; tsa i [r ] ← ⟨dat e, wr it er ⟩ [START_REF] Biran | A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor[END_REF] end if; (11) end for; [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]

if ∃ℓ : j ℓ = i then done i ← true end if.
Algorithm 2: Construction of an MWMR snapshot object CAMP n,t [SCD-broadcast] (code for p i ) and snapshot(). As far as MWMR snapshot objects are concerned, there are implementations where each operation has an O(n) cost 4 .

As far as the construction of an SWMR (or MWMR) snapshot object in crash-prone asynchronous message-passing systems where t < n/2 is concerned, it is possible to stack two constructions: first an algorithm implementing SWMR (or MWMR) atomic read/write registers (e.g., [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF])), and, on top of it, an algorithm implementing an SWMR (or MWMR) snapshot object. This stacking approach provides objects whose operation cost is O(n 2 log n) messages for SWMR snapshot, and O(n 2 ) messages for MWMR snapshot. An algorithm based on the same low level communication pattern as the one used in [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF], which builds an atomic SWMR snapshot object "directly" (i.e., without stacking algorithms) was recently presented in [START_REF] Delporte-Gallet | Implementing snapshot objects on top of crash-prone asynchronous messagepassing systems[END_REF] (the aim of this algorithm is to perform better than the stacking approach in concurrency-free executions).

An algorithm for atomic MWMR snapshot in CAMP n,t [SCD-broadcast]

Local representation of REG at a process p i . At each register p i , REG[1..m] is represented by three local variables reд i [1..m] (data part), plus tsa i [1..m] and done i (control part).

• done i is a Boolean variable.

• reg i [1..m] contains the current value of REG[1.
.m], as known by p i . Timestamp-based order relation. We consider the classical lexicographical total order relation on timestamps, denoted < t s . Let ts1 = ⟨h1, i1⟩ and ts2 = ⟨h2, i2⟩. We have ts1 < t s ts2 def = (h1 < h2) ∨ ((h1 = h2) ∧ (i1 < i2)). 4 Snapshot objects built in read/write models enriched with operations such as Com-pare&Swap, or LL/SC, have also been considered, e.g., [START_REF] Imbs | Help when needed, but no more: efficient read/write partial snapshot[END_REF][START_REF] Jayanti | An optimal multiwriter snapshot algorithm[END_REF]. Here we are interested in pure read/write models.

• tsa i [1..m]
Algorithm 2: snapshot operation. In this algorithm, a message sync(i) is scd-broadcast (line 1) and after reception of this message (line 12), the local value of reg i [1..m] is returned (line 2). The message sync(i) which is scd-broadcast is a pure synchronization message, whose aim is to entail the refreshment of the value of reg i [1..m] (lines 5-11) which occurs before the setting of done i to true (line 12). Algorithm 2: write operation. (Lines 3-4) When a process p i wants to assign a value v to REG[r ], it invokes REG.write(r , v). This operation starts by a re-synchronization, as in the snapshot operation, whose side effect is here to provide p i with an up-todate value of tsa i [r ].date (line 3). Then, p i associates the timestamp ⟨tsa i [r ].date + 1, i⟩ with v, and scd-broadcasts the data/control message write(r , v, ⟨tsa i [r ].date + 1, i⟩). In addition to informing the other processes on its write of REG[r ], this message write() acts as a re-synchronization message, exactly as a message sync(i). When this synchronization terminates (i.e., when the Boolean done i is set to true), p i returns from the write operation.

Algorithm 2: scd-delivery of a set of messages. When process p i scd-delivers a message set, namely, {write(r j 1 , v j 1 , ⟨date j 1 , j 1 ⟩), . . . , write(r j x , v j x , ⟨date j x , j x ⟩), sync(j x +1 ), . . . , sync(j y )} it first looks if there are messages write(). If it is the case, for each register REG[r ] for which there are messages write(r , -, -) (line 5), p i computes the maximal timestamp carried by these messages (line 6), and updates accordingly its local representation of REG[r ] (lines 7-10). Finally, if p i is the sender of one of these messages (write() or sync()), done i is set to true, which terminates p i 's re-synchronization (line 12). Time and Message costs. An invocation of snapshot() involves one invocation of scd_broadcast(), while an invocation of write() involves two. As scd_broadcast() costs O(n 2 ) protocol messages and 2∆ time units, snapshot() cost the same, and write() costs the double.

Theorem 2. Algorithm 2 builds an MWMR atomic snapshot object in the model CAMP n,t [SCD-broadcast]. The operation snapshot costs one SCD-broaddast, the write() operation costs two.

operation propose(in i ) is (1) done i ← false; scd_broadcast msg(i, in i ); wait(done i );

(2) return(lub(r ec i )).

when the message set { msg(j 1 , v j 1 ), . . . , msg(j x , v jx )} is scd-delivered do (3) r ec i ← r ec i ∪ {v j 1 , . . . , v jx }; (4) if ∃ℓ : j ℓ = i then done i ← true end if.

Algorithm 5: Solving Lattice Agreement in CAMP n,t [SCD-broadcast] (code for p i ) to its local copy of the counter for its invocation of read() terminates (this is the rule known under the name "read your writes").

Algorithm 4 is the resulting algorithm. In addition to counter i , each process manages a synchronization counter lsc i initialized to 0, which counts the number of increase() and decrease() executed by p i and not yet locally applied to counter i . Only when lsc i is equal to 0, p i is allowed to read counter i .

The cost of an operation increase() and decrease() is 0 time units plus the O(n 2 ) protocol messages of the underlying SCD-broadcast. The time cost of the operation read() by a process p i depends on the value of lsc i . It is 0 when p i has no "pending" counter operations.

Remark As in [START_REF] Attiya | Sequential consistency versus linearizability[END_REF], using the same technique, it is possible to design a sequentially consistent counter in which the operation read() is fast, while the operations increase() and decrease() are not.

SCD-BROADCAST IN ACTION (ITS POWER): LATTICE AGREEMENT TASK

Definition. Let S be a partially ordered set, and ≤ its partial order relation. Given S ′ ⊆ S, an upper bound of S ′ is an element x of S such that ∀ y ∈ S ′ : y ≤ x. The least upper bound of S ′ is an upper bound z of S ′ such that, for all upper bounds y of S ′ , z ≤ y. S is called a semilattice if all its finite subsets have a least upper bound. Let lub(S ′ ) denotes the least upper bound of S ′ . Let us assume that each process p i has an input value in i that is an element of a semilattice S. The lattice agreement task was introduced in [START_REF] Attiya | Atomic snapshots using lattice agreement[END_REF] and generalized in [START_REF] Faleiro | Generalized lattice agreement[END_REF]. It provides each process with an operation denoted propose(), such that a process p i invokes propose(in i ) (we say that p i proposes in i ); this operation returns an element z ∈ S (we say that it decides z). The task is defined by the following properties, where it is assumed that each non-faulty process invokes propose().

• Validity. If process p i decides out i , we have in i ≤ out i ≤ lub({in 1 , . . . , in n }). • Containment. If p i decides out i and p j decides out j , we have out i ≤ out j or out j ≤ out j . • Termination. If a non-faulty proposes a value, it decides a value. Algorithm. Algorithm 5 implements the lattice agreement task. It is a very simple algorithm, which scd-broadcasts one message and waits for its local rception. The text of the algorithm is selfexplanatory. Theorem 4. Algorithm 5 solves lattice agreement.

Remark 1. SCD-broadcast can be built on top of read/write registers (see below Theorem 5). It follows that the combination of Algorithm 5 and Algorithm 6 provides us with a pure read/write algorithm solving the lattice agreement task. As far as we know, this is the first algorithm solving lattice agreement, based only on read/write registers.

Remark 2. Similarly to the algorithms implementing snapshot objects and counters satisfying sequential consistency (instead of linearizability), Algorithm 5 uses no message sync().

Let us also notice the following. Objects are specified by "witness" correct executions, which are defined by sequential specifications. According to the time notion associated with these sequences we have two consistency conditions: linearizability (the same "physical" time for all the objects) or sequential consistency (a logical time is associated with each object, independently from the other objects). Differently, as distributed tasks are defined by relations from input vectors to output vectors (i.e., without referring to specific execution patterns or a time notion), the notion of a consistency condition (such as linearizability or sequential consistency) is meaningless for tasks.

THE COMPUTABILITY POWER OF SCD-BROADCAST (ITS LIMITS)

This section presents an algorithm building SCD-broadcast on top of SWMR snapshot objects. (Such snapshot objects can be easily obtained from MWMR snapshot objects.) Hence, it follows from (a) this algorithm, (b) Algorithm 1, and (c) the impossibility proof to build an atomic register on top of asynchronous message-passing systems where t ≥ n/2 process may crash [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF], that SCD-broadcast cannot be implemented in CAMP n,t [t ≥ n/2], and snapshot objects and SCD-broadcast are computationally equivalent.

From snapshot to SCD-broadcast

Shared objects. The shared memory is composed of two SWMR snapshot objects. Let ϵ denote the empty sequence.

• Algorithm 6: An implementation of SCD-broadcast on top of snapshot objects (code for p i )

• to_deliver i : auxiliary variable whose aim is to contain the next message set that p i has to scd-deliver.

The function members(set_seq) returns the set of all the messages contained in set_seq.

Description of Algorithm 6. When a process p i invokes scd_broadcast(m), it adds m to sent i [i] and SENT [i] to inform all the processes on the scd-broadcast of m. It then invokes the internal procedure progress() from which it exits once it has a set containing m (line 1).

A background task T ensures that all messages will be scddelivered (line 2). This task invokes repeatedly the internal procedure progress(). As, locally, both the application process and the underlying task T can invoke progress(), which accesses the local variables of p i , those variables are protected by a local fair mutual exclusion algorithm providing the operations enter_mutex() and exit_mutex() (lines 3 and 11).

The procedure progress() first invokes the internal procedure catchup(), whose aim is to allow p i to scd-deliver sets of messages which have been scd-broadcast and not yet locally scd-delivered.

To this end, catchup() works as follows (lines 12-17). Process p i first obtains a snapshot of SETS_SEQ, and saves it in sets_seq i (line 12). This allows p i to know which message sets have been scd-delivered by all the processes; p i then enters a "while" loop to scd-deliver as many message sets as possible according to what was scd-delivered by the other processes. For each process p j that has scd-delivered a message set set containing messages not yet scd-delivered by p i (predicate of line 13), p i builds a set to_deliver i containing the messages in set that it has not yet scd-delivered (line 14), and locally scd-delivers it (line 16). This local scd-delivery needs to update accordingly both sets_seq i [i] (local update) and SETS_SEQ[i] (global update).

When it returns from catchup(), p i strives to scd-deliver messages not yet scd-delivered by the other processes. To this end, it first obtains a snapshot of SENT , which it stores in sent i (line 5).

If there are messages that can be scd-delivered (computation of to_deliver i at line 6, and predicate at line 7), p i scd-delivers them and updates sets_seq i [i] and SETS_SEQ[i] (lines 7-9) accordingly.

CONCLUSION

What was the paper on? This paper has introduced a new communication abstraction, suited to asynchronous message-passing systems where computing entities (processes) may crash. Denoted SCD-broadcast, it allows processes to broadcast messages and deliver sets of messages (instead of delivering each message one after the other). More precisely, if a process p i delivers a set of messages containing a message m, and later delivers a set of messages containing a message m ′ , no process p j can deliver a set of messages containing m ′ before a set of messages containing m. Moreover, there is no local constraint imposed on the processing order of the messages belonging to a same message set. SCD-broadcast has the following noteworthy features:

• It can be implemented in asynchronous message passing systems where any minority of processes may crash. Its costs are upper bounded by twice the network latency (from a time point of view) and O(n 2 ) (from a message point of view). • Its computability power is the same as the one of atomic read/write register (anything that can be implemented in asynchronous read/write systems can be implemented with SCD-broadcast). • When interested in the implementation of a concurrent object O, a simple weakening of the SCD-broadcast-based atomic implementation of O provides us with an SCDbroadcast-based implementation satisfying sequential consistency (moreover, the sequentially consistent implementation is more efficient than the atomic one).

On programming languages for distributed computing. Differently from sequential computing for which there are plenty of high level languages (each with its idiosyncrasies), there is no specific language for distributed computing. Instead, addressing distributed settings is done by the enrichment of sequential computing languages with high level communication abstractions. When considering asynchronous systems with process crash failures, total order broadcast is one of them. SCD-broadcast is a candidate to be one of them, when one has to implement read/write solvable objects and distributed tasks.

Theorem 1 .

 1 Algorithm 1 implements the SCD-broadcast communication abstraction in CAMP n,t [t < n/2]. Moreover, each invocation of the operation scd_broadcast() requires O(n 2 ) protocol messages. If there is an upper bound ∆ on messages transfer delays (and local computation times are equal to zero), each SCD-broadcast costs at most 2∆ time units.

4

  SCD-BROADCAST IN ACTION (ITS POWER): SNAPSHOT OBJECT 4.1 Snapshot object Definition. The snapshot object was introduced in [1, 3]. A snapshot object is an array REG[1.

Theorem 5 .

 5 Algorithm 6 implements SCD-Broadcast in the classical wait-free read/write model CARW n,t [t < n].

  1, which implements SCDbroadcast in CAMP n,t [t < n/2]. From a terminology point of view, an application message is a message that has been scd-broadcast by a process, while a protocol message is an implementation message generated by Algorithm 1. each process stores a quadruplets qdplt = ⟨qdplt .msд, qdplt .sd, qdplt .f , qdplt .cl⟩ whose fields have the following meaning.

	Local	metadata	quadruplets.	For	each	applica-
	tion message m,

• qdplt .msд contains an application message m, • qdplt .sd contains the id of the sender of qdplt .msд, • qdplt .sn contains the local date (seq. number) associated with m by its sender. Hence, ⟨qdplt .sd, qdplt .sn⟩ is the identity of the application message m. • qdplt .cl is an array of size n, initialized to [+∞, . . . , +∞].

  ). Then, p i participates in the fifo-broadcast of m (line 11) and records its local progress by increasing sn i (line 12). is (1) send forward_msg(m, sn i , i, sn i , i) to itself;(2) wait(∄ qdpl t ∈ buffer i : qdpl t .sd = i).when the message forward_msg(m, sd, sn sd , f , sn f ) is fifo-delivered do % from p f (3) forward(m, sd, sn sd , f , sn f ); let to_deliver i ← {qdpl t ∈ buffer i :| {f : qdpl t .cl [f ] < ∞} | > n 2 }; (16) while (∃ qdpl t ∈ to_deliver i , ∃ qdpl t ′ ∈ buffer i \ to_deliver i : | {f : qdpl t .cl [f ] < qdpl t ′ .cl [f ]} | ≤ n2 ) do to_deliver i ← to_deliver i \ {qdpl t } end while;[START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF] if (to_deliver i ∅)

	(7)	then qdpl t .cl [f ] ← sn f
	(8)	else t hr eshold [1..n] ← [∞, . . . , ∞]; thr eshold [f ] ← sn f ;
	(9) (10)	let qdpl t ← ⟨m, sd, sn sd , thr eshold [1..n]⟩; buffer i ← buffer i ∪ {qdpl t };
	(11) (12)	fifo_broadcast forward_msg(m, sd, sn sd , i, sn i ); sn i ← sn i + 1
	(13)	end if
	(14) end if.
	procedure try_deliver() is
	(15)

• There is a quadruplet qdplt in buffer i associated with m, i.e., qdplt = ⟨m, -, -, -⟩ ∈ buffer i . In this case, p i assigns sn f to qdplt .cl[f ] (line 7), thereby indicating that m was known and forwarded by p f at its local time sn f . operation scd_broadcast(m) (4) try_deliver().

procedure forward(m, sd, sn sd , f , sn f ) is (5) if (sn sd > clock i [sd])

(

6) then if (∃ qdpl t ∈ buffer i : qdpl t .sd = sd ∧ qdpl t .sn = sn sd ) (18) then for each qdpl t ∈ to_deliver i do clock i [qdpl t .sd] ← max(clock i [qdpl t .sd], qdpl t .sn) end for; (19) buffer i ← buffer i \ to_deliver i ; (20) mset ← {m : ∃ qdpl t ∈ to_deliver i : qdpl t .msд = m }; scd_deliver(mset ) (21) end if. Algorithm 1: An implementation of SCD-broadcast in CAMP n,t [t < n/2] (code for p i )

  is an array of timestamps associated with the values stored in reg i [1..m]. A timestamp is a pair made of a local clock value and a process identity. Its initial value is ⟨0, -⟩. The fields associated with tsa i [r ] are denoted ⟨tsa i [r ].date, tsa i [r ].proc⟩.

  SENT [1..n]: snapshot object (initialized to [∅, . . . , ∅]), such that SENT [i] contains the messages scd-broadcast by p i .• SETS_SEQ[1..n]: snapshot object (init. to [ϵ, . . . , ϵ]), such that SETS_SEQ[i] contains the sequence of the sets of messages scd-delivered by p i .The notation ⊕ is used for the concatenation of a message set at the end of a sequence of message sets.Local objects. Each process p i manages the following local objects.• sent i : local copy of the snapshot object SENT .• sets_seq i : local copy of the object SETS_SEQ. scd_broadcast(m) is (1) sent i [i] ← sent i [i] ∪ {m }; SENT .write(sent i [i]); progress().(2) background task T is repeat forever progress() end repeat. catchup() is (12) sets_seq i ← SETS_SEQ.snapshot();[START_REF] Chaudhuri | More choices allow more faults: set consensus problems in totally asynchronous systems[END_REF] while (∃j, set : set is the first set in sets_seq i [j] : set ⊈ members(sets_seq i [i]) do (14) to_deliver i ← set \ members(sets_seq i [i]); (15) sets_seq i [i] ← sets_seq i [i] ⊕ to_deliver i ; SETS_SEQ.write(sets_seq i [i]);

	procedure progress() is
	(3) enter_mutex();
	(4) catchup();
	(5) sent i ← SENT .snapshot();
	(6) to_deliver i ← (∪ 1≤j ≤n sent i [j]) \ members(sets_seq i [i]); (7) if (to_deliver i ∅)
	(8) (9)	then sets_seq i [i] ← sets_seq i [i] ⊕ to_deliver i ; SETS_SEQ.write(sets_seq i [i]); scd_deliver(to_deliver i )
	(10) end if;
	(11) exit_mutex().
	(16)	scd_deliver(to_deliver i )
	(17) end while.

operation procedure

Total order broadcast is also called atomic broadcast. Actually, total order broadcast and consensus have been shown to be computationally equivalent[START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. A more general result is presented in[START_REF] Imbs | Which broadcast abstraction captures k-set agreement[END_REF], where is introduced a communication abstraction which "captures" the k-set agreement problem[START_REF] Chaudhuri | More choices allow more faults: set consensus problems in totally asynchronous systems[END_REF][START_REF] Raynal | Set agreement. Encyclopedia of Algorithms[END_REF] (consensus is 1-set agreement).

From the point of view of the maximal number of process crashes that can be tolerated, assuming failures are independent.

ACKNOWLEDGMENTS

This work was partially supported by the Franco-German DFG-ANR Project 14-CE35-0010-02 DISCMAT (devoted to connections mathematics/distributed computing) and the French ANR project 16-CE40-0023-03 DESCARTES (devoted to layered and modular structures in distributed computing).

operation increase() is (1) done i ← false; scd_broadcast plus(i); wait(done i );

(2) return().

operation decrease() is the same as increase() where plus(i) is replaced by minus(i).

operation read() is (3) done i ← false; scd_broadcast sync(i); wait(done i ); [START_REF] Aspnes | Wait-free data structures in the asynchronous PRAM model[END_REF] return(count er i ).

when the message set { plus(j 1 ), . . . ,minus(j x ), . . . , sync(j y ), . . . } is scd-delivered do (5) let p = number of messages plus() in the message set; (6) let m = number of messages minus() in the message set; [START_REF] Attiya | Atomic snapshots in O (n log n) operations[END_REF]

operation decrease() is the same as increase() where plus(i) is replaced by minus(i).

operation read() is (4) wait(l sc i = 0); [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF] return(count er i ).

when the message set { plus(j 1 ), . . . ,minus(j x ), . . . } is scd-delivered do (6) let p = number of messages plus() in the message set; [START_REF] Attiya | Atomic snapshots in O (n log n) operations[END_REF] let m = number of messages minus() in the message set; (8) count er i ← count er i + pm; (9) let c = number of messages plus(i) and minus(i) in the message set; [START_REF] Biran | A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor[END_REF] Sequentially consistent snapshot object. When considering Algorithm 2, let us suppress line 1 and line 3 (i.e., the messages sync are suppressed). The resulting algorithm implements a sequentially consistent snapshot object. This results from the suppression of the real-time compliance due to the messages sync. The operation snapshot() is purely local, hence its cost is 0. The cost of the operation write() is one SCD-broadcast, i.e., 2∆ time units and O(n 2 ) protocol messages. The proof of this algorithm is left to the reader.

SCD-BROADCAST IN ACTION (ITS POWER): COUNTER OBJECT

Definition. Let a counter be an object which can be manipulated by three parameterless operations denoted increase(), decrease(), and read(). Let C be a counter. From a sequential specification point of view C.increase() adds 1 to C, C.decrease() subtracts 1 from C, C.read() returns the value of C. As indicated in the Introduction, due to its commutative operations, this object is a good representative of a class of CRDT objects (conflict-free replicated data type as defined in [START_REF] Shapiro | Conflict-free replicated data types[END_REF]).

An algorithm satisfying linearizability. Algorithm 3 implements an atomic counter C. Each process manages a local copy of it denoted counter i . The text of the algorithm is self-explanatory. The operation read() is similar to the operation snapshot() of the snapshot object. Differently from the write() operation on a snapshot object (which requires a synchronization message sync() and a data/synchronization message write()), the update operations increase() and decrease() require only one data/synchronization message plus() or minus(). This is the gain obtained from the fact that, from a process p i point of view, the operations increase() and decrease() which appear between two consecutive of its read() invocations are commutative. Theorem 3. Algorithm 3 implements an atomic counter.

An algorithm satisfying sequential consistency. The previous algorithm can be easily modified to obtain a sequentially consistent counter. To this end, a technique similar to the one introduced in [START_REF] Attiya | Sequential consistency versus linearizability[END_REF] can be used to allow the operations increase() and decrease() to have a fast implementation. "Fast" means here that these operations are purely local: they do not require the invoking process to wait in the algorithm implementing them. Differently, the operation read() issued by a process p i cannot be fast, namely, all the previous increase() and decrease() operations issued by p i must be applied