Brice Nédelec

Pascal Molli

Achour Mostéfaoui

Breaking the Scalability Barrier of Causal Broadcast for Large and Dynamic Systems

Many distributed protocols and applications rely on causal broadcast to ensure consistency criteria. However, none of causality tracking state-of-the-art approaches scale in large and dynamic systems. This paper presents a new nonblocking causal broadcast protocol suited for such systems. The proposed protocol outperforms state-of-the-art in size of messages, execution time complexity, and local space complexity. Most importantly, messages piggyback control information the size of which is constant. We prove that for both static and dynamic systems. Consequently, large and dynamic systems can finally afford causal broadcast.

INTRODUCTION

Causal broadcast [START_REF] Hadzilacos | A modular approach to fault-tolerant broadcasts and related problems[END_REF] is a fundamental building block of many distributed applications [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF] such as distributed social networks [START_REF] Borthakur | Petabyte scale databases and storage systems at facebook[END_REF], distributed collaborative softwares [START_REF] Nédelec | Crate: Writing stories together with our browsers[END_REF][START_REF] Heinrich | Exploiting single-user web applications for shared editing: a generic transformation approach[END_REF], or distributed data stores [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF][START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF][START_REF] Bailis | Bolt-on causal consistency[END_REF][START_REF] Lloyd | Don't settle for eventual: Scalable causal consistency for wide-area storage with cops[END_REF][START_REF] Bravo | Saturn: A distributed metadata service for causal consistency[END_REF]. Causal broadcast is a reliable broadcast where every connected process delivers each broadcast message exactly once following the happen before relationship [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF][START_REF] Schwarz | Detecting causal relationships in distributed computations: In search of the holy grail[END_REF]: when Alice comments on Bob's picture, everyone receives the comment after the picture; unrelated events are delivered in any order.

Unfortunately, causal broadcast has proven expensive in dynamic environments where any process can broadcast a message at any time [START_REF] Charron-Bost | Concerning the size of logical clocks in distributed systems[END_REF]. While gossiping constitutes an efficient mean to disseminate messages to millions of processes [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF][START_REF] Kenneth | Bimodal multicast[END_REF], ensuring causal delivery of these messages remains overcostly. Using state-of-the-art protocols, each message piggybacks a -possibly compressed -vector of Lamport's clocks [START_REF] Almeida | Interval tree clocks[END_REF][START_REF] Fidge | Timestamps in message-passing systems that preserve partial ordering[END_REF][START_REF] Mattern | Virtual time and global states of distributed systems[END_REF][START_REF] Singhal | An efficient implementation of vector clocks[END_REF]. The message overhead increases monotonically, for entries cannot be reclaimed without consensus. The message overhead increases linearly with the number of processes N that ever broadcast a message in the system. Several messages W may deffer their delivery, for preceding messages did not arrive yet [START_REF] Syed Akbar Mehdi | I can't believe it's not causal! scalable causal consistency with no slowdown cascades[END_REF]. The delivery execution time takes linear time O(W.N ) as well. Vector-based protocols eventually become overcostly and ©Brice Nédelec, Pascal Molli, Achour Mostéfaoui inefficient.

To provide causal order, [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] employs a different strategy. Instead of piggybacking a vector in each message, processes forward all messages exactly once using FIFO communication means. Gossip encompasses forwarding so this does not constitute an overhead of the approach. Messages arrive ready so they are delivered immediately. This approach is both lightweight and efficient. However, its scope is restricted to static systems. In dynamic systems where processes can join, leave, add or remove communication means, using this approach may lead to causal order violations.

In this paper, we break the scalability barrier of causal broadcast for large and dynamic systems. Our contribution is threefold:

• We provide a powerful extension of [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] that extends its scope to dynamic systems. We prove that adding new communication means between processes constitutes the sole factor in causal order violation. Our approach solves this using bounded buffers and few control messages.

• We provide the complexity analysis of our broadcast protocol. Table 1 compares our protocol to two representative solutions. Our approach handles dynamic systems while providing constant size overhead on messages, and constant delivery execution time.

• We provide an experimentation highlighting the impact of our protocol on transmission delays before delivery. Indeed, to tolerate dynamicity our protocol temporarily disables new communication means. The experiment shows that even under bad network conditions and high dynamicity, our protocol hardly degrades the mean transmission time before delivery.

Consequently, causal broadcast finally becomes an affordable and efficient middleware for distributed protocols and applications in large and dynamic systems. The rest of this paper is organized as follows: Section 2 shows the background and motivations. Section 3 details the model, our proposal, the proofs, and the complexity. Section 4 explains the results of experimentation. Section 5 reviews the related work. We conclude in Section 6.

SRDS'18 draft

draft SRDS '18 Table 1: Complexity of causal broadcast protocols. N is the number of processes that ever broadcast a message. W is the number of received messages awaiting delivery. P is the number of delivered messages that are temporarily kept before being safely purged to forbid double delivery.

BACKGROUND AND MOTIVATIONS

Causal broadcast ensures that every connected process delivers each broadcast message exactly once [START_REF] Hadzilacos | A modular approach to fault-tolerant broadcasts and related problems[END_REF] following the happen before relationship [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF]. If the sending of a message m precedes the sending of a message m then every process that delivers these two messages needs to deliver m before m . Otherwise it can deliver them in any order. Encoding the logical time at broadcast regarding all other broadcasts then piggybacking this control information in each broadcast message allows processes to ensure causal order on message delivery. Instead, [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] uses FIFO links and systematically forwards delivered messages. Intuitively, the dissemination pattern asserts that no paths from a process to another process carry messages out of causal order.

Figure 1 depicts this principle. The system comprises 3 processes connected to each other with FIFO links. In Figure 1a, Process A broadcasts a. It sends a to Process B and Process C. In Figure 1b, Process B receives, delivers, and forwards a. In Figure 1c, it broadcasts b. Consequently, all processes must deliver a before delivering b. In Figure 1d, Process A receives, delivers, and forwards b. Process A fulfills the causal order constraint between a and b. In Figure 1e The principle of [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] works in large systems where processes have partial knowledge of the membership.

ally receives, delivers, and forwards the messages following causal order. In large systems comprising from hundreds to millions of processes, no process can afford to maintain the full membership to communicate with. Instead, processes have a much smaller view called neighborhood. Forwarding messages allows them to reach all members of the system, either directly or transitively in a gossip fashion [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF][START_REF] Kenneth | Bimodal multicast[END_REF]. In large systems, forwarding is mandatory. Processes pay the price of gossiping whatever broadcast protocol. They must create and send copies of the original broadcast message. Since draft SRDS '18 gossiping already encompasses forwarding of messages, it does not constitute an additional overhead of [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF].

Figure 2 shows that such causal broadcast ensures causal order in larger systems where processes have limited knowledge of the membership. Process A only knows about Process B and Process D. Yet, Process A's broadcast messages a and a arrive to all other processes either directly or transitively. In addition, a and a always arrive in causal order at all processes despite concurrency and whatever the dissemination path.

Unfortunately, [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] ensures causal order only in static systems where the membership does not change and no links are added or removed. These are not practical assumptions. In practice, processes may join and leave the system at any time; and processes may reconfigure their neighborhood at any time [START_REF] Nédelec | Crate: Writing stories together with our browsers[END_REF]. Figure 3 shows an example of message dissemination in dynamic settings where causal delivery is violated. In Figure 3a, Process A broadcasts a. It sends a to all its neighbors. Here, it sends a to Process B only. Afterwards, in Figure 3b, Process A adds a link to Process C. Message a is still traveling. In particular, it did not reach Process C yet. In Figure 3c, Process A broadcasts a . In this example, messages travel faster using the direct link from A to C than using B as intermediate. We see in Figure 3d that a arrives at Process C before a. Figure 3e shows that not only it violates causal delivery but also propagates the violation to all processes downstream.

The causal broadcast presented in this paper extends [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] and solves the causal order violation issue of dynamic systems. Table 1 shows its complexity. Most importantly, message overhead and delivery execution time remain constant, i.e., our approach is both lightweight in terms of generated traffic and efficient. The local space complexity is linear in terms of number of processes that ever broadcast a message, and awaiting messages. The local space complexity also comprises a data structure to ensure causal order. We show in Algorithm 3 that the size of this structure can be bounded even in presence of system failures, such as crashes. This makes causal broadcast an affordable and efficient middleware for distributed protocols and applications even in large and dynamic systems.

The next section describes the proposed causal broadcast. It details its operation, provides the proofs that it works in both static and dynamic settings, and shows its complexity analysis.

CAUSAL BROADCAST FOR LARGE AND DYNAMIC SYSTEMS

In this section, we introduce PC-broadcast (stands for Preventive Causal broadcast), a causal broadcast protocol that breaks the scalability barrier for large and dynamic systems.

Our approach is preventive: instead of repairing causal order violations or reordering received messages, it simply makes sure that messages never arrive out of causal order. Processes can immediately deliver messages upon receipt. This not only removes most of control information piggybacked in broadcast messages, but also leads to constant delivery execution time. Protocols and applications can finally afford causal broadcast in large and dynamic systems without loss of efficiency.

