Michel Raynal

Eduardo Fernando

Distributed Computability: a Few Results Masters Students Should Know

As today Informatics is more and more (driven) eaten by its applications, it becomes more and more important to know what can be done and what cannot be done. For a long time now, this is well known in sequential computing. But today the world becomes more and more distributed, and consequently more and more applications are distributed. As a result, it becomes important, or even crucial, to understand what is distributed computing and which are its power and its limits. This article is a step in this direction when looking from an agreement-oriented fault-tolerance point of view.

Teaching is not an accumulation of facts.

 Correctness may be theoretical, ... but incorrectness has practical impact. M.

Introduction 1.Sequential and parallel computing

Sequential computing All curricula in informatics have a section devoted to computability in sequential computing. It follows that students know fundamental results such as

• the automata hierarchy, namely: Finite State automata Pushdown automata Turing machine,

• the Church-Turing thesis stating that everything that can be mechanically computed can be computed by a Turing machine, • the impossibility to solve some well-defined problems (such that the halting problem [START_REF] Turing | On computable numbers with an application to the Entscheidungsproblem[END_REF]),

• The impossibility to bypass some bounds (for example design a comparison-based sorting algorithm whose number of comparisons is always smaller than O(n log n), where n is the number of elements to sort). • The notion of non-determinism and the P = NP conjecture. This basic theoretical knowledge, together with algorithms and programming, constitutes the pillars on which stands sequential computing.

Parallel computing Parallel computing was introduced to solve efficiency issues [START_REF]Parallel computing[END_REF]. As in the recursive thinking, the idea is to decompose a problem Pb in independent sub-problems, and then recompose their solutions to obtain a solution to Pb. Said in an other way, the key of parallel computing is data independence. It consists in making data (or blocs of data) independent of each other, so that they can be processed independently the ones from the others -i.e. without interactions-, which, from an efficiency point of view, means processing them simultaneously.

The decomposition of the set of input data in independent data is under the control of the programmer and constitutes the core of the design of parallel algorithms. Put it differently, if efficiency was not the issue, the problems addressed in parallel computing could be solved with a sequential algorithm.

Distributed computing

An informal view (from [START_REF] Raynal | Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF]) Distributed computing was born in the late 1970s when researchers and practitioners started taking into account the intrinsic characteristic of physically distributed systems. The field then emerged as a specialized research area distinct from networking, operating systems, and parallel computing.

Distributed computing arises when one has to solve a problem in terms of pre-defined distributed entities (usually called processors, nodes, processes, actors, agents, sensors, peers, etc.) such that each entity has only a partial knowledge of the many parameters involved in the problem that has to be solved. While parallel computing and real-time computing can be characterized, respectively, by the terms efficiency and on-time computing, distributed computing can be characterized by the term coordination in the presence of uncertainty. In distributed computing, the computing entities are not defined by the programmer but imposed to her, who has to allow them to correctly cooperate.

This uncertainty is created by asynchrony, multiplicity of control flows, absence of shared memory and global time, failure, dynamicity, mobility, etc., all called adversaries. The set of of the adversaries defines what is called the environment. Let us notice that the environment constitutes an implicit and unknown input of any distributed execution (in the sense it can affect the result produced by the execution).

Mastering one form or another of uncertainty is pervasive in all distributed computing problems. A main difficulty in designing distributed algorithms comes from the fact that no entity cooperating in the achievement of a common goal can have an instantaneous knowledge of the current state of the other entities, it can only know some of their past local states.

As we can see, the aim of parallel computing and distributed computing can be seen as being orthogonal: parallel computing is looking for data independence in order to split the computation in independent computing entities to obtain efficient algorithms, while the aim of distributed computing is to allow computing entities to cooperate in the presence of adversaries.

Two quotations Here are two quotes that can help the reader capture the spirit of distributed computing. The first one is an humorous quote from L. Lamport [START_REF] Lamport | Message-Id: <8705281923.AA09105@jumbo[END_REF]:

A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable. This quote can be seen as a funny version of the FLP theorem (presented below). The second one (from [START_REF] Herlihy | Power and limits of distributed computing shared memory models[END_REF]) stresses the fundamental difference between sequential computing and distributed computing when looking at computability. In sequential systems, computability is understood through the Church-Turing Thesis: anything that can be computed, can be computed by a Turing Machine. In distributed systems, where computations require coordination among multiple participants, computability questions have a different flavor. Here, too, there are many problems which are not computable, but these limits to computability reflect the difficulty of making decisions in the face of ambiguity, and have little to do with the inherent computational power of individual participants.

Preliminaries

Computing models

The reader interested in the notion of model can consult [START_REF] Schneider | What good are models, and what models are good? Distributed Systems[END_REF].

Computing entities In the following we consider a static system is made up of a set of n asynchronous computing entities (called processes in the following), denoted p 1 , ..., p n . The local power of a process is the one of a Turing machine. "Asynchronous" means that each process progresses at its own speed, which can vary with time, and remains always unknown to the other processes.

Process failures Two types of process failures are considered.

