Daniel Wilhelm

Luciana Arantes

Pierre Sens

A scalable causal broadcast that tolerates dynamics of mobile networks

Causal broadcast is at the core of collaborative applications, distributed databases, conferencing, or social networks. Existing causal broadcast algorithms are either not scalable or cannot be implemented on mobile networks because they do not take into account the features of these networks: limited capacities of nodes (computation, storage, energy), unreliable communication channels, and the dynamics of connections due to node mobility, node failure, and join/leave of nodes. This work presents a causal broadcast algorithm for mobile networks. The algorithm is scalable: control information piggybacked on messages and maintained on nodes is of small size. Experiments conducted on OMNeT++, a realistic network simulator, confirms the effectiveness of our causal broadcast protocol, rendering causal broadcast affordable in mobile networks.

its battery becomes flat, or a hardware failure occurs. Interferences cause message losses on the wireless network. To the best of our knowledge, no causal broadcast solution handling those characteristics has been proposed.

Existing implementations of causal broadcast either piggyback information on messages [START_REF] Mostéfaoui | Probabilistic causal message ordering[END_REF] [START_REF] Prakash | An efficient causal ordering algorithm for mobile computing environments[END_REF][8] [START_REF] Mattern | Virtual time and global states of distributed systems[END_REF] or organize nodes in logical topologies in which messages are disseminated through reliable FIFO channels [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] [START_REF] Nédelec | Breaking the scalability barrier of causal broadcast for large and dynamic systems[END_REF]. The first approach is not suitable for mobile networks that contain many mobile hosts, due to scalability issues, because the size of information piggybacked on messages either grows with the number of nodes [START_REF] Fidge | Timestamps in message-passing systems that preserve the partial ordering[END_REF] [START_REF] Mattern | Virtual time and global states of distributed systems[END_REF], or with the message load [START_REF] Mostéfaoui | Probabilistic causal message ordering[END_REF] [START_REF] Prakash | An efficient causal ordering algorithm for mobile computing environments[END_REF]. The second approach [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] [START_REF] Nédelec | Breaking the scalability barrier of causal broadcast for large and dynamic systems[END_REF] ensures that messages are implicitly causally ordered at reception. Therefore, no information is piggybacked on messages, making that approach scalable. However, [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] considers a static network, and the dynamic model of [START_REF] Nédelec | Breaking the scalability barrier of causal broadcast for large and dynamic systems[END_REF] is not applicable to mobile networks. Moreover, [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF][16] require reliable FIFO channels, which are not provided by mobile networks, even with TCP, because a host moving to a new cell drops the connection with its previous cell, and pending messages of that connection are lost.

Several works address causal multicast in mobile networks [START_REF] Chandra | Causal multicast in mobile networks[END_REF] [17] [START_REF] Anastasi | A reliable multicast protocol for distributed mobile systems: Design and evaluation[END_REF][3] [START_REF] Li | A mobile-support-station-based causal multicast algorithm in mobile computing environment[END_REF]. However, they usually make unrealistic assumptions such as reliable [START_REF] Chandra | Causal multicast in mobile networks[END_REF] [START_REF] Prakash | An efficient causal ordering algorithm for mobile computing environments[END_REF] and/or FIFO [START_REF] Benzaid | An optimal causal broadcast protocol in mobile dynamic groups[END_REF][12] channels, or reliable host connection protocols. In addition, they do not address the problem that hosts might fail to connect to a cell's station before moving to another cell, which might lead to many concurrent connection initializations. Furthermore, they usually consider that hosts are reliable, i.e., they never fail, and the proposed solutions do not scale. Finally, causal multicast requires additional information to handle multicast groups, not necessary for causal broadcast.

Stations handle interferences on the wireless network by caching messages for retransmission. Discarding cached messages once they become obsolete is an important issue to deal with. Some existing implementations, such as [START_REF] Chandra | Causal multicast in mobile networks[END_REF][3], propose costly centralized solutions since the source station that initially broadcast a message coordinates the protocol for discarding it from all other stations, inducing a high overhead of message traffic (acknowledge messages) and memory storage (a message is cached at all stations even if only one station requires it).

This work presents a scalable causal broadcast algorithm designed for mobile networks. Hosts can join/leave the network and fail, permanently or transiently, at any time. They move freely and might be temporarily disconnected from the network when out of range of all stations. We assume no reliable connection protocol, and the algorithm handles multiple concurrent connections by the same host. Resource limitations of hosts are handled by keeping causal information at stations, while hosts only keep very little control information. Messages piggyback only a few integers as control information. Contrarily to existing centralized solutions [START_REF] Chandra | Causal multicast in mobile networks[END_REF] [3], the discarding of obsolete messages cached at stations is decentralized: a station discards a message once all hosts connected to it acknowledged the message. Consequently, stations only cache necessary messages, and no extra messages are exchanged for message discarding.

Summing up, the proposed causal broadcast algorithm is scalable in both the number of hosts and stations, has a low message traffic and storage overhead, while handling mobile network dynamics without the constraining assumptions of FIFO wireless links [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF][16] [START_REF] Nédelec | Causal broadcast: How to forget?[END_REF] or causal multicast approaches [START_REF] Chandra | Causal multicast in mobile networks[END_REF] [START_REF] Benzaid | An optimal causal broadcast protocol in mobile dynamic groups[END_REF].

Experiments were conducted over OMNeT++/INET [START_REF] Varga | The omnet++ discrete event simulation system[END_REF]. The proposed algorithm is compared to [START_REF] Chandra | Causal multicast in mobile networks[END_REF], a causal multicast algorithm for mobile networks which we extended to causal broadcast. Experiments confirm that our algorithm outperforms the latter.

The paper is organized as follows. Section 6 discusses related work. Section 2 presents the background and Section 3 the model. Section 4 describes the proposed causal broadcast algorithm. Section 5 presents the experimental results. Section 7 concludes the paper.

BACKGROUND

Causal order ensures that nodes deliver messages while respecting the causal relation between them, as defined by the happenedbefore relation [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] introduced by Leslie Lamport:

Happened-before relation: Considering two events e 1 and e 2 , e 1 causally precedes e 2 , or e 1 → e 2 iff: (a) e 1 and e 2 occur on the same process and e 1 precedes e 2 or (b) for a message m e 1 =send(m) and e 2 =deliver(m) or (c) there exists an event e 3 such that e 1 → e 3 and e 3 → e 2 .

Causal broadcast is a group communication service that provides the application processes with two primitives co-broadcast(m), that broadcasts a message m to all nodes, and co-deliver(m), that delivers m to the application. Causal broadcast is defined by the following properties [START_REF] Nédelec | Causal broadcast: How to forget?[END_REF]: Causal broadcast: Validity. If a process co-delivers a message m from a process q, q previously co-broadcasts m. Integrity. A process co-delivers a message m at most once. Causal order. The delivery order of messages follows the happenedbefore relationship: co-broadcast(m) → co-broadcast(m') ⇒ process q | co-deliver(m') → co-deliver(m). Termination. A message co-broadcasted by a correct process is codelivered by all correct processes. The delivery of a message is delayed until all messages that causally precede it are delivered. Usually, in mobile networks, stations discard messages once all hosts delivered them. Hosts that join the network will, therefore, not receive and deliver these messages.

Our algorithm extends the FIFO dissemination approach proposed in [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] to mobile networks. The algorithm of [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] ensures causal order through FIFO dissemination in static networks where reliable nodes are connected by reliable FIFO channels, thereby ensuring that no path exists over which messages travel out of causal order. For example, in Figure 1 A broadcasts m, which causally precedes

MODEL

Mobile networks are composed by mobile hosts, denoted host(s), and static support stations, denoted station(s). Hosts and stations communicate through message passing. Applications running on hosts use a group communication service to join and leave the network, as well as to broadcast messages to all hosts and deliver them in causal order. The characteristics of stations are the following:

• Each station is at the center of a cell, corresponding to the area covered by its antenna's transmission range. • Stations are supposed reliable and do not move or leave the network, because a failing station would disconnect the area covered by it, and cell overlapping should be avoided (even though it cannot be realistically completely prevented) because of interferences on the wireless network. Hence, we assume hardware replication for stations. • Stations do not have energy limitations and have much more storage and computational capacity than hosts.

The characteristics of hosts are the following:

• A host is connected to at most one station (generally the closest one) at any given moment, and communicates with the system through that station, by sending messages on the wireless network. • A host can join and leave the network at any moment. A host that joins the network will not deliver those messages that the station to which it connects has previously discarded. • Hosts move freely inside and outside cells.

• Hosts might temporarily or permanently fail. For example, a host is temporarily faulty until its battery is recharged, or is permanently faulty if it has a hardware failure. A faulty host stops sending, receiving, and processing messages, and loses all variables stored in volatile memory. • Hosts have computational, storage, and energy limitations.

The wireless network is unreliable, due to interferences that lead to message losses while stations are connected by a high-speed wired network, which is FIFO and reliable, and over which is built a static logical tree-based overlay.

Hosts can be in the states up or down. A station controls the state of hosts connected to it: it considers a connected host as down if the host leaves the system, or if it receives no message from the host for a given interval of time (assume a failure). Otherwise, the station considers the host as up.

A host joining the system does not deliver those messages already discarded by the station that acknowledges its system join. Hence, we modify the termination condition of causal broadcast: Termination. Note s j,k the station from which host k received the system join acknowledgment. A message m co-broadcasted by an up process is co-delivered by all up processes k for which s j,k did not discarded m prior to k's connection.

CAUSAL BROADCAST ALGORITHM

This section presents our causal broadcast algorithm, denoted WAS, which extends the FIFO dissemination approach [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] to mobile networks, where hosts are not static, neither reliable, and communicate through unreliable wireless channels with stations which, in their turn, communicate among themselves through reliable channels.

The algorithm is divided into three parts: (1) dissemination of application messages, (2) join/leave operations, and (3) handoff procedure to handle hosts moving between cells.

Dissemination of application messages

Hosts are the source of application messages, and stations ensure that all hosts deliver them causally. A host broadcasts an application message by sending it to the station to which it is connected. The station then forwards the message to the hosts of its cell through the wireless network, as well as to other stations through the wired network. Each station ensures that the hosts connected to it deliver application messages in causal order.

On the wireless network, message loss and FIFO ordering are handled by assigning sequence numbers to messages, and storing them in buffers for retransmission until destination nodes acknowledge them. A host uses variables seq h to order messages it sends, and seq NC to order messages it receives. A station uses seq C to order messages it broadcasts, and stores seq h and seq NC of each host connected to it. In both stations and hosts, a local buffer, RBuffer, stores received messages until they are FIFO ordered, and SBuffer stores sent messages until they are acknowledged by all destination(s). A host keeps a message in SBuffer until its cell's station acknowledges the message. A station keeps a message in SBuffer until all hosts connected to it acknowledge the message.

Every application message is uniquely identified by (id h , seq h ), where seq h is the sequence number that host id h associated to the message. Moreover, since cells may overlap, every message sent over a wireless network cell also piggybacks the id of this cell (id C ). Upon reception of the message, hosts and stations verify id C and only take into account messages sent inside their cell.

Nodes (hosts and stations) regularly send acknowledge messages, containing ranges of sequence numbers to acknowledge application messages whose sequence numbers are in these ranges. Hosts do not send acknowledgments during handoffs, since they would Application messages which are delivered by all hosts are considered obsolete and should then be discarded by stations. Existing algorithms use a centralized deletion of obsolete messages [START_REF] Chandra | Causal multicast in mobile networks[END_REF], which has an overhead both in terms of stored messages in station SBuffer and the number of messages sent over the wired network: each application message m is managed by a station called MSS init , and acknowledge messages for m from each host are forwarded to MSS init . Once MSS init received an acknowledge message from each host, it broadcasts a delete message to all stations in order to discard m. To overcome such an overhead, we have introduced a decentralized mechanism where stations discard messages using only local information: a station discards a message as soon as all hosts connected to it have acknowledged the message. Therefore, our approach does not require message exchanges between stations and a station only caches messages required by hosts of its cell.

h 1 s 1 s 2 h 2 m 1 m 1 m1 ,1 x m 1 ,1 m 1 m 1 m1 ,1 m 1 m1 d(m 1 ) m1 ,1 m 2 m 1 m 2 m 2 ,1 d(m 2 ) m2 ,2 m 1 m 2 m 2 m 1 m 2 ,2 m 1 m 2 d(m 1 ) d(m 2 ) m 1 ,1 ∅ ∅ ∅ ac k= 2 ∅ ∅ ∅ ∅ ∅ ∅ ac k= 1 m 1 m 2 ∅ ∅ ∅ ac k = 1 ∅ ∅ ∅ ac k = 2
Figure 2 shows the broadcast and delivery of two messages causally related. h 1 is connected to s 1 and h 2 to s 2 . Stations s 1 and s 2 are connected by a wired channel. Hosts (resp. stations) piggyback seq h (resp. seq C ) in application messages. SBuffers are represented in bold. First, h 1 broadcasts m 1 . Upon reception, s 1 forwards m 1 to s 2 and broadcasts it in its cell, which contains h 1 . Upon reception, s 2 forwards m 1 to h 2 . h 2 receives and delivers m 1 , then broadcasts m 2 (co-broadcast(m 1 ) → co-broadcast(m 2 )). h 2 (resp. s 2 ) stops transmitting m 1 (resp. m 1 and m 2 ) upon reception of the acknowledge message regularly sent by s 2 (resp. h 2 ). Suppose h 1 did not receive neither m 1 the first time s 1 broadcast it due to interferences, nor its acknowledgment. Hence, h 1 retransmits m 1 . s 1 ignores the second reception of m 1 since it already received m 1 . Upon reception of m 2 , s 1 broadcasts it. Then h 1 receives and buffers m 2 because the sequence number that s 1 attached to m 2 is equal to 2, and h 1 awaits a message with seq=1. Eventually, s 1 broadcasts m 1 again and, upon reception, h 1 delivers m 1 then m 2 . Finally, h 1 (resp. s 1 ) acknowledges m 1 and m 2 (resp. m 1 ). Hence, m 1 and m 2 are completely discarded from the network, i.e., removed from the buffers of all nodes. Host h i might also move to another cell s j before receiving connect ACK from its previous station s i . In this case, h i will send a join message to s j , despite the fact that s i might have also received a join message, and therefore registered h i . However, a host should be connected to only one station, which is the one that received the latest join message sent by the host, in this case s j .

In order to handle its multiple registrations, h i keeps the list PS which contains the stations that might have registered its connection attempts. It identifies each of these attempts with a connection sequence number, denoted Ses, which it increments when changing cells. Thus, when h i changes cells during the connection Ses, before receiving a connect ACK message from s i , h i saves the tuple (s i , Ses) in PS. Host h i then attaches PS to the join message sent in the new cell. Every station also keeps the Ses value corresponding to the latest connection of every host connected to it.

Station s j replies to join with a connect ACK message which contains seq C , the sequence number of the oldest message s j caches in SBuffer. It also registers h i and sends a Delete message for each tuple (s i , Ses) in PS. Upon receiving a Delete message, s i unregisters h i , if it has been registered in the connection Ses. Such a procedure ensures that eventually h i is only registered at s j .

Upon reception of connect ACK , h i completes the connection initialization by updating seq NC to seq C , and PS to (s j , Ses), since s j will be the station that will control causal information related to it. h i will then deliver messages based on seq NC sequence number.

Leaving the network. A host leaves the network by sending a leave message containing PS, until a station, regardless of which one, acknowledges it. The station which receives leave sends a Delete message to each station s of the tuples (s, Ses) of PS, which will unregister h i if registered.

Handoff procedure