Model

A distributed system comprises processes. Processes can communicate with each other using messages. A process is faulty if it crashes, otherwise it is correct. We do not consider byzantine processes.

Definition 3 (Unpartitioned network). A network is unpartitioned if and only if for any pair of correct processes, there exist a path -a link or a sequence of links -of correct processes between them. We only consider unpartitioned overlay networks.

Causal broadcast is a communication primitive that relies on reliable broadcast to send messages to all processes in the system. Figure 3: Causal broadcast [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] may violate causal order in dynamic settings.

Definition 4 (Uniform reliable broadcast). When a process A broadcasts a message b A (m), each correct process B in the network eventually receives it r B (m) and delivers it d B (m). Uniform reliable broadcast guarantees 3 properties: Validity: If a correct process broadcasts a message, then it eventually delivers it. Uniform Agreement: If a process -correct or not -delivers a message, then all correct processes eventually deliver it. Uniform Integrity: A process delivers a message at most once, and only if it was previously broadcast. draft SRDS'18

Algorithm 1: R-broadcast at Process p.

1 INITIALLY: 2 Q // Set of processes, p's neighborhood 3 received ← ∅ // Set of received messages 4 DISSEMINATION: 5 function R-broadcast(m) 6 received ← received ∪ m 7 foreach q ∈ Q do sendTo(q, m) // broadcast 8 R-deliver(m) 9 upon receive(m) 10 if m ∈ received then 11 received ← received ∪ m 12 foreach q ∈ Q do sendTo(q, m) // forward 13 R-deliver(m)
Algorithm 1 shows the instructions of a uniform reliable broadcast. It uses a structure that keeps track of received messages in order to deliver them at most once. Since processes may not have full membership knowledge, processes must forward broadcast messages. Since the network does not have partitions, processes either receive the message directly from the broadcaster or transitively. Thus, all correct processes eventually deliver all messages exactly once. Rbroadcast ensures validity, uniform agreement, and uniform integrity.

Causal broadcast is a reliable broadcast that also ensures a specific ordering among message deliveries. To define a delivery order among messages, we define time in a logical sense using Lamport's definition [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF].

Definition 5 (Happen before [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF]). Happen before is a transitive, irreflexive, and antisymmetric relation → that defines a strict partial order of events. The sending of a message always precedes its receipt.

To order messages broadcast by every process, we define causal order.

Definition 6 (Causal order). The delivery order of messages follows the happen before relationships of corresponding broadcasts

: ∀A, B, C, b A (m) → b B (m ) =⇒ d C (m) → d C (m )

Definition 7 (Causal broadcast). Causal broadcast is a uniform reliable broadcast ensuring causal order.

Theorem 1 (Constraint flooding in deterministic overlay networks is causal [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF]). In static networks, a broadcast protocol is causal if it uses FIFO links, forwards all broadcast messages exactly once, and uses all its outgoing links.

From Theorem 1, reliable broadcast from Algorithm 1 is causal if communication links employed to communicate with neighbors in Q are FIFO. This holds only for static networks where Q is immutable. In practice, processes can join, leave, add or remove links to neighbors from Q at any time.

Lemma 1 (R-broadcast is causal in dynamic systems subject to removals). R-broadcast using FIFO links is a causal broadcast in dynamic systems where processes can leave the system or links can be removed.

Proof. Removing a process from the network and removing all the incoming and outgoing links of this process is equivalent. Since we assume that removals do not create network partitions1 , all correct processes eventually receive all broadcast messages. In addition, removing a link or a process does not reorder causally related messages. Hence, each process receives and delivers each broadcast message in causal order as in static systems.

draft SRDS'18

Link removals and process departures do not endanger broadcast properties. However, Figure 3 shows that adding links may lead to causal order violations. The next section describes PC-broadcast, a causal broadcast that handles all dynamicity.

Causal order in dynamic systems

PC-broadcast stands for Preventive Causal broadcast. It prevents causal order violations by forbidding the usage of new links until proven safe. It constitutes a powerful yet simple extension of [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF]. Table 1 shows that it preserves both constant message overhead and constant delivery execution time in dynamic settings.

Figure 3 shows that adding links may infringe the causal order property of causal broadcast. New links may act as shortcuts for new messages: new messages that travel through new links may arrive before preceding messages that took longer paths. To prevent this behavior, we define the safety of a link. PC-broadcast uses all and only safe links to disseminate messages.

Definition 8 (Safe link). A link from Process A to Process B is safe if and only if Process B received or will receive all messages delivered by Process A before receiving any message that Process A will deliver

: saf e AB ≡ ∀m, m , d A (m) → s AB (m ) =⇒ r B (m) → r BA (m )
Added links start unsafe. In Figure 3, Process A uses the link to broadcast a while it is unsafe: Process B did not receive a yet, and there was no guarantee that Process B would receive a before receiving a from the new link. In this example, the worst happens and Process B receives then delivers a before a which violates causal order.

The challenge is to make unsafe links safe using local knowledge only. A straightforward mean for Process A to achieve this consists in sending all its delivered messages to Process B using this unsafe link. This guarantees that any message delivered by A will be received by B before A starts using the new -now safe -link for causal broadcast. However, this is costly both in local space and generated traffic. Performing an anti-entropy round to extract missing messages would also be overcostly in terms of generated traffic for it would require sending the vector of received messages [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF]. Instead, Process A avoid sending most of messages by initiating a ping phase to Process B.

Definition 9 (Ping phase). Ping phase starts when Process A pings Process B. Ping messages π travel using safe links. When Process B receives this ping, it replies to Process A. Replies ρ travel using any communication mean. Ping phase ends when Process A receives the reply of Process B.

Lemma 2 (Ping phases acknowledge broadcast receipts). A ping phase from Process A to Process B acknowledges the receipt by B of all messages delivered by Process A before this ping phase:

∀m, d A (m) → s A (π AB ) ∧ r A (ρ AB ) =⇒ r B (m)
Proof. Suppose a process A initiates a ping phase to a process B. Suppose a series of messages delivered by Process A. Process A sent every of these messages exactly once using all its outgoing safe links. Processes that will receive these messages either already forwarded them or will forward them in their receipt order. Since Process A's ping travels using safe links after these messages, when Process B receives the ping, it already received all messages delivered by Process A. Process A receives Process B's reply after Process B received the ping. Consequently, when Process A receives Process B's reply, Process B received all messages delivered by Process A before the start of this ping phase.

Upon receipt of Process B's reply, Process A has the guarantee that Process B received all its delivered messages preceding the ping phase. This is not sufficient, for ping phases take time. Messages delivered during ping phase by Process A may not be received by Process B yet. To fill this gap, Process A sends to Process B the messages it buffered during the ping phase.

Definition 10 (Buffering). Process A records in a buffer B all its delivered messages during a ping phase to Process

B. ∀m, s A (π AB ) → d A (m) ∧ d A (m) → r A (ρ AB ) ⇔ m ∈ B
Lemma 3 (Ping phase and buffering makes safe links). Process A makes an unsafe link to Process B safe by completing a ping phase to Process B then finalizing it by sending all delivered messages buffered during ping phase using the new link.

Proof. Suppose a series of messages m 1 . . . m i . . . m j delivered by a process A. Suppose Process A initiated a ping phase to a process B after delivering m i . Suppose Process A receives Process B's reply after m j . We must show that when Process A delivers a message after m k , Process B received or will receive m 1 . . . m j before. From Lemma 2, when Process A receives Process B's reply, Process B received m 1 . . . m i . Since Process A buffered all messages delivered since the beginning of the ping phase, the buffer contains m i+1 . . . m j when the ping phase ends. Since links are FIFO, sending messages of this buffer using the new link guarantees that Process B will receive them before receiving any m k delivered after m j . The link from Process A to Process B is safe.

Lemma 4 (PC-broadcast is causal in dynamic systems subject to additions). In dynamic systems where processes can join or add links, broadcasting using all and only safe FIFO links ensures causal order. Without partition, the broadcast is causal.

Proof. PC-broadcast ensures validity, uniform agreement, and uniform integrity, for it extends R-broadcast that ensures all 3 properties. We must show that PC-broadcast ensures causal order: Figure 4: PC-broadcast does not violate causal order in dynamic settings.

∀A, B, C, b A (m) → b B (m ) =⇒ d C (m) → d C (m ). ∀A, B, b A (m) → b B (m ) ⇔ d B (m) → d B (m ) ⇔ d B (m) → s B (m ) ⇔ d B (m) → (∀C ∈ Q, s BC (m )).
Since all links in Q are safe links, r c (m) → r CB (m ) (see Definition 8). Since delivery order follows first receipt order, d C (m) → d C (m ). This order on message delivery transitively reach all correct processes as long as the network remains unpartitioned.