• Crash failure model. A crash is a premature unanticipated halt by a process. Moreover once crashed, a process remains crashed forever. It is important to notice that a process behaves correctly until it crashes (if it ever crashes). • Byzantine failure model. This type of failure was introduced in the early eighties [START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Pease | Reaching agreement in the presence of faults[END_REF]. A Byzantine process is a process that does not follow the behavior defined by the algorithm it is assumed to execute. Such an incorrect behavior can be intentional or not. When intentional, it is sometimes called "malicious". In this model a crash is considered as a Byzantine failure.

Given a run and according to the failure model, a process that does not commit a failure is a correct (or non-faulty) process. Otherwise it is a faulty process. The fact we do not know in advance which are the correct and the faulty processes is one of main sources of non-determinism that distributed algorithms have to master.

Let us also notice that these are more sophisticated Byzantine failure models -not addressed in this article-that distinguish crash failures from Byzantine failures (the former being less severe than the latter).

Communication model We consider two communication models.

• Shared memory model. In this model the processes communicate through atomic registers. According to the primitive operations the processes can use to access these registers, two sub-models can be defined.

-In the basic read/write (RW) model, the only operations a process can invoke to access a register are read and write. -In the read/modify/write (RMW) model, in addition to read and write primitive operations, a process can invoke one or more sophisticated primitive operations such as Test&Set(), Fetch&Add(), Compare&Swap(), or LL/SC (linked load/store conditional). According to the operations enriching the basic RW model, there are many RMW models. The model enriched with the primitive operation op is denoted RMW+op.

As an example let us consider the model RMW+Compare&Swap. As LL/SC, the operation Compare&Swap, is an atomic conditional write. The effect of Compare&Swap(R, old, new) where R is a shared register and old and new are two values is the following. If R = old, the operation assigns new to R and returns true. If R = old, R is not modified and the operation returns false.

• Message-passing model. In this model the processes exchange message on top of a communication network. In this case, in addition to the local power provided by a Turing machine, the processes can send and receive messages. It is assumed that the network is reliable (i.e., there is neither loss, creation, nor alteration of messages).

Progress conditions

Case of the failure-free model In a failure-free context, two progress conditions have been defined for the high level operations invoked on shared objects defined by the programmer or supplied by a library (e.g., the operations push() and pop() associated with a stack). According to the underlying communication model, these objects are implemented on top of registers of the shared memory, or on top of the local memories of the processes (in this case, the communication medium can be messagepassing or shared memory). Deadlock-freedom states that if one or more processes invoke an high level operation on a shared object, at least one invocation will succeed. Starvation-freedom is a stronger progress condition, namely it states that if any process invokes an operation on a shared object, its invocation will succeed. Deadlock-free and starvation-free mutual exclusions are a classical techniques used to protect accesses to shared objects [START_REF] Rajsbaum | Mastering concurrent computing through sequential thinking: A half-century evolution[END_REF].

Case of the shared memory crash-prone model In this context, the situation is different. The crash of a process p while it is accessing a shared object can prevent other processes from forever accessing the object. Intuitively, this is due to the fact that no process can know if p crashed or is is only very slow. As a consequence, since the early nineties, progress conditions suited to asynchronous crash-prone systems have been proposed.

• Obstruction-freedom [START_REF] Herlihy | Obstruction-free synchronization: double-ended queues as an example[END_REF]. An object operation is obstruction-free if, assuming the invoking process p does not crash and executes in isolation for a long enough period, its invocation terminates. "In isolation" means that, if any, the concurrent invocations of operations on the same object by other processes have stopped their execution -maybe in the middle of their code-and remain pending until p returns from its invocation). • Non-blocking [START_REF] Herlihy | Linearizability: a correctness condition for concurrent objects[END_REF]. An object operation is non-blocking if, whatever the number of concurrent invocations, at least one of them terminates. Non-blocking extends deadlock-freedom to process crash failures. • Wait-freedom [START_REF] Herlihy | Wait-free synchronization[END_REF]. An object operation is wait-free if all its invocations by processes that do not crash terminate. Wait-freedom extends starvation-freedom to process crash-failures.

In the case of Byzantine failures, the progress condition states that the invocation of an operation by a correct process must terminate if the number of Byzantine processes doe not bypass a pre-defined threshold.

Case of the asynchronous message-passing model In this context, according to the problem (object to implement) that is solved, the previous progress conditions may apply in the case of crash failures.

But this not true for all the problems. As for Byzantine failures in shared memory systems, in many cases, the progress condition that is considered states that an operation invoked by a correct process must terminate if some assumptions are satisfied. These assumptions usually involve the maximum number of processes that can be faulty [START_REF] Herlihy | From wait-free to arbitrary concurrent solo executions in colorless distributed computing[END_REF].

3 Asynchronous Crash-Prone Shared Memory

The consensus object

A notion of universality Considering the asynchronous crash-prone shared memory model, M. Herlihy introduced the notions of a universal object and a universal construction [START_REF] Herlihy | Wait-free synchronization[END_REF]. This notion of universality concerns the wait-free implementation of the objects defined by a sequential specification ("wait-free implementation" means that all the operations of the object that is built must be wait-free). To this end, he introduced the notion of a universal object type. An object type T is universal if a universal construction can be built from

• any number of objects of type T , and