A station maintains causal information related to those hosts connected to it. Hence, when a host h i changes cell, its causal information must be transferred from its previous cell's station s p to its new cell's station s n . Existing handoff procedures [START_REF] Chandra | Causal multicast in mobile networks[END_REF]

[2][3] make s p s n h i h j 1 m1 1 m 2 2 m 1 2 m 2 3 m 1 m 2 3 m 2 m 1
Figure 4: Sequence number assignation by stations several unrealistic assumptions, such as reliable wireless channels or that a moving host always succeeds in connecting to its cell's station before moving to another cell.

Moreover, they usually identify messages on the wired network by vector clocks, whose size is the number of stations. Hence, they are not scalable in terms of stations. The handoff procedure of our algorithm does not make such assumptions and its dissemination approach scales. It handles message losses on the wireless network as well as simultaneous connection attempts of the same host, without doing assumptions about the success of those connection attempts. Our dissemination approach scales, but requires an extra control to compare the message ordering at stations. Finally, our algorithm implements a decentralized discard approach of obsolete messages at stations, removing the message and memory overhead of centralized approaches, but also requiring an extra control when hosts change cells.

We start the handoff section by discussing the problems that the handoff procedure faces (handoff challenges), then we describe the handoff procedure algorithm itself, and finally, we give a handoff execution example.

Handoff challenges.

We highlight the following points: Host connections. In a real configuration, a moving host h i cannot determine which station keeps its causal information, since it cannot distinguish between cases (b) and (c) of Figure 3. Furthermore, it might connect to several stations in a short time interval, which might lead to simultaneous h i 's handoff instances. Thus, simultaneous handoff procedures of host h i must be handled, by ensuring that the latest handoff procedure will correctly be executed and that previous handoff procedures are ended/aborted.

Message ordering. In the dissemination phase, stations assign local sequence numbers to messages as they are received. For example, in Figure 4, at 1 , h i and h 2 broadcast m 1 and m 2 respectively. At 2 , s p receives m 1 and forwards it to s n . Similarly, s n forwards m 2 to s p . At 3 , s p and s n respectively adopt [m 1 ,m 2 ] and [m 2 ,m 1 ] orders. Consequently, if h i delivers m 1 while connected to s p and then connects itself to s n , s n cannot assign to h i the sequence number seq NC =1, because h i would then never deliver m 2 and deliver m 1 twice. In fact, seq NC is only meaningful for the last initialized connection of h i , which is identified by Ses LC , the last connection number in which h i initialized seq NC . To determine which messages h i has delivered, s n must therefore exchange information with s p .

Decentralized discard mechanism of obsolete messages. A station discards a message once all hosts connected to it have acknowledged the message. This local deletion approach may lead to different SBuffer states of s n and s p : when h i connects to s n , s n might have already discarded messages that s p still caches, and that h i did not deliver yet. For instance, in Figure 4, suppose that h i connects to s n before delivering m 2 , but that s n already discarded m 2 when h i connects to it. s n must then recover m 2 from s p , and h i should deliver m 2 before delivering messages currently broadcasted by s n .

Task of h i :

Moving from s p 's cell to s n 's cell Another point that makes the comparison of the SBuffer states of s n and s p difficult, is that s p does not maintain information about messages it has already discarded. For example, in Figure 4, if s p deletes m 1 once h i acknowledged it, then when h i moves to s n , s p cannot inform s n that h i has already delivered m 1 , since it caches no information about m 1 . Moreover, since stations receive messages at different times, s n might receive messages that s p only receives later. s n must distinguish between messages that s p receives during the handoff from messages that s p already discarded (i.e. m 1 ).

Handoff procedure description.

When h i moves to s n 's cell, it sends a connect message to s n that contains: the connection sequence number Ses, the connection sequence number Ses LC of its last acknowledged connection, the sequence number seq NC of the last message h i delivered, and the list PS containing the stations that might register h i . The pseudo-code of the handoff procedure is given by Tasks h i , s n , and s p .

s p = s 1 s n = s 2 m 2 m 2 m 2 m 1 m 1 m 1 m 3 m 3 m 3 m 3 m 3 m 3 h i c o n n e c t c o n n e c t c o n n e c t R e q 1 R e q 1 R e q 1 R s p 1 R s p 1 R s p 1 R e q 2 R e q 2 R e q 2 R s p 2 R s p 2 R s p 2 h i A p p = 2 A p p = 2 A p p = 2 a c k a c k a c k
Upon reception of a connect message, s n verifies if it has already registered h i (line s n .1) which happens if (1) h i was previously connected to s n , then tried to connect to another station but the connect message was lost (Figure 3.b), and then h i tried to re-connect to s n ; (2) s n already received the connect message but the connect ACK message was lost (Figure 3.c). Station s n distinguishes between (1) and ( 2) with the help of Ses i , since in case (1), Ses LC is equal to Ses i . In this case, h i might have delivered messages without acknowledging them and, therefore, s n takes seq NC of h i as an acknowledgment. In both cases, if h i has no message to deliver which s n discarded from its SBuffer, then s n sends a connect ACK message to initialize the connection on h i 's side (s n .7). On the other hand, s n registers h i if not registered (lines s n .9 -s n .10) and starts the handoff procedure.

Figure 5 shows a handoff procedure, which is a message exchange composed of three phases:

• Phase 1: detection by s n of discarded messages that h i has not delivered. Messages Req 1 and Rsp 1 are exchanged between s p and s n in this phase. • Phase 2: detection by s n of messages that h i has not delivered among messages that s n caches. Messages Req 2 and Rsp 2 are exchanged between s p and s n in this phase. • Phase 3: initialization of the connection between s n and h i . Phase 1: s n starts this phase by sending Req 1 to the previous stations included in PS that might register h i (line s n .10). Note that (1) all messages not delivered by h i that s n discarded were received by s n before send(Req 1 ), because s n discards no message after the reception of h i 's connect message unless h i acknowledged it; (2) the FIFO dissemination approach on the wired network ensures that, upon reception of Req 1 , s p receives all messages that s n received before sending Req 1 . Upon reception of Req 1 , station s p uses seq NC piggybacked onto Req 1 to identify the messages that h i has not delivered yet (line s p .8), and sends their respective id via Rsp 1 .

The FIFO dissemination approach on the wired network ensures that, upon receiving Rsp 1 , s n received all messages that h i could have delivered in previous connections. s n might have already discarded some of those messages. s n identifies the messages it discarded but that h i has not delivered (lines s n .12), and requests them in Req 2 message. Then, s p piggybacks these messages onto the Rsp 2 message, keeping the same order as in its SBuffer (line s p .13).

Simultaneous handoff procedure instances for h i are handled sequentially. If Req 1 messages are received during a handoff execution, the one with the highest Ses value is kept pending provided that it is newer than the current handoff's Ses value. The station will handle that Req 1 at the end of the current handoff (line s p .20). Req 1 messages with lower Ses values concern handoffs of previous connection attempts and are discarded. At the end of the handoff s n sends a Delete message containing the handoff's Ses value (line s p .2) to the stations of PS so that those stations unregister h i .

Phase 2: The FIFO dissemination approach on wired channels guarantees that messages that h i could deliver when connected to s p are received by s n at latest at Rsp 1 , since Rsp 1 was sent after that s n sent connect, and h i delivers no message from s p after changing cell (after sending connect). Messages not delivered by h i that s n receives before sending Req 1 are identified by s p in Rsp 1 . Phase 2 identifies messages that s n receives between send(Req 1 ) and receive(Rsp 1 ) that h i has not delivered.

The FIFO dissemination on wired channels also guarantees that messages received by s n between send(Req 1 ) and receive(Rsp 1 ) are surely received by s p between receive(Req 1 ) and receive(Req 2 ). s p saves the id of such messages and sends this list of ids to s n in Rsp 2 message (lines s p .9 -s p .12).

Upon reception of Rsp 2 , s n determines which messages h i has not delivered among those received before Rsp 1 . The messages are those (1) s p identified as not delivered by h i (line s p .8), (2) s p received between the receptions of Req 1 and Req 2 (line s p .12). On the other hand, h i has already delivered all the other messages s n received before Rsp 1 . Moreover, messages that s n receives after Rsp 1 are not delivered by h i because the FIFO dissemination approach on wired channels ensures that all messages received by s p before it sent the Rsp 1 message were also received by s n before receive(Rsp 1 ).

Phase 3: Assigning a sequence number to h i is not sufficient to identify all messages already delivered by h i . For example, in Figure 4, if h i delivered m 1 before connecting to s n but did not deliver m 2 , then s n must give to h i the sequence number 0 (seq NC = 0), so that it will deliver m 2 . However, without additional control, h i would then also deliver m 1 again. To prevent h i of delivering the same messages twice, s n adds h i 's id to the messages h i already delivered but which are still cached in s n 's SBuffer(line s n .14), and, upon receiving them, h i will only increment seq NC and not deliver them again.

Moreover, s n must send to h i messages identified at Phase 2 that it already discarded but that h i did not deliver. s n sends these messages to h i , ordered as in msg, also piggybacking (id h i ,Ses i ) that identify the handoff procedure instance. Once h i acknowledged all of them, or if h i has no message to deliver that s n discarded (s n .16), then s n concludes the handoff by sending a connect ACK message to h i with seq C i , the sequence number of the oldest message in s n 's SBuffer that h i has not delivered (line s n .18). At its side, h i ends the handoff by setting seq NC , seq h , and Ses LC (line h n .4).

Handoff example

Figure 5 presents the handoff executed when h i , previsouly connected to s p , tries to connect to s n in the configuration of Figure 4. For better readability, we assume that no other handoff procedure takes place simultaneously for h i . At the beginning of the handoff s p has discarded m 1 , s n discarded m 2 , and h i delivered m 1 . Both stations receive m 3 during the handoff.

Host h i sends a connect message to s n , which contains seq NC =2, since h i delivered m 1 . Upon reception of the connect message, s n sends Req 1 to s p with seq NC =2. When receiving Req 1 , s p concludes that h i has not delivered m 2 and replies with Rsp 1 = {{id(m 2 )}, seq h = 1} (seq h =1 since h i already broadcasted m 1 ). s n requests then m 2 via Req 2 , since it has already discarded m 2 . s p replies with Rsp 2 containing the requested message ({m 2 }) and the list of messages received between Rsp 1 and Rsp 2 ({id(m 3 )}). Finally, s p unregisters h i . s n determines with Rsp 2 which messages of its SBuffer={m 1 , m 3 } h i has delivered. s n received m 1 before Rsp 1 , and s p did not identify m 1 as not delivered by h i . Hence, h i already delivered m 1 and s n adds h i 's id via m 1 . In addition, h i must first deliver m 2 before delivering m 3 . Thus, s n resends m 2 received from s p with seq C =0 to h i . Finally, s n discards m 2 once h i acknowledged it, assigns seq C i =3 to h i , since h i delivered m 1 and m 2 , and sends connect ACK to h i . Upon reception of connect ACK , h i sets seq NC =3.

Host failures

Hosts can fail temporarily or permanently and stations handle such failures. The duration of temporal failures should be bounded in time. In fact, a station does not discard a message until all hosts of its cell, including the faulty one, have acknowledged the message. Hence, a long temporal failure would increase the number of messages a station broadcasts, which in turn would increase the station's cell's message collision rate. The latter would then decrease the throughput, which could reach the point where messages are delivered more slowly than new messages are broadcasted, degrading the cell forever. Thus, stations control their cell's collision rate and a station unregisters a faulty host before this rate becomes too high. A station considers that a host is faulty when it does not receive any message from the host during a given time interval, or if the message collision rate becomes too high due to the lack of acknowledgments from the host.

Few variables of the host's persistent local storage should be restored when it recovers from a temporal failure: seq h , seq NC , Ses, and Ses LC , and unacknowledged messages broadcasted by the host before its failure. Note that the number of these messages is quite small since messages are acknowledged very fast. A host saves seq h (resp., seq NC ) when broadcasting an application (resp., acknowledge) message, Ses when changing cell, and Ses LC when the host receives the confirmation that the station registered it. Upon recovering, the host restores these variables and sends a recover message to the station of its cell. However, since a faulty host can move during its temporal failure or stay faulty for a long time, this station might not keep the host's causal information. If the station still registers the host, it replies to the host with a connect ACK message. Otherwise it broadcasts a recovery req to stations, which reply with either the host's causal information, or a message that notifies that they do not store the host's causal information. If no station maintains the host's causal information, the end of the recovery procedure is similar to the join procedure, otherwise to a cell changing.

Summing up, our algorithm tolerates permanent and transient failures, requiring few persistent information. Based on wireless message loss rate and timeouts, a station removes from its memory a host that permanently or temporarily failed. We point out that, inherent to wireless networks, interferences constrain the effectiveness of transient fault tolerance.

PERFORMANCE EVALUATION

Experimental setup. Experiments were conducted on INET, a network simulator implemented on OMNeT++ [START_REF] Varga | The omnet++ discrete event simulation system[END_REF]. INET offers communication layers (e.g., TCP/UDP/Ethernet/IPv4/MAC), node mobility, node failures, and network interferences in wired and wireless networks.

Since no causal broadcast in mobile networks has been proposed yet, we compare our algorithm, denoted WAS, with the one proposed by Chandra and Kshemkalyani [START_REF] Chandra | Causal multicast in mobile networks[END_REF], denoted CK, which we have described in Section 6. We extended CK, which provides a causal multicast algorithm, to causal broadcast.

Stations are placed to ensure a complete area coverage with a minimum intersection of cells. Hosts are placed randomly in each cell at initialization. Antennas have a communication range of 120m and a bandwidth of 20Mb/s. Stations are connected by a wired network organized into a tree of degree 3 whose links have a bandwidth of 100Mb/s and a delay of 10ms. Application messages have a size of 100 bytes and are encapsulated in IPv4/MAC packets, whose header has 8 (resp., 20) bytes for UDP (resp., TCP). Therefore, an UDP (resp., TCP) packet has an overhead of 20(IPv4)+20(MAC)+8(UDP)=48 (resp., 60) bytes. UDP is used for communication on the wireless network, while TCP on the wired network. Each host broadcasts application messages following a Poisson distribution. Hosts move in a straight line with a speed of 5km/h≈1.39m/s inside the area covered by stations, and change direction every 5 seconds.

Experimental results concern three evaluations: (1) scalability comparison between WAS and CK, (2) comparison between a centralized and decentralized message discarding, (3) execution of WAS in a scenario with faulty hosts.

Scalability

Throughput and delivery delay. The first experiment, whose results are shown in Figure 6, evaluates the maximal throughput when the number of hosts per cell increases. The experiment contains 10 stations and a total number of hosts that varies from 100 to 400 (x-axis). Results, presented in a logarithmic scale, show that WAS has a much higher (x10-20) throughput than CK, and that the throughput of CK decreases faster than WAS. In a system containing 400 hosts, the maximal throughput of WAS is more than 20x higher than CK. The throughput of CK is bounded mostly by the fact that a station only sends an application message to a host once the latter has acknowledged all the message's dependencies. Consequently, hosts send acknowledge messages very frequently, which negatively impacts performance because of a higher message collision rate on the wirless network. Moreover, CK has a delivery delay -the delay between broadcast(m) and deliver(m) -2 times higher than WAS, because a station waits that a host acknowledges a message's dependencies before sending it to the host.

The second experiment measures the size and number of messages, evaluated at the IPv4 level, when the number of hosts increases. Results are shown in Figures 7 and8 respectively. The number of stations is adapted to keep a ratio of 20 hosts/cell. 20 messages are broadcasted per second in the system.

Number of sent messages. Figure 8 shows that WAS sends much fewer messages on both the wired and wireless networks. Moreover, the number of messages sent by CK increases much faster than the number of messages sent by WAS. WAS sends fewer messages on the wireless network because (1) hosts acknowledge messages less often than CK (20x), ( 2 8: Sent messages in the network reception following seq NC piggybacked on messages, contrarily to CK where hosts do not buffer messages since stations only send a message m to a host once the host can causally deliver m. Hence, stations must retransmit messages less often than with CK (x5). On the wired network, CK sends more messages due to its centralized approach to discard obsolete messages. WAS implements a decentralized mechanism which requires no message exchange to discard obsolete messages. We point out that CK sends much fewer messages on the wired network than theoretically expected, because acknowledge messages of CK are small, and TCP groups many of them in a single packet.

Amount of sent data. Figure 7 shows that WAS sends a lower amount of data than CK. On the wireless network, this is mostly due to acknowledge messages. Even though these messages contain only a few integers, they have an additional size of 48 bytes because they are encapsulated in UDP/IPv4/Mac packets. However, only a few acknowledge messages can be grouped into one single packet since the station will not send the next messages to deliver until the current ones are acknowledged. On the wired network, acknowledge and delete messages are grouped by TCP, which mostly removes the encapsulation overhead. However, those many acknowledge and delete messages scale up fast. Moreover, with CK stations piggyback a vector of size N (N=number of stations) on application messages sent over the wired network, and that vector rapidly takes much space when the number of stations increases. WAS only piggybacks a few integers on application messages.

Decentralized discard mechanism

This section compares our decentralized discard approach, used by WAS, with the existing centralized discard approach [START_REF] Chandra | Causal multicast in mobile networks[END_REF].

In the third experiment, 200 hosts are distributed over 10 cells, the wireless network has a bitrate of 1Mb/s, and 35 messages are broadcasted per second for 300s. Figure 9 shows the number of messages that stations store in their respective SBuffer. Curve Max shows the maximum number of messages cached in a stations' SBuffer, i.e., approximately the number of messages each station would store with a centralized discard approach. Curve Avg shows the average number of messages a station stores in its sending buffer, and curve Deviation gives the standard deviation between the average and the number of messages each station caches. The curves Avg and Deviation do not take into account the SBuffer of the station that stores the most messages, in order to compare both curves with the Max curve.

The comparison of curves Avg and Max of Figure 9 shows that the number of messages cached by stations can vary a lot. Such a variation depends on the message loss rate in the station's cell: the higher the message loss rate, the longer a station caches a message, since lost messages must be retransmitted. The message loss rate depends on the number of messages to broadcast as well as the position of hosts in the network. The probability of message collision is higher in areas where two cells overlap because the respective stations send messages over their cells that might collide. Similarly, areas with a high density of hosts have a higher message loss rate. The standard deviation is low, mostly around 10 messages, except for a short period around 70s where a heavily loaded cell degrades its adjacent cells. Hence, the number of messages a station stores in SBuffer is mostly close to the average for all stations, except for some stations whose local characteristics make their send buffer grow temporarily. In a decentralized message discard approach, message loss rate and failing hosts only have a local impact. The comparison of curves Avg and Max shows that with a decentralized message discard approach, stations store up to 4 times fewer messages than with a centralized one, and that, on average, stations store 40-50% fewer messages.

Finally, a host that fails stops acknowledging messages. Hence, the station which the host is connected to will stop discarding messages, and Figure 10 shows that, in presence of host failures, the station to which the faulty host is connected then caches many more messages than the other stations (8-10x more). Hence, the decentralized discard approach caches up to 8-10 times fewer messages on stations in presence of host failures.

Transient host failures

The last experiment, whose results are presented in Figure 10 for 5s, the second at t=40s for 7s, and so on. When a host fails it stops acknowledging messages. The number of messages cached in the SBuffer of the station that registers the faulty host then grows. Hence, we measure the impact of transient failures through the number of messages cached in the SBuffer of that station.

Curve Max shows the maximum number of messages cached in a station's SBuffer which is, during failures, the number of messages cached by the station at which the faulty host is registered. Curve Avg shows the average number of messages a station stores in its SBuffer, and curve Deviation gives the standard deviation between the average and the number of messages each station caches. In order to evaluate the impact that a cell containing a faulty host has on the other cells, the former is not taken into account in the computation of Avg and Deviation. Vertical dashed lines represent a host crash.

During each failure, the number of messages cached by the station that registers the faulty host linearly increases. Those messages are also broadcasted by that station. Nevertheless, the number of cached messages sharply decreases once the host recovers, showing that, very fast, the host receives the missing messages and the cell rapidly reaches the same message load it had before the failure.

Curve Avg shows that, on average, a faulty host has a low impact in the number of messages stored by the other stations, except for the last failure occurring at t=255s.

Curve Deviation also shows that the increasing size of SBuffer of the faulty host's station has no impact on other cells, as long as the SBuffer does not become bigger than 150-200 messages. Once the SBuffer exceeds that size, the faulty host's station begins to degrade adjacent cells that overlap with it. In fact, the station broadcasts application messages and retransmits messages not acknowledged by the faulty host, thus increasing the number of messages sent by the station. This leads to an increasing number of message collisions in the cell, including the areas where the cell overlaps with other cells. Hosts in those overlapping areas, connected to other stations, will receive fewer messages, because of this higher message collision rate. Hence, they will deliver messages more slowly, increasing the number of messages broadcasted by the neighboring stations of the faulty host's cell. During the last crash occurring between t=250s and t=273s, the 3 adjacent cells of the faulty host's cell are impacted, explaining why the average size Therefore, the failure of a host first and mostly has an impact in the cell in which it occurs and afterwards in adjacent cells when its cell's station stores more than 150-200 messages. Nevertheless, such an impact rapidly disappears once the host recovers.

In conclusion, experiments confirm that WAS is more scalable than CK in terms of the number of hosts per cell, as well as in terms of total hosts and/or stations. WAS sends much fewer messages than CK both on the wired and wireless network, the amount of sent data is also much lower, and WAS has half the delivery delay of CK. Second, the decentralized message discard mechanism of WAS caches much fewer messages than CK, particularly during host failures. Finally, in WAS, the impact of a transient host failure is sharply absorbed after the faulty host recovers.

RELATED WORK

Charron-Bost proved [START_REF] Charron-Bost | Concerning the size of logical clocks in distributed systems[END_REF] that without additional assumptions on the system, the size of the information required to causally order messages grows linearly with the number of nodes of the system. Therefore, solutions based on logical clock vectors [START_REF] Fidge | Timestamps in message-passing systems that preserve the partial ordering[END_REF][13] [START_REF] Birman | Lightweigt causal and atomic group multicast[END_REF] are not suitable to huge mobile networks since they are not scalable.

Plausible clocks [START_REF] Rojas | Plausible clocks: Constant size logical clocks for distributed systems[END_REF], Bloom filters [START_REF] Ramabaja | The bloom clock[END_REF], and Probabilistic clocks [START_REF] Mostéfaoui | Probabilistic causal message ordering[END_REF] have constant size and ensure causal order with high probability. However, even though they greatly reduce causal control information in networks with a large number of nodes, messages might be delivered out of causal order.

Hierarchical approaches [START_REF] Adly | Maintaining causal order in large scale distributed systems using a logical hierarchy[END_REF] group nodes into clusters and logically organizes them in a tree. Causal information is handled only at the cluster level. However, clusters must be reorganized in presence of nodes churn and a node moves only inside its own cluster. Hence, such a solution cannot be applied to mobile networks because hosts move between cells/clusters and join/leave the network.

Many causal dissemination protocols [5][16][15] [START_REF] Santos | Localized reliable causal multicast[END_REF], exploiting message propagation and forwarding over reliable FIFO links on overlay networks, have been proposed in the literature. They do not require any causal information since messages are implicitly causally ordered at reception. A static tree is used in [START_REF] Blessing | Tree topologies for causal message delivery[END_REF] to disseminate messages while, by using scalable data structures, [START_REF] Nédelec | Breaking the scalability barrier of causal broadcast for large and dynamic systems[END_REF] [START_REF] Nédelec | Causal broadcast: How to forget?[END_REF] extend [START_REF] Blessing | Tree topologies for causal message delivery[END_REF] protocol for dynamic systems. Nevertheless, the considered dynamics of the system cannot be applied to mobile networks, because every new channel must be initialized by message exchange through already initialized channels. Consequently, a path of initialized channels must always connect each pair of nodes, which is not always the case when a host moves to a new cell without having initiated the connection with the latter.

In [START_REF] Santos | Localized reliable causal multicast[END_REF], a reliable causal multicast is presented where nodes maintain only local metadata about their neighborhood, being, thus, scalable. The algorithm tolerates faults and outperforms other multicast causal algorithms with local views, but channels are assumed to be static.

Several works [START_REF] Chandra | Causal multicast in mobile networks[END_REF][17] [2] [3] [START_REF] Li | A mobile-support-station-based causal multicast algorithm in mobile computing environment[END_REF] have proposed causal multicast for mobile networks.

Chandra and Kshemkalyani [START_REF] Chandra | Causal multicast in mobile networks[END_REF] consider a dynamic system composed of fixed stations and mobile hosts. For each connected host h, a station maintains information to control causal order on behalf of h. When a node h moves to a new station, its information is transferred from the previous station to the new one. A node can leave its previous station only after the new station has acknowledged the reception of such information which implies some constraints on the mobility model. Moreover, the algorithm implements a centralized message discarding of obsolete application messages, which has an overhead both in terms of stored messages in station SBuffer and number of messages sent over the wired network: each application message m is managed by a station called MSS init , and acknowledge messages for m from each host are forwarded to MSS init . Once MSS init received an acknowledge message from each host, it broadcasts a delete messsage to all stations in order to discard m.

In [START_REF] Prakash | An efficient causal ordering algorithm for mobile computing environments[END_REF], messages piggyback only direct dependencies. Such an approach copes with the dynamics of mobile networks since causal information does not depend on node identifiers. However, every node, including mobile hosts that have memory limitations, maintains a matrix of size N 2 , where N corresponds to the maximum number of nodes in the system. Moreover, the information piggybacked on messages grows with the number of concurrent messages In [START_REF] Anastasi | A reliable multicast protocol for distributed mobile systems: Design and evaluation[END_REF], the authors propose a multicast protocol that tolerates a dynamically changing system membership. On the other hand, host mobility is not supported by the algorithm, which does not implement any handoff procedure. Contrarily, [START_REF] Benzaid | An optimal causal broadcast protocol in mobile dynamic groups[END_REF] and [START_REF] Li | A mobile-support-station-based causal multicast algorithm in mobile computing environment[END_REF] present causal multicast protocols that tolerate node mobility among stations, but both consider that wireless channels are FIFO and reliable, the connection protocol is reliable, and hosts do not fail, which are not realistic assumptions.

CONCLUSION

We have presented in this article a causal broadcast algorithm tailored to the features and dynamics of mobile networks. The latter include host mobility, dynamic host membership, unreliable dynamic wireless channels, memory and computing constraints of mobile hosts, scalability issues due to the high number of mobile hosts and stations, and mobile host failures. Messages piggyback few causal information. Mobile hosts have a low memory footprint while stations have a memory footprint that grows linearly with the number of locally connected mobile hosts. Stations discard obsolete messages with only local information, removing the message exchange between stations used by centralized message discarding approaches.

Performance results from simulations done on OMNeT++/INET show that our algorithm has a much lower message overhead, delivery delay, and caches fewer messages than a representative algorithm adapted to provide causal broadcast [START_REF] Chandra | Causal multicast in mobile networks[END_REF]. Furthermore, the decentralized approach to discard obsolete messages of our algorithm results in much fewer messages cached by stations, as well as much fewer messages sent on the network compared to a centralized approach. Finally, performance results show that hosts that temporarily fail fastly catch up after recovering, and that the decentralized discard approach of obsolete messages mostly limit the impact of host failures to the cells in which those failures occure.

APPENDIX -PROOF OF THE ALGORITHM Proof when nodes never move between cells

Theorem 1: WAS ensures causal broadcast in mobile networks when hosts do not move between cells. Validity. A station initially disseminates only messages co-broadcasted by hosts connected to it. Hence, all application messages disseminated among stations are messages co-broadcasted by a host. Moreover, a host only codelivers messages that the station to which it is connected sends to it. Hence, hosts only co-deliver messages co-broadcasted by hosts. Integrity. The wired network connecting stations is FIFO and reliable. Hence, on the wired network, our dissemination approach ensures that every station receives each message once and that the message is causally ordered at reception. Each station then attributes a unique sequence number to each message it receives and sends them to the hosts of its cell. A host delivers messages in increasing sequence number. Thus, a host that delivers a message m will never deliver m again, since its local sequence number will be greater than the sequence number of m. Causal order. As explained above, messages are causally ordered upon their reception at stations. A station attributes an increasing sequence number to each message following its arrival time. Hence, if m → m ′ , then stations receive m before m', and, therefore, m.seq < m ′ .seq. Moreover, hosts deliver messages in increasing sequence number. Hence, hosts deliver messages causally ordered. Termination. A host h i that joins the system is not considered up until the station s i to which h i connects itself receives h i 's join message. Upon reception of the message, s i attributes to h i the sequence number of the application message it caches with the lowest sequence number. Moreover, s i retranmits the join acknowledgment as well as every cached application message until h i acknowledged each pf them (i.e., after having delivered it), or s i considers h i as down. Hence, all messages that s i did not discarded upon the reception of h i 's join message will be delivered by h i , given that h i remains an up process.□

Proof when nodes move between cells

Now we show that WAS ensures causal order even when hosts move between cells.

Lemme 1: When a host h i leaves the cell of station s p and connects to station s n , then s n recovers those messages it has previously discarded and that h i has not delivered yet. First, s n does not delete messages after s n .recv(connect) from h i unless h i acknowledges them. On the other hand, messages not delivered by h i but discarded by s n are received by s n before s n .recv(connect). Station s n recovers those discarded messages during the handoff with s p : (1) Phase 1 composed of Req 1 and Rsp 1 identifies them. The reliable FIFO channels connecting stations ensure that, when s p receives the Req 1 message sent by s n , it received all the messages that s n received prior to s n .recv(connect). s p replies to Req 1 with Rsp 1 which contain msg, the list with the ids of messages h i have not delivered among those s p received before Req 1 . (2) Phase 2 composed of Req 2 and Rsp 2 recovers at s n the messages of msg that s n has discarded. In Req 2 , s n requests to s p the messages of msg nd it has already discarded, and s p sends them to s n in Rsp 2 . Thus, at the end of Phase 2, s n buffers all messages it has discarded prior to the connection of h i that it has not delivered yet.

Lemme 2: Upon reception of Req 1 , s p received all messages that h i has delivered. h i stops to deliver messages once it sends a connect message to s n , and will only deliver messages again after receiving connect ACK from s n . Moreover, s n sends Req 1 to s p after receiving connect from h i . Hence, s p receives Req 1 after that h i sent connect, i.e., after h i stopped to deliver messages. Since s p handles the causal information of h i , the latter only delivers messages already received from s p . Hence, messages that h i delivered are received by s p at latest when s p receives Req 1 .

Lemme 3: Upon reception of Rsp 1 , s n received all messages that h i has delivered. Following Lemme 2, upon reception of Req 1 , s p received all messages that h i delivered. s p forwarded all those messages to s n (FIFO dissemination). Moreover, s p replies to Req 1 by sending Rsp 1 to s n . The FIFO dissemination ensures that, upon the reception of Rsp 1 , s n received all messages that s p forwarded prior to s p 's reception of Req 1 . Therefore, upon the reception of Rsp 1 , s n received all messages that s p broadcasted until its reception of Req 1 , i.e., messages that h i might delivered.

Lemme 4: The union of the lists m nd of Rsp 1 and msg rcv of Rsp 2 contain the id of messages that h i did not deliver among the messages that s n receives before the reception of Rsp 1 . Following Lemme 2, h i did not deliver any message that s p receives between Req 1 and Req 2 . msg rcv contains those messages. Among the messages that s p received before the reception of Req 1 , those not delivered by h i are contained in m nd . Therefore, m nd ∪ msg rcv contains the list of messages (or their id) not delivered by h i among the messages s p received upon the reception of Req 2 . The FIFO dissemination ensures that upon reception of Req 2 , s p received all messages that s n received upon reception of Rsp 1 . Hence, m nd ∪ msg rcv contains the list of messages or their id not delivered by h i that s n received upon the reception of Rsp 1 .

Lemme 5: Messages that h i has not delivered are those that s n receives before Rsp 1 identified or contained in m nd ∪ msg rcv and the messages s n receives after Rsp 1 . Following Lemme 4, messages that h i has not delivered among the ones s n receives before Rsp 1 are those contained in m nd ∪ msg rcv . Following Lemme 3, messages that h i delivered are received by s n upon its reception of Rsp 1 . Hence, all messages s n receives after Rsp 1 are not delivered by h i .

Lemme 6: To respect causal order, h i must first deliver the messages of msg rcv of Rsp 2 , i.e., messages that s n discarded before the connection of h i but that h i did not deliver, before delivering messages currently broadcasted by s n . Hosts acknowledge messages whose sequence number is lower than their seq NC . Hence, messages that s n discards have a lower sequence number than messages s n still caches. h i must, therefore, first deliver messages of msg, since hosts deliver messages in increasing sequence number.

Theorem 2: WAS ensures causal broadcast in mobile networks where hosts move between cells. Following Theorem 1 WAS ensures causal broadcast in mobile networks where hosts do not move between cells. We will show that the handoff procedure of WAS ensures that the causal information of a host that moves to a new cell is transmitted to the new cell's station and, therefore, the new cell's station also ensures causal broadcast for the moving host. Validity. The validity of causal broadcast does not change when hosts move between cells. Hence, the validity proof of Theorem 1 holds. Integrity. Following Theorem 1, hosts co-deliver a message at most once when not changing cell. Let's show that when a host h i moves from the cell of station s p to the cell of station s n , that s n will identify the messages that h i did already deliver, and that h i will not deliver those messages again. Following the corollary of Lemme 5, messages that s n caches that h i has already delivered are those that s n receives before Rsp 1 that are not identified in m nd ∪msg rcv . «««< HEAD s n broadcasts these message piggybacking h i 's id on them, and h i does not deliver them, but only increments its sequence number to deliver the next messages sent by s n . Moreover, following Lemme 5 messages that s n receives after Rsp 1 are not delivered by h i . Therefore, h i will not deliver again messages it has already delivered. Hence, h i will not deliver any message twice, i.e., h i will deliver a message at most once. Causal order. Theorem 1 shows that causal order is ensured when hosts do not change cell. Let's show that when a host changes cell, no application message is lost and that the host delivers them respecting causal order. Following Lemme 6, h i must first deliver messages it has not delivered yet but that s n discarded prior to its connection. Following Lemme 1, s n recovers those messages at s p which orders them in the list msg rcv of Rsp 2 following their reception order. Moreover, s n sends them to h i before sending to h i messages it currently broadcasts. Therefore, h i will deliver those messages in FIFO (and consequently in causal) order. Following the corollary of Lemme 5, messages that s n caches that h i has already delivered are the messages that s n receives before Rsp 1 that are not identified in m nd ∪ msg rcv . s n piggybacks h i 's id on those messages, and h i does not deliver them, but only increments its sequence number to deliver the following messages sent by s n . Hence, all messages which piggyback h i 's id have been already delivered by h i . For all other messages cached by s n , h i will deliver them in increasing sequence number order. Hence, h i first delivers messages not cached anymore by s n , then it delivers the messages cached by s n in increasing sequence number order, i.e., causally ordered. Termination. Theorem 1 shows that the termination is ensured when hosts never move between cells. Let's show that an up host that changes cell will co-deliver all application messages. Note that a host that delivers no message because it changes to often its cell would eventually be considered as down by the station registering it. Therefore, periodically, hosts are supposed to be long enough inside a cell in order to deliver outstanding application messages. Let's consider that host h i moves from the cell of station s p to the cell of station s n . Following Lemme 1, s n recovers messages it discarded among those h i has not delivered yet in the list msg rcv of Rsp 2 . s n then sends those messages to h i . Moreover, after receiving the connect message from h i , s n will not discard any message unless it considers h i as down, and will retransmit them periodically until h i acknowledges them. Hence, the handoff procedure ensures that s n recovers and sends to h i all messages it discarded that h i has not delivered, and for all other messages not delivered yet by h i , s n caches them and will retransmit them until h i acknowledged them.□ Proof that handoffs finish and that the most recent will execute Lemme 8: PS that host h i appends on connect messages contains the station that holds h i 's causal information, as well as the corresponding connection sequence number. Station s n only sends a connect ACK to h i once it received h i 's causal information. Hence, h i knows, when receiving a connect ACK message from s n during the connection Ses k , that s n maintains its causal information during the connection with sequence number Ses k . Hence, h i sets PS to (s n , Ses k ) when it receives a connect ACK message from station s n during the connection Ses j . Otherwise, when h i changes cell, it appends the tuple (s i , Ses j ) on PS when it connects to station s i with the connection sequence number Ses k . Hence, PS contains the identifier (s n , Ses k ) of the last confirmed connection that maintained its causal information, as well as the tuples (s i , Ses j ) of later connections that might maintain its causal information.

Lemme 9: All connections not included in PS that h i appends on connect messages are either finished or will be finished by a Delete message. h i adds the tuple (s i , Ses j ) to PS each time it changes cell and connects to station s i with connection sequence number Ses j . It sets PS to (s n , Ses k ) when receiving a connect ACK from s n during the connection Ses k . Hence PS contains the connection identifiers since the last connection (s n , Ses k ) in which h i received a connect ACK . When sending a connect ACK message, s n also sends a Delete message for all connections of PS. A non finished connection (s i , Ses j ) of PS will then be finished by station s i at reception of the Delete message. Hence, all connection not contained in PS are either finished or will be finished by a Delete message.

Lemme 10: If several handoffs occure simultaneously for the same host, then the station that started the handoff with the highest session sequence number, i.e. the handoff of the most recent connection, will eventually be the only station that registers the host and holds its causal information. Consider host h i that changes cell several times in a short time interval, leading to a sequence (s j , Ses j ), i < j < k of handoffs occuring simultaneously. We show that station s k will eventually hold h i 's causal information with th connection session number Ses k . Following lemme 8, the causal information of h i is maintained in one of the connection (s i , Ses i ) contained in PS. s k sends a Req 1 message to station s i for each connection (s i , Ses i ) of PS. The station that maintains the causal information of h i either receives Req 1,k from s k or from another station s j , i < j < k. If it first receives Req 1,k from s k , then it will send the causal information of h i to s k , and s k will, at the end of the handoff (s n . [START_REF] Rojas | Plausible clocks: Constant size logical clocks for distributed systems[END_REF]), send Delete messages to finish all connections of PS. Therefore, s k will maintain the causal information of h i and all other stations will unregister h i . If the station that holds h i 's causal inforamtion first receives the Req 1,j message from another station s j , i < j < k, then s j will receive the causal information of h i . However, following lemme 8 s j the connection for which s j does the handoff is included in PS. Hence, s j will receive the Req 1,k message from s k . If upon reception of Req 1,k the handoff of s j is not finished, it will cache Req 1,k until the end of the handoff where it will handle it. If the handoff is finished, it will handle Req 1,k directly. Hence, s k will eventually receive the causal

Figure 1 :

 1 Figure 1: Causal broadcast by dissemination [9] m' broadcast by B. All nodes receive m before m' since all nodes forward m at reception on all their channels.

Figure 2 :

 2 Figure 2: Broadcast of m 1 and m 2 acknowledge application messages received from another station, which might order messages differently.Application messages which are delivered by all hosts are considered obsolete and should then be discarded by stations. Existing algorithms use a centralized deletion of obsolete messages[START_REF] Chandra | Causal multicast in mobile networks[END_REF], which has an overhead both in terms of stored messages in station SBuffer and the number of messages sent over the wired network: each application message m is managed by a station called MSS init , and acknowledge messages for m from each host are forwarded to MSS init . Once MSS init received an acknowledge message from each host, it broadcasts a delete message to all stations in order to discard m. To overcome such an overhead, we have introduced a decentralized mechanism where stations discard messages using only local information: a station discards a message as soon as all hosts connected to it have acknowledged the message. Therefore, our approach does not require message exchanges between stations and a station only caches messages required by hosts of its cell.Figure2shows the broadcast and delivery of two messages causally related. h 1 is connected to s 1 and h 2 to s 2 . Stations s 1 and s 2 are connected by a wired channel. Hosts (resp. stations) piggyback seq h (resp. seq C ) in application messages. SBuffers are represented in bold. First, h 1 broadcasts m 1 . Upon reception, s 1 forwards m 1 to s 2 and broadcasts it in its cell, which contains h 1 . Upon reception, s 2 forwards m 1 to h 2 . h 2 receives and delivers m 1 , then broadcasts m 2 (co-broadcast(m 1 ) → co-broadcast(m 2 )). h 2 (resp. s 2 ) stops transmitting m 1 (resp. m 1 and m 2 ) upon reception of the acknowledge message regularly sent by s 2 (resp. h 2 ). Suppose h 1 did not receive neither m 1 the first time s 1 broadcast it due to interferences, nor its acknowledgment. Hence, h 1 retransmits m 1 . s 1 ignores the second reception of m 1 since it already received m 1 . Upon reception of m 2 , s 1 broadcasts it. Then h 1 receives and buffers m 2 because the sequence number that s 1 attached to m 2 is equal to 2, and h 1 awaits a message with seq=1. Eventually, s 1 broadcasts m 1 again and, upon reception, h 1 delivers m 1 then m 2 . Finally, h 1 (resp. s 1 ) acknowledges m 1 and m 2 (resp. m 1 ). Hence, m 1 and m 2 are completely discarded from the network, i.e., removed from the buffers of all nodes.

  n e c t a c k c o n n e c t a c k c o n n e c t a c k

Figure 5 :

 5 Figure 5: Handoff procedure

Figure 6 :Figure 7 :

 67 Figure 6: Throughput in function of hosts per cell

  Messages sent over the wired network

Figure

  Figure8: Sent messages in the network reception following seq NC piggybacked on messages, contrarily to CK where hosts do not buffer messages since stations only send a message m to a host once the host can causally deliver m. Hence, stations must retransmit messages less often than with CK (x5). On the wired network, CK sends more messages due to its centralized approach to discard obsolete messages. WAS implements a decentralized mechanism which requires no message exchange to discard obsolete messages. We point out that CK sends much fewer messages on the wired network than theoretically expected, because acknowledge messages of CK are small, and TCP groups many of them in a single packet.Amount of sent data. Figure7shows that WAS sends a lower amount of data than CK. On the wireless network, this is mostly due to acknowledge messages. Even though these messages contain only a few integers, they have an additional size of 48 bytes because they are encapsulated in UDP/IPv4/Mac packets. However, only a few acknowledge messages can be grouped into one single packet since the station will not send the next messages to deliver until the current ones are acknowledged. On the wired network, acknowledge and delete messages are grouped by TCP, which mostly removes the encapsulation overhead. However, those many acknowledge and delete messages scale up fast. Moreover, with CK stations piggyback a vector of size N (N=number of stations) on application messages sent over the wired network, and that vector rapidly takes much space when the number of stations increases. WAS only piggybacks a few integers on application messages.

Figure 9 :

 9 Figure 9: Messages in station sending buffers

Figure 10 :

 10 Figure 10: Messages stations cache when hosts failof the SBuffer increases. Moreover, contrarily to previous failures where the faulty host takes less than a second to acknowledge messages, the host takes 7 seconds to acknowledge all messages. Therefore, the failure of a host first and mostly has an impact in the cell in which it occurs and afterwards in adjacent cells when its cell's station stores more than 150-200 messages. Nevertheless, such an impact rapidly disappears once the host recovers.In conclusion, experiments confirm that WAS is more scalable than CK in terms of the number of hosts per cell, as well as in terms of total hosts and/or stations. WAS sends much fewer messages than CK both on the wired and wireless network, the amount of sent data is also much lower, and WAS has half the delivery delay of CK. Second, the decentralized message discard mechanism of WAS caches much fewer messages than CK, particularly during host failures. Finally, in WAS, the impact of a transient host failure is sharply absorbed after the faulty host recovers.

  1: if did not receive connect ACK from s p then : send(<connect,id h ,seq NC ,Ses,Ses LC ,PS>) to s n receive <connect ACK ,seq h m ,seq C m ,Ses m >: 5: if Ses==Ses m then 6: seq NC =seq C m ;seq h =seq h m ;Ses LC =Ses m ;PS={s n ,Ses m } (<Req 1 ,id h ,seq NC ,Ses LC ,Ses>) to stations of PS receive <Rsp 1 ,id h ,seq h ,m nd ,Ses> from station s p : 11: seq h i =seq h 12: msg req =message of m nd that s n already discarded 13: send(<Req 2 ,id h ,msg req ,Ses>) to s p receive <Rsp 2 ,id h ,msg,msg rcv ,Ses> from station s p : 14: piggyback id h on messages h i has delivered at s p 15: send to h i messages already discarded by s n (∈ msg) 16: if msg == ∅ then (<connect ACK ,id h ,seq C i ,Ses i >) to h i 19: send(<Delete,id h ,PS[i].Ses>) to stations of PS i 20: rcv(Req 1 ) for stored Req 1 with highest Ses

	2:	PS ∪ = {s p , Ses}
	3: Ses++
	Task of s 3:	use seq NC as acknowledgment
	4:	Ses i =Ses ; PS i = PS
	5: seq C 9: Register(id h )
	10:
	17:	seq C

4n : receive <connect,id h ,seq NC ,Ses,Ses LC ,PS> from host h i : 1: if id h registered ∧ handoff over ∧ Ses ≥ Ses i then 2: if Ses LC ==Ses i then i = determine seq C attributed to h i 6: if no message discarded from SBuffer to deliver then 7: send(<connect ACK ,id h ,seq C i ,Ses i >) to h i 8: else sendi = min(m.seq, m ∈ s n .SBuffer not delivered by h i ) 18: send

  Task of s p : receive <Req 1 ,id h ,seq NC ,Ses LC ,Ses>: 1: if current handoff and Ses>Ses i then ,id h ,seq h i ,m nd ,Ses>) to s n receive <Req 2 ,id h ,msg req ,Ses>: 9: msg= messages s n requests in msg req 10: m rcv = messages s p received since receive(Req 1 ) 11: unregister(id h ) 12: send(<Rsp 2 ,id h ,msg,m rcv ,Ses>) to s n

	2:	save Req 1
	3: else if Ses>Ses i then
	4:	if Ses LC == Ses i then
	5:	use seq NC as acknowledgment
	6:	m nd ={(id h ,seq h ) of messages h i has not delivered}
	7:	Ses i =Ses
	8:	send(<Rsp 1

information of h i . Moreover, s k will send a Delete message to close all conection of PS, and following Lemme9, all connections not included in PS are finished or will be finished by a Delete message. Hence, eventually s k will be the only station that registers h i and it will hold h i 's causal information.

Theorem 3: Each handoff eventually ends. Following lemme10, if several handoffs occure for the same host simultaneously, the station that initiated the most recent handoff will eventually hold the host's causal information. If a handoff is not concurrent with another one, it will execute normally. Hence, each handoff eventually ends. □