Algorithm 2 shows a small set of instructions that implement safe links. Figure 4 shows on an example how it solves causal order violations. In Figure 4a, Process A broadcasts a. In Figure 4b, Process A wants to add a link to Process C. It sends a ping message π to Process C (see Line 11) and awaits for the latter's reply. We leave aside the implementation of this send function (e.g. broadcast or routing). While awaiting, Process A keeps its normal functioning and maintain a buffer of messages associated with the unsafe link (see Line 25). In Figure 4c, Process A broadcasts another message a . It sends it normally to Process B but does not send it to Process C directly. Instead, it buffers it. In Figure 4d, Process C receives Process A's ping message π. Since links are FIFO, it implicitly means that Process C also received a. Process C sends a reply ρ to Process A (see Line 13). ρ can travel through any communication mean. In Figure 4e, Process A receives ρ. Consequently, Process A knows that Process C received and delivered at least a and all preceding messages. It empties the buffer of messages to Process C (see Line 16). Afterwards, the new link is safe. Process A uses the new link normally.

Theorem 2 (PC-broadcast is a causal broadcast). PCbroadcast is a causal broadcast in both static and dynamic network settings.

Algorithm 2: PC-broadcast at Process p. Proof. For static networks, it comes from [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF]. For dynamic networks, it comes from Lemmas 1 and 4.

7 if |Q| > 1 then 8 counter ← counter + 1 9 Q ← Q \ q // is unsafe 10 B[q] ← ∅ //

Bounding space consumption

Algorithm 2 ensures causal delivery of messages even in dynamic network settings. Compared to the original causal broadcast for static networks [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF], it uses an additional local structure: buffers of messages. It associates a buffer to each new unsafe link. We assumed that the size of these buffer stays small in general, for it depends on the time taken by the ping phase which is assumed short. However, network conditions may invalidate this assumption. Figure 5 depicts scenarios where buffers grow out of acceptable boundaries.

In Figure 5a, the issue comes from high transmission delays from Process A to Process B, and from Process B to Process C compared to the number of messages to broadcast and forward. The ping message π did not reach Process C yet that the buffer contains a lot of messages. In Figure 5b, the issue comes from the departure of Process C. Depending on network settings, Process A may not be able to detect Process C's departure. The former will never receive the awaited reply and the buffer will grow forever. In Figure 5c, the reply ρ itself fails to reach Process A. For the recall, this message can travel to Process A by any communication mean, including unreliable ones. If this fails, Process A's buffer to Process C will grow forever. Algorithm 3 solves the unbounded growth issue of buffers. It solves the issue from the buffer owner's perspective. Figure 6 shows how this algorithm bounds the size of buffers. In Figure 6a, Process A broadcast a; then wanted to add a link to Process C so it sent a ping message; then broadcast a and a so it buffered them. We see that the ping message π 1 carries a counter. The new buffer is identified by the same counter. In Figure 6b, Process A receives, delivers, and forwards the message x. Each message delivery increases the size of current buffers. The algorithm checks if the size of the buffer exceeds the configured bound (see Line 15). Adding x to the buffer would exceed the bound of 2 elements. This is the first ping phase failure. Process A simply restarts the ping phase: it resets the buffer and sends another ping message π 2 (see Line 24). The counter of the reset Algorithm 3: Bounding the size of buffers.

I[i] = q do I ← I \ i 19 R ← R \ q 20 function retry(q) 21 for i ∈ I such that I[i] = q do I ← I \ i 22 if q ∈ R then 23 R[q] ← R[q] + 1 24 if R[q] ≤ maxRetry then open(q) 25 else close(q)
26 HANDLING FAILURES: buffer is the one of the new ping message. In the meantime, Process C receives π 1 and sends the corresponding reply ρ 1 . In Figure 6c, Process A receives a broadcast message y. It delivers it, checks if the buffer can admit it, adds the message to the buffer, and forwards it. Process A also receives the first reply ρ 1 but discards it, for no buffers have such counter. In Figure 6d, Process C receives π 2 and sends the corresponding reply ρ 2 to Process A. In Figure 6e, Process A receives ρ 2 . Since the corresponding buffer exists, it empties it. The new link is now safe to use for causal broadcast.

While it solves the issue of unbounded buffers, it also brings another issue. For instance, if the maximal size of buffers is too small, it could stuck the protocol in a loop of retries. We address this issue by bounding the number of retries. However, it means that the ping phase could fail entirely. Causal broadcast must not employ the new link. In extreme cases, it could cause partitions in the causal broadcast overlay network. It would violate the uniform agreement property of causal broadcast. Thus, we assume a sufficiently large maximal bound. It never creates partitions, for most links become safe, and the failing ones are replaced over time thanks to network dynamicity.

Other orthogonal improvements are possible. For instance, causal broadcast could use reliable communication means to acknowledge the receipt of the ping message. The time taken between the sending and the receipt of the reply would increase when failures occur. However, it would take less time than resetting the buffering phase.

Complexity

We review and discuss about the complexity of PCbroadcast. We distinguish the complexity brought by (i) the overlay network, (ii) reliable broadcast, (iii) and causal order. Overlay network. Processes cannot afford the upkeep of full membership in large and dynamic systems. Instead, each process builds a partial view the size of which is considerably smaller than the actual network size. To maintain these partial views, each process runs a peer-sampling protocol [START_REF] Bertier | D2ht: The best of both worlds, integrating rps and dht[END_REF][START_REF] Jelasity | Gossip-based peer sampling[END_REF][START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF]. Some peer-sampling protocols provides partial views the size of which scales logarithmically with the actual network size [START_REF] Nédelec | An adaptive peer-sampling protocol for building networks of browsers[END_REF]. The number of messages forwarded by each process for each broadcast remains small, for this number is equal to their view size: O(Q) where Q is the size of the partial view. Reliable broadcast. Gossiping constitutes an efficient mean to disseminate messages to all processes [START_REF] Demers | Epidemic algorithms for replicated database maintenance[END_REF][START_REF] Kenneth | Bimodal multicast[END_REF]. Algorithm 1 shows that it relies on a local structure to guarantee that messages are delivered exactly once. This structure grows linearly with the number of processes in the network: O(N ). In addition, each message piggybacks a pair process, counter that identifies it: O(1). Checking if a message is a duplicate takes constant time: O(1). Causal ordering. Causal ordering primarily uses FIFO links to broadcast messages which implies a constant size overhead on messages O(1). PC-broadcast constitutes an advantageous tradeoff when the system features light routing capabilities. For instance, protocols building systems using neighbor-to-neighbor interactions [START_REF] Jelasity | Gossip-based peer sampling[END_REF][START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF][START_REF] Nédelec | An adaptive peer-sampling protocol for building networks of browsers[END_REF] only require 3 control messages per added link (see Section 4); protocols featuring message rout- ing such as DHT require O(log(N )) control messages per added link. However, in the worst case, PC-broadcast requires O(N 2 ) control messages per added links, for it falls back to broadcasting control messages.

The space complexity of PC-broadcast is that of FIFO links plus buffered messages ensuring safety. The size of buffers depends on the ping phase duration. Assuming a system featuring light routing capabilities, we assume that this time remains short so the number of buffered messages stays small. As shown in Section 3, network conditions can make this assumption false. Algorithm 3 allows to bound the size of each buffer and handle network failures.

Overall. Generated traffic remains the most important criterion for scalability. The traffic generated by PC-broadcast for each process and for each broadcast only depends on the size of messages and the overlay network chosen to broadcast messages. The size of messages is an irreducible variable; and many protocols designed to build overlay networks achieve high scalability in terms of network size and dynamicity [START_REF] Bertier | D2ht: The best of both worlds, integrating rps and dht[END_REF][START_REF] Jelasity | Gossip-based peer sampling[END_REF][START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF], [START_REF] Nédelec | An adaptive peer-sampling protocol for building networks of browsers[END_REF][START_REF] Voulgaris | Cyclon: Inexpensive membership management for unstructured p2p overlays[END_REF]. Consequently, PCbroadcast achieves high scalability in both these terms too. PC-broadcast is efficient, for the upper bound on the complexity of delivery execution time does not depend on any factor.

However, to ensure causal order, PC-broadcast may not use all outgoing links in dynamic settings, for some may be temporarily unsafe. This negatively impacts the overlay network properties. The next section shows an experiment that highlights the influence of PC-broadcast's way to ensure causal order on the underlying overlay network. In particular, it shows that the number of hops required by a broadcast message to reach all processes increases when delays on transmission increase.

EXPERIMENTATION