• any number of atomic read/write registers.

It is shown in [START_REF] Herlihy | Wait-free synchronization[END_REF] that the consensus object type (defined below) is universal.

The Consensus object Consensus is a one-shot object that provides the processes with a single operation denoted propose(). (One-shot" means that a process may invoke d propose() at most once). When a process p i invokes propose(v i ) we say " p i proposes the value v i ". Such an invocation returns a value v and, when this occurs, we say "p i decides v". In the context of process crah failures, consensus is defined by the three following properties (validity and agreement are safety properties, while wait-freedom is a liveness property).

• Validity: The value decided by a process is a proposed value.

• Agreement: No two processes decide different values.

• Wait-freedom: The invocation of propose() by a non-faulty process terminates.

Principles underlying universal constructions

The universality of the consensus object comes from the fact that it allows the processes to agree on a unique order to apply the operations invoked on the object O that is built. On the client side each process can invoke an operation on O by announcing it to all the processes. On the server side, the processes execute a sequence of rounds, each using a new consensus object. During each round, each process proposes to the consensus object the operations it sees as being proposed and not yet applied to O. The proposal output by the consensus object is the winner proposal for the corresponding round, and the sequence of operations it contains is applied by each process to its local copy of the object (if the state machine replication -SMR-paradigm is used [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF][START_REF] Raynal | The notion of universality in crash-prone asynchronous message-passing systems: a tutorial[END_REF][START_REF] Schneider | Implementing fault-tolerant services using the state machine approach[END_REF]), or to the unique copy of the object in the case where the object O is stored in a shared memory [START_REF] Herlihy | Wait-free synchronization[END_REF]. All the universal constructions rely on a helping mechanism [START_REF] Censor-Hillel | Help! Proc. 34th Symposium on Principles of Distributed Computing (PODC'15)[END_REF], which ensures that the operations invoked by processes that crash during their invocations are applied by all or none the non-crashed processes.

More advanced topic: Yet more universal constructions The previous constructions consider the construction of a single object. A more general construction is described in [START_REF] Gafni | Generalizing universality[END_REF], that considers the case where, not only one, but k objects are built and the wait-freedom property is satisfied for at least one of them. This construction relies on k-set agreement, a generalization of consensus [START_REF] Chaudhuri | More choices allow more faults: set consensus problems in totally asynchronous systems[END_REF].

A yet more general construction is described in [START_REF] Raynal | Distributed universality[END_REF], that considers the simultaneous construction of k objects such that the wait-freedom property is satisfied for at least ℓ of them, 1 ≤ ℓ ≤ k. Such a construction relies on the k-simultaneous consensus object defined in [START_REF] Afek | The k-simultaneous consensus problem[END_REF].

The consensus hierarchy

The consensus number notion This notion was introduced in [START_REF] Herlihy | Wait-free synchronization[END_REF]. The consensus number of an object type T is the greatest integer n such that, despite asynchrony and any number of process crashes, it is possible to build a consensus object from atomic read/write registers and objects of type T in a system of n processes. If there is no such finite n, the consensus number of T is +∞.

It is shown in [START_REF] Herlihy | Wait-free synchronization[END_REF] that the consensus numbers defines an infinite hierarchy such that • Read/write registers have consensus number 1. (The first proof showing that consensus cannot be wait-free implemented on top of read/write registers in the presence of asynchrony and any number of process crashes appeared in [START_REF] Loui | Memory requirements for agreement among unreliable asynchronous processes[END_REF].) • Test&Set registers, Fetch&Add registers, stacks, queues have consensus number 2.

• Compare&Swap registers, LL/SC (linked load/store conditional) registers, Memory-to-Memory swap registers have consensus number +∞.

A simple object family covering the full hierarchy The k-sliding read/write register object, in short RW(k) was introduced in [62] (a similar object was independently introduced in [START_REF] Gelashvili | A complexity-based hierarchy for multiprocessor synchronization[END_REF]). This object is a a natural generalization of an atomic read/write register, which corresponds to the case k = 1). This object is an (initially empty) sequence of values such that the write of a value v adds v at the end of the sequence, and a read returns the sub-sequence of the last k written values (if only x < k values have been written, the read return these x values). It is easy to see that the type RW( 1)is the read/write register type, while RW(+∞) is nothing else than a ledger [START_REF] Raynal | Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF].

Universal constructions Universal constructions based on consensus objects or on operations whose consensus number is +∞ (such as LL/SC), are described in many articles, e.g. [START_REF] Ellen | Universal constructions that ensure disjointaccess parallelism and wait-freedom[END_REF][START_REF] Fatourou | Highly-efficient wait-free synchronization[END_REF][START_REF] Herlihy | Wait-free synchronization[END_REF][START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF][START_REF] Raynal | Distributed universal constructions: a guided tour[END_REF], and and in textbooks such as [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Herlihy | The art of multiprocessor programming[END_REF][START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF][START_REF] Taubenfeld | Synchronization algorithms and concurrent programming[END_REF]].

Objects at level 1 of the hierarchy It follows from the previous hierarchy that, as they have consensus number 2, objects such as stacks and queues cannot be wait-free implemented on top of read/write registers only. Differently, important objects such as snapshot [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], renaming [START_REF] Attiya | Renaming in an asynchronous environment[END_REF][START_REF] Castañeda | The renaming problem in shared memory systems: an introduction[END_REF], immediate snapshot [START_REF] Borowsky | Immediate atomic snapshots and fast renaming[END_REF], and approximate agreement [START_REF] Dolev | Reaching approximate agreement in the presence of failures[END_REF] have consensus number 1 and can consequently be waitfree built on top of read/write registers only, despite asynchrony and any number of process crashes. The interested reader can consult textbooks such as [START_REF] Herlihy | The art of multiprocessor programming[END_REF][START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF][START_REF] Taubenfeld | Synchronization algorithms and concurrent programming[END_REF] where are described wait-free implementation of such objects. The family of the CRDT objects (Conflict-free Replicated Data Types [START_REF] Shapiro | Conflict-free replicated data yypes[END_REF]) is a sub-class of the objects at level 1 of the consensus hierarchy.

Implication of the hierarchy for consensus number > 1 It follows from Herlihy's infinite hierarchy, that no object with consensus number x > 1 can be wait-free implemented on top of an object whose consensus number is smaller than x.

It follows from this observation that, while a shared stack (or a queue) can be implemented on top of atomic read/write atomic registers in an asynchronous failure-free systems (whatever the number of processes), this is impossible in a crash-prone system. This, which at first glance may seem surprising and counter-intuitive, is due to the fact their consensus number is 2, while the consensus number of read/write registers is 1.

It follows that, differently from what occurs in sequential computing (where read/write registers are the cells of a Turing machine) and more generally in failure-free concurrent computing, read/write registers are not universal in asynchronous crash-prone systems, where consensus is needed to cope with the non-determinism created by the environment (net effect of asynchrony and crash failures).

Read/write with respect to read/modify/write An important point lies in the fact that a write operation not only defines a new value for the register R to which it is applied, but also erases its past which is then lost forever. Differently, while operations such as Fetch&Add(R) or Test&Set(R) (whose consensus number is 2) are unconditional writes, they return the previous value of the register R to which they are applied (and consequently this value is not lost forever and can used by the invoking process). More, the operation Compare&Swap(R, old, new) (whose consensus number is +∞) is a conditional write (it modifies the register R to which it is applied only if its current value is equal to the parameter value old).

Domain of consensus numbers

The notion of consensus number has been defined in the context of the asynchronous shared memory model in which any number of processes may crash. Such a notion cannot be directly applied to message-passing systems or Byzantine failures.

Advanced topics

The multiplicative power of consensus numbers has been investigated in [START_REF] Imbs | The multiplicative power of consensus numbers[END_REF]. An extension of the consensus number hierarchy to multi-threaded systems is presented in [START_REF] Perrin | Extending the wait-free hierarchy to multi-threaded systems[END_REF]. It has been shown in [START_REF] Afek | Deterministic objects: life beyond consensus[END_REF][START_REF] Daian | A wealth of sub-consensus deterministic objects[END_REF] that given any integer x ≥ 1, there is an infinite number of objects O(x, 1), O(x, 2), etc., such that, while they all have consensus number x, it is possible to build O(x, y) from O(x, y -1) but O(x, y -1) cannot be built from O(x, y) (hence, there is an infinite computability-related sub-hierarchy between any two consecutive consensus numbers). An exhaustive survey of the consensus number land is presented in [START_REF] Raynal | An Informal visit to the wonderful land of consensus numbers and beyond[END_REF].

A notion close but different from consensus numbers, called d-solo executions, is presented in [START_REF] Herlihy | From wait-free to arbitrary concurrent solo executions in colorless distributed computing[END_REF]. A process runs solo when it computes its local output without receiving any information from other processes, either because they crashed or they are too slow. While in wait-free shared memory models at most one process may run solo in an execution, any number of processes may have to run solo in an asynchronous wait-free message-passing model. In the d-solo model, 1 ≤ d ≤ n, up to d processes may run solo. A hierarchy of wait-free models is described in [START_REF] Herlihy | From wait-free to arbitrary concurrent solo executions in colorless distributed computing[END_REF] that, while weaker than the basic crash-prone read/write model, are nevertheless strong enough to solve non-trivial tasks.

Synchronous Message-Passing Systems

From now on, we assume the inter-process communication is through message-passing. Moreover, each pair of processes is connected by a reliable bidirectional channel.

Round-based communication

In a synchronous message-passing system the processes execute a sequence of rounds whose progress is governed by an external clock, the progress of which defines a sequence of rounds. Each round r is composed three phases.

• Phase 1: at the beginning of a round r each process sends a message to the other processes. If a process crashes during this sending phase, an arbitrary subset of processes receives the message. • Phase 2: a process receives messages sent by the other processes.

• Phase 3: according to its current local state and the messages it has received, a process does local computations that modifies its local state.

The synchrony property The fundamental synchrony property (provided for free) of the synchronous message-passing system model lies in the fact that a message sent by a process during a round r is received by its destination process during the very same round r.

If follows from the synchrony property that, if a process p crashes during round r, a non-crashed processes learns it during round r or round (r + 1) (because it does not receive a message from p). As we can see, this synchrony property drastically reduces the non-determinism due to environment.

Consensus in the round-based synchronous communication model

Let t, 1 ≤ t < n, be a model parameter denoting the maximum number of processes that may be faulty in a run. It is assumed that t is known by the processes. Moreover, given a run, let f , 0 ≤ f ≤ t be the number of faulty processes in this run. We have the following results concerning consensus [START_REF] Aguilera | A simple bi-valency proof that t-resilient consensus requires t + 1 rounds[END_REF][START_REF] Dolev | Early stopping in Byzantine agreement[END_REF][START_REF] Fischer | A lower bound for the time to ensure interactive consistency[END_REF].

The case of process crashes In the synchronous failure-prone message-passing model, the synchrony assumption is strong enough to allow consensus to be solved. More precisely, we have the following.

• Consensus can be solved for any value of t < n.

• The maximal number of rounds to solve consensus is min(f + 2, t + 1).

The case of Byzantine processes As a Byzantine process can never decide or can decide any value, and the non-Byzantine processes can propose different values, the definition of consensus must be appropriately modified in order an algorithm can be designed. We consider here the following classical definition [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Dolev | Early stopping in Byzantine agreement[END_REF][START_REF] Raynal | Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF].

• Validity: If all the non-faulty processes propose the same value, this value is decided. In the other cases any value can be decided. • Agreement: No two non-faulty processes decide different values.

• Wait-freedom: The invocation of propose() by a non-faulty process terminates.

Let us observe that, in the case of binary consensus (only two values can be proposed), it follows from the validity property that the value decided by the non-faulty processes is always a value proposed by one of them [START_REF] Raynal | Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF].

A stronger validity property is used in some articles, namely: If (t + 1) non-faulty processes propose the same value, this value is decided. In the other cases any value can be decided. This does not change the following results.

Considering the round-based communication model, we have the following results.

• Consensus can be solved if and only if t < n/3 [START_REF] Lamport | The Byzantine generals problem[END_REF][START_REF] Pease | Reaching agreement in the presence of faults[END_REF].

• The maximal number of rounds needed to solve Byzantine consensus is min(f + 2, t + 1) [START_REF] Dolev | Early stopping in Byzantine agreement[END_REF].

• If the model is enriched with message authentication, the previous necessary and sufficient condition (t < n/3) becomes t < n/2.

Remark 1 Let us notice that there are algorithms that (at the additional cost of two synchronous rounds) reduce multi-valued synchronous consensus to binary synchronous consensus in the presence of t < n/3 Byzantine processes [START_REF] Mostéfaoui | Two-bit messages are sufficient to implement atomic read/write registers in crash-prone systems[END_REF][START_REF] Raynal | Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF][START_REF] Turpin | Extending binary Byzantine agreement to multivalued Byzantine agreement[END_REF].

Remark 2 As far as synchrony assumptions are concerned, it is important to say that the synchrony offered by the round-based synchronous communication model is not the weakest synchrony assumption that allows consensus to be solved. In other words, the synchronous communication model is stronger than necessary. This point is addressed in Section 5.4 for the case of Byzantine failures.

Asynchronous Message-Passing Systems

An asynchronous message-passing distributed system is such that both the processes and the communication channels are asynchronous. An asynchronous channel is such that there is no assumption of the transfer delay of each message, except it is finite.

In the following we consider three problems, and for each of them consider the case of crash failures an the case of Byzantine processes. As previously, t denotes the maximal number of processes that may commit failures.

Construction of an atomic read/write register

As a read/write register is the most basic object of sequential computing, and, more generally, a file is nothing else than a "big" read/write register, it is natural to try to build a such a register on top of an synchronous message-passing system prone to process (crash or Byzantine) failures.

The case of process crashes The most important result, due to [START_REF] Attiya | Sharing memory robustly in message passing systems[END_REF], is the following necessary and sufficient condition:

• t < n/2 is a necessary and sufficient condition to build an atomic read/write register in asynchronous n-process system prone to process crash failures.

Intuitively, this is due to the following reason. If t ≥ n/2, the processes can be partitioned in two subsets Q1 and Q2 such that the communication inside each partition is rapid while the communication between the two partitions is arbitrarily slow. In this case, the processes of Q1 (reps. Q2) cannot distinguish the case were the processes Q2 (reps. Q1) have crashed or are arbitrarily slow. This is called an indistinguishability argument [START_REF] Attiya | Indistinguishability[END_REF]. Differently, if t < n/2, it is possible for a process to communicate with a majority of processes without risking to become blocked forever. As any two majorities intersect, we have then Q1 ∩ Q2 = ∅, from which portioning can be prevented.

The efficiency of algorithms implementing read/write registers in the presence of asynchrony and a majority of processes that do not crash has been addressed in [START_REF] Dutta | Fast access to distributed atomic memory[END_REF][START_REF] Mostéfaoui | Time-efficient read/write register in crash-prone asynchronous message-passing systems[END_REF]. It is shown in [START_REF] Mostéfaoui | Two-bit messages are sufficient to implement atomic read/write registers in crash-prone systems[END_REF] that, in addition to the value of the register, messages have to carry two bits of control information.

The case of Byzantine processes As a Byzantine process can pollute each register it writes, the shared memory must be restricted to be an array M [1..n] of single-writer multi-reader (SWMR) atomic registers. Hence, M [i] can read by all the processes but written only by p i . Considering such a context, the following necessary and sufficient condition is proved in [START_REF] Imbs | Read/Write shared memory abstraction on top of an asynchronous Byzantine message-passing system[END_REF]:

• t < n/3 is a necessary and sufficient condition to build a shared memory made up SWMR atomic registers in an asynchronous n-process system in which up to t process may be Byzantine.

Algorithms building such a Byzantine-tolerant shared memory are presented in [START_REF] Imbs | Read/Write shared memory abstraction on top of an asynchronous Byzantine message-passing system[END_REF][START_REF] Mostéfaoui | Atomic read/write memory in signature-free Byzantine asynchronous message-passing systems[END_REF].

An intuitive explanation of the t < n/3 assumption Let us consider the worst case, namely n = 3t+1. So, there are at least n-t = 2t+1 non-faulty processes. Let us partition the processes in four sets: Q1, Q2, Q3, and Q4, so that each of Q1, Q2, and Q3 contains t processes, Q4 contains a single process, and all the up to t Byzantine processes are in Q3. As there are nt = 2t + 1 non-faulty processes, a process can communicate with this number of processes without risking to be blocked. But, due to asynchrony, it is possible that, inside the set of nt = 2t + 1 processes with which it communicates, t processes are Byzantine, each of them sending different values to distinct processes (while it is assumed to send the same value). Given any two non-faulty processes p i and p j , let P i = Q1 ∪ Q3 ∪ Q 4 the set of processes the set of processes communicating with p i , and

P j = Q2 ∪ Q3 ∪ Q 4 .
We have then

|P i ∩ P j | = t + 1,
when means that there is at least one non-faulty that communicate with both p i and p j .

Consensus in the presence of asynchrony and process crashes

Consensus impossibility One of most important results of asynchronous crash-prone message-passing rums i the following one, known under the name FLP, according to its the name of its authors (Fischer, Lynch, and Paterson [START_REF] Fischer | Impossibility of distributed consensus with one faulty process[END_REF]).

• There is no deterministic algorithm that solves consensus in asynchronous message-passing systems in which even a single process may crash.

To prove their theorem, the authors considered binary consensus and, assuming an algorithm can solve consensus, they introduced a new notion that revealed to be extremely simple and powerful, namely the notion of valence of a global state (also called configuration) of the algorithm assumed to solve consensus.

A state in 0-valent (resp.,1-valent), if only 0 (resp. 1) can be decided from this state (maybe no one knows it, but in such a state "the dices are thrown"). 0-valent states and 1-valent states are called mono-valent states. A bi-valent state in a state in which nothing has yet been decided (maybe no one knows it, but in such a state "the dices are not yet thrown").

The proof is then made up of two parts. The first consists in showing that among all possible global states, at least one of them is bi-valent. The second part consists in showing, that given any algorithm assumed to solve consensus, if it is in a bi-valent state there is a execution of it that moves it in a new bi-valent state, from which follows that the algorithm will never terminate.

How to circumvent FLP? Several approaches have proposed to circumvent the impossibility of consensus in asynchronous crash-prone systems.

• Add scheduling assumptions that restrict the set of possible behaviors (e.g., [START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF][START_REF] Dolev | On the minimal synchronism needed for distributed consensus[END_REF][START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF][START_REF] Mostéfaoui | Asynchronous implementation of failure detectors[END_REF]).

• Provide the processes with information on failures [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF]. It has been shown in [START_REF] Chandra | The weakest failure detector for solving consensus[END_REF] that the weakest information on crash failures that allows consensus to be solved is captured by the failure detector, called eventual leader and denoted Ω [START_REF] Chandra | The weakest failure detector for solving consensus[END_REF]. Such a failure detector provides each process p i with a read-only variable leader i , which always contains a process identity, and these local variables are such that there is an unknown but finite time τ after which they all contain the same identity, which is the identity of a process that does not crash.

• Restriction on the sets of input vectors. An input vector is the vector (unknown by the processes) of size n, the entry i containing the value proposed by p i . This approach, called condition-based, was introduced in [START_REF] Mostéfaoui | Conditions on input vectors for consensus solvability in asynchronous distributed systems[END_REF].

• Use randomization. For crash failures, this approach was introduced in [START_REF] Ben-Or | Another advantage of free choice: completely asynchronous agreement protocols[END_REF].

Several algorithms based on each of the previous assumptions are described in [START_REF] Raynal | Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF].

Advanced topic Computability-related equivalences between round-based synchronous models constrained by message adversaries and and asynchronous crash-prone message-passing models enriched with failure detectors are presented in [START_REF] Afek | A simple characterization of asynchronous computations[END_REF][START_REF] Raynal | Round-based synchrony weakened by message adversaries vs asynchrony enriched with failure detectors[END_REF].

Consensus in the presence of asynchrony and Byzantine processes

As Byzantine failures are more severe than crash failures The FLP impossibility remains valid in the Byzantine failure model. Many Byzantine-tolerant consensus algorithms have been proposed. They are based on asynchronous rounds, which -differently from the synchronous model-must be explicitly built by the algorithm. The major part of these algorithms consider binary consensus.

Starting with an early article by M. Rabin [START_REF] Rabin | Randomized Byzantine generals[END_REF], these algorithms use randomization to circumvent the consensus impossibility. Among the existing algorithms the one described in [START_REF] Mostéfaoui | Signature-free asynchronous binary Byzantine consensus with t < n/3, O(n 2 ) messages, and O(1) expected time[END_REF] is optimal in several respects. More precisely:

• It requires t < n/3 and is consequently optimal with respect to t.

• It uses a constant number of communication steps per round.

• The expected number of rounds to decide is constant.

• The message complexity is O(n 2 ) messages per round.

• Each message carries its type, a round number plus a constant number of bits.

• The algorithm uses a weak common coin. Weak means here that there is a constant probability that, at every round, the coin returns different values to distinct processes. • Finally, the algorithm does not assume a computationally limited adversary (and consequently it does not rely on signed messages).

Algorithms that reduce Byzantine multi-valued consensus to Byzantine binary consensus are described in [START_REF] Ben-Or | Asynchronous secure computations with optimal resilience[END_REF][START_REF] Mostéfaoui | Intrusion-tolerant broadcast and agreement abstractions in the presence of Byzantine processes[END_REF][START_REF] Mostéfaoui | Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with t < n/3, O(n 2 ) messages, and constant time[END_REF].

Remark The necessary and sufficient condition t < n/3 can be weakened into t < n/2 if the underlying asynchronous architecture is enriched with an appropriate temperproof distributed component such as TTCB (Trusted Timely Computing Base). As an example, the interested reader will find in [START_REF] Correia | How to tolerate half less one Byzantine nodes in practical distributed systems[END_REF][START_REF] Correia | BFT-TO: intrusion tolerance with less replicas[END_REF][START_REF] Veronese | Efficient Byzantine faulttolerance[END_REF] the development of such an approach.

Byzantine consensus: the minimal synchrony assumption

While consensus can be solved in the round-based synchronous message-passing system model where up to t < n/3 processes can be Byzantine, it cannot be solved in fully asynchronous process model where up to t < n/3 processes can be Byzantine. Hence, the question: which is the weakest synchrony assumption that allows consensus to be solved in the presence of up to t < n/3 Byzantine processes. This question has been answered in [START_REF] Bouzid | Minimal synchrony for Byzantine consensus[END_REF], where it is shown that the following synchrony assumption is necessary and sufficient condition.

Uni-directional channels Let us assume that each pair of processes is connected by two uni-directional communication channels. (This is to be as general as possible as it becomes possible to associate different transfer delays to each direction of a bi-directional channel.)

Eventually timely channel Let us consider the channel connecting a process p to a process q. This channel is eventually timely if there is a finite time τ and a bound δ, such that any message sent by p to q at time τ ′ ≥ τ is received by q by time τ ′ + δ. Let us observe that neither τ nor δ are known by the processes.

Eventual t + 1 bisource An eventual t + 1 bisource is a non-faulty process p that has (a) eventually timely input channels from t correct processes and (b) eventually timely output channels to t correct processes (these input and output channels can connect p to different subsets of processes).

It is shown in [START_REF] Bouzid | Minimal synchrony for Byzantine consensus[END_REF] that the existence of an eventual t + 1 bisource is the weakest synchrony assumption that allows Byzantine-tolerant consensus to be solved. This article presents also an algorithm based on this assumption.

Reliable Broadcast

Reliable broadcast belongs to the family of fundamental problems of fault-tolerant distributed computing [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF]. As previously, it comes in two versions according to the process failure model. Reliable means here that the set of the messages that are delivered satisfy well-defined properties, which are crucial to the design of provably correct distributed software.

Reliable broadcast in the presence of crash failures This communication abstraction, that provides the processes with two operations denoted R_broadcast() and R_deliver(), is defined by the following properties. When a process invokes R_broadcast(m), we say that it "r-broadcasts m". Similarly, when it issues R_deliver() and obtains the message m, we say that it "r-delivers m".

• Validity. If a process p i r-delivers a message m from a process p j , m has previously been rbroadcast by p j . • Integrity. Assuming all the messages are different, no process r-delivers twice the same message (no duplication). • Termination-1. If a non-faulty process r-broadcasts a message m, it r-delivers m.

• Termination-2. If a process r-delivers a message m, every non-faulty process r-delivers the message m.

Let us notice that in the last item, the process that r-delivers m can be faulty or non-faulty. It is easy to see that this communication abstraction satisfies the following properties.

• The non-faulty processes r-deliver the same set M of messages, which includes all the the messages they r-broadcast and a subset of the messages r-broadcast by faulty processes. • A faulty process r-delivers a subset of the messages in M . This abstraction is easy to implement. When a process invokes R_broadcast(m), it sends a copy of m to each process, and when a process receives a message m for the first time it forwards it to the other processes (except its sender). It is easy to see that an invocation of R_broadcast() generates at most O(n 2 ) sending of m.

Reliable broadcast in the presence of Byzantine processes (BRB) In the Byzantine failure context, it is not possible to control the message r-deliveries of the Byzantine process. The definition becomes the following one.

• If a non-faulty process p i r-delivers a message m from a non-faulty process p j , m has previously been r-broadcast by p j . • Integrity. Assuming all the messages are different, no non-faulty process r-delivers twice the same message (no duplication). • Termination-1. If a non-faulty process r-broadcasts a message m, it r-delivers m.

• Termination-2. If a non-faulty process r-delivers a message m, (whatever the sender of m) every non-faulty process r-delivers the message m.

Similarly to the case of crash failures, the following agreement property follows from the previous properties: the non-faulty processes delivers the same set of messages M , which contains (at least) all the messages they r-broadcast.

On Byzantine reliable broadcast algorithms Bracha presented in [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF] an elegant signature-free algorithm, which implements the reliable broadcast abstraction in the presence of asynchrony and up to t < n/3 Byzantine processes. It is proved in [START_REF] Bracha | Asynchronous Byzantine agreement protocols[END_REF][START_REF] Bracha | Asynchronous consensus and broadcast protocols[END_REF] that t < n/3 is an upper bound for the number of Byzantine processes, hence Bracha's algorithm is optimal from a t-resilience point of view. From an operational point of view, this algorithm is based on a double echo mechanism of the value broadcast by the sender process. For each application message, this algorithm requires three consecutive communication steps, and generates (n -1)(2n + 1) implementation messages.

It is natural that, as it is a fundamental communication abstraction, Byzantine reliable broadcast has been addressed by many authors. Here are a few recent results.

• The BRB algorithm presented in [START_REF] Imbs | Trading t-resilience for efficiency in asynchronous Byzantine reliable broadcast[END_REF], implements the broadcast of an application message with only two communication steps (single echo mechanism), two message types, and n 2 -1 protocol messages. The price to pay for this gain in efficiency is a weaker t-resilience, namely t < n/5. Hence, this algorithm and Bracha's algorithm differ in the trade-off t-resilience versus message/time efficiency.

• Scalable BRB is addressed in [START_REF] Guerraoui | Scalable Byzantine reliable broadcast[END_REF]. The issue is here not to pay the O(n 2 ) message complexity cost. To this end, the authors use a non-trivial message-gossiping approach which allows them to design a sophisticated BRB algorithm satisfying fixed probability-dependent properties.

• BRB in dynamic systems is addressed [START_REF] Guerraoui | Dynamic Byzantine reliable broadcast[END_REF]. Dynamic means that a process can enter and leave the system at any time. In their article the authors present an efficient BRB algorithm for such a context. This algorithm assumes that, at any time, the number of Byzantine processes present in the system is less than one third of total number of processes present in the system.

• An efficient algorithm for BRB with long inputs of ℓ bits using lower costs than ℓ single-bit instances is presented in [START_REF] Nayak | Improved extension protocols for Byzantine broadcast and agreement[END_REF]. This algorithm, which assumes t < n/3, achieves the best possible communication complexity of Θ(nℓ) input sizes. This article also presents an authenticated extension of the previous algorithm.

Further Readings

The reader interested in dissymetric progress conditions will consult [START_REF] Imbs | A liveness condition for concurrent objects: x-wait-freedom[END_REF][START_REF] Imbs | On asymmetric progress conditions[END_REF][START_REF] Taubenfeld | The computational structure of progress conditions and shared objects[END_REF]. A tutorial on the notion of universality in crash-prone asynchronous message-passing systems is presented in [START_REF] Raynal | The notion of universality in crash-prone asynchronous message-passing systems: a tutorial[END_REF]. There are several textbooks entirely devoted to fault-tolerant distributed computing, e.g. [START_REF] Attiya | Distributed computing: fundamentals, simulations and advanced topics[END_REF][START_REF] Ch | Reliable and secure distributed programming[END_REF][START_REF] Garg | Elements of Distributed Computing[END_REF][START_REF] Herlihy | The art of multiprocessor programming[END_REF][START_REF] Kshemkalyani | Distributed computing: principles, algorithms and systems[END_REF][START_REF] Lamport | Specifying systems[END_REF][START_REF] Lynch | Distributed algorithms[END_REF][START_REF] Raynal | Concurrent programming: algorithms, principles and foundations[END_REF][START_REF] Raynal | Distributed algorithms for message-passing systems[END_REF][START_REF] Raynal | Fault-tolerant message-passing distributed systems: an algorithmic approach[END_REF][START_REF] Santoro | Design and analyis of distributed algorithms[END_REF][START_REF] Taubenfeld | Synchronization algorithms and concurrent programming[END_REF] to cite a few. Differently, the textbook [START_REF] Raynal | Distributed algorithms for message-passing systems[END_REF] is entirely devoted to algorithms for failure-free asynchronous distributed systems.

In the today blockchain-dominated technology, the previous readings could help better understand what can be done and which are the assumptions needed to obtain provably reliable distributed software.

Acknowledgments

This work was partially supported by the French ANR project ByBLoS (ANR-20-CE25-0002-01) devoted the modular design of building blocks for large-scale trustless multi-users applications.