Colette Johnen
email: colette.johnen@labri.fr

Luciana Arantes
email: luciana.arantes@lip6.fr

Pierre Sens
email: pierre.sens@lip6.fr

FIFO and Atomic broadcast algorithms with bounded message size for dynamic systems

Keywords: Theory of computation, Distributed algorithms, dynamic graphs, communication primitive, FIFO broadcast, Causal Broadcast, Atomic Broadcast, bounded message size

may come

FIFO and Atomic broadcast algorithms with bounded message size for dynamic systems

I. INTRODUCTION

Many applications in distributed message-passing system (e.g. publish subscriber systems, permission-based mutual exclusion, replicated server systems, etc.) use group communication broadcast primitives to disseminate a message to all processes of the system. They are usually implemented on top of a pointto-point network. Existing broadcast primitives often provide reliability properties, imposing constraints on the order of message delivery by processes. Some examples of message ordering are FIFO, causal, and total order [START_REF] Hadzilacos | A modular approach to fault-tolerant broadcasts and related problems[END_REF]. Another feature that a broadcast can present is termination detection which ensures that if a process broadcasts a message it will be aware that the message has been delivered by all correct processes within a finite time.

In this article we are particularly interested in FIFO broadcast which is a reliable broadcast that guarantees that messages broadcast by the same sender are delivered in the order they were broadcast. FIFO broadcast provides application ordering semantics of messages broadcast by the same sender and are thus used by applications where, for instance, the sender's actions or updates to sender's replicated data must be applied in FIFO order by all processes. Such a message ordering is usually implemented with the sender including in each This study was partially supported by ANR project ESTATE : ANR-16 CE25-0009-03. message a sequence number which is incremented at every new broadcast. By keeping a buffer to temporarily store out of order messages, processes deliver the sender's messages respecting their sequence number order [START_REF] Hadzilacos | A modular approach to fault-tolerant broadcasts and related problems[END_REF]. We should point out that since the sequence number values are not bounded, such an implementation may be unfeasible for long-term applications with high broadcast frequency.

The majority of broadcast algorithms of the literature have been proposed for unreliable static distributed systems whose nodes and/or links can fail but the point-to point communication network is fixed and process membership is known [START_REF] Hadzilacos | A modular approach to fault-tolerant broadcasts and related problems[END_REF], [START_REF] Défago | Total order broadcast and multicast algorithms: Taxonomy and survey[END_REF], [START_REF] Cachin | Introduction to Reliable and Secure Distributed Programming[END_REF], [START_REF] Aguilera | On quiescent reliable communication[END_REF]. However, many current distributed computing systems are usually unstructured, self-organizing, and, like MANETs (mobile ad-hoc networks) or Mobile Robot Networks [START_REF] Michael | Maintaining connectivity in mobile robot networks[END_REF], support nodes' mobility. Therefore, the network communication structure varies and the temporal variations in the network topology imply that these systems cannot be viewed as a static connected graph with fixed paths between nodes established before the broadcast of messages. The communication connection graph is dynamic and a path between two nodes, denoted journey, is built dynamically over the time. On the other hand, to guarantee dissemination of messages in dynamic networks, recurrent connectivity among nodes is a fundamental assumption for broadcast algorithms.

By considering an asynchronous systems with fixed constant number N of processes communicating through a dynamic network that ensures recurrent connectivity, we propose in this article a FIFO broadcast algorithm with both termination detection and bounded message structure for controlling sender's messages ordering. Processes execute in synchronous round and, since they do not fail, thus the membership of the system does not change. The number of processes N is known by all processes but not the system membership which they discover by executing the algorithm. Due to the dynamics of the network links, messages can be lost. Every message is identified by a counter plus a label value. The former is bounded to 2N and the latter varies from 0 to 2. Since a message, besides the broadcast data, includes the sender's identification, the counter, and a 2-bit timestamp vector with N entries, its requires at most 2N + O(log(N )) + msgSize bits where msgSize is the size bound in bits of the broadcast data.

In order to model the dynamics of the network, we apply the Class T C R (recurrent connectivity) of Time-varying Graph (TVG) formalism [START_REF] Casteigts | Timevarying graphs and dynamic networks[END_REF]. In the class T C R , at any point in time, every vertex can reach all others through a journey (i.e. the equivalent of a path in static graph). Without a journey from the vertex s to r starting after t, s cannot send message to r at or after t whatever is the routing mecanism used. Note that the temporal length of a journey (i.e. the equivalent of the path length in static graph) is unbounded in the Class T C R . So, the broadcast delay cannot be bounded in the Class T C R . If the dynamic graph belongs to the Class T C B (∆) (i.e., at any point in time, every vertex can reach all others through a journey whose the temporal length is at most ∆), a broadcast requires at most ∆ rounds.

By calling the FIFO broadcast and delivery primitives of the new algorithm, we present a second algorithm that easily implements a FIFO total order (atomic) broadcast.

As discussed in the Related Work Section, some existing works have proposed broadcast algorithms for some classes of dynamic networks [START_REF] Dell | Information dissemination in highly dynamic graphs[END_REF], [START_REF] Casteigts | Deterministic computations in time-varying graphs: Broadcasting under unstructured mobility[END_REF], [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF], [START_REF] Raynal | A simple broadcast algorithm for recurrent dynamic systems[END_REF], [START_REF] Casteigts | Shortest, fastest, and foremost broadcast in dynamic networks[END_REF], [START_REF] Gómez-Calzado | A connectivity model for agreement in dynamic systems[END_REF], [START_REF] Ahmadi | The cost of global broadcast in dynamic radio networks[END_REF] for subclasses of T C R . They mainly focus on the efficiency of information dissemination in terms of number of rounds, giving some lower bounds for different dynamic graph classes. They do not study the delivery order of a sequence of messages from one emitter; neither the size of broadcast messages to ensure FIFO order property.

The rest of the paper is organized as follows. Section II discusses some related work while Section III introduces some concepts and the computational model. Sections V and VI respectively present the proposed FIFO broadcast algorithm and its proofs of correctness. The FIFO, total order algorithm is described in Section VII. Finally, Section VIII concludes the paper.

II. RELATED WORK

The problem of broadcasting messages has been widely studied in the message passing model [START_REF] Marandi | Ring paxos: Highthroughput atomic broadcast[END_REF], [START_REF] Lundström | Self-stabilizing uniform reliable broadcast[END_REF], in wireless networks [START_REF] Blywis | Gossip routing in wireless mesh networks[END_REF], [START_REF] Haas | Gossip-based ad hoc routing[END_REF] or overlay network [START_REF] Eugster | Lightweight probabilistic broadcast[END_REF], [START_REF] Frey | Heterogeneous gossip[END_REF] using gossip protocols.

An extensive survey, collecting around sixty total order broadcast algorithms in message passing model, is presented in [START_REF] Défago | Total order broadcast and multicast algorithms: Taxonomy and survey[END_REF] where the algorithms are classified according to the mechanism they use to order messages: communication history, privilege-based, moving sequencer, fixed sequencer, and destinations agreement. It is worth pointing out that total order broadcast primitives are a fundamental building block for a lot of distributed systems, applications, algorithms and services such as State Machine Replication [START_REF] Rajsbaum | 60 years of mastering computing through sequential thinking[END_REF], managing replicated database [START_REF] Agrawal | Exploiting atomic broadcast in replicated databases (extended abstract)[END_REF], [START_REF] Stanoi | Using broadcast primitives in replicated databases[END_REF], [START_REF] Pedone | The database state machine approach[END_REF], sequential consistency [START_REF] Baldoni | Implementing a regular register in an eventually synchronous distributed system prone to continuous churn[END_REF], [START_REF] Perrin | On composition and implementation of sequential consistency[END_REF], shared registers implementation with Byzantine failure [START_REF] Bonomi | Multi-writer regular registers in dynamic distributed systems with byzantine failures[END_REF] or continuous churns [START_REF] Attiya | Emulating a shared register in a system that never stops changing[END_REF].

In the gossip model, messages are propagated at each round either with a certain probability to all the neighbors or to a subset of neighbors chosen at random. Such a model is different from a dynamic graph model since each edge is randomly chosen and not in a adversarial way. In [START_REF] Clementi | Information spreading in stationary markovian evolving graphs[END_REF], [START_REF] Clementi | Rumor spreading in random evolving graphs[END_REF], gossip broadcast in edge-Markovian evolving graph is studied. Markovian evolving graphs are dynamic-graph models where the links among a fixed set of nodes change during time according to an arbitrary Markovian rule.

Fewer works study broadcasting in the presence of dynamic changes. The seminal work of [START_REF] Awerbuch | Polynomial end-to-end communication[END_REF] considered the problem of end-to-end message delivery under an assumption of eventual connectivity. Some papers address broadcasting under churn scenario handling constant join and leave of nodes in overlay networks [START_REF] Ghodsi | Selfcorrecting broadcast in distributed hash tables[END_REF], [START_REF] Li | An efficient broadcast algorithm in distributed hash table under churn[END_REF] but without considering changes in the network topology.

The work in [START_REF] Dell | Information dissemination in highly dynamic graphs[END_REF] shows that it is possible to flood a single message to all nodes which eventually stop sending messages in 1-interval, a weak connectivity model in which the communication graph may change from round to round, nevertheless it stays connected all times. Such a class of dynamic networks is contained in

T C B (N ) T C R .
The T-interval connectivity model was introduced in [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF]. In this model, for every T (T ≥ 1), consecutive rounds, a stable connected spanning tree exists. A T-interval connected dynamic graph is also a 1-interval connected one. In [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF], lower bounds of rounds to disseminate k pieces of information without termination detection to all the nodes in a T-interval connected dynamic graph are presented. In [START_REF] Ahmadi | The cost of global broadcast in dynamic radio networks[END_REF], the authors propose a variant of T-interval, denoted T-interval k-connected, where there exists a k-vertex-connected stable subgraph during T rounds. Any k-vertex-connected graph belongs to the T C R class. They study the single-message broadcast problem in this model providing a probabilistic protocol.

The authors in [START_REF] Casteigts | Deterministic computations in time-varying graphs: Broadcasting under unstructured mobility[END_REF], [START_REF] Casteigts | Shortest, fastest, and foremost broadcast in dynamic networks[END_REF] focus on broadcasting with termination detection over three different subclasses of the dynamic TVG class T C R : eventual, bounded, or periodic reappearance of links. They compare the feasibility of three variants of the broadcast problem minimizing the delivery date at every node, the number of hops, and overall duration of broadcast, respectively.

In [START_REF] Raynal | A simple broadcast algorithm for recurrent dynamic systems[END_REF], Raynal et al. proposed a reliable broadcast algorithm suited to the class of dynamic systems where all links appears and disappears infinitely often (i.e., a subclass of T C R ). The broadcast is based on a spanning-tree on top of which processes forward received messages to their respective neighbors.

Finally, in [START_REF] Gómez-Calzado | A connectivity model for agreement in dynamic systems[END_REF], the authors present a hierarchy of three classes of time-varying graphs and provide a solution for each class to the problem of Terminating Reliable Broadcast. The stronger class studied is T C B (∆).

III. BACKGROUND

In this section, we present the FIFO and Total order specifications implemented by our algorithms as well as some concepts about time varying graph and their classes on which are solution is based.

A. Broadcast with termination detection

The following specification of FIFO broadcast is an adaptation of the original one [START_REF] Hadzilacos | A modular approach to fault-tolerant broadcasts and related problems[END_REF] in a system where all processes are correct.

• Validity: If a process p invokes Broadcast(m), then it eventually executes Deliver(id(p), m). • Agreement: If a process executes Deliver(id, m), then all other processes eventually execute Deliver(id, m) • Integrity: a process delivers at most once the message (id(p), m) and only if p has previously invoked Broadcast(m) • FIFO order: If process p invokes Broadcast(m2) after invoking Broadcast(m1) then every process delivers (id(p), m2) after having delivered (id(p), m1). A broadcast with termination detection requires that, if a process p invokes Broadcast(m), then p eventually detects that all processes have delivered the message (id(p), m) within finite time.

Similarly, the specification of atomic (total order) broadcast can be also adapted when all processes are correct, by applying the above three definitions of Validity, Agreement, and Integrity properties and the total order property which states that all processes deliver the broadcast messages in the same order. More precisely:

• Total order: If a process delivers (id, m) before delivering (id , m ) then all processes deliver (id, m) before delivering (id , m ). The atomic broadcast and consensus are equivalent problems [START_REF] Chandra | Unreliable failure detectors for reliable distributed systems[END_REF].

B. Dynamic Graphs

We model the network dynamics using the dynamic graph (DG for short) paradigm [START_REF] Charron-Bost | The firing squad problem revisited[END_REF].

For any directed graph G, we denote by V (G) its vertex set and by A(G) its set of directed edges. A dynamic graph G with vertex set V (DG for short) is an infinite sequence of directed loopless graphs G 1 , G 2 , ... such that V (G i ) = V , for every i ∈ N * . For every i ∈ N * , we denote by G i the dynamic graph G i , G i+1 , ... with vertex set V , i.e., the suffix of G starting from position i.

A journey J can be thought as a path over time from a starting vertex p 1 to a destination vertex q k , i.e., J is a finite non-empty sequence of pairs J = (e 1 , t 1 ), (e 2 , t 2 ), ..., (e k , t k ) where ∀i ∈ {1, . . . , k}, e i = (p i , q i ) ∈ A(G ti ) and i < k ⇒ q i = p i+1 ∧ t i < t i+1 . We respectively denote by dpt(J ) and arr(J ) the starting position t 1 and the arrival position t k of J .

The temporal length of J is equal to arr(J ) -dpt(J ) + 1. We denote by J G (p, q) the set of journeys from p to q in G.

We let

G be the binary relation over V such that p G q if and only if p = q or there exists a journey from p to q in G.

The temporal distance from p to q in G, dG (p, q), is defined as follows: dG (p, q) = 0 if p = q, otherwise dG (p, q) is min{arr(J ) : J ∈ J G (p, q)} (by convention, we let min ∅ = +∞). Roughly speaking, the temporal distance from p to q in G gives the minimum timespan for p to reach q in G. The temporal distance from p to q in G at position i ∈ N * , dG,i (p, q), is the temporal distance from p to q in G i , i.e., dGi (p, q). Similarly, the temporal diameter in G at position i ∈ N * is the maximum temporal distance at position i between any two vertices in G.

For all previous notations, we omit the subscript G when it is clear from the context. TVG Classes. A class of dynamic graphs is defined as a particular set of dynamic graphs.

Class T C R (Recurrent Connectivity), denoted by C 5 in [1]: at any point in time, every vertex can reach all the others through a journey. Formally,

G ∈ T C R iff ∀p ∈ V, ∀q ∈ V, ∀i ∈ N * , p Gi q.
Class T C B (∆) (Bounded Temporal Diameter), denoted by T C(∆) in [START_REF] Gómez-Calzado | A connectivity model for agreement in dynamic systems[END_REF]: every vertex is always at temporal distance at most ∆ from all other vertices. Formally,

G ∈ T C B (∆) iff ∀p ∈ V, ∀q ∈ V, ∀i ∈ N * , dG,i (p, q) ≤ ∆.

IV. COMPUTATIONAL MODEL

We consider the computational model defined in [START_REF] Barjon | Maintaining a distributed spanning forest in highly dynamic networks[END_REF], [START_REF] Charron-Bost | The firing squad problem revisited[END_REF]. We assume a distributed system composed of a set V of N processes. Each process has a local memory, a local sequential and deterministic algorithm, and message exchange capabilities. We assume that each process p has a unique identifier (ID for short), denoted id(p) and taken from an arbitrary domain IDSET totally ordered by <. Processes communicate by message passing through an interconnected network that evolves over the time. The dynamic topology of the network is modeled by a dynamic graph G = G 1 , G 2 , ... with vertex set V , i.e., the set of processes. Processes execute their local algorithms in synchronous rounds. For every i ∈ N * , the communication network at Round i is defined by G i , i.e., the graph at position i in G. ∀p ∈ V , ∀i ∈ N * , we denote by IN (p) i = {q ∈ V : (q, p) ∈ A(G i )} the set of p's neighbors at Round i. IN (p) i is assumed to be unknown by p, whatever be the value of i. A process q belongs to IN (p) i if the message q sent in round i is received by p during the round i, i.e., the communication channel from q to p exists and the message from q is not lost.

A distributed algorithm A is a collection of N local algorithms A(p), one per process p ∈ V (n.b., different processes may have different codes). At each round, the state of each process p ∈ V in A is defined by the values of its variables in A(p). Some variables may be constant in which case their values are predefined and their value cannot be corrupted. In the presented algorithms, process identifier and the number of processes are constant variables.

A configuration of A for V is a vector of N components γ = (s 1 , s 2 , . . . , s N ), where s 1 to s N represent the states of the processes in V . Let γ 1 be the initial configuration of A for V . For any (synchronous) round i ≥ 1, the system moves from the current configuration γ i to some configuration γ i+1 , where γ i (resp., γ i+1 ) is the configuration at the beginning (resp., the end) of Round i. Such a configuration change is atomically performed by every process p ∈ V according to the following three steps, defined in its local algorithm A(p):

1) p sends a message consisting of all or a part of its local state in γ i by calling the primitive SEND(). The messages of others processes in transit at p are also sent by calling the primitive SEND() on them. 2) using Primitive RECEIVE(), p receives all messages sent by processes in IN (p) i ; 3) p computes its state in γ i+1 . An execution of a distributed algorithm A in a dynamic graph G = G 1 , G 2 , ... is an infinite sequence of configurations γ 1 , γ 2 , . . . of A for V such that ∀i > 0, γ i+1 is obtained by executing a synchronous round of A on γ i based on the communication network at Round i, i.e., the graph G i .

V. FIFO BROADCAST WITH TERMINATION DETECTION Algorithm 2 provides FIFO Broadcast primitives with termination detection for Class T C R and bounded message size, assuming that the number of processes N of the system is known. Variables and macros are defined in Algorithm 1. We should point out that broadcasting with detection of termination cannot be solved in dynamic networks without additional knowledge (e.g., the number of processes) [START_REF] Casteigts | Shortest, fastest, and foremost broadcast in dynamic networks[END_REF].

The algorithm is based on rounds. At every round, a process s either broadcasts an application message, if the latter exists, or an empty one (⊥). In the first case, the message is delivered by the N processes within the current round. A bounded sequence number, denoted label, is assigned to every broadcast message.

As the network is dynamic, every process s keeps the current broadcast message as well as the most recent ones it received from each other process of the system in a local buffer. Every message also contains a N size timestamp vector: if the message was sent by s, the entry corresponding to s keeps the label of the last message it broadcast, otherwise (r = s) the value of this entry corresponds to the label of the last message broadcast from s received by r, i.e., an acknowledgement from r for the reception of s'message. The local buffer of a process is updated upon reception of a message, keeping, for each other process, only the most recent one. Process s continually sends the messages of its local buffer. The s'current broadcast terminates only after receiving from every other process r a message whose timestamp vector entry related to s acknowledges the reception of the message in question. Then, s starts its next broadcast: either an application message or (⊥).

Labels range from the finite set {0, 1, 2}. Only these three label values are sufficient to distinguish different messages in transit broadcast by a process. In other words, if, at each broadcast of a new message, process s updates the label assigned to the message to (i + 1) mod 3, our algorithm ensures that there will never exist two messages in transit whose timestamp vector entry related to s is equal to i, corresponding to two different messages broadcast by s. In fact, during the i + 3 th broadcast by s, all messages from r = s in transit were sent at or after the reception by r of the i + 1 th message broadcast by s, i.e., there is no message in transit (in a process local buffer) from r which acknowledged a previous s'broadcast message with label i. Consequently, tagging broadcast messages with labels within {0, 1, 2} does not induce ambiguity to distinguish message acknowledgments. • queueBrdcst(p) : queue with the messages that p has to broadcast; initially, the queue is empty.

A. Description of the algorithm

• ack(p) : set of processes having received the current broadcast message, initially the set is {id(p)}.

• msgB(p) : message being forwarded, initially, its value is brdcst⊥.

• myCnt(p) : count the number of timestamp updates during the current broadcast, initially its value is 0.

• myT S(p)[] : myT S(p)[q] keeps the timestamp of the current or last message broadcast by q and received by p; initially, myT S(p)[p] = 1 and myT S(p)[q] = 0 if q = p • M sgsT (p) : set that keeps messages in transit in the format id, m, updtCnt, T S ∈ IDSET × msgT ype × N × {0, 1, 2} N . Initially, the set contains the single message id(p), msgB(p), myCnt(p), myT S(p) .

Macros and Predicates:

• i ⊕ j :

(i + j) mod 3 • i ⊕ : i mod 3 • (ts1, cpt1) > ⊕ (ts2, cpt2) iff (ts1 = ts2 ⊕ 1) or ((ts1 = ts2) and (cpt1 > cpt2))
Whenever the application layer of p invokes the procedure FD brcst in order to broadcast a message, the latter is enqueued in queueBrdcst(p). At the end of the current p' broadcast, the algorithm broadcasts the first message of queueBrdcst(p) (if-block starting in line 21).

At the beginning of every round, by calling the SEN D primitive, p sends all the messages in M sgsT (p) (line 4). p will insert its current message in M sgsT (p) at the end of the round (line 26). This message will then be sent at the beginning of the next round. The content of the message is composed by the current values of p's local variables msgB, myCnt, and myT S (see local variables description of Algorithm 1). Hence, a message msg = id(p), m, updtCnt, T S has the following four fields: • id(p): the identifier of the sender; • m : the data of the message (application data or brdcst⊥).

If m = brdcst⊥, m is not delivered. In this case, msg contains only acknowledgments; • updtCnt is the current value of the timestamp update counter; • T S is a vector of size N that contains both the acknowledgments and the label of the msg. Precisely, the label of msg = id(p), m, updtCnt, T S sent by p is T S[p], while for q = p, T S[q] is the label of message sent by q, acknowledged by p.

Before inserting in M sgsT (p) a new message broadcast by q, the current q's message kept in M sgsT (p) is removed from it (lines 9-11 if q = p, otherwise lines [START_REF] Perrin | On composition and implementation of sequential consistency[END_REF][START_REF] Bonomi | Multi-writer regular registers in dynamic distributed systems with byzantine failures[END_REF]. Thus, M sgsT (p) contains at most a single message of q at any configuration. The ith broadcast of a message issued by process s, named m(s, i), takes several rounds which comprise the delay to carry the data kept in msgB(s) to every process plus the delay taken for the reception by p of the acknowledgments regarding m(s, i) from the other processes. Process s starts its i + 1th broadcast during the round in which its ith broadcast has finished. In this case, s has received an acknowledgment from every other process (i.e., |ack(s)| = N -if-block starting at line 18 -). This round is named t s,i+1 .

If the application has called the FD brcst primitive, at least i+1 times before the beginning of the i+1th broadcast by s (i.e., queueBrdcst(s) is not empty) then m(s, i + 1) = msgB(s) is a message dequeued from queueBrdcst(s). In this case s delivers m(s, i + 1) by calling FD dlr(id(s), m(s, i + 1)) (ifline 23). Otherwise (i.e., queueBrdcst(s) is empty), m(s, i+1) is set to brdcst⊥ (if-else-block starting at line 21).

In both cases, the set ack(s) contains just s, i.e., the only process having delivered m(s, i + 1) (ack(s) = {s} -line [START_REF] Frey | Heterogeneous gossip[END_REF].

Then, myT S(s)[s] value is updated to (i+1) ⊕ (line 20) which will be the label of the messages sent by s during the i + 1th broadcast.

Let r be a process distinct of s. myT S(r)[s] contains the label of the last s's broadcast data m, received by r. At the beginning of the ith broadcast of s this value is i ⊕ 2 = i -1 mod 3. When r receives for the first time s's message sent during its ith broadcast, myT S(r)[s] is set to myT S(r)[s] ⊕ 1 = msg.T S[s] = i ⊕ = i mod 3. This round is called t s,i (r). Hence, r will verify the if-condition of line 14 and, if m(s, i) is an application data, r will deliver it by calling FD dlr(id(s), m(s, i)) (line 17). Then, myT S(r)[s] will be updated to the value i ⊕ (line 15) and, therefore, the next messages sent by r, which will have the label msg.T S[s] = myT S(r)[s] = i ⊕ , acknowledge the reception of m(s, i).

When s receives a message of r acknowledging the reception of m(s, i) (i.e., T S[r] = i ⊕ ), r is inserted in the set ack(s) since, in this case, r has received m(s, i) (line 13).

During the ith broadcast, s does not send at each round the same message. Nevertheless, their field m has the same value m(s, i) = msgB(s) or m(s, i) = brdcst⊥ as well as the label value T S[s] = i ⊕ = i mod 3. Both of them are only changed during the execution of the if-block starting at line 18 (i.e., during the round t s,i+1 , ending the ith broadcast). It is worth pointing out that messages of s sent during two consecutive broadcasts have distinct labels whose values are taken from the finite set {0, 1, 2}.

On the other hand, during the ith broadcast of s, the message sent by s changes whenever the acknowledgment array myT S is updated (line block [START_REF] Lundström | Self-stabilizing uniform reliable broadcast[END_REF][START_REF] Blywis | Gossip routing in wireless mesh networks[END_REF][START_REF] Haas | Gossip-based ad hoc routing[END_REF]. At every update, s increments myCnt value (line 16). It is reinitialized to 0 at the beginning of each broadcast (lines [START_REF] Frey | Heterogeneous gossip[END_REF][START_REF] Rajsbaum | 60 years of mastering computing through sequential thinking[END_REF][START_REF] Agrawal | Exploiting atomic broadcast in replicated databases (extended abstract)[END_REF][START_REF] Stanoi | Using broadcast primitives in replicated databases[END_REF][START_REF] Pedone | The database state machine approach[END_REF][START_REF] Baldoni | Implementing a regular register in an eventually synchronous distributed system prone to continuous churn[END_REF]. The label and updtCnt values of messages are used by a process r = s to choose which messages of s to keep in its set M sgsT (r) -(if-condition at line 8). In section VI, we prove that a process r keeps in transit, i.e., in M sgsT (r), only the most recent message of s (Lemma 4).

VI. PROOF OF CORRECTNESS OF FIFO BROADCAST

PRIMITIVES IN CLASS T C R A. Predicate W F Brdcst(s, i)
In a configuration γ, a message msg is in transit if it exists a process q, such that msg ∈ M sgsT (q). We denote t s,i the round where s starts its ith broadcast.

The verification of predicate W F Brdcst(s, i) in the configuration reached after t s,i (i.e., γ s,i ) allows to establish that every process delivers once m(s, i) during the time interval [t s,i , t s,i+1 [ if m(s, i) = brdcst⊥, otherwise no s-message is delivered (Theorem 1). W F Brdcst(s, 1) is verified in the configuration γ s,1 . We will prove that the predicate W F Brdcst(s, i) is verified in the configuration γ s,i (Lemma 6), for all i ∈ N * . Definition 1 (predicate W F Brdcst(s, i)): t s,1 is 0, a virtual round reaching the configuration γ 1 . For i > 1, t s,i denotes the round where s executes the line block 19-24 for the i-1th time.

γ s,i is the configuration reached after the round t s,i .

m(s, i) is the value of msgB(s) in γ s,i .

The predicate W F Brdcst(s, i) is defined as : a myT S(s)[s] = i ⊕ and ack(s) = {s} and myCnt(s) = 0 b id(s), msgB(s), myCnt(s), myT S(s) ∈ M sgsT (s) s,i).a ensures that the local s's variables have a correct value. Predicates W F Brdcst(s, i).b and W F Brdcst(s, i).c ensure that any s-messages in transit are not old (i.e., their label is i ⊕ 2 except the one that has the label i ⊕ , this one carries m(s, i)). Predicate W F Brdcst(s, i).d ensures that any process r = s is ready to deliver a s-message with label i ⊕ . Let q be a process distinct of s. Predicate W F Brdcst(s, i).e ensures that the q-messages in transit are not too old -their s-acknowledgment (i.e., T S[s] value) is not i ⊕ -. This last property guarantees that during [t s,i , t s,i+1 [, the set ack(s) contains only process that have received and handled m(s, i). Thus, the broadcast ends after every process has actually received m(s, i).

c ∀r ∈ V /{s}, if id(s), -, -, T S ∈ M sgsT (r) then T S[s] = i ⊕ 2 d ∀r ∈ V /{s}, myT S(r)[s] = i ⊕ 2 e ∀r ∈ V , if id, -, -, T S ∈ M sgsT (r) then id = id(s) or T S[s] = i ⊕ Predicate W F Brdcst(
In Section VI-B, we prove that, if m(s, i) = brdcst⊥, and the predicate W F Brdcst(s, i) is verified in γ s,i then at the end of ith broadcast of s, m(s, i) is delivered by every process. In the Section VI-C, we establish that the ith broadcast of s terminates and also that W F Brdcst(s, i) is verified in γ s,i for all i values.

We conclude that the broadcast primitives of Algorithm 2 ensure FIFO broadcasts with detection of termination (corollary 3). If the dynamic graph belongs to the Class T C B (∆), a broadcast requires 2∆ rounds.

In section VI-D, we establish that the value of updtCnt field of any message is bounded by 2N . Hence a message requires at most 2N +O(log(N ))+msgSize bits with msgSize being the bound of the data size to broadcast (application data or brdcst⊥).

B. Proof of the Algorithm Safety

Lemma 1: Let assume that in the configuration γ s,i , W F Brdcst(s, i) is verified. In the configurations of [γ s,i , γ s,i+1 [, every s-message in transit labeled i ⊕ contains m(s, i). No s-message in transit has the label i ⊕ 1 in the configurations of [γ s,i , γ s,i+1 [.

Proof: The verification of W F Brdcst(s, i).b and of W F Brdcst(s, i).c in the configuration γ s,i ensure that (1) a single s-message having the label i ⊕ is in transit and the data carried by the message is m(s, i); (2) no s-message in transit has the label i ⊕ 1. A s-message having the label i ⊕ 1 will be in transit, only after the execution of the if-block of line 18, which happens within t s,i+1 round.

The mailbox of p contains the message msg during the round t if and only if ∃q ∈ IN (p) t such that msg ∈ M sgsT (q) in the configuration γ t .

Let r be a process of V /{s}. We denote t s,i (r), the first round after t s,i when the r mailbox contains a s-message msg = id, m, -, T S with label i ⊕ . We denote γ s,i (r) the configuration reached after the round t s,i (r).

Lemma 2: Let assume that in the configuration γ s,i , W F Brdcst(s, i) is verified. In the configurations of

[γ s,i , γ s,i (r)[, a s-message in M sgsT (r) has label i ⊕ 2 and myT S(r)[s] = i ⊕ 2.
During t s,i (r), r executes the if-block of line 14 when r handles a s-message.

In the configurations of [γ s,i (r), γ s,i+1 [, a s-message in M sgsT (r) has thus label i ⊕ and myT S(r)[s] = i ⊕ .

Proof: In the configuration γ s,i , myT S(r)[s] = i ⊕ 2 as W F Brdcst(s, i).d is verified. During the rounds of time interval [t s,i + 1, t s,i+1 (r)[, any s-message in r's mailbox has the label i ⊕ 2 (Lemma 1).

Thus, during [t s,i + 1, t s,i+1 (r)[, r handles only s-message labeled by i ⊕ 2. So, r does not execute the if-block of line 14 when handling s-messages. Therefore, in the configurations of

[γ s,i , γ s,i+1 (r)[, myT S(r)[s] = i ⊕ 2 and if r has in transit a s-message then it is labeled with i ⊕ 2.
During t s,i (r), r executes the if-block of line 14 to handle msg, delivering (id(s), m), if m = brdcst⊥. Then, myT S(r)[s] = i ⊕ and it keeps such a value until the r's mailbox contains a s-message labeled i ⊕ 1. According to Lemma 1, during [t s,i (r), t s,i+1 [, r's mailbox does not contain any s-message labeled i ⊕ 1. Consequently, myT S(r)[s] = i ⊕ and r handles only s-message with label i ⊕ .

Observation 1: Let i ∈ N * . Let also assume that in the configuration γ s,i , W F Brdcst(s, i) is verified. In the configurations of [γ s,i , γ s,i+1 [, myT S(s)[s] = i ⊕ and id(s), m(s, i), -,labeled by i ⊕ belongs to M sgsT (s).

Definition 2 (round t s,i (r)): Let r be a process of V /{s}. We denote t s,i (r), the first round after t s,i where s executes the if-block in line 12 to insert id(r) in ack(s).

Lemma 3:

We have t s,i < t s,i (r) < t s,i (r) ≤ t s,i+1 in γ s,i , if W F Brdcst(s, i) is verified.
Proof: A message id, -, -, T S acknowledges m(s, i) iff T S(s) has the value i ⊕ .

Since W F Brdcst(s, i).d and W F Brdcst(s, i).e are both verified in γ s,i , there is no r-message in transit in the configurations of [γ s,i , γ s,i+1 (r)[ acknowledging m(s, i), as T S(r)[s] = i ⊕ 2. We denote t s,i (r), the first round after t s,i where the s mailbox contains a r-message acknowledging m(s, i). The s mailbox contains a r-message acknowledging m(s, i) in the tth round, only if there exists a r-message acknowledging m(s, i) in transit in the configuration γ t . We have t s,i (r) > t s,i (r). We have t s,i (r) ≥ t s,i (r) > t s,i (r), as the s mailbox contains a r-message acknowledging m(s, i) during the round t s,i (r). The verification of W F Brdcst(p, i).e in the configuration γ s,i ensures that |ack(s)| = N during [t s,i + 1, t s,i (r)[. Thus, t s,i (r) ≤ t s,i+1 . We conclude that t s,i < t s,i (r) < t s,i+1 as by definition t s,i < t s,i (r).

Definition 3 (configuration γ +

s,i ): Let γ + s,i be the configuration before the round t s,i+1 .

Observation 1, Lemma 1, Lemma 2 and Lemma 3 allows us to establish the following corollary.

Corollary 1: Let i ∈ N * and let r and s be two processes. Assuming that in the configuration γ s,i , W F Brdcst(s, i) is verified. In the configuration γ + s,i , myT S(r)[s] = i ⊕ and if r has in transit a s-message then this message is labeled by i ⊕ and it contains m(s, i). In the configuration γ s,i+1 , W F Brdcst(s, i + 1).a, W F Brdcst(s, i + 1).b, W F Brdcst(s, i + 1).c, and W F Brdcst(s, i + 1).d are verified.

Observation 2: During [γ 1 , γ + s,1 ], every message in transit verifies T S[s] = 2. W F Brdcst(s, 2).e is verified in γ s,2 . We have t s,i+1 = max r∈V /{s} {t s,i (r)}.

Theorem 1: Let assume that in the configuration γ s,i , W F Brdcst(s, i) is verified. During the time interval [t s,i , t s,i+1 [, at most a single s-message is delivered by any process. If m(s, i) = brdcst⊥, then (id(s), m(s, i)) is delivered by every process otherwise no process delivers a s-message during the time interval [t s,i , t s,i+1 [. Proof: Process s delivers a s-message only during the execution of the if-block of lines 18-24, so only during the round t s,i . According to if-block in line 23, No message is delivered if m(s, i) = brdcst⊥. If m(s, i) = brdcst⊥ then i > 1, and s executes the if-else-block of line 21 during the round t s,i ; hence s delivers (id(s), m(s, i)).

Let r = s be a process. During a round where r delivers a s-message, myT S(r)[s] changes its value (if-block of lines [START_REF] Lundström | Self-stabilizing uniform reliable broadcast[END_REF][START_REF] Blywis | Gossip routing in wireless mesh networks[END_REF][START_REF] Haas | Gossip-based ad hoc routing[END_REF]. If i > 1 then r does not execute the line block 9-17 during t s,i according to γ + s,i-1 properties (Corollary 1) and t s,i properties (Lemma 1). During t s,1 = 0, no message is delivered. Lemma 2 establishes that myT S(r)[s] changes its value only once during [t s,i + 1, t s,i+1 [, i.e., at round t s,i (r). In the round t s,i (r), the data of the handled s-message is m(s, i) (Lemma 1). If m(s, i) = brdcst⊥, (id(s), m(s, i)) is delivered (see if-line 17) otherwise no s-message is not delivered.

C. Proof of the Algorithm Liveness

The ith broadcast of s is terminated, if for any process r = s, t s,i (r) exists, and the configuration γ s,i verifies W F Brdcst(s, i) (Observation 2). In this Section, we state that any broadcast of a process s terminates.

The timestamp of a s-message id(s), -, updtCnt, T S is the tuple (T S[s], updtCnt). We note msg.ts the timestamp of message msg. Let msg1 and msg2 be two messages sent by s. The comparison msg1.ts > ⊕ msg.ts is noted msg1 > ⊕ msg2.

We denote msg(r, s, γ) the s-message in M sgsT (r) in the configuration γ, if such a message exists. We denote mb(r, t) the mailbox of r during round t. msg ∈ mb(r, t) if and only if ∃q ∈ IN (r) t such that msg ∈ M sgsT (q) in the configuration before the round t. The set mb(r, t) ∪ {∀s ∈ V, msg(r, s, γ -)} is denoted We denote mb + (r, t).

The relation > ⊕ is used by process r to select which smessage to keep in transit, i.e., during the round t every smessages of mb + (r, t) are discarded except one -if-statement in line 8. Let msg1 the s-message sent in round t and msg2 the s-message sent in round t + 1. The algorithm code ensures that msg2 > ⊕ msg1 or msg1 = msg2. However, the relation > ⊕ is not transitive. Hence, it is necessary to establish the conditions that allow processes to apply the > ⊕ relation in order to compare the sending rounds of two s-messages.

By lack of space, the proof of the following lemma is not presented.

Lemma 4: Let r = s be a process. Let γ -be a configuration in [γ s,i , γ + s,i ]) where W F Brdcst(p, i) is verified in γ s,i . Let t be the round from γ -reaching γ + . If mb + (r, t) contains a smessage then msg(r, s, γ + ) is the latest s-message in mb + (r, t) otherwise msg(r, s, γ + ) does not exist.

Even reusing message labels and timestamps, processes may order s-messages in transit according to their sending round during the time interval [t s,i + 1, t s,i+1 ] if W F Brdcst(p, i) is verified in γ s,i . Thus, every process r, distinct from s, keeps in transit among all received s-messages the most recent one during [t s,i + 1, t s,i+1 ] (Lemma 4). Definition 4 (well-formed configuration): A configuration γ is well-formed if for each process p, it exists i p ∈ N * such that γ ∈ [γ p,ip , γ p,ip+1 [ and W F Brdcst(p, i p ) is verified in γ p,ip . A round of a well-formed configuration is said well-formed. We name γ bad (resp. t bad ) the first configuration (resp. round) that is not well-formed.

According to the definition of well-formed configuration, it exists pb and ib such that γ bad = γ pb,ib and W F Brdcst(pb, ib) is not verified in γ pb,ib . Moreover, according to Observation 2, ib > 2.

By lack of space, the proof of the following lemma is not presented.

Lemma 5: Let p and q be two distinct processes. We name γ a+ ≤ γ bad the configuration after the round ta. The message msg(p, q, γ a+ ) is sent after td if and only if there exists a journey from q to p whose the departure is after td and its arrival is before or at ta. Lemma 6: All configurations are well-formed.

Proof: According to the definition of well-formed configuration, it exists pb and ib such that γ bad = γ pb,ib and W F Brdcst(pb, ib) is not verified in γ pb,ib . More precisely, W F Brdcst(pb, ib).e is not verified in γ pb,ib (Corollary 1). According to Observation 2, we have ib > 2.

Let u and v be two processes with u = pb. In the following, we prove that msg(v, u, γ pb,ib ) is sent at t ∈ ]t pb,ib-2 (u), t pb,ib ]. Let γ be a configuration of [γ pb,ib-2 , γ pb,ib-1 [. Among the u-messages msg = id(u), -, -, T S in transit in γ, only the messages sent during ]t pb,ib-2 (u), t pb,i-1 ] verify T S[pb] = (ib -2) ⊕ . Therefore, the mailbox of pb, during the round t pb,i-2 (u) contains a u-message sent after t pb,ib-2 (u). Thus, there exists a journey from u to pb whose departure is after t pb,ib-2 (u) and its arrival is at or before t pb,ib-2 (u) ≤ t pb,ib-1 according to Lemma 5. If v = pb then the message msg(v, pb, γ pb,ib-1 (v)) is sent after t pb,ib-1 (Lemma 2). According to Lemma 5, there exists a journey from pb to v = pb whose the departure is after t pb,ib-1 and its arrival is at or before t pb,ib-1 (v). Hence, there is a journey from u to v whose departure is after t pb,ib-2 (u) and arrival is at or before t pb,ib-1 (v) ≤ t pb,ib if v = pb, otherwise its arrival is at or before t pb,ib-1 .

Lemma 5 allows us to conclude that msg(v, u, γ pb,ib ) is sent at t ∈ ]t pb,ib-2 (u), t pb,ib ]. As t is well-formed, Lemma 2 establishes that message msg(v, u, γ pb,ib ) = id(u), -, -, T S verifies T S[pb] ∈ {(ib-2) ⊕ , (ib-1) ⊕ }. So W F Brdcst(pb, ib).e is verified in γ pb,ib (i.e., T S[pb] = ib ⊕ ∀u ∈ V /{pb} and ∀v ∈ V ). We conclude that γ bad does not exist.

The following corollary is a consequence of Lemma 6 and Lemma 5.

Corollary 2: Let s and r be two distinct processes. There exists a journey from s to r whose the departure is after t s,i and arrival is t if and only if t s,i (r) ≤ t.

There exists a journey from r to s whose the departure is after t s,i (r) and its arrival is t if and only if t s,i (r) ≤ t.

The two first statements (i.e., liveness) of the corollary that follows is a consequence of the Observation 2, Corollary 2 while the third statement (i.e., safety) is a consequence of the Theorem 1, and Lemma 6 :

Corollary 3: Let s be a process of V and i ∈ N * .

• In a graph of the class T C R with the process set V , γ s,i exists. Proof: For all i ∈ P ositive, in γ s,i , myCnt(s) = 0 (as s executes the line 19 during t s,i ).

During rounds of [t s,i + 1, t s,i+1 [, the value of myCnt(s) is only incremented (line 16) when myT S(s) is updated. The value of myCnt(s) is bounded by 2N in the configurations of [γ s,i + 1, γ s,i+1 [, if s does not update 3 times the acknowledgment value associated to a process r distinct of s (i.e., myT S(s)[r]).

In the sequel, we assume that s updates 3 times myT S(s)[r] during [t s,i +1, t s,i+1 [. Theorem 1 establishes that myT S(s)[r] changes of value only one time during [t r,j + 1, t r,j+1 [ : at round t r,j (s). We conclude that it exists j ∈ N * such that t s,i < t r,j (s) < t r,j+1 (s) < t r,j+2 (s) < t s,i+1 .

Let p be a process distinct of s. There is a journey from s to r starting after t r,j (s) and arriving at or before t r,j+1 (Corollary 2). If p = r, there is a journey from r to p starting after t r,j+1 and arriving at or before t r,j+1 (p). If p = r then t s,i (p) ≤ t r,j+1 (p), otherwise t s,i (r) ≤ t r,j+1 . If p = r, there is a journey from p to r starting after t s,i (p) ≤ t r,j+1 (p) and arriving at or before t r,j+2 . There is a journey from r to s starting after t r,j+2 and arriving at or before t r,j+2 (s). So t s,i (p) ≤ t r,j+2 (s) according to Corollary 2 for every process p in V . After the processing of messages in s' mailbox during the round t r,j+2 (s), we have receivers(s) = V , so t r,j+2 (s) = t s,i+1 (Observation 2).

We conclude that in the configurations of [γ s,i , γ s,i+1 [, the value of myCnt(s) is bounded by 2N .

Corollary 4: In any message in transit in any configuration, the value of the field updtCnt is bounded by 2N .

A label has 3 values, so T S is an array of N entries, each of them of 2-bits size.

The size of a process identifier is c.log(N ) bits. A message size is at most 2N + O(log(N )) + msgSize bits.

VII. CAUSAL TOTAL ORDER BROADCAST Algorithm 3 provides Causal Total Order Broadcast primitives (also called Atomic broadcast primitives) in Class T C R assuming that N is known. Algorithm 3 requires a FIFO Broadcast with termination detection algorithm implementation as the one of Algorithm 2 : a process starts a new atomic broadcast after detecting the termination of the previous one, i.e., every process has delivered the previous broadcast message.

Algorithm 3 design is a new variant of communication history schema to establish the delivering order [START_REF] Défago | Total order broadcast and multicast algorithms: Taxonomy and survey[END_REF]. The processes delay the messages delivery according to a deterministic policy regarding the merging the message streams from each process. More precisely, a process p waits to have received at least a broadcast message from every process to handle a single received message per process (the first received one) -i.e. these messages are delivered according to the sender identifier order. To avoid deadlock, each process permanently performs a atomic broadcast. When a process has not data to atomically broadcast, it broadcasts the neutral data (i.e. atomic⊥) that is not delivered to the application layer. Algorithm 3 implements the procedure Atomic Broadcast(m) by calling the FIFO Broadcast procedure FD brcst i.e. the line 2 is executed. Whenever process p receives a message m broadcast by q, it calls the FIFO Broadcast procedure FD dlr(id(q), m); i.e. p executes line block 4-9.

Algorithm 1 :

 1 variables and macro of FIFO Broadcast with detection of termination in T C R for process p. Constant Variables: N ∈ N * : number of processes in the DG id(p) ∈ IDSET : the identifier of p Local Variables:

Algorithm 2 :

 2 Code of FIFO Broadcast with detection of termination in T C R for process p.

  = id, m, updtCnt, T S ∈ M sgsT (p)) 5 mailbox := RECEIVE() // processing of receiving messages of q = p 6 forall tuples msg = id(q), m, updtCnt, T S in mailbox do 7 if id(q) = id(p) then // keep the latest q-message8 if msg = id(q), -, updtCnt , T S / ∈ M sgsT (p) or (T S[q], updtCnt) > ⊕ (T S [q], updtCnt ) then 9 if msg ∈ M sgsT (p) then 10 remove msg of M sgsT (p) 11 insert id(q), m, updtCnt, T S in M sgsT (p) // delivery of q-acknowledgment 12 if T S[p] = myT S(p)[p] then 13 insert id(q) in ack(p) // new broadcasting from q 14 if T S[q] = myT S(p)[q] ⊕ 1 then 15 myT S(p)[q] := myT S(p)[q] ⊕ 116 myCnt(p) + + 17 if m = brdcst⊥ then FD dlr(id(q), m) // start a new broadcast 18 if |ack(p)| = N then 19 ack(p) := {id(p)} ; myCnt(p) := 0; 20 myT S(p)[p] := myT S(p)[p] ⊕ 1 // determine the information broadcast 21 if queueBrdcst(p) is not empty then 22 msgB(p) := queueBrdcst(p).dequeue ; 23 if msgB(p) = brdcst⊥ then FD dlr(id(p), msgB(p)) 24 else msgB(p) := brdcst⊥ // add/update the p's message 25 remove id(p), -, -,of M sgsT (p) 26 insert id(p), msgB(p), myCnt(p), myT S(p) in M sgsT (p)

•

  In a graph of the class T C B (∆) with the process set V , t s,i+1 ≤ t s,i + 2∆ .• (id(s), m(s, i)) is delivered once by every process during the time interval[t s,i , t s,i+1 [ if m(s, i) = brdcst⊥.Otherwise no process delivers a s-message during this time interval.D. Proof of the bounded message sizeTheorem 2: For all s ∈ V and for i ∈ N * , in the configurations of [γ s,i , γ s,i+1 [, the value of myCnt(s) is bounded by 2N .

Algorithm 3: Causal Total Order Broadcast in T C R for process p. • receivedM sgs(p)[] : is an array of N queues. receivedM sgs(p)[q] contains the not delivered messages received from q. They are inserted in receivedM sgs(p)[q] according to their respective receiving round. Initially, all queues are empty.

• atomicCounter(p) : counts the number of messages that p should atomically broadcast. Initially, its value is zero. Each process perpetually executes an atomic broadcast. The broadcast message is either provided by the application or equals to atomic⊥. The variable atomicCounter(p) records the current number of messages that p is or are waiting to be atomically broadcast. The value of atomicCounter(p) is incremented at each execution of the procedure Atomic Broadcast (line 2) and decremented during the execution of the procedure FD dlr if p ends its current atomic broadcast (line 9 in if-block starting at line 5). If p has no atomically broadcast going-on (i.e. atomicCounter(p) = 0) then its start a new atomic broadcast of the neutral data by calling Atomic Broadcast(atomic⊥) (line 11).

At the invocation of FD dlr(id(q), m), the message m is included in the queue receivedM sgs(p)[q] and thus considered as a waiting message. When every queue receivedM sgs(p)[q] is not empty, i.e., there is a waiting message from every process, the if-condition of line 5 is verified. Then p handles one waiting message per process q; this message is the first one in queue receivedM sgs(p) [q]. The N handled messages are removed of their queue and delivered, provided they are not atomic⊥.

By lack of space, proof of the correctness of Algorithm 3 are only sketched. m(s, j) denotes the jth message atomically broadcast by the process s.

< Rlex denotes the reversed lexicographic order: m(id(p), i) < Rlex m(id(q), j) if and only if (i < j) or (i = j and id(p) < id(q)).

Let m(p, i) and m(q, j) be two atomically broadcast messages not equal to atomic⊥. Algorithm 3 ensures that If m(p, i) < Rlex m(q, j) then m(p, i) is atomically delivered before m(q, j) by every process.

On every process, the delivering order is the reversed lexicographic order of the messages. Hence, algorithm 3 provides FIFO total order Broadcast primitives in Class T C R as Validity, Agreement, and Integrity, Fifo order, Total order properties are verified.

If r atomically delivers m(s, i) before atomically broadcasting m(r, j) then j > i. So, algorithm 3 ensures the Local order property. (local order property) If a process broadcasts a message m and a process delivers m before broadcasting m , then every process delivers m before m . Hadzilacos and Toueg [START_REF] Hadzilacos | A modular approach to fault-tolerant broadcasts and related problems[END_REF] prove that the property of Causal order is equivalent to the combination of Fifo order and Local order properties. Algorithm 3 provides causal total order broadcast primitives in Class T C R .

VIII. CONCLUSION

In this article we have presented two broadcast algorithms that respectively provide FIFO and total orders for the delivery of broadcast messages on top of dynamic systems with recurrent connectivity. We model the latter with the Class T C R of Timevarying Graph formalism [START_REF] Casteigts | Timevarying graphs and dynamic networks[END_REF]. System membership, composed by N processes, is fixed but unknown. The algorithms ensure termination detection and tolerate message losses. The size of their message is bounded to 2N + O(log(N )) + msgSize bits where msgSize is a bound size in bits of broadcast data.

The second algorithm provides a causal total order of message delivery.

Futures directions research for our work is to design an algorithm able to deal with fault as process crashes, byzantine fault or transient fault.


Meldin Mathew

Nathalie Lyczko

Ange Nzihou
email: ange.nzihou@gmail.com

Sabu Thomas
email: sabuthomas@mgu.ac.in

Facile One-Step Synthesis of Calcium Phosphate/Cellulose Composite: Synthesis, Morphology, Structure and Properties

Keywords: calcium phosphate, cellulose composite, differential scanning calorimetry (DSC), infrared spectroscopy, thermogravimetric analysis (TGA)

This study focusses on reporting a facile one-step synthesis method to fabricate calcium phosphate-microcrystalline cellulose composite with an enhanced surface area. The composite preparation is done using a simple one-step method called co-precipitation method under ambient and 60 °C temperature. The calcium carbonate and orthophosphoric acid are taken, which are the two best known widely available starting materials for the synthesis of calcium phosphate. The sample is collected and taken for the drying process in an oven at 105 °C. The characterizations like XRD, SEM, BET, FTIR, TGA, and DSC of the demonstrated composites are done. From BET analysis, it can be concluded that the surface area of the demonstrated composite enhances substantially after the incorporation of the microcrystalline cellulose.

Introduction

The calcium phosphate has various eternal ranges of applications because of their sorption capacity, chemical-thermal stability and biocompatibility. [1] These specifications can be used to cover the needs of many other areas, for example, protein isolation and purification, production of biocompatible ceramics, liquid chromatography, [2] drug delivery, in catalysis, water treatment, fertilizers and pharmaceutical industry, [3] soil remediation, etc. [4] Thus, various work has been investigated on the synthesis of calcium phosphate such as microwave irradiation, [5] spray drying method having controlled morphology, [6] preparation involving hydrothermal condition, [7] sol-gel process, [8] precipitation in aqueous solution, [9] emulsion route, [10] ultrasonic freeze drying technique, [11] preparation using templates, etc. [12] Among these methods, the precipitation of orthophosphate using a calcium source in an aqueous medium seems to be the major simple technique to prepare calcium phosphate powder. Even though there are different types of calcium sources are present, calcium carbonate gained a considerable attention above all due to its eco friendliness, huge availability, non-appearance of the interfering anions and cost effective, viable production from municipal and industrial wastes. [13] The specialty of orthophosphoric acid has been studied and reported by Doan et al. and they enumerate that, orthophosphoric acid was perfect, due to its ability on the dissolution of the CaCO 3 and was the only reactant that leads to complete utilization of the starting orthophosphate group. [14] Therefore, looking from all aspects of the CaCO 3 and the orthophosphoric acid, they are the best-known components of the calcium phosphate preparation process.

Inorganic phosphate serves a long historical background as a constituent part of the bone and teeth, it is already proposed for the bone fracture treatment. [15] The calcium phosphate has been proved already for the effective removal of heavy metals like Pb, Zn, Cu, Co, and Cr. [16] Moreover, the most hazardous radioactive nuclides like strontium and cesium removal studies also were conducted with modified hydroxyapatite. [17] Different phosphate and calcium sources have been studied and reported for the preparation of calcium phosphate. [18] The effect of stirring rate, water-solid ratio, reaction time, Ca-P ratio, etc. is important to enhance the adsorption properties in the preparation aspects and they reported with effective results. [14,19] The relevant functioning of calcite on metal adsorption has also been analyzed. [20] The scavenging property of phosphate and its structural specialty also has been studied and reported. [21] Being an abundant biomass source and biodegradable polymer, cellulose has gained considerable interest among the scientific community. Cellulose has excellent properties like good strength, high surface area, good rigidity, biocompatibility, hydrophilicity, relative thermo-stabilization, sorption capability and varying optical appearance which makes them as a promising candidate to perform in enormous applications. [22] Especially the enormous amount of hydroxyl group present on the surface of the cellulose helps them to facilitate various surface chemistries. Physical incorporation/blending of cellulose in variant forms such as nanoparticles, gels, copolymers and membranes was also introduced to make smart composites for numerous applications. Fibrous membranes, [23] reinforced agents, [24] magnetic devices, [25] drug delivery, [26] barrier films, [27] optical media, [28] electrical devices, [29] thickeners, [30] water treatment devices, [31] stabilizers, [32] etc., are some of the areas where cellulose are being used.

In this study, we have fabricated a calcium phosphate/cellulose composite in a facile single step process. The composite preparation was done at ambient and 60 °C. For the comparative study with composite, calcium phosphate alone also was prepared. We enhanced the surface area via microcrystalline cellulose (MCC) co-precipitation with calcium phosphate. The sample was collected and taken for the drying process in an oven at 105 °C. In order to study their behavior associated with the properties acquired, we used different characterization techniques like TGA, SEM, XRD, PSD, BET and FTIR.

Characterization

BET Analysis

The samples prepared at ambient and 60 °C temperature were taken for different physical, chemical and thermal analysis. The surface area analysis was done by BET study. After the outgassing step around 105 °C under high vacuum, standard nitrogen adsorption at 77k was proceeded. The isotherm obtained using Micromeritics Tristar II 3020 and with a Micromeritics 3 FLEX was used for the analysis of the sample.

FTIR Spectroscopy

The prepared samples were taken for the FTIR analysis to study the interactions of functional groups presenting in the sample prepared. The spectra were recorded using a SHIMADZU spectrometer-8400S sweeping between 4000 and 500 cm -1 were used.

X-Ray Diffraction Analysis

The X-ray diffraction data were collected using a Phillips Panalytical X'pert Pro MPD diffractometer. The radiation source ray used was the copper (Cu) whose wavelength K𝛼 is 1.543 Å. A nickel filter was used to remove the Cu K𝛽 ray. The apparatus operates at a voltage of 45 kV and at an intensity of 40 mA. The diffractogram was recorded from 10 to 8°in 2𝜃. The step size was 0.017°in 2𝜃 and the scan step time was 29.89 s. The phase identification was carried out from the databases JCPDS and COD.

Thermal Analysis

The thermal analysis of the sample was done by using TGA/DSC apparatus SDT Q600 by TA instrument. Twenty milligram of the sample were used in each analysis and heated from room temperature to 1000 °C, with a heating rate of 5 °C min -1 .

SEM

For the morphological studies, the SEM analysis performed on Philips XL30 ESEM apparatus. Samples taken for the analysis were used without sputter coating and performed at 8 kV voltage.

Result and Discussion

BET Surface Area

The surface area of calcium phosphate and the composite were measured using BET analyser. From the result, it could be concluded that, the surface area of the composite enhanced substantially, compared to calcium phosphate. It is well known that, surface area of the composite plays a vital role in the adsorption behaviour.

From Table 1, it is clearly understood that, the sample prepared at ambient condition showed values of 2.3 to 11.1 (m 2 g -1 ) the neat calcium phosphate and MCC filled composite, respectively. The sample prepared at 60 °C also showed an increment from 8.7 to 18.8 (m 2 g -1 ) upon the addition of MCC. The incorporation of the microcrystalline cellulose led to the substantial enhancement of the surface area of calcium phosphate. Moreover, from the result, it can conclude that, the influence of reaction temperature is noticeable. The reason had been studied and reported by Minh et al. [14] According to them, the reaction temperature has a great involvement to minimize the amount of intermediate like brushite, monetite etc. Furthermore, the remaining CaCO 3 in the product was reduced. Therefore, the reaction being carried out at 60 °C led to the formation of calcium phosphate with enhanced surface area. The XRD and TGA studies were provided with supporting data by showing the reduced CaCO 3 and intermediate contents.

FTIR Spectroscopic Analysis

Figure 1 represents the IR spectrum of the calcium phosphate and composite. For all samples, spectra showed the vibrational strong peaks of PO 4 3-at 1018-1078 m -1 , 960-980 cm -1 , and 550-592 cm -1 of hydroxyapatite phase. Medium vibrational peaks of PO 4 3-also were observed at 470-480 cm -1 of hydroxyapatite phase.

The remaining unreacted CaCO 3 was present on 1400 cm -1 . A peak around 1000 cm -1 was due to the tricalcium phosphate (Ca 3 (PO 4 ) 2 ) formed as an intermediate during the reaction. The O-H bending peak corresponding to the dehydration of the surface moisture content was observable around 1600 cm -1 , which reflects in the TGA analysis as well.

The main reason for the absence of stretching peaks observed by the hydroxyl group of the cellulose was well known here due to the deposition of calcium phosphate layer on the surface of the microcrystalline cellulose during co-precipitation process. The SEM images obtained during the analysis gave strong evidence for this peak disappearance from the IR spectrum.

X-Ray Diffraction Analysis

The XRD pattern of the calcium phosphate prepared at ambient and 60 °C were taken (Figure 2). The calcium phosphate prepared at ambient condition showed the peaks of hydroxyapatite 2𝜃 = 31.7 0 . Other peaks of tricalcium phosphate (Ca 3 (PO 4 ) 2 ) intermediate was appeared in the graph on 2𝜃 = 30.9 0 . The unreacted cal-cium carbonate associated with the calcium phosphate was also present in the compound.

For the sample prepared in 60 °C shows good crystal clarity than the sample prepared in ambient condition. The peaks analogous to the hydroxyapatite are visible here on 2𝜃 = 25.3 0 , 2𝜃 = 31.8 0 and 2𝜃 = 32.9 0 . The peaks of unreacted CaCO 3 remaining in the product is visible at 2𝜃 = 29.3 0 . The formation of calcium phosphate at 60 °C, did not show the peaks, corresponding to the intermediates due to the effect of temperature. The relevant JCPDS data are shown at the inset for the reference (CaCO 3 : ICDD 00-047-1743; Ca 10 (PO 4 ) 6 (OH) 2 : ICDD: 01-073-0293; Ca 3 (PO 4 ) 2 ICDD 00-032-0176).

We have analysed the XRD of the composites prepared at ambient as well as the 60 0 C. We understood that both the composite and the calcium phosphate prepared alone does not show any differences in the diffraction pattern.

Thermo Gravimetric Analysis

Figure 3a shows the thermograph of the calcium phosphate and its composite prepared at ambient condition. There are three degradations for the calcium phosphate and the primary weight loss took place around 100 °C. This was due to the dehydration of the system and the weight loss is 0.7%. Second weight loss was observed in 175 °C, due to the degradation of brushite. We used the DSC graph, to study the phenomena associated with different weight losses. Here, at 175 °C, we got an endothermic peak on DSC profile, corresponding to the mass loss 1.3%. The major sharp weight loss (decomposition) between 610 °C and 720 °C could be attributed to the decarbonation in the calcium carbonate and this turns into calcium oxide and carbon dioxide (CaCO 3 → CaO + CO 2 ). The total weight loss was about 12.4%. For the graph of the composite prepared with microcrystalline cellulose, there are four decompositions present. The first peak was observed around 100 °C, due to the removal of surface moisture. Second peak starts around 320 °C, which belongs to the cellulose oxidation with a mass loss about 14.1%. The succeeding transition around 450 °C is due to the removal of contaminants on CaCO 3 . Thermal degradation of CaCO 3 was between 610 °C and 720 °C followed by decarbonation. Total mass loss of the system is 20.4%.

The thermograph, Figure 3b depicted the analysis of the calcium phosphate and its composite prepared at 60 °C condition. When considering the composite prepared using calcium phosphate and MCC, its primary peak near to 100 °C due to the dehydration of the surface moisture. The second peak was between 300 °C and 500 °C, corresponding to the cellulose oxidation and the weight loss was about 14.1%. Here, the corresponding exothermic peak was distinctly registered on DSC analysis. The next peak was observed at 600 °C due to the decarbonation of the CaCO 3. For the calcium phosphate prepared at 60 °C, the primary peak was observed around 100 °C could be attributed to the dehydration of moisture content. The second peak occurred between 610 °C and 720 °C which can be due to the decarbonation of CaCO 3 with a weight loss of 11.7%. Here also, the corresponding phase transitions were clearly detectable on DSC curves with two exothermic peaks. The total mass loss of the composite and calcium phosphate was 22.9% and 15.9%, respectively.

Scanning Electron Microscopy

Figure 4a,b was the SEM images of calcium phosphate prepared at 60 °C and ambient temperatures, respectively. Here, the sheet like structure of the particle can be assigned to the presence of brushite/OCP in the product. The sample prepared under 60 °C was more uniform and finely structured. The particle size was small and the distribution was more uniform and narrow. The high heterogenic nature of the product synthesized at ambient temperature shows varying diameter ranging up to 110 µm. In both cases, the developed flakes of calcium phosphate were assembled to give their cluster in the structure and those were spread along in the sample. Figure 4c represented the SEM images of microcrystalline cellulose. A web like appearance with self-assembled structure resulted into a spherical shaped cellulose particle with micro range. The composite images were given on Figure 4d,f composite prepared using co-precipitation method, under SEM analysis was found as well organized form of calcium phosphate and microcrystalline cellulose. In some places, cellulose has been shown to be covered with calcium phosphate. This was understood, when the SEM was performed at high voltage. When the voltage switched from 8 to 30 kV, the cellulose was found much darker than the calcium phosphate and this was clearly depicted in Figure 4g. Therefore, a deposition of calcium phosphate layer, on the surface of the cellulose was found. In certain cases, the microcrystalline cellulose and calcium phosphate were found to be separated. In this case, secondary forces such as Vander Waals force were considerably help them to stay organized.

In order to study the enhanced surface area, due to the addition of microcrystalline cellulose into the calcium phosphate, we used particle size distribution analysis. The analysis showed that, the enhancement of the surface area was due to the decreased particle size. The sample prepared at ambient temperature showed an enhancement in surface area from 2.3 to 11.1 m 2 g -1 due to the addition of the microcrystalline cellulose and the average particle size decreased from 60 to 4 µm. Similarly, the surface area enhanced from 8.7 to 18.8 m 2 g -1 in the case of composite prepared at 60 °C when the average particle size decreased from 50 to 4 µm. In both cases, we observed a substantial enhancement in surface area due to the incorporation of microcrystalline cellulose. Therefore, the microcrystalline cellulose substantially improved the surface area of the resultant composite.

Conclusion

We have carefully performed two reaction strategies in this study at ambient and 60 °C temperature. For the incorporation of cellulose into the calcium phosphate, co-precipitation method was used. The surface area analysis of the sample showed an enhancement with the incorporation of cellulose. Surface area of the calcium phosphate was upgraded from 2.3 (60 µm) to 11.1 m 2 g -1 (4 µm) at ambient condition treatment, and at the 60 °C reaction, 8.7 m 2 g -1 (50 µm) was modified to 18.8 m 2 g -1 (4 µm). The particle size distribution studies of the composite showed that the enhanced surface area was due to the decreased particle size in the composite.

The temperature has a strong effect on the reduction the amount of intermediate in the product formation. In 48-h reaction and at 60 °C, calcium phosphate and its composite formed with less amount of intermediate. This was supported by the Xray diffraction studies, FTIR spectroscopy and thermal analysis. Microscopic investigation showed the cellulose-calcium phosphate interaction facilitated via either by surface coating on cellulose or by some secondary interactions like Vander Waals force.

Experimental Section

Calcium carbonate powder, CaCO 3 (Solvay), was chosen as the Ca source for the calcium phosphate preparation. Phosphate source was chosen for the preparation is orthophosphoric acid, H 3 PO 4 (Merck). The synthesis has been done via a U form glass reactor with 2.3 L capacity and is equipped with a vertical stainless steel rotor. For each synthesis, 300 gm of calcium carbonate and 1200 mL water (corresponds to the weight ratio (L/S) of water to calcium carbonate as 4) were poured into the reactor under stirring at 400 rpm, which prevents intermediate formation like brushite, leading to good reaction rate and the better consumption of the reactant species by getting efficient contact between them. The amount of orthophosphoric acid poured into the reactor was 206.91 gm. This was corresponding to the molar ratio of calcium to phosphorus (Ca/P) which was 1.67. The reaction of calcium carbonate and phosphoric acid can be written as,

10CaCO 3 + 6H 3 PO 4 → Ca 10 (PO 4 ) 6 (OH) 2 + 10CO 2 + 8H 2 O ( 1 )
This Equation 1 represents the calcium phosphate formation in a single step reaction using aqueous medium. The temperature of the reaction was set at ambient and 60 °C for the study of 48-h reaction. Studies have shown that, 99.5% of CaCO 3 was consumed in a 48-h reaction. The formation of intermediate, like brushite (CaHPO 4. 2H 2 O), also could be reduced by choosing this reaction time and temperature.

The product formed after 48 h reaction made into powder by filtration of the suspension on 0.45 µm filter paper followed by a drying overnight at 105 °C.

Preparations of Calcium Phosphate/Microcrystalline Cellulose (MCC) Via Co-Precipitation Method: The co-precipitation method was employed for the preparation of calcium phosphate/microcrystalline cellulose. The cellulose microcrystalline cellulose material used is a polysaccharide composed of long chains of 𝛽 (1,4) linked d-glucose units and it is purchased from Sigma Aldrich. This is used for a wide range of applications such as microfibrils, biofilms, and biodegradable composites. The surface area of this type of MCC has been reported by Vehovec et al. and it was given as 0.903 m 2 g -1 . [33] The ease of production was the main advantage of the demonstrated technique. This method consists of simultaneous precipitation of calcium phosphate with microcrystalline cellulose. For the preparation, the microcrystalline cellulose was added to the 2.3 L U form glass reactor with water and phosphate source mixture. For the addition, 20% weight of CaCO 3 : 60 gm of microcrystalline cellulose was used. The microcrystalline cellulose was added along with phosphate source into the reactor with water. After 48 h of reaction, the product was collected and dried.

Figure 1 .

 1 Figure 1. FTIR spectrum of calcium phosphate and the composite.

Figure 2 .

 2 Figure 2. X-ray diffraction analysis of calcium phosphate.

Figure 3 .

 3 Figure 3. a) TG analysis of calcium phosphate and composite prepared in ambient temperature; b) TG analysis of calcium phosphate and composite prepared in 60 °C temperature.

Figure 4 .

 4 Figure 4. a) SEM analysis and particle size distribution of calcium phosphate prepared at ambient temperature. b) SEM analysis and particle size distribution of calcium phosphate prepared at 60 °C temperature. c) SEM images of microcrystalline cellulose. d) SEM analysis and particle size distribution of composite prepared at ambient temperature. f) SEM analysis and particle size distribution of composite prepared at 60 °C temperature. g) SEM analysis of the composites observed under a) 8 kV and b) 30 kV.

Figure 4 .

 4 Figure 4. Continued

Table 1 .

 1 BET surface area of calcium phosphate and the composite.

	CaP and the Composite	Prepared Condition	S P [m 2 g -1 ]
	H 3 PO 4 + CaCO 3	Ambient	2.3
	H 3 PO 4 + (CaCO 3 + MCC)	Ambient	11.1
	H 3 PO 4 in CaCO 3	60 °C	8.7
	H 3 PO 4 in (CaCO 3 + MCC)	60 °C	18.8

Acknowledgements

The author would like to express my sincere gratitude to the RAPSODEE research centre for the funding and the fellow staffs for providing great support throughout this project. My sincere thanks to Dr. Deepu. A. Gopaku-mar, Suji Mary Zachariah, and Dr. Hanna J. Maria for their helpful advices, care, and instructions.

Conflict of Interest

The authors declare no conflict of interest.