PC-broadcast provides causal order with constant size message overhead. This feature comes at a cost: at first, new communication means are disabled for causal broadcast. In this section, we evaluate the impact of PC-broadcast on the message delivery in a specific overlay network that corresponds to random graphs. The experiments run on the Peer-Sim simulator [START_REF] Montresor | Peersim: A scalable P2P simulator[END_REF] that allows simulations to reach high scale in terms of number of processes. Our implementation is available on the Github platform at http://github. com/chat-wane/peersim-pcbroadcast. Objective: To observe the transmission delay introduced by PC-broadcast on message delivery. We expect the delay to increase as the latency increases. Description: We build an overlay network with a topology close to random graphs using Spray [START_REF] Nédelec | An adaptive peer-sampling protocol for building networks of browsers[END_REF]. The overlay networks comprise 1k, and 10k processes respectively. Networks are dynamic. Each process' neighborhood Q changes at least once every 60 seconds; and on average twice every 60 seconds. Each exchange involves two processes that both add and remove half of their partial view. Links are FIFO, bidirectional, and have transmission delays. The delay increases over time up to 5 seconds. Consequently, the duration of ping phases increases during the experiment. Links become safe slower. We measure the shortest path length from a random set of processes to all other processes. It represents the average number of hops taken by broadcast messages before being received and delivered by all. Multiplied by the transmission latency of links, it represents the transmission delay of broadcast messages before being received by all processes. We perform measurements on 2 broadcast protocols: PCbroadcast and R-broadcast. R-broadcast uses all available links to broadcast messages in a gossip fashion. Transmission delays before delivery are similar to piggybacking approaches [START_REF] Almeida | Interval tree clocks[END_REF][START_REF] Fidge | Timestamps in message-passing systems that preserve partial ordering[END_REF][START_REF] Mattern | Virtual time and global states of distributed systems[END_REF][START_REF] Singhal | An efficient implementation of vector clocks[END_REF][START_REF] Birman | Reliable communication in the presence of failures[END_REF][START_REF] Hadzilacos | Distributed systems. chapter Fault-tolerant Broadcasts and Related Problems[END_REF][START_REF] Mostéfaoui | Probabilistic causal message ordering[END_REF] without accounting for the time taken to send large messages (e.g. each message conveys a vector clock of 10k entries when the network comprises 10k broadcasters). Larger packets induce larger transmission time. Results: Figure 7 shows the result of the experiment. The x-axis depicts the delay set on message transmission for each link. The top part of the figure shows the average shortest path length. The bottom part of the figure shows the average number of unsafe links per process that cannot be used for causal broadcast yet. Figure 7 shows that both R-broadcast and PC-broadcast deliver message quickly to all processes. The overlay network guarantees that paths stay short and logarithmically scaling with the number of random neighbors in partial views. The top part of Figure 7 shows that measurements made on PC-broadcast increase while measurements made on Rbroadcast stay constant. R-broadcast uses all neighbors pro-draft SRDS '18 vided by Spray while PC-broadcast excludes links still in buffering phase. The more latency on transmission, the longer the buffering phase. The bottom part of Figure 7 shows that the number of elements in the buffers increases accordingly.

Figure 7 shows that the growth of path length stays small even when transmission delays become high. The number of elements in buffers stays small because the buffering phase takes a constant number of hops to complete: at most 3 hops. The path length grows even slower, for removing 3 among 17 links has restricted impact on overlay networks close to random graphs.

This experimentation shows that even under bad network conditions (high transmission delays) and using highly dynamic overlay networks (random peer-sampling), the number of unsafe links remains small. The negative impact expected on transmission time before message delivery remains small. In practice, we expect smaller network transmission delays, and overlay networks less subject to neighborhood changes (e.g. exploiting user preferences, or geolocalization). In such settings, we expect PC-broadcast to have a negligible negative impact on the overlay network properties.

The next section reviews state-of-the-art techniques designed to maintain causal order among messages.

RELATED WORK

This section reviews the related work of logical clocks. It goes from piggybacking approaches to vector-based approaches. Then, it reviews explicit dependency tracking and dissemination-based approaches. Piggybacking approaches [START_REF] Birman | Reliable communication in the presence of failures[END_REF][START_REF] Hadzilacos | Distributed systems. chapter Fault-tolerant Broadcasts and Related Problems[END_REF]. A trivial way to ensure causal ordering of messages is to piggyback all causally related messages since the last broadcast message along with the new broadcast message. Even by piggybacking the identifiers of messages instead of messages themselves, the broadcast message size may increase quickly depending on the application. PC-broadcast does not piggyback all preceding messages in broadcast messages. However, an accumulation of messages arises during buffering. As discussed in Section 3.4, we can assume that links quickly become safe so the buffer size stays small, and we can easily set a threshold on the buffer size. Vector clock approaches [START_REF] Fidge | Timestamps in message-passing systems that preserve partial ordering[END_REF][START_REF] Mattern | Virtual time and global states of distributed systems[END_REF]. A vector clock is a vector of monotonically increasing counters. It encodes the partial order of messages using this vector: V C(m) < V C(m ) =⇒ m → m . Before delivering a message, processes using vector-based broadcast check if the vector of the message is ready regarding their local vector. If it detects any missing preceding message, the process delays the delivery. To implement this vector-based broadcast (i) each process must maintain a vector locally; (ii) each message must piggyback such vector; (iii) there is 1 counter per process that ever broadcast a message. To accurately track causality, processes cannot share their entry. To safely track causality, processes cannot reclaim entries. Hence, even with compaction approaches [START_REF] Singhal | An efficient implementation of vector clocks[END_REF], the vectors grow linearly in terms of number of processes that ever broadcast a message. In [START_REF] Almeida | Interval tree clocks[END_REF], the complexity is reduced to the actual number of processes in the network. Still, these approaches do not scale, particularly in dynamic networks subject to churn and failures. In comparison to these vector-based approaches, our approach reduces the generated traffic of causal broadcast by a factor of N in the most common context where processes have partial knowledge of the network membership. Probabilistic approaches [START_REF] Mostéfaoui | Probabilistic causal message ordering[END_REF] sacrifices on causality tracking accuracy: messages may be delivered out of order under a computable boundary. The size of control information in messages depends on the desired boundary. Unlike vector-based approach, our broadcast cannot state if two messages are concurrent, accurate causal delivery is a feature provided by default by the propagation scheme. Once safe, FIFO links deliver message in causal order without further delay. The speed of delivery is that of FIFO links.

Explicitly tracking semantic dependencies allows broadcast protocols to reduce the size of piggybacked control information [START_REF] Bailis | Bolt-on causal consistency[END_REF][START_REF] Lloyd | Don't settle for eventual: Scalable causal consistency for wide-area storage with cops[END_REF][START_REF] Mukund | Optimized or-sets without ordering constraints[END_REF]. For instance, when Alice comments on Bob's picture, everyone must receive the picture before the comment. The broadcast message only piggybacks one semantic dependency. When Alice comments on multiple pictures at once, the broadcast message piggybacks all dependencies. Message overhead increases linearly with the number of semantic dependencies. To track semantic dependencies, causal broadcast becomes application dependent. Instead our approach remains application-agnostic. Comments, pictures, etc. are events that relate to all preceding events. When Alice comments on Bob's picture, everyone will receive this event before the former event and all other preceding events. Whatever the number of preceding events, broadcast messages only piggyback constant size control information.

Preserving causal order using dissemination paths reduces generated traffic by keeping message overhead constant [START_REF] Bravo | Saturn: A distributed metadata service for causal consistency[END_REF][START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF]. State-of-the-art does not support dynamic systems [START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF], or supports it using epochs [START_REF] Bravo | Saturn: A distributed metadata service for causal consistency[END_REF] that confines usability to small scale systems where failures are uncommon. In comparison, we designed PC-broadcast to handle large and dynamic systems. Our approach provides a lightweight and efficient mean to reconfigure dissemination paths using local knowledge without impairing causal order. Saturn [START_REF] Bravo | Saturn: A distributed metadata service for causal consistency[END_REF] along with PC-broadcast could ease online changes in configuration while improving its resilience to failures and topology changes.

CONCLUSION

In this paper, we described a non-blocking causal broadcast protocol that breaks scalability barriers for large and dynamic systems. Using PC-broadcast, message overhead and delivery execution time remain constant. Causal broadcast finally becomes an affordable and efficient middleware for large scale distributed applications running in dynamic environments.

As future work, we plan to investigate on reducing the space complexity of reliable broadcast. Section 3.4 reviews structures with linearly increasing space consumption. We can reduce this complexity in static systems. We can prune the structure from already received messages, for we know that the number of duplicates is equal to the number of incoming links [START_REF] Raynal | Distributed algorithms for messagepassing systems[END_REF]. Unfortunately, this does not hold in dynamic systems. We would like to investigate on a way to prune the structure in such settings. This would make causal broadcast scalable as well on generated traffic as on space consumption.

We also plan to investigate on retrieving partial order of events. Section 5 states that vector-based approaches allows to compare an event with any other event. They can decide on whether one precedes the other, or they are concurrent. They can build the partial order of event using this knowledge. Our approach cannot by default. However, in extreme settings where the overlay network is fully connected, we can assign a vector to each received message using local knowledge only, and without message overhead. We would like to investigate on a way to build these vectors locally in more realistic settings where processes have partial knowledge of the membership.

  dynamic systems message overhead local space consumption delivery execution time vector-based[START_REF] Schwarz | Detecting causal relationships in distributed computations: In search of the holy grail[END_REF] O(N ) O(N + W.N ) Process B receives and delivers a. Process B forwards a using its FIFO links. Process A receives and delivers b. Process A forwards b using its FIFO links. Process C cannot receive b without having received a beforehand.

Figure 1 :

 1 Figure 1: Causal broadcast [11] ensures causal order.

Figure 2 :

 2 Figure2: The principle of[START_REF] Friedman | Causal ordering in deterministic overlay networks[END_REF] works in large systems where processes have partial knowledge of the membership.

  Process C receives and delivers a before a. This violates causal order. Process C propagates the causal order violation.

  Process A wants to add a link to Process C. It sends a ping message π to Process C using one of its FIFO links. Process A broadcasts a . It does not send it through the new link but buffers it. Process C receives π and replies to A. The reply ρ can travel by any communication mean. Process A receives Process C's reply. The former safely empties its buffer to Process C. Using the new link cannot cause causal order violation anymore.

20 B ← B \ q 21 26 PC

 202126 B do B[q] ← B[q] ∪ m // buffers Reply ρ fails.

Figure 5 :

 5 Figure 5: Buffers may grow unbounded due to network conditions.

8 upon 10 I[id] ← to 11 upon 12 I ← I \ id 13 R ← R \ to 14 upon 16 retry(q) 17 upon

 810111213141617 ping(f rom, to, id)9 if q ∈ R then R[q] ← 0 receiveAck(f rom, to, id) PC-deliver(m) 15 foreach q ∈ B such that |B[q]| > maxSize do close(q) 18 for i ∈ I such that

27 upon

 27 timeout(f rom, to, id) 28 if id ∈ I then retry(to) Process A wanted to add a link to Process C after having broadcast a. Afterwards, it broadcast a and a . Process A receives, delivers, and forwards x.Since the buffer size would exceed the maximal boundary, it resets the buffer with a new counter and sends a ping message with this counter. In the meantime, Process C receives π 1 and sends ρ 1 . Process A forwards y and buffers it. It also receives ρ 1 but no buffers exist with this counter. Process A simply discards ρ 1 . Process C receives π 2 and sends the corresponding reply ρ 2 . Process A receives ρ 2 . It empties the buffer with the corresponding counter. Now, the direct link to Process C is safe.

Figure 6 :

 6 Figure 6: Buffers become bounded. We allow only 2 elements in each buffer.

Figure 7 :

 7 Figure 7: Impact of PC-broadcast on the overlay network.

It may create partitions infringing the uniform agreement property. Network partitioning constitutes an orthogonal problem that we do not address in this paper.

ACKNOWLEDGMENTS

This work was partially funded by the French ANR projects O'Browser (ANR-16-CE25-0005-01), and Descartes (ANR-16-CE40-0023).


Marie Swiatek
email: marie.swiatek@univ-savoie.fr

Gilles Fraisse

Mickael Pailha

Stratification Enhancement for an Integrated Collector Storage Solar Water Heater (ICSSWH)

Keywords: ICSSWH, PIV, thermal stratification, reverse flow

Stratification is a key point in increasing performances of storage systems. The experimental study conducted only focuses on the charging of a high aspect ratio cavity representing the storage system of an ICSSWH, and the exchange with the solar collector is modeled by a constant heat flux. Thermal stratification is enhanced by placing in the system a stratification plate and by changing the position of the heat exchange zone between solar collector and storage. The parameters that vary in this study are the angle of inclination of the system (30, 45 and 60 °relative to the horizontal), the heat flux imposed (1800, 2700 and 3600 W/m 2 ) and the length of the stratification plate. The experiments lasted three hours. Satisfying stratification was obtained, mainly due to the reverse flow occurring in the system. However, this phenomenon increases with time and could result in creating a dead volume under the heat exchange area. This aspect will be further studied using CFD models. The impact of a good thermal stratification in the system will also be studied by determining the annual performance of the ICSSWH.

Introduction

In France, the successive regulations for energy consumption in buildings made the resort to renewable energies mandatory, increasing the need of solar systems both thermal and photovoltaic (PV). Solar thermal systems are efficient enough because they can cover approximately 50 % of the annual needs for domestic hot water (DHW). The installation cost remains the main impediment to their broad development. In addition, the relative complexity of classical systems with the collector installed on the roof and the storage inside the building can make it difficult to find available space for the storage in both new and U, V, W velocity components according to the system coordinates (m/s)

x, y, z system coordinates already existing buildings. Integrated Collector Storage Solar Water Heaters (ICSSWH) combine the advantages of low cost, minimal maintenance and ease of installation. At present, various systems are commercially available in different countries, with companies producing them mostly from the Mediterranean area or the southern hemisphere. They are usually very compact with a simple design and function almost passively. However, the main lock still impeding the increase in installation of such devices in France is their resistance to freezing conditions, as most of the time the upper part of the thermal storage is also the absorber, resulting in important heat losses to the environment, more importantly during night time. The low compacity of these systems due to their geometry is also not favorable for heat losses. Therefore, in order for ICSSWH to be as efficient as the classical solar thermal systems, heat losses should be minimized and heat transfers should be maximized to compensate the lower velocities in the system due to the absence of pumping device. Concerning heat losses, a performant insulation and a separation of the absorber from the storage part can result in a significant decrease of the thermal losses. As for heat transfer maximization, thermal stratification is a phenomenon proven to improve heat exchange in thermal storages [START_REF] Lavan | Experimental study of thermally stratified hot water storage tanks[END_REF]. The aim of this paper is to study the charge of the storage tank of an ICSSWH with enhanced thermal stratification. Various types of ICSSWH exist nowadays, with different methods for heat exchange between solar radiation, storage and DHW supply. Some function with direct heat exchange; and in many configurations, the absorber is a face of the storage tank, and the water heated is directly used without a heat exchanger inside the storage tank. Many of those configurations use solar concentration and are called Compound Parabolic Concentration as shown in Fig. 1(a) [START_REF] Chaouachi | Energetic Performances Study of an Integrated Collector Storage Solar Water Heater[END_REF]. There can also be tubular storage for which the storage tank is made up of several tubes placed inside an absorber box, as shown in Fig. 1(b) [3]. These systems are efficient in climates where there is not a high risk of reaching freezing conditions, because the opening left for solar radiation allows important heat losses. Other configurations have a storage with a triangular (Fig. 1(c)) [START_REF] Mohamad | Integrated solar collectorstorage tank system with thermal diode[END_REF] or parrallelepipedic (Fig. 1(d)) [START_REF] Soletrol | Topsol[END_REF] storage, with only one face used as the absorber, the others being insulated. This allows to reduce heat losses during night time compared to the previoulsy presented systems. In this paper, the system studied is closer to the last configuration, except that the heat tranfer from the absorber to the tank is an indirect one, as well as that between the tank and DHW, allowing the complete insulation of the storage tank. As mentioned previously, stratification of temperatures in a thermal storage increases its efficiency due to the fact that it helps keeping lower temperatures at the bottom to maximize heat exchange with the collector, and higher temperatures at the top to have better heat exchange with DHW. In addition, a more efficient storage means that the whole ICSSWH will be more efficient. This phenomenon has been characterized and quantified by various parameters and many authors in order to compare systems. Therefore, different definitions can be found in literature to describe thermal stratification and evaluate its efficiency, some based on graphical observations, others on figures of merit or non-dimensional numbers, but also some based on first or second law of thermodynamics calculations [START_REF] Haller | Methods to determine stratification efficiency of thermal energy storage processes â Review and theoretical comparison[END_REF]. In many papers, the definitions used for the dynamic (charge and discharge) and static (storage) parts of the cycle are separated. In our case, as only the charge is considered, the definitions used for dynamic mode were reviewed. Among all these, the most relevant definitions adaptable to our case are the following :

The temperature difference ∆T between the highest and lowest temperatures measured inside the system at a given time t. This parameter has the advantage to be very easy to know once the temperature profiles are available, and it gives a good insight of the degree of stratification inside the system. However, it gives no information about the level of temperature present.

The Richardson number Ri, which is believed to be the most relevant non dimensional parameter to describe the ability of a system to establish proper thermal stratification [START_REF] Castell | Dimensionless numbers used to characterize stratification in water tanks for discharging at low flow rates[END_REF]. Its expression is given by Eq. ( 1):

Ri = g • β • cos(θ) • ∆T • L c V 2 c ( 1
)
where β is the volume expansion coefficient (K -1 ), θ (°) is the angle of inclination with respect to the horizontal, and L c (m) and V c (m/s) are respectively the characteristic length and velocity.

The stratification coefficient ST defined by Eq. ( 2) [START_REF] Wu | An experimental investigation of the effect of water removal and replacement on the thermal stratification in a horizontal water storage tank[END_REF]:

ST = 1 m res i m i (T i -T ) 2 (2)
with m res (kg) the mass of water in the storage tank, T i (K) and m i (kg) respectively the average temperature and the mass of water contained in the node i, and T (K) the average temperature in the storage tank at time t.

The previously introduced parameters will be used to characterize and compare the experimental configurations tested for this study and decide which ones are the more efficient.

Ways to improve thermal stratification and hence increase ICSSWH efficiency have been studied in literature. Several authors resorted to an insulated plate placed parallel to the flat collector and close to it [START_REF] Garg | Theoretical and experimental studies on collector/storage type solar water heater[END_REF][START_REF] Kaushik | Effect of baffle plate on the performance of a triangular built-in-storage solar water heater, Energy conversion and management[END_REF]. This results in a channel in which the water is heated, then going up directly at the top of the storage. This system allows the separation of upward and downward flow, thus reducing mixing which is one of the main causes of stratification destruction. By adding a thermal diode at the bottom or the top of the channel [START_REF] Mohamad | Integrated solar collectorstorage tank system with thermal diode[END_REF][START_REF] Faiman | Reducing the heat loss at night from solar water heaters of the integrated collectorstorage variety[END_REF], this system also helps reducing losses during the night impeding the flow in the channel to go downward and cooling the whole storage. The drawback of this solution reveals when the storage is already charged : if the temperature at the top part of the storage near the channel outlet is hotter than the fluid being heated in the channel, it can result in the blocking of the upward flow. A mean to overcome this problem was suggested by Smyth et. al [START_REF] Smyth | A comparative performance rating for an integrated solar collector/storage vessel with inner sleeves to increase heat retention[END_REF][START_REF] Smyth | Annual performance of heat retaining integrated collector/storage solar water heaters in a northern maritime climate[END_REF][START_REF] Smyth | Heat retaining integrated collector/storage solar water heaters[END_REF], which consisted in a perforated plate in order for the fluid to be deposited at its corresponding layer of temperature from the channel to the storage part of the ICS.

In order to reduce losses to the environment, the aspect ratio of the system also plays its part as it has an influence on the thermocline, which is the size of the area separating the hot and cold fluid zones. The thermocline thickness is another parameter used in literature to characterize thermal stratification in energy storages as the thinner it is, the more the storage is considered close to a perfectly stratified system. It was not decided to be a studied parameter in this study because the values found were not in agreement with the graphical observations for stratification: some cases with smaller temperature difference and a lower average temperature stored could have a better value for the thermocline thickness. According to Souza [START_REF] Souza | Experimental study of a partially heated cavity of an integrated collector storage solar water heater (IC-SSWH)[END_REF], the increase in aspect ratio of two storages with the same thermocline thickness reduces the volume of fluid in this area, and Lavan and Thompson [START_REF] Lavan | Experimental study of thermally stratified hot water storage tanks[END_REF] underlined that the higher aspect ratios implied more losses to the environment. Therefore, an aspect ratio of 3 or 4 would be a good compromise between thermal performances and cost of insulation and materials. In addition, Hahne and Chen [START_REF] Hahne | Numerical study of flow and heat transfer characteristics in hot water stores[END_REF] and Nelson et al. [START_REF] Nelson | Experiments on stratified chilled water tanks[END_REF] showed that the improvement of stratification was negligible for aspect ratios superior to respectively 4 and 3.

In this paper, we are going to focus on one particular ICSSWH system with a solar loop to collect solar radiation which indirectly exchange heat with the storage tank over a height of 0.2 m. The charging of the storage system has already been experimented previously by Souza [START_REF] Souza | Experimental study of a partially heated cavity of an integrated collector storage solar water heater (IC-SSWH)[END_REF], which configuration consisted in a parallelepiped storage tank of high aspect ratio (H/L = 13) heated at the bottom with a constant heat flux, as shown in Fig. 2. The value of the aspect ratio is high compared to the recommended values of literature due to the fact that for this system architectural integration was also taken into account. Three values of angle θ (30, 45 and 60 °) and of heat flux ϕ (1800, 3600 and 5400 W/m 2 ) were studied during three hours.

In such system, the flow was shown to be two-dimensional in the lower part and three-dimensional in the top part, the evolution of the boundary between 2D and 3D flows changing according to the instant in time of the experiment and the value of the Rayleigh number defined by Eq (3):

Ra ϕ,hϕ = g • β • cos(θ) • h 4 ϕ • ϕ α • ν • λ (3)
Also, very poor thermal stratification was observed, with a maximal temperature difference between the top and the bottom of the storage tank of only 4.2 after charging for three hours at an angle of 30 °and a heat flux of 5400 W/m 2 . In order to improve stratification, a device was inserted into the storage tank consisting of an acrylic plate placed parallel to the top wall creating a channel. It allows to separate the upward and downward flows and to reduce the mixing effect. It was also proven that it made the flow two dimensional, thus allowing the use of 2D numerical model to further study several parameters for the plate. In the experimental study conducted by J. Souza, the plate was placed 8 mm away from the top wall (see Fig. 2), and only the case with the angle of 45°and the heat flux of 3600 W/m 2 . It showed that this configuration did not significantly improved thermal stratification in the system. In addition, the plate at this distance does not generate enough pressure drop to reduce the velocity of the fluid flow. Henceforth, a numerical study of the plate was conducted [START_REF] Souza | Conception et optimisation dun capteur solaire thermique innovant adapté à la rénovation énergétique grâce à lintégration du stockage[END_REF], and it showed that stratification would be enhanced significantly if the channel thickness was smaller. However, if the plate is too close to the top wall, it gets warmer due to the hot upward flow circulating in the channel, thus creating a secondary boundary layer on the cavity-side of the stratification plate, annihilating its effect. The optimal solution would be to have an adiabatic plate, or to insulate it, which was applied in the prototype of this system [START_REF] Fraisse | Study of a new Integrated Solar Collector[END_REF]. The annual performance of this prototype was satisfactory, as it was only a bit lower than that of a more classical system such as the thermosyphon: for the Chambery climate, with an angle of 30 °, a collector surface of 2 m 2 , a storage volume of 150 L and a DHW need of 200 L/day at 45 , the solar fraction was of 37.8 % [START_REF] Fraisse | Compte-rendu de fin de projet ANR Reneausol[END_REF]. However in this system a satisfactory thermal stratification was never reached.

New configuration

In order to improve this parameter and thus get a better efficiency for the whole system, the idea was at first to find means to increase pressure drop to reduce velocities. Solutions found in literature such as perforated plates or obstacles were proven useless due to the already small order of magnitude of the velocities occurring in the system. Therefore, this kind of solutions were abandoned, and another solution to improve stratification is to change the location of the heat input that influences the buoyancy forces in the system [START_REF] Barzegar | Transient Thermal Behavior of a Vertical Solar Storage Tank with a Mantle Heat Exchanger during No-Flow Operation[END_REF]: the higher the heat exchange zone in the system, the lower the buoyancy force due to the fact that there is less height to be heated (in the formula ∆ρ.g.H). The decrease in this force tends to reduce velocities in the system, hence minimizing the mixing effects that are partly responsible for stratification destruction.

As a consequence, we placed the heat exchange zone in the middle part of the top wall of the cavity. However, in this case, the stratification plate is mandatory in order for the volume under the heat exchange zone not to be a dead volume useless in terms of energy storage. In this case, the plate also ensures that the fluid loops in the storage tank, such that the cold fluid at the bottom is piped to the heat exchange zone, heated up and placed at the top. This way, the heat exchange between the solar loop and the tank will be more efficient than if the plate was not present, and thermal stratification achieved would generate hotter temperatures on the top part of the system. This allows a better heat exchange with the domestic hot water (DWH) heat exchanger placed inside the tank (not represented here).

Two plate lengths are studied in this paper : one stopping at the end of the heat exchange zone (y = 0.75 m) -denoted Hme (m standing for the fact that the heat exchange is placed in the middle of the top wall; and e for end), and another stopping at a fixed length 0.9 m away from the bottom of the systemdenoted Hmf (f standing for fixed).

This new configuration brings about a set of new physical phenomena that were not encountered in the previous case. Actually, the fact that the heat exchange zone is placed near the end of the channel generates a reverse flow. To characterize this phenomenon, a modified Rayleigh number Ra * ϕ,hϕ is used taking into account the channel aspect ratio A r = e c /h ϕ : Ra * ϕ,hϕ = Ra ϕ,hϕ • A r . The reverse flow has obviously an effect on the thermal stratification in the storage tank, and this study will help understanding it. Reverse flow has been studied both experimentally and numerically with both air and water as working fluids, but its origin is still not surely known [START_REF] Dupont | Two-dimension experimental study of the reverse flow in a free convection channel with active walls differentially heated[END_REF]. The first experimental studies of this phenomenon were conducted by Sparrow et al. [START_REF] Sparrow | Observed flow reversals and measured-predicted Nusselt numbers for natural convection in a one-sided heated vertical channel[END_REF] with water as working fluid. They concluded that the Nusselt number was not affected by the appearance of the reverse flow. Li et al. [START_REF] Li | Effect of surface radiation on natural convective flows and onset of flow reversal in asymmetrically heated vertical channels[END_REF] numerically studied reverse flow of air neglecting radiative transfer and without using the Boussinesq approximation but giving laws of variations of quantities according to the temperature. The results showed that the maximum velocity was nearly independent from the spacing between the heated and adiabatic wall and that for a fixed value of the modified Rayleigh number Ra * ϕ,hϕ , the reverse flow increases with the spacing between the walls. Brangeon [START_REF] Brangeon | Contribution à l'étude numérique de la ventilation naturelle dans des cavités ouvertes par la simulation des grandes échelles[END_REF] numerically researched the influence of the angle of inclination and saw that the more the system was tilted close to the horizontal, the more the heat exchanges, the flow rate and the reverse flow area diminished. Dupont et al. [START_REF] Dupont | Two-dimension experimental study of the reverse flow in a free convection channel with active walls differentially heated[END_REF] experimentally studied the reverse flow of air and concluded that the boundary layer thickness did not seem affected by the change in heat flux imposed. For an equivalent configuration, Samot et al. [START_REF] Samot | Mesure de température dans un écoulement renversé à la sortie d'un thermosiphon vertical chauffé à flux constant[END_REF] defined areas of occurrence for this phenomenon according to the Rayleigh number Ra ϕ,hϕ and the aspect ratio of the channel. For ventilation purposes, Khanal et al. [START_REF] Khanal | Flow reversal effects on buoyancy induced air flow in a solar chimney[END_REF] inclined the adiabatic wall such that the outlet is as thick as the boundary layer to prevent reverse flow from happening as this phenomenon tends to decrease the total mass flow in the system. All these studies allow to keep in mind the main parameters influencing the reverse flow. However, they all are placed in an open environment, which is not the case in this study. In addition, our channel geometry is different as there is a large part of unheated walls under the heated zone, and in some cases above as well. All these changes have an influence on the reverse flow that cannot be quantified as it has never been studied before to the knowledge of the authors.

In our experimental set up, the reverse flow cannot be studied very deeply due to the fact that there is no visibility inside the channel for PIV measurements. Therefore no precise data will be observed in this area, but the velocity profiles near the channel outlet are available.

Experimental setup

Bench description

The system studied experimentally consists in a 1.3 m high, 0.62 m wide and 0.1 m deep cavity made up of glass, as shown in Fig. 3. It is filled with distilled water seeded with polyamid seeding particles (PSP) of density 1.03 and average diameter 5 µm. The main cavity is divided into three cavities by means of two acrylic "splitting" plates. The resulting central cavity is 0.3 m wide and is the one in which the particle image velocimetry (PIV) measurements will take place. Both side cavities are 0.15 m wide. One of them is used to install all the measuring devices, while the other is left untouched in order to leave a window open to PIV measurements. The two acrylic splitting plates come up with a groove to slide in the 4 mm thick acrylic stratification plate 5 mm apart from the front wall. The purpose of the splitting plates is to be considered as adiabatic walls. The whole system -apart from the side walls -is insulated with 6 mm thick extruded polystyrene of thermal conductivity λ = 0.035 W/(m.K), thus creating a third type boundary condition of fixed heat exchange coefficient with ambient temperature. A gap is left in the middle of the insulation to allow the laser sheet for PIV to illuminate the middle plane of the system.

The constant heat flux imposed is controlled by means of a heating system located in the middle of the front wall. This system consists in three electrical heaters (0.2 × 0.2 m), sandwiched between on the one hand a stainless steel plate in contact with the water in the system also insuring that the heating system is water proof, and on the other hand three layers of 5 mm thick insulating silicon foam. On the back of the heaters, in the middle of the central heater are found two heat flux sensors (0.1 × 0.1 m) to measure the heat flux that is not going towards the water. There is also a thermocouple on each heater to monitor its temperature. On each side of the layer of silicon foam adjacent to the heaters are found eight couples of K-type thermocouples in order to give another estimation of the heat flux not going to the water, as the heat flux sensors have not been calibrated but have the uncertainty given by the supplier, which is of 30 µV/(W/m 2 ).

Eighteen T-type thermocouples are also installed in the system. Ten of them are placed in the splitting plate to get the temperature at the center plane of the middle cavity. The position of the first thermocouple at the bottom is x = 5 cm , y = 11 cm , incremented along the y-axis by 12 cm, resulting in the tenth thermocouple being placed at x = 5 cm , y = 119 cm. Six thermocouples are found three at each side of the same splitting plate in order to verify the assumption of adiabatic wall. The first pair is placed at the bottom is located with the coordinates x = 5 cm , y = 18 cm , with a distance between the next pairs of 48 cm along the y-axis.

Another thermocouple is used to monitor the ambient temperature during the experiment.

All thermocouples have been calibrated and have an uncertainty of ±0.2 .

Protocol

The water temperature can be controlled at the initial time by means of a thermobath and a heat exchanger placed next to the system. The temperature is thus initialized before the system is filled, giving a uniform temperature of 20±0.5 . The temperature inside the room of experiment could not be controlled, so it usually varied around 23 ±1 . In our case, most of the experiments last 3 hours in order to limit the effects of a varying ambient temperature, and also to be able to start and stop an experiment in the length of a working day. In fact, after each experiment, the water is transferred to a reservoir in order for the temperature to be initialized for the next experiment. Concerning PIV measurements, the central plane is divided into eleven planes of study for the camera to be able to capture the entire system. The system is monitored every five minutes, and it takes about 30 s for the acquisition to be completed.

For the cases studied, the varying parameters were the length of the stratification plate, the values of the constant heat flux imposed and the angle of inclination of the system. Concerning the latter, the same values as in the previous study have been chosen : 30, 45 and 60°relative to the horizontal axis. Regarding the heat flux, the values chosen are 1800 W/m 2 , 2700 W/m 2 and 3600 W/m 2 .

Ra ϕ,hϕ

Tilt angle to the horizontal (°) Concerning the values of the modified Rayleigh number, they vary between 1-4×10 9 , the highest value being obtained for A30P36 and the lowest for A60P18. The values decrease with the heat flux imposed and with increasing values of the tilt angle, just as the results shown in the table for Ra ϕ,hϕ . For both Rayleigh numbers, the values are characteristic of the end of the laminar flow and the beginning of the transitional flow [START_REF] Bejan | Convection heat transfer[END_REF]. In both cases, the configuration Hme or Hmf is not specified as the parameters taken into account for the Rayleigh determination do not involve the length of the plate but only the channel thickness and the heat exchange length, which is the same for both cases.

Thermal behavior

For all cases, we performed a global energy balance of the system. The injected flux ϕ inj in the water can be measured thanks to the power supplied by the generator and the thermocouples and heat flux sensors placed on the other side of the heating elements. The heat flux lost ϕ hl can be estimated knowing the thermal conductivity of the glass and of the insulating panels and their respective thickness. An average discrepancy rate was calculated as ((ϕ injϕ hl )/ϕ inj ), and values around 10 % were obtained for all cases.

The adiabadicity of the "splitting" plates was also verified by determining ϕ lat . The maximum value of 0.6 W was obtained for the HmfA60P36 case at t = 3h, which corresponds to less than 0.5 % of the injected flux; and for all cases the values varied around 0.2-0.3 % of the injected flux, which validate the hypothesis of adiabatic wall.

Concerning the losses in the other walls (top-bottom and superior-inferior, ie the walls of the measuring cavity echanging with the environment), their value depend on the position inside the cavity. Actually, as the room temperature was sometimes higher than the bottom temperature inside the system, a heat gain can be observed in this part whereas at the top of the system, the temperature is always higher than the room temperature after one hour of charge or more, so there are heat losses in this part. The mean value of losses inside the system (balance between gains at the bottom and losses at the top) increases with time and its value represents less than 1 % of the injected flux after three hours of charge.

Fig. 4 shows the evolution of temperature over time in the cavity for different thermocouples. The trend is linear except for the beginning, and it is possible to notice that depending on the position in the cavity, the time of establishment of linear variation is different: it is less than 10 min for the thermocouple located at the top while for the thermocouple located in the middle it is nearer to 30 min. It is also possible to notice that, depending on the configuration studied, the slope is not the same at a given heat flux: cases with the plate ending at the end of the heat exchange zone (Hme) stratify better than those having a longer stratification plate (Hmf). The linear evolution of temperature is expected for cases with constant heat flux imposed and a well insulated system.

In order to qualify stratification, graphical methods representing the temperature pofiles along the system can be used as shown in Fig. 5. These results show that the systems with lower angle have a better thermal stratification as they achieve higher temperatures at the top nodes of the storage tank, keeping a lower temperature at the bottom. Besides, as noticed previously, cases with longer stratification plate reach lower temperatures at the top than cases with stratification plate stopping at the end of the heating zone. Fig. 5 also shows a significant increase in stratification compared to the previously studied case [START_REF] Souza | Experimental study of a partially heated cavity of an integrated collector storage solar water heater (IC-SSWH)[END_REF]. Actually, the case Hbf shown is heated from the bottom until the line y = 0.2 m, and the stratification plate goes until the line y = 0.9 m as shown in Fig. 2.

Based on these profiles, it is possible to determine the temperature difference in the tank at a given time. After a three hour charge, higher results of 22.9

were obtained for case HmeA30P36, and then values decreased with power supply and increasing inclination angles to reach 10 for the case HmfA60P18. The determination of the stratification coefficient ST shows consistent results (Fig. 6). It is possible to notice that this trend evolution is the same for the Rayleigh number previously determined in Table 1. It means that for our cases, the higher the Rayleigh number, the better the stratification. Values of the Richardson number for the Hme and Hmf cases were all superior to 1, which means that a good thermal stratification is likely to take place in the tank.

Flow characterization

In order to characterize the flow in the system, several parameters are taken into account. Once the PIV acquisition is done, a velocity field can be found, allowing to compute other quantities.

The vorticity ω z of a 2D flow, determined by Eq. ( 4), describes the local rotation of the fluid around the z-axis.

ω z = ∂V ∂x - ∂U ∂y (4)
Vorticity in a fluid highlights the areas where the fluid is spinning relative the the point being looked at. It can be the case when vortices are present inside a flow, or near the walls due to high shear stresses. Both phenomena are present in the system in our case.

The divergence of a velocity field in a steady state 2D flow is given by Eq. ( 5):

∂U ∂x + ∂V ∂y = 0 (5)
If this equation is not verified, then it means that the term linked to the third velocity component ∂W/∂z is not equal to zero. In this case, the flow cannot be considered 2D as the mass flow is not conserved in the study plane. Therefore this quantity allows to verify the 2D aspect of the flow. Mass conservation is also checked by comparing the up and down flow rates at given lines in the study plane: one at y = 0.75 m (the channel outlet for Hme cases), and from y = 0.9 m (the channel outlet for Hmf cases) to y = 1.2 m, one every 10 cm, as shown in Fig 7 . Unless otherwise specified, the values of velocities given in the following paragraph are the y-axis component, meaning the velocity V. For all cases, the mass balance has been evaluated for all the previously mentioned profiles (at the channel outlet and above the stratification plate). The average values were around 0.021 kg/(m.s) and 0.032 kg/(m.s) after one and three hours respectively for both cases. These values are of the same order of magnitude as the maximal ones obtained by J. Souza [START_REF] Souza | Experimental study of a partially heated cavity of an integrated collector storage solar water heater (IC-SSWH)[END_REF] when studying the stratification plate case, which was concluded to be predominantly bidimensional (2D). Combined with the observations of divergence field in the study plane, the same conclusion can be reached in our case: only restricted areas show a three-dimensional characteristic. This conclusion is important as it allows the use of 2D computations to model this system using computational fluid dynamics (CFD).

The profiles of vorticity and divergence in the entire system for the worst case of mass balance is shown in Fig. 8.

Concerning the fluid flow behavior, it is possible to notice several kinds of phenomena occurring in the system, as represented in Fig. 9(a).

Zone A represents the plume going out of the channel toward the upper part of the system. This ascending motion is created by the density difference found locally in the system: the fluid is heated in the channel in the neighborhood of the heat exchange zone, activating buoyancy forces and creating the flow for the system to be at equilibrium. Plume entrainment can be observed in the surrounding fluid. In this area, the maximum velocities measured for all cases In this region, it can be noted that the values of velocities, maximum and average, tend to decrease with time. This phenomenon can be explained by the fact that the system temperature increases with time, thus reducing the density difference between the fluid near the heat exchange zone and the rest of the fluid in the system, which reduces the buoyancy force. Zone B represents the reverse flow. This phenomenon occurs for both Hme and Hmf cases. Its magnitude cannot be observed clearly using PIV due to the fact that there is no visibility inside of the channel. Actually, the position of the devices do not allow to see the phenomena occurring in this part and the channel thickness is small compared to other scales in the system. However, if a line is placed at a small offset after the channel outlet, it is possible to see the downward flow that is partly going to re-enter the channel. The average velocity magnitudes V = (U 2 + V 2 ) 1/2 at those lines vary for Hme cases around 0.73 and 0.8 mm/s for 1 and 3 hours respectively, and for Hmf cases around 0.56 and 0.74 mm/s for 1 and 3 hours respectively.

It is possible to note that the velocities in these two zones are higher for Hme cases, which are the ones that have a better thermal stratification. It can be explained by the fact that the "loop" in this part (above the channel outlet) is more active and hence more efficient in heating this area. This is the reason why temperatures are higher at the top of the system for these cases compared with Hmf cases.

A visualization of the flow was done using fluorescein as a fluid tracker for the Hme case inclined at 45 °and heated with a flux of 3600 W/m 2 . Fig. 9(b) shows the phenomena occurring in the two previously described zones.

Fig. 10 highlights the fact that by varying the inclination angle of the system, the angle at which the fluid re-enters the channel is also changing to keep close to an horizontal line. The fluid previously heated in the channel mostly stays in the upper part instead of going downard. Zone C is where the fluid is descending to the lower part of the system. For all cases, higher velocities have been observed close to the stratification plate, which can be explained by the fact that the fluid is taking the shortest way to loop inside the closed system. The average downward velocities in this region are taken along the profiles located in the middle of the acquisition regions R2, R3 and R5 (see Fig. 7). For both cases, a dramatic decrease in the velocities in this region can be observed. The values obtained for Hme cases are around 0.7 mm/s at 1h and decrease to 0.13 mm/s at t = 3 h. As for Hmf cases, the values vary around 1.2 mm/s and 0.2 mm/s for 1 and 3 hours respectively.

By looking at the values of velocities previously given, it is possible to understand that with time, the reverse flow is getting more and more important : taking into account the fact that the velocities of the plume (zone A) are decreasing with time while the reverse flow tends to increase with time, it makes it relatively even more important. It has the effect of reducing the global loop of the fluid in the system (after going up to the top, the fluid is going to the bottom of the system to be piped in the channel in this part), explaining the decrease of the downward velocities in zone C. This effect is even more important for Hme cases.

Zone D is that of the aspiration of the fluid in the channel and the edge effects at the opposite corner. Part of the fluid in this last part goes upward along the bottom wall until a height which varies depending on the case. The phenomenon is accentuated when the ambient temperature is higher than the system temperature, resulting in the heating of the lower part of the system due to heat conduction in the glass, thus creating an ascending flow.

Fig. 11 shows an example of the velocity profile plots at different lines in the system for an average case: shorter plate (Hme) with an angle of inclination of 45 °and a heat flux of 2700 W/m 2 after three hours of charge.

It is possible to notice that the plume gets larger as it goes up, due to plume entrainment. Also, higher downward velocities are seen near the plate for both R2 and R5 zones. However, the upward motion is only observable in the bottom region (R2).

Conclusion

The system experimentally studied in this paper is a high aspect ratio cavity (H/L = 13) filled with water representing the storage part of an ICSSWH with indirect heat exchange with both the solar collector and the DHW. Only the charging part of the system is studied, and it lasts three hours for each experiment. Considering the inertia of the system, the flow is always transitional along the experiment (steady state cannot be reached). To model heat exchange with the solar collector, a constant heat flux is imposed, and the exchange zone is placed in the middle of the top wall. Three values of heat flux are studied (1800, 2700 and 3600 W/m 2 ), and the system is inclined with three angles relative to the horizontal (30, 45 and 60 °).

Compared with a previously studied case heated at the bottom, the temperature stratification inside the system is enhanced : while the maximum temperature difference measured in the previous system was of 4.2 after three Changing the position of the heat exchange zone had the effet to reduce the buoyancy forces inside the system, and by placing the heating zone near the channel outlet, a reverse flow clearly appeared. Though both these phenomena are responsible for a better stratification, the reverse flow is the one having more influence. It also increases with time, reducing the global loop of fluid inside the system. The main risk is that after a long period of charge, the fluid no longer moves at the bottom part, resulting in a dead volume under the heating zone.

CFD studies of this system, as well as global model for the determination of the annual performances should allow to further understand the phenomena and see if a better thermal stratification actually increases global system efficiency.

Figure 1 :

 1 Figure 1: Various types of ICSSWH

Figure 2 :

 2 Figure 2: Schematic representation of the previously studied case with stratification plate [15, 18], the one represented being denoted Hbf

Figure 3 :

 3 Figure 3: Diagram of the cavity with the thermocouples

Figure 4 :

 4 Figure 4: Temperature evolution over time in the cavity at various positions for cases inclined with 30°and heated with a constant heat flux of 3600 W/m 2

Figure 5 :

 5 Figure 5: Temperature profiles after 1h and 3h of charging the system with a constant heat flux of 3600 W/m 2 , compared with the previous case with stratification plate [15] (Hbf)

Figure 6 :

 6 Figure 6: Values of the stratification coefficient ST according to different cases, angles and heat flux supplied

Figure 7 :

 7 Figure 7: Representation of the system with the PIV measurement regions and the lines used for post processing

Figure 8 :Figure 9 :

 89 Figure 8: Vorticity and divergence of the case with shorter plate (Hme) inclined at 60°and heated with a constant heat flux of 3600 W/m 2 , at t = 3 h

Figure 10 :

 10 Figure 10: Comparison of the reverse flow for several angles after three hours for the shorter plate configuration (Hme) and a heat flux of 1800 W/m 2

Figure 11 :

 11 Figure 11: Velocity profiles for the shorter plate case (Hme) with an inclination angle of 45 °and a heat flux of 2700 W/m 2 at t = 3 h

Table 1 :

 1 Cases studied experimentally and the value of the Rayleigh number

	Heat flux (W/m 2 )	30	45	60
	1800	A30P18 7.97×10 10	A45P18 6.51×10 10	A60P18 4.60×10 10
	2700	A30P27 1.20×10 11	A45P27 9.77×10 10	A60P27 6.91×10 10
	3600	A30P36 1.59×10 11	A45P36 1.30×10 11	A60P36 9.21×10 10