Nadjet Belblidia

Luís Marcelo Dias De Amorim

Henrique Maciel Kosmalski Costa

Jeremie Leguay

Henrique M K Luís

Costa

Jérémie Leguay

Vania Conan

PACS: Chopping and shuffling large contents for faster opportunistic dissemination

Keywords: Chopping and shuffling large contents for faster opportunistic dissemination Oracle Random Seq Oracle Random Seq Oracle Random Seq (c) RT, Area 1, 000m × Oracle Random Seq Oracle Random Seq Oracle Random Seq (b) Source 26, 0, 01 Oracle Random Seq (c) Source 44, 0, 01 Oracle Random Seq (d) Source 47

come

I. Introduction

Important advances in the area of opportunistic networks have been achieved including the conception of applications to enable content sharing among users on the move [START_REF] Lebrun | Bluetooth content distribution stations on public transit[END_REF], [START_REF] Lenders | Wireless Ad Hoc Podcasting[END_REF], [START_REF] Mcnamara | Media sharing based on colocation prediction in urban transport[END_REF]. In our daily lives, users generate, consume, and share contents that are becoming increasingly larger. We address the following question: how to efficiently disseminate such large contents in opportunistic networks when contacts have limited capacity? This is a realistic situation, as portable devices such as smartphones and compact cameras are now able to generate high-definition videos that are resource-consuming. As an idea, average standard videos on YouTube are 10MB long [START_REF] Gill | YouTube traffic characterization: A view from the edge[END_REF]; in HD quality, this value goes up to 40MB. If we consider Bluetooth as the underlying transport technology (as suggested in several proposals), transferring such amounts of data opportunistically would require contacts of 80 to 320 seconds, at best.

A few experimental initiatives have shown that most contact durations in human-driven opportunistic networks fall under the minute [START_REF] Tournoux | The accordion phenomenon: Analysis, characterization, and impact on DTN routing[END_REF], [START_REF] Gaito | Opportunistic forwarding in workplaces[END_REF], [START_REF] Barrat | High resolution dynamical mapping of social interactions with active RFID[END_REF]. 1 For example, Gaito et al. show in their experiment that the median contact time is 48 seconds, i.e., more than 50% of the contacts last for less than 1 1 Other fundamental papers could not show such a behavior as they relied on beaconing periods of 120 seconds or more [START_REF] Chaintreau | Impact of human mobility on opportunistic forwarding algorithms[END_REF], [START_REF] Eagle | Reality mining: Sensing complex social systems[END_REF]. minute. Trying to transfer large contents during these shortlived encounters becomes impractical, as two main limitations rise. First, nodes that experience short contacts frequently might never receive the data. Second, transfer opportunities are wasted leading to poor overall performance.

To optimize data dissemination in such scenarios, it is fundamental to adapt the size of messages to the contact capacity by fragmenting the transmitted data. In this paper, we suppose that contents are divided into pieces of standard size. The main challenge when disseminating fragmented data is to decide which piece(s) should be sent when two nodes meet (see Section III). One possibility is to rely on a naive approach and transfer pieces in a sequential order, i.e., nodes disseminate the pieces with the lowest identifiers first. As we will show later, the main problem with this approach is that it does not capture the conditions of the network and leads to poor dissemination ratio. Another possibility is to disseminate pieces in a uniformly-distributed random way, but it does not capture contact patterns either. In this paper, we show that: (i) the order of piece dissemination matters, (ii) bad piece selection can lead to ineffective contacts, and (iii) uniform random selection is not enough. To our knowledge, no previous work has addressed this problem.

To counterpart the abovementioned issues, we propose PACS (Prevalence-Aware Content Spreading), a popularitybased strategy to select pieces to be exchanged between neighbors solely based on node-local information. Through their successive contacts, nodes keep track of the dissemination level of the pieces throughout the network and use this information to transfer less prevalent pieces first. To this end, nodes exchange a small Boolean vector when in contact. By combining such vectors over time, nodes are able to build a popularity map of pieces in the network. We show that such a simple strategy significantly increases the system performance.

We evaluate PACS using both synthetic and real-world mobility traces from intermittently-connected networks. Synthetic user movements are generated using the random trip model [START_REF] Palchaudhuri | Perfect simulations for random trip mobility models[END_REF] and the community-based mobility model proposed in [START_REF] Musolesi | A community based mobility model for Ad Hoc network research[END_REF]. Additionally, we have also used movement traces obtained from RollerNet, an intermittently-connected mobile network formed between 62 people during a rollerblading tour in the streets of Paris, which lasts for 3 hours [START_REF] Tournoux | The accordion phenomenon: Analysis, characterization, and impact on DTN routing[END_REF].

In summary, the key contributions of PACS are: prevents nodes form getting the same pieces first, which leads to quick increase in the number of infected nodes.

??? n 1 n 2 n 3 n 3 n 3 n 1 n 2 n 2 t = t 1 t = t 2 t = t 3 1 2 4 3 1 2 4 3 1 2 1 2 1 2 1 2 1 2 (a) Sequential. n 1 n 2 n 3 n 3 n 3 n 1 n 2 n 2 t = t 1 t = t 2 t = t 3
• More useful contacts. PACS leads to much higher contact effectiveness, i.e., it reduces the number of contacts that cannot be used because nodes have the same pieces.

• Reduced dissemination delay. By turning more contacts into effective opportunities, PACS significantly reduces the latency for the contents to be fully pushed to all nodes.

II. Content Spreading in Opportunistic Networks

In this section, we provide all the necessary background before introducing the dissemination algorithms.

A. Problem Statement

In our problem, we consider a certain number of pieces that compose a content. The content must be disseminated to a population of mobile nodes that communicate opportunistically. The problem we face here is: given the pieces and a contact opportunity, which subset of these pieces should be transferred if the contact is insufficient to transmit all of them?

Our objective is to define an algorithm to select pieces to be transferred when two nodes get into communication range. This algorithm should generate little overhead and still lead to fast content dissemination. Note that this problem is similar to file swarm in peer-to-peer networks [START_REF] Cohen | Incentives build robustness in BitTorrent[END_REF]. However, in our case infection can only happen when nodes meet physically.

B. Motivating Example

We now illustrate why the proper selection of pieces to send is important. The straightforward approach for a node to disseminate a content in an opportunistic network is to transfer pieces based on an increasing order of identifiers. We will call this strategy sequential in the remainder of this paper.

We show in Fig. 1(a) the sequential approach at three consecutive time instants. In the very beginning, only node n 1 has the content (composed of four pieces). At t = t 1 , n 1 meets n 2 . This latter has no pieces yet. The contact allowing the transfer of two pieces, n 1 sends then pieces 1 and 2. At t = t 2 , n 1 meets n 3 (which does not have any pieces either). As for the previous case, n 1 transfers the first two pieces. At t = t 3 , node n 1 has left the network. When n 2 and n 2 meet, the contact opportunity cannot be used because both nodes have the same pieces.

The ideal case would have been the one illustrated in Fig. 1(b). Node n 1 , instead of disseminating the same pieces each time it meets a node, applies some randomized strategy to avoid the situation described above. Here, at t = t 3 , nodes n 2 and n 3 are able to exchange pieces turning the encounter into a useful contact. In a real network composed of dozens or even hundreds of nodes, contact patterns are expected to be much more complex than the example above. We propose a generalization to the solution shown in Fig. 1(b).

C. Network model and assumptions

Let N = {n 0 , n 1 , . . . , n N } be the set of N nodes in the network. Nodes are mobile, but we do not assume any a priori knowledge of mobility patterns. For the sake of simplicity, we assume that all nodes in the network are interested in the unique content that is initially only available at a single node. Without loss of generality, we call this node the data source and denote it as n 0 . The generalization to any number of data sources and contents is straightforward.

The data source chops the content into K pieces of equal size. Pieces are sequentially identified as C = {c 0 , c 1 , . . . , c K-1 }. Nodes use their contact opportunities to get pieces, i.e., we assume that there is no infrastructure to help the dissemination process. Nodes can get pieces from the data source and from any other node in the network having it. Each node n i stores locally an availability bitmap vector a n i = {a 0 , . . . , a K-1 }, where a k = 1 if the node has piece c k , and a k = 0 otherwise.

The necessary contact time to transfer one piece is noted τ. We call this a contact slot. Thus, a contact duration t can be used to transfer ⌊ t τ ⌋ pieces. All the variables are summarized in Table I.

III. Basic content dissemination strategies

We now detail the operation of the basic strategies. A strategy specifies the pieces to transfer during a contact slot. We call "basic" strategies the sequential one illustrated in Section II-B and a randomized one where pieces to be transferred are selected following a uniform law.

A. Sequential content dissemination

In the sequential strategy, nodes transfer pieces to neighbors in an increasing order of identifiers. This implies that if a node has piece c j , it necessarily has pieces c k , ∀0 ≤ k ≤ j. We note ĉn i as the largest identifier node n i has, i.e., ĉn i = j if a j = 1 and a j+1 = 0. Initially, all nodes in the network are looking for the first piece (i.e., c 0 ) except the data source n 0 that already has all pieces. Formally, ĉn i = -1, ∀n i ∈ N\n 0 and ĉn 0 = K -1.

When two nodes n i and n j meet, they exchange their corresponding ĉ. Consider first the case where ĉn i > ĉn j , which means that n i has at least one piece that n j does not have. As long as the contact duration allows, node n i transfers pieces following the sequence c ĉn j +1 , c ĉn j +2 , . . . , c ĉn i . If ĉn i < ĉn j , the same is done but from n j to n i . At each transfer, the receiving node increments its ĉ.

Note that if ĉn i = ĉn j , the contact will be useless as the nodes have exactly the same contents. For a contact of duration t, the maximum number of pieces transferred is min{|ĉ iĉ j |; ⌊t/τ⌋}.

B. Uniform random content dissemination

The idea behind the uniform content spreading strategy is to select, among the pieces a neighbor has not received yet, the ones to be transferred in a uniformly-distributed random way. When nodes n i and n j meet, they exchange their availability vectors a n i and a n j (as defined in Section II-C). Node n i (resp. n j ) computes a n i ∧ (¬a n j ) (resp. a n j ∧ (¬a n i )), which gives the candidate pieces to be transferred (∧ stands for the "and" operator and ¬ is "not'). During the contact time, one or more of these candidate pieces are chosen to be transferred based on a uniformly-distributed random way. After one round of exchanges, nodes update their availability vectors as:

a n i = a n i ∧ i c j→i , a n j = a n j ∧ i c i→ j . (1)
where i c i→ j and i c j→i are vectors of K elements with all positions equal to 0 except the position relative to the piece just received, which is set to 1.

IV. PACS: Prevalence Aware Content Spreading

The goals of PACS are to achieve fast content dissemination while keeping the overhead low and making better use of contact opportunities. The challenges of conceiving such a system are mainly twofold. First, nodes must have a clue on the dissemination progress of each piece, so that they can appropriately prioritize their transmissions. Second, the dissemination information must remain local to reduce the overhead and achieve a scalable solution.

In PACS, in addition to the availability vector, node n i also keeps a prevalence vector p n i = {p 0 , p 1 , . . . , p K-1 }. As it will Algorithm 1 n i PACS strategy 1: while contact with(n j ) do 2:

receive f rom(n j , a n j ); 3:

p n i = p n i + a n j ; 4:
if (a n i ∧(¬a n j ) ∅) and (initiate connexion with(n j )) then 5:

c s ← prevalence selection f rom((a n i ∧ (¬a n j )), p n i ); 6:
send to(n j , c s ); if (a n j ∧(¬a n i ) ∅) and (connexion initiated by(n j )) then 9:

receive f rom(n j , c s ); 10:

i c j→i = {i 0 , . . . , i K-1 }; i k = 0, ∀k < K (k s) and i s = 1 11: a n i ← a n i ∧ i c j→i ; 12:
end if 13: end while become clearer later, the goal of p n i is to give a local view of the prevalent pieces in the network. Initially, all nodes have an empty prevalence vector. When nodes n i and n j meet, they exchange their availability vectors, exactly in the same way as the uniform content dissemination strategy. They also update their prevalence vectors respectively as:

an i ni nj an j 1 1 0 1 0 0 p ni p nj 1
p n i = p n i + a n j , p n j = p n j + a n i . (2)
Among the candidate pieces to be transferred, nodes select the one with the lowest prevalence. In case of tie, a piece is chosen in a uniformly distributed random way. Let c i→ j be the piece sent by n i to n j and c j→i be the piece sent by n j to n i . Once this step done, nodes update their availability vectors as indicated in Equation 1.

In the very beginning, the prevalence vector has a limited influence on the selection algorithm but gains importance as nodes move and exchange pieces. We show an example in Fig. 2. After exchanging their availability vectors, nodes update their prevalence vectors as indicated in Equation 2(p n i = {6, 1, 3, 2} and p n j = {8, 3, 5, 1} ). Then, n j transfers to n i the piece c 3 that is the only piece it is able to select, while n i chooses the less prevalent piece from {c 1 , c 2 } to send to n j . According to p n i , piece c 1 is less prevalent than piece c 2 . Node n i sends c 1 to n j . Once the exchanges are done, the respective availability vectors are set to a n i = {1, 1, 1, 1} and a n j = {1, 1, 0, 1}. The strategy is described in Algorithm 1.

Note that PACS has some similarities with peer-to-peer systems, notably BitTorrent [START_REF] Cohen | Incentives build robustness in BitTorrent[END_REF], [13]. Indeed, PACS uses a BitTorrent-like content swarming where data is divided into several pieces. When two nodes are in range of each other, they try to exchange the pieces with the lowest prevalence first. This corresponds somehow to the rarest-first algorithm used in BitTorrent. Nevertheless, the notion of rarest piece is essentially different in the two cases. In BitTorrent, each peer maintains a list of the number of copies in its peer set. This list corresponds to the prevalence vector described in PACS but contains exactly the number of copies in the peer set (neighborhood). In PACS, instead, nodes update their prevalence vector each time they initiate a connection with another node. Even if both strategies give the node an egocentric view of the rarest pieces, PACS adapts the algorithm to counterbalance the instability of a node's neighborhood due to the dynamics of the environment. Indeed, the nodes that are the most represented in the prevalence vector are those encountered often and/or during longer time intervals.

V. Evaluation framework

In this section, we summarize the simulation and model parameters. We use the ONE [START_REF] Keränen | The ONE Simulator for DTN Protocol Evaluation[END_REF] simulator with both mobility models and real movement trace based simulations.

A. Simulation parameters

We study the impact of the following main parameters: Area size. We select two areas: 300m×300m and 1,000m×1,000m. The first area is of the size of a train station when the second area is large as a city neighborhood. Number of nodes. The number of nodes varies between 100 and 2,500 nodes. By default, the number of nodes is set to 250. This parameter, associated to the area size, determines both the network density and the network diameter. Data size. We consider a unique content originally available at a single data source. The content size is set to either 12MB or 48MB. We select these values to fit a realistic scenario of video dissemination. As observed in [START_REF] Gill | YouTube traffic characterization: A view from the edge[END_REF], videos in YouTube have a mean duration of 4.15 minutes for an average size of 10MB. In our simulations, a 12MB-file represents a standard definition video, while a 48MB-file is a high definition video. Piece size. We investigate the impact of the piece size on the effectiveness of the algorithms. The piece size is incremented exponentially from 96kB to 12MB. By default, the piece size is set to 384kB. The piece size together with the content size determines the number of pieces.

These parameters are summarized in Table II. Bold values stand for the defaults.

B. Parameters of the mobility models

We used two mobility models for the simulations. First, nodes follow the random trip model. We only consider the steady state of the random waypoint by applying the formulas described in [START_REF] Palchaudhuri | Perfect simulations for random trip mobility models[END_REF]. Second, nodes move according to the community-based model formulated by Musolesi et al. [START_REF] Musolesi | A community based mobility model for Ad Hoc network research[END_REF].

For both models, nodes move at walking speed (between 0.5m/s and 1.5m/s). Two nodes are able to communicate when in communication range of 10m. Data is transferred at a throughput of 125 kBps. In addition, each model has specific parameters. For random trip, nodes may pause between two trips. Node pause time is uniformly selected in the interval [0, 120]s. In the community-based model, nodes are grouped

C. Real-world trace configuration

We use the RollerNet trace to evaluate the performance of the spreading strategies in real-world environment [START_REF] Tournoux | The accordion phenomenon: Analysis, characterization, and impact on DTN routing[END_REF]. The trace has been generated through contact logs between Intel iMote nodes (equipped with a Bluetooth interface). Each iMote performs regular scans and registers the MAC addresses of the responding devices around. The RollerNet trace has been collected during a rollerblading tour in Paris. iMotes were distributed to 62 participants and the total duration of the tour was about three hours. This trace is publicly available to the community through the Crawdad repository. 2The number of nodes is set to the number of participants in the experiment (i.e., 62). The transmission throughput of nodes is set to 125 kBps that correspond to an average Bluetooth throughput. At each simulation run, the data source is changed. The trace configuration is summarized in Table II.

D. Benchmarking

We compare PACS with the two basic strategies described in Section III: the sequential strategy and the uniform random strategy. Besides these strategies, we consider a centralized strategy where a central entity maintains a global prevalence vector. The global prevalence vector is used to select the piece to be transferred by nodes in the same way as in PACS. Nevertheless, it is only updated when a node receives a piece. The global prevalence vector reflects exactly the current dissemination state of each piece in the network. We call this strategy the dissemination Oracle. Obviously, deploying such a centralized strategy is impracticable in a real opportunistic network. We only use it for comparison purposes.

VI. Synthetic mobility evaluation

We use two mobility models to generate synthetic traces. First, we study the simple case of mobility induced by the

A. Impact of the network density and the network diameter

We vary both the area size and the number of nodes to study the dissemination delay of a 12MB-file (Fig. 3). We define the dissemination delay as the required duration for the content to be received by all the nodes in the network. It is the elapsed time between the transmission of the first piece to the first node and the reception of the last piece by the last node. We also measure the contact effectiveness (Fig. 4). The contact effectiveness is the ration between the time used for transfers over the total contact durations (in the period comprised between the first and the very last piece transfers). It indirectly measures the availability of new pieces when nodes meet. An effectiveness closer to zero means that nodes meet but seldom have pieces to transfer, while effectiveness closer to one reflects frequent exchanges. As expected, for the four strategies, the larger the number of nodes (denser network), the smaller the dissemination delay and contact effectiveness. This is due to the increase of the number of contact opportunities in denser networks. The sequential strategy gives the worse performances. Such a tendency is asserted in dense networks (Fig. 3(a) and Fig. 3(b)). Regardless of the number of nodes and the area size, PACS performs better than the sequential and the random strategies, achieving more than 2× faster dissemination delays. Furthermore, the results of PACS tend to the ones obtained using the oracle strategy.

B. Impact of the strategy on the piece dissemination evolution

We want to understand the reason of such a difference in the dissemination delay between the strategies. First, we compare the strategies regarding the piece dissemination evolution. Fig. 5 shows the proportion of time required, among the total time, to fully disseminate a specific percentage of pieces. The total time corresponds to the dissemination delay. The piece dissemination is faster with the random and sequential strategies. Indeed, all the nodes get the first piece after 17% of the total time for the random and only after 7% of the total time for the sequential. This reflects the fact that all nodes start by getting the same pieces with those strategies. In opposite, with PACS and oracle, nodes start by getting different pieces and no piece is fully disseminated before 82% of the total time for Oracle and 71% of the total time for PACS. Then, we analyze the impact of the strategy on the node infection evolution. Fig. 6 shows the proportion of time required, among the total time, to infect a definite percentage of nodes. A node is infected when getting all the pieces. Regardless the mobility model, we observe two different behaviors. Clearly, with PACS and oracle, nodes are infected very quickly compared to the random and sequential strategies. With PACS and oracle, the first node is infected at the middle of the total time. On the other hand, this first node is only infected at 80% of the total time, with the random and sequential strategies. Moreover, when the simulation achieves 90% of the total time, only 1.6% (resp. 29%) of nodes are infected with the sequential strategy (resp. random strategy) whereas 96% of nodes are already infected with PACS and oracle. Indeed, in a real scenario, we get more satisfied nodes with PACS since the node infection is faster.

C. Impact of the strategy on the neighborhood redundancy

We define the neighbor redundancy as the average fraction of useless connections selected by each node at each slot. A connection is considered useless if the two nodes involved in it have no pieces to exchange. We consider the dissemination of a 48MB file divided on 128 pieces. Fig 7 shows the neighborhood redundancy according to the number of nodes in the network. For all strategies, the nodes face more useless connections when the network is denser. Indeed, with the random trip model for example (Fig. 7(a)), only 1% or less of the selected connection is useless with 100 nodes in the network. This proportion is 10 times larger for 250 nodes.

The impact of network density can be explained by the augmentation of simultaneous co-located contacts. In the same neighborhood, nodes can get pieces from more neighbors when the network in denser. In particular, two co-located nodes can get the same pieces at the same time but from different neighbors. As a consequence, a future contact between these two nodes becomes useless. We observe, however, that PACS limits neighborhood redundancy as compared to sequential and random strategies. For example, with 500 nodes, the number of useless connection with PACS is divided by two comparing to the random strategy. This highlights the fact that co-located nodes get more heterogeneous pieces with PACS.

VII. Real-world trace evaluation

In this section, we evaluate the performance of the spreading strategies in the real-world context of the RollerNet trace. We vary the scenario by setting each node in the network as data source. Plots represent average results. Section V-C summarizes the experimentation details.

A. Impact of the piece size

Regardless the strategy, the dissemination delay increases with the augmentation of the piece size (Fig. 8). One reason is that the larger the piece size, the less the number of contact opportunities able to transmit the piece. Moreover, when the piece is too voluminous, the dissemination fails in many cases. This is what happens, when trying to send pieces larger than 1.5MB (resp. 3MB) for 48MB data (resp. 12MB data). Nevertheless, comparing the different strategies, the increase of the dissemination delay is less significant with PACS than with the sequential and random strategies. This difference is more noticeable when disseminating larger data (Fig. 8(b)). Indeed, when the number of contact opportunities able to transmit the piece is smaller, the impact the strategy grows.

B. Impact of the piece selection strategy

This section investigates the importance of the piece selection strategy in a real environment. We analyze the impact of the strategy in the evolution of both piece dissemination and node infection. Figs. 9(a) and 9(b) confirm the observations made with the mobility models. Indeed, compared to the sequential and random strategies, PACS achieves slower piece dissemination and a faster node infection. Clearly, the percentage of nodes having all pieces and playing the role of a source node increases faster with PACS. This observation reflects a higher heterogeneity of the disseminated pieces with PACS that explains the better dissemination delay.

To see in detail how the dissemination evolves in time, we estimate the piece dissemination delay (Fig. 10). We define the piece dissemination delay as the time required for a particular piece to be fully disseminated. We consider the dissemination of a 48MB data divided into 32 pieces of 1.5MB. Each plot in the figures represents a different data source. We clearly distinguish two different behaviors. On the one hand, the random and the sequential strategies (Fig. 10(c), Fig. 10(d)) achieve the dissemination of the first pieces very quickly. Nevertheless, they spend much more time to disseminate the last pieces. This can be explained by the lack of piece diversity in the network that causes useless contact opportunities. On the other hand, oracle and PACS (Fig. 10(b), Fig. 10(a)) start by spreading various pieces. This explains the slowness of the first piece dissemination. But, because nodes get different pieces, the overall dissemination is faster.

C. Impact of the data source

The data source may have an impact on the dissemination success. Fig. 11 shows the dissemination delay according to the data source ID. We assume the dissemination of a 12MB data divided on 2 pieces of 6MB. When the strategy fails to disseminate the content before the end of the trace, the dissemination delay is set to -1. The strategies dissemination success depends on the data source. Indeed, for some data sources (for example, nodes 26 and 50), the dissemination fails regardless the strategy. Moreover, we observe some data sources that achieve the dissemination for some strategies and fail for the others (for example, nodes 44 and 47). This last observation highlights the fact that the piece selection strategy remains important even when the number of pieces is small (here, there is only 2 pieces). Furthermore, we notice that PACS has the same delivery rate as oracle and outperforms the random and sequential strategies by more than 13%.

We further investigate the dissemination failures. Fig. 12 shows the node infection delay according to data source ID. We denote the node infection delay as the elapsed time before a particular node receives the full content. We consider three particular data sources: 26, 44, and 47. When node 26 is the data source, no strategy completes the dissemination (this represents 8% of the points in Fig 11). In this case, the infection of the first node in the network comes very late comparing to the common case represented by the source node 7 (Fig 12(a)). Nevertheless, even if the dissemination is not achieved for all strategies, the node infection delay is faster in PACS comparing to the random and sequential strategies. Indeed, with PACS, 95% of nodes are infected at the time 7,135 of the trace whereas the same rate is reached by the random and sequential strategies at time 8,810. When node 44 is the source, PACS and oracle complete the dissemination while the random and sequential strategies fail (represents 14.5% of the points in Fig 11). Here, the random and sequential strategies infect only 82% nodes when PACS achieves the dissemination. Finally, when node 47 is the source, random and sequential strategies achieve the dissemination while oracle and PACS fail (represents 1.6% of the points in Fig. 11). In this case, PACS infects 98% of the nodes at time 6,681 and fails to infect the last node even if it remains 30% of the total time. We find that the last non-infected node becomes isolated at this moment. This is due to the random selection of the neighbor with whom pieces are exchanged.

VIII. Related work

As discussed in Section IV, our solution is inspired by BitTorrent. Several solutions have been proposed to adapt BitTorrent to opportunistic and Ad Hoc networks [START_REF] Rajagpalan | A cross-layer decentralized BitTorrent for mobile Ad Hoc networks[END_REF], [START_REF] Gaddam | Study of BitTorrent for file sharing in Ad Hoc networks[END_REF], [START_REF] Sbai | P2P content sharing in spontaneous multi-hop wireless networks[END_REF]. Most of these adaptations, however, aim at constructing and maintaining an overlay network that enables multi-hop message routing. In other terms, nodes do not to be direct neighbors to become peers. Our solution, in turn, uses the network layer and the immediate communication capabilities of the nodes to disseminate data. Nadan et al. proposed SPAWN, a cooperative strategy for content downloading in vehicular networks [START_REF] Nandan | Co-operative downloading in vehicular Ad Hoc wireless networks[END_REF]. The piece selection scheme used in SPAWN is based on a proximity-driven strategy called rarest-closest. Such a strategy selects the rarest pieces and then ranks them based on the distance to the closest peer that has that piece. This solution shares with PACS the same motivations, i.e., they prioritize rarer pieces and consider peer location. SPAWN and PACS differ however on a fundamental aspect. SPAWN, as the abovementioned solutions, constructs an applicationlayer overlay that does not limit the peer selection to the one-hop neighborhood. Hence, it needs a routing protocol that maintains multi-hop routes between peers. Some other solutions implemented file swarming by only considering one-hop communications [START_REF] Goel | Efficient peer-to-peer data dissemination in mobile Ad Hoc networks[END_REF], [START_REF] Lee | P2P content distribution to mobile bluetooth users[END_REF]. Both solutions use uniformly-distributed random piece selection. Nevertheless, they use network coding in order to mitigate the coupon collection problem by increasing piece heterogeneity.

IX. Conclusion and open issues

In this paper, we proposed, designed, and evaluated PACS, an efficient strategy to disseminate large contents in opportunistic networks. PACS selects pieces to disseminate based on their prevalence in the network. We evaluate PACS using both mobility based and real-world trace simulations. Thanks to a more heterogeneous piece distribution, PACS achieves better dissemination delays and faster node infection than the sequential and random strategies.

Future work includes several interesting open issues. A first question is the impact of the selected neighbor, i.e., how to better select the relaying node when having several simultaneous contact opportunities. Second, in this paper, we considered a unique content dissemination. An interesting future direction is to consider the case of multiple contents to disseminate to multiple user groups. In this case, extending the algorithm with a caching policy could be a good solution [START_REF] Yin | Supporting cooperative caching in Ad Hoc networks[END_REF], [START_REF] Fiore | To Cache or Not To Cache?[END_REF]. Another important concern is the overhead induced by content fragmentation in this scenario (which includes extra headers for each piece). Indeed, our results showed that faster dissemination is obtained with smaller pieces. Nevertheless, to implement such a solution in reality, we must account for the tradeoff between overhead and dissemination delay. Finally, we also intend to extend PACS with networking coding capabilities.

Fig. 1 .

 1 Fig. 1. A motivating example. Selecting the pieces to transfer is fundamental to efficient dissemination of fragmented contents.

  State 1: select pieces.

  State 2: update local vectors.

Fig. 2 .

 2 Fig. 2. Piece selection using PACS. Initially, n i has pieces {c 0 , c 1 , c 2 } and n j has pieces {c 0 , c3}.

  (d) CB. Area 1, 000m × 1, 000m.

Fig. 3 .

 3 Fig. 3. Dissemination delay according to the number of nodes. Dissemination of a 12MB data divided on 32 pieces of 384kB. Random trip (RT) versus community-based model (CB).

  CB. Area 1, 000m × 1, 000m.

Fig. 4 .

 4 Fig. 4. Contact effectiveness according to the number of nodes. Dissemination of a 12MB data divided on 32 pieces of 384kB. Random trip (RT) versus community-based model (CB).

Fig. 5 .

 5 Fig. 5. Piece dissemination evolution. 250 nodes. Dissemination of a 48MB data divided on 128 pieces of 384kB. Area 1, 000m × 1, 000m.

Fig. 6 .

 6 Fig. 6. Nodes infection evolution. 250 nodes. Dissemination of a 48MB data divided on 128 pieces of 384kB. Area 1, 000m × 1, 000m.

Fig. 7 .

 7 Fig. 7. Neighborhood redundancy. Dissemination of a 48MB data divided on 128 pieces of 384kB. Area 1, 000m × 1, 000m.

Fig. 8 .

 8 Fig. 8. Dissemination delay according to the piece size. Nodes move based on RollerNet trace. (Please note that the two graphs do not use the same scale, for the sake of visualization.)

Fig. 9 .

 9 Fig. 9. Dissemination evolution. Dissemination of a 48MB data divided on 128 pieces of 384kB. Nodes move based on RollerNet trace.

Fig. 10 .

 10 Fig. 10. Piece dissemination delay. Dissemination of a 48MB data divided on 32 pieces of 1.5MB. Nodes move based on RollerNet trace.

Fig. 11 .

 11 Fig. 11. Dissemination delay according to the data source ID. Dissemination of a 12MB data divided on 2 pieces of 6MB. A dissemination delay equals to -1 means that the strategy fails to disseminate the content. λ is the complete delivery rate. Nodes move based on RollerNet trace.

Fig. 12 .

 12 Fig. 12. Node infection delay according to data source ID. Dissemination of a 12MB data divided on 2 pieces of 6MB. Nodes move based on RollerNet trace.

TABLE I Summary

 I of the variables.

	Variable	Definition
	N	Set of nodes in the network
	N	Number of nodes in N
	n 0	Data source
	C	Content to be disseminated
	K	Number of pieces that compose C
	c i	ith piece of C
	τ	Contact slot (time to transfer one piece)
	a n j	Availability bitmap of node n j

TABLE II Simulation

 II parameters. The initial number of groups is set to 50. Groups are mapped onto a topographical space corresponding to cells. The number of cells in the area is set to 3×3. TableIIsummarizes the parameters of the models.

		Area size	300m×300m, 1,000m×1,000m
		Number of nodes	100, 250, 500, 1,000, 2,500
	Factors	Data size	12MB, 48MB
		Piece size	96kB, 192kB, 384kB, 768kB,
			1.5MB, 3MB, 6MB, 12MB
		Range	10m
	Parameters of the models	Moving speed Throughput	[0.5, 1.5] m/s 125 kBps
		Number of nodes	62
	RollerNet configuration	Trace duration Throughput	3 hours 125 kBps
	together based on social relationship among individuals.

http://crawdad.cs.dartmouth.edu/meta.php?name=upmc/rollernet

Acknowledgment

This work is partially supported by the ANR Crowd project under contract ANR-08-VERS-006, the European Commission in the framework of the FP7 Network of Excellence NEW-COM++ under contract 216715, and the following Brazilian Agencies: Capes, CNPq, Faperj, and Finep/Funttel.


J Lepinoux

Comparing Kinetic Monte Carlo simulations with Cluster Dynamics: what can we learn about precipitation? Application to AlZr alloys

Keywords: Monte-Carlo, aluminium alloys, clusters, precipitation, numerical modelling, numerical simulation Cluster Dynamics, Precipitation, Nucleation, Free Energy, Coagulation

Comparing Kinetic Monte Carlo simulations with

Cluster Dynamics: what can we learn about precipitation? Application to AlZr alloys.

INTRODUCTION

The goal of the present paper is multi fold:

-To propose a methodology to compare a model, mesoscopic or macroscopic, designed to predict precipitation, with Kinetic Monte Carlo (KMC) simulations, -To apply this methodology to a particular model, i.e. Cluster Dynamics (CD), in the case study of AlZr alloys, -To show what can be learnt about precipitation, from the combination of these two methods and additional tools, even in situations considered to be trivial.

Among classical approaches, CD is certainly the most rigorous way to model precipitation in binary alloys, especially when monomers are known to be the only mobile clusters. Indeed, this simple method is able to treat the different stages of precipitation, from nucleation to coalescence while avoiding usual approximations of macroscopic models (Clouet et al., 2005). The interest of modelling precipitation in binary alloys is nowadays mostly to check the validity of ingredients whose macroscopic models are built on. And comparing respective results of CD and KMC is a privileged way to improve our understanding of precipitation fundamentals. Such improvements seem highly desirable to avoid misinterpretations while trying to model much more complex situations like those encountered in modern industrial alloys.

The CD scheme is based on pairs of condensation and evaporation coefficients, noted β n and α n+1 . A recently enhanced thermodynamic solution has been shown to correctly reproduce socalled equilibrium distributions of clusters in a wide range of (normalized) temperature or solubility limit in the case of L1 2 clusters embedded in a FCC matrix (Lépinoux, 2006 and2009). Three situations, i.e. sets of solute concentration and temperature, concerning low solubility limit AlZr alloys were selected: 1% at 873 K, 1% at 723 K and 3% at 873 K, referred to hereafter as case 1, 2 and 3, respectively. It has been shown that in these alloys only monomers are mobile, or diffuse Clouet (2004), Clouet et al. (2004). In addition, these solute concentrations are smaller than the percolation threshold of the cubic structure (1/4 of about 30%, see [START_REF] Stauffer | Introduction to Percolation Theory[END_REF]. Thus, such alloys exhibit interesting features to test the ability of CD to predict precipitation Basic equations are briefly recalled in section 2 to be applied to supersaturated alloys. Sections 3 and 4 present the difficulties of comparing such a model with KMC simulations due to the small finite volume considered in atomistic simulations while CD is applied to a pseudo-infinite continuum. To minimize these difficulties, it is proposed to adapt the classical scheme to a finite volume. Various discrepancies are observed between CD and KMC, depending on temperature and materials properties. To understand the origin of these divergences, a comparison procedure has been developed and some guidelines to get the best from such comparisons are provided. Section 5 shows that the morphological analysis of clusters built-in during KMC simulations provides new insights about precipitation. Finally, in section 6, gathering all results, some ingredients missing in CD to correctly reproduce KMC results are identified and discussed.

All KMC data mentioned in this paper were provided by courtesy from E. Clouet or obtained with the KMC code from SRMP (CEA, Saclay); details about the KMC simulations can be found in Clouet (2004) and Clouet et al. (2004).

FUNDAMENTAL EQUATIONS OF CLUSTER DYNAMICS

The fundamental equations of CD are briefly recalled; details about the derivation of following equations can be found in Clouet et al. (2005) and Lépinoux (2009). The structure of the master equation for the evolution of clusters of the atomic concentration C n of clusters of size n>1 writes:

Ċ n = α n+1 C n+1 +β n-1 C n-1 -α n +β n C n (1)
The evolution of monomers concentration is simply given by the conservative condition:

∑ n=1 n C n = C 0 (2)
where C 0 is the solute concentration in the system. The pair of coefficients β n and α n+1 are the global exchange rates from class n to class n+1 and reversely, associated with the mechanisms of monomer condensation and evaporation, respectively. These two coefficients are coupled by the relation:

β n α n+1 =C 1 exp -∆F n+1 -∆F n /k B T ( 3
)
where C 1 is the monomer concentration, k B is the Boltzmann constant, ∆F n is the difference of chemical potential between that of a n-mer and that of n monomers. The chemical potential of nmers, F n , can be written as (Lépinoux, 2009):

F n =F n 0 +k B T ∑ k ln 1-C k V k,n (4)
It is composed of two contributions: the first one, F n 0 is the free energy of (isolated) clusters assumed in thermodynamic equilibrium, while the second term is an entropy contribution of the cluster gas; in particular it accounts for the effect of frustration of the matrix (V k,n is the number of atomic sites forbidden to a k-mer by an n-mer). The connection with physical time is given by the coefficient

β n = D ω S n R n C 1 ( 5
)
where D is the diffusion coefficient of monomers (impurity diffusion coefficient), ω is the atomic volume, S n and R n are the surface and radius of clusters, respectively.

As shown recently in Lépinoux (2009) the master equations can be rewritten in a different way to make clearer the weak coupling between thermodynamics and kinetics. Defining ρ n as ρ n =β n /C 1 and ϕ n as ϕ n =β n /α n+1 the new form of the system is:

∂ C n ∂ C 1 = [ ϕ n+1 ρ n+1 C n+1 -ρ n C n -ϕ n ρ n C n -ρ n-1 C n-1 ] / [ Ċ 1 C 1 ] (6)
Ċ1

C 1 = -∑ n>1 n [ ϕ n+1 ρ n+1 C n+1 -ρ n C n -ϕ n ρ n C n -ρ n-1 C n-1 ] (7)
Indeed, according to equation ( 5) ρ n is proportional to n 1/3 which is a weak coupling with n, the cluster size. In the complete absence of coupling between ρ n and n these two equations would be simpler and cluster distributions would depend only on the coefficients ϕ n , which are purely thermodynamic quantities. Despite a coupling in n 1/3 , equations (6-7) strongly suggest to examine the evolution of precipitation kinetics versus C 1 instead of versus the physical time, to first focus on thermodynamics and decide whether the predicted thermodynamic states are correct or not.

COMPARISON OF CLUSTER DISTRIBUTIONS -MICROSCOPIC SCALE

As in under-saturated or weakly super-saturated alloys studied in Lépinoux (2009), the key quantity to examine is the distribution of clusters, i.e. their atomic concentration versus their size, defined as the number of solute atoms they contain. Indeed, this is important information characterizing the thermodynamic state of the alloy at a given time, or equivalently at a given concentration of monomers; it will be shown later that this information is not sufficient to fully describe the system, nevertheless it remains the best starting point. The usual "precipitation kinetics" is just the evolution of these distributions with time.

The main drawback of such a direct comparison between KMC and CD cluster distributions is that CD considers a pseudo-infinite medium while for obvious computing limitations KMC simulations necessarily deal with very small volumes. For instance, a volume of 10 7 atomic sites induces a cutoff in the possible atomistic concentrations at 10 -7 (cf. figure 1). Due to present computer limitations, it is not possible to investigate over a range of system sizes large enough to conclude about the absence of influence of this size constraint on cluster distributions, nevertheless this seems to be an acceptable influence. Of course, it is easy to impose similar conditions to CD: considering the same volume of material than in KMC simulations, classical CD equations are applied to integers (i.e. number of clusters) instead of floating numbers (i.e. concentration of clusters). When appropriated, some randomness is introduced following classical algorithms to solve properly numerical operations with integers, which does not modify results of CD calculations, disregarding normal statistical variations. The main advantage of this adaptation of CD is that the lengths of respective cluster distributions can now be compared. Unfortunately, the direct comparison of such cluster distributions is even more difficult to interpret due to the increasing number of empty classes of size, now in both distributions. To by-pass this difficulty, instead of comparing the direct cluster distributions, it is highly preferable to consider the cumulative distributions, defined as follows:

C n = ∑ k=1 n kC k (8)
Compared with direct distributions, an advantage of these cumulative distributions is to exhibit a much lower dispersion over various runs and a low dependence on the size of the simulation box, provided this one is larger than a certain size, depending slightly on the imposed conditions (for the present problem, 10 6 atomic sites is an very acceptable minimum). In principle, one could fit these curves with continuous functions and compare their first derivative, i.e. to rebuild equivalent direct distributions; but this procedure is rather cumbersome and can be source of various errors. Analysing these cumulative distributions is less trivial but much safer. Before any particular comparison some general and simple properties can be guessed about these cumulative distributions. Most of divergences should concern classes of large size and as the concentrations of these classes are very small compared with the monomer concentration, these deviations are likely to be stable. On the contrary, the deviations concerning classes of small size should vanish much faster due to the strong tendency of the system to come back at equilibrium whatever the origin of deviations. Of course, comparisons between the two methods have to be done for the same concentration of monomers, as done in figures 1 and 2. Now we consider the respective shapes of cluster distributions obtained with KMC and CD, as well as their evolution.

-Case 1: C 0 =1%, T=873 K At the beginning, until precipitation starts, with a critical size n*=19, both distributions are in perfect agreement. After the beginning of precipitation a small divergence appears, larger for large classes as expected. This divergence propagates towards classes of small size then decreases as a plateau appears within the cluster cumulative distribution. Such a plateau corresponds to a widening hole within the direct distribution of cluster size, due to the increasing separation between supercritical clusters and the solid solution. Of course, at a given point of this evolution, the width of this no-cluster range might slightly depend on the size of the system but it is not an artefact. Finally only a small residual translation persists in the last part of the curve while the critical size is around 30 (beware of the logarithmic scale in abscissa). In first approximation, the observed differences are small enough to conclude that for weakly supersaturated alloys CD reproduces fairly well KMC distributions and in this case, it is not necessary to improve the CD algorithm. However the observed deviations are interesting to understand, in relation with the two following cases, of higher supersaturation.

-Case 2: C 0 =1%, T=723 K As in case 1, before precipitation starts with a critical size n*=7, KMC and CD distributions are in excellent agreement. Then, note that deviation which develops has the opposite sign to that observed in case 1. In addition the amplitude of this deviation is much larger and concerns a much larger fraction of classes of cluster size. In this case, this means that the growth of clusters is faster than expected. A possible mechanism will be discussed later.

- At this stage we have identified three different possible scenarii of deviation for KMC cluster distributions versus those predicted by CD. One could examine the evolution of the monomer concentration versus time; of course, other deviations are observed. As they are not helpful to understand why thermodynamic states are different, they are not reported here. Thus, to understand what these deviations mean, we need to get more information about the clusters. A simple and classical way is to report the evolution of average quantities characterizing cluster distributions as proposed in the next section.

COMPARISON OF CLUSTER DISTRIBUTIONS: MACROSCOPIC SCALE

Indeed, although in KMC simulations the location of every solute atom is available at any time, for the sake of simplicity, the classical outputs are average quantities which can be obtained from the analysis of cluster distributions. For this purpose, it is usual to take the critical size n* of clusters as defined by the classical nucleation theory (Clouet et al., 2005) as the threshold to distinguish stable precipitates from unstable clusters, during the whole kinetics. Thus, at any time, only clusters of size n larger that this theoretical critical size are counted as precipitates and the provided outputs are typically:

the atomic concentration of precipitates N p the average size of precipitates n the atomic fraction of precipitates F p =N p n By construction, only two of these three quantities are independent, thus one of them can be disregarded. If one wants to compare with experimental data, it is obvious that the two first quantities are the most convenient (see for instance (Clouet et al., 2005)). But to compare numerical results the average size of clusters should be avoided; indeed, the usual shape of obtained curves is highly inappropriate for an in-depth comparison, contrary to that reporting the evolution of F p which exhibits a more regular slope. Thus, here, only F p and N p will be used to compare CD and KMC precipitation kinetics, while the average size will be disregarded. Figure 3a shows the usual representation mode of these quantities, i.e. their evolution versus the physical time, while figure 3b shows the evolution of the same quantities versus (1-C 1 )/C 0 , both for case 1. For CD results, two solutions are compared: -CD 1) the classical solution, with a constant free surface energy, here taken from Clouet et al.,

(2004) -CD 2) the complete solution, i.e. equation ( 4) figure 3 -Case 1: C 0 =1%, T=873 K, n*=19 (figure 3a-b) If one considers only figure 3a there is a clear advantage to the second solution for the prediction of the number of precipitates but for the precipitated fraction it is difficult to conclude. Now if one considers figure 3b, there is no more ambiguity: the second solution is almost correct, the beginning is perfect, then the predicted concentration of precipitates is 20% too small but later the two curves converge, confirming figure 2a. On the contrary, the first one is definitely disqualified. As explained in Lépinoux (2009) thermodynamics and kinetics cannot be completely separated; nevertheless, to understand the deviations of cluster distributions reported in the previous section, the representation mode adopted in figure 3b is the most efficient one to test various approximate solutions. Consequently, only this representation mode will be used for the two other cases to focus -Case 1: C 0 =1%, T=723 K, n*=7 (figure 3c) Again, the precipitated fraction predicted by CD is almost perfect, only a tiny difference can be noted at the very beginning. The concentration of precipitates exhibits the same kind of deviation as the precipitated fraction at the very beginning of precipitation, then it is correct up to the maximum of this curve. After the peak, a noticeable deviation appears and there is no evidence of convergence. Again this confirms the increasing deviation observed in figure 2b.

-Case 3: C 0 =3%, T=873 K, n*=8 (figure 3d) The most streaking feature is that the CD solution clearly fails to reproduce the beginning of the precipitation kinetics although it converges and is in fairly good agreement up to the N p peak. However a deviation similar to that observed in case 2 seems to develop after this peak even if it is at a lesser extent. Note also that the deviation observed at the beginning of the kinetics is of the same type than in the case 2, it is just much more pronounced. This suggests that the early deviation observed in figure 2c has a short time-life in case 2 and has been overlooked.

Finally, it seems that case 2 and 3 exhibit a main type of deviation but also a secondary one, the roles being inversed between these two cases. The information provided by such comparisons is rather poor but at least it confirms the existence of major discrepancies between KMC and CD results in a more conventional way.

CD is based on two strong hypotheses worth examining:

clusters are at thermodynamic equilibrium diffusion of monomers is the only mechanism for growth or decay of clusters

CHARACTERIZING THE MORPHOLOGY OF KMC CLUSTERS

A great advantage of KMC is that coordinates of the atoms are available at any time. Thus at a given time, or concentration of monomers, it is possible to visit all clusters and to compare their morphology with the predicted one for clusters at thermodynamic equilibrium. For that purpose, we need to define some properties, necessarily related to the free energy of clusters. It is recalled that the free energy term F n 0 for clusters at thermodynamic equilibrium can be calculated by a Monte-Carlo technique based on the sampling of two quantities, namely the capture and the release rate, defined as follows, respectively (Lépinoux, 2005 and 2009): (10) Subscripts (n) and (n+1) mean that the thermal averages are calculated over ensembles of configurations of size (n) and (n+1) respectively. N bonds in and N bonds out are the number of bonds between the site where a solute atom is going to be exchanged with a solvent atom, with the cluster ("in") or with the next shell ("out"), respectively.

P n,n+ 1 0 = ∑ N bonds out exp N bonds in T w /T n (9) P n+1,n 0 = ∑ N bonds out exp-N bonds in T w /T n+1
The ratio of these two quantities is related to the difference of free energy between configurations of (n+1) solute atoms in one hand and that of a configuration of n solute atoms and a monomer on the other hand, as follows: However, the relevance of these coefficients and their ratio is not restricted to the calculation of F n 0 . Indeed, they characterize the morphology of the cluster-matrix interface; thus they can be used to reveal and quantify a deviation of the cluster morphology versus their average shape at thermodynamic equilibrium (Lépinoux, 2009). Multiplying the capture factor by C 1 allows to put into evidence the local critical cluster size n* defined by the value of n such that C 1 P n,n+ 1 0 = P n,n-1 0 . This local critical size coincides with the usual macroscopic one only in highly dilute alloys where the second term in equation ( 4) is negligible.

P n,n+ 1 0 P n+1, n 0 =Exp- F n+1 0 -F n 0 -F 1 0 kT (11)
Whatever the total solute concentration, the monomer concentration and the temperature, these two as-defined quantities exhibit a clear change of behaviour around n* where they respective curves intersect and define two regions as shown in figure 4 for case 1: -n<n*, disregarding statistical fluctuations, the predicted values (equilibrium) superimpose pretty well with the KMC data, as expected.

-n>n*, the KMC data no longer behave as expected. Both factors increase much faster than expected: this is the signature of cluster morphologies more extended, in average, than the average one at equilibrium. The release factor characterizes the cluster side of the cluster-matrix interface and is consequently more sensitive to details of the cluster morphology than the capture factor, related to the matrix side. This explains why the deviation of the release factor is always larger than that of the capture factor. Then the question to address is whether it is a general rule or particular to weakly supersaturated alloys as in case 1 and at some steps of the precipitation kinetics.

In figure 5, the evolution of the release factor was plotted for increasing values of n*, while C 1 decreases. As can be seen, the deviation continues to develop while n* increases, and the larger the size of precipitates, the larger the deviation of their morphology from the equilibrium shape, in all cases. This confirms that the relative weight of extended configurations is higher than at thermodynamic equilibrium, whatever the supersaturation. In the two first cases, i.e. with C 0 =1%, the starting of the deviation corresponds pretty well with the value of n*. But in case 3, i.e. with C 0 =3%, note that this seems true only at the very beginning of precipitation; then the deviation tends to start earlier and earlier; for the last curve it starts for n about half of n*. Note that for a given cluster size, in the first approximation the deviation is quite the same for the various distributions, for a given case. Nevertheless this deviation seems to slowly decrease. This is particularly clear in figure 5b for the last set of KMC values. Among all analysis provided here, this is the best clue of convergence toward equilibrium in the late stage of precipitation (of the investigated range). Note also for n<n* a deviation of opposite sign clearly appears. All these points will be discussed later.

Thus, the examination of coefficients P n,n+ 1 0 and especially P n+1,n 0 provides interesting information about the change of morphology of clusters as a function of their size during precipitation, nevertheless, according CD, it is their ratio, P n,n+ 1 0 / P n+1,n 0 (equation 11), which is the relevant quantity from a thermodynamic point of view. Strictly speaking, this quantity cannot be extracted from KMC results, nevertheless the quantity P n,n+ 1 0 / P n,n-1 0 is an excellent approximation provided that n is greater than typically 10. To improve the accuracy of comparisons, the KMC data were compared with expected values of P n,n+ 1 0 / P n,n-1 0 , instead of the ratio P n,n+ 1 0 / P n+1,n 0 ; again the physical information is quite the same. The results reported in figure 6 for increasing values of n*, as in figure 5, are more or less dispersed due to the limited size of the system but all exhibit the same global trend. Up to n* (approximately), again clusters exhibit the same properties as at thermodynamic equilibrium, while for larger values the ratio deviates more and more toward lower . Apart this general behaviour the particularities observed in figure 5 for cases 2 and 3 can be observed here too, but at a lesser extent, due to the less sensitive P n,n+ 1 0 coefficient. Nevertheless this seems to confirm some change in cluster morphology, some kind of "recovery" in the late step, especially in figure 6b. Note in figure 6c that the properties of clusters seem to be fairly independent of their size, at least in the final distributions. This point will be also discussed later.

Dispersion

One of the last sets of data (n*=19) in figure 6c is analysed again in figures 7 and 8 to focus on two aspects. As indicated in the figure captions, the points plotted in previous figures are averages for given cluster sizes, which hides the dispersion per class of size. Figure 7 shows that this dispersion is particularly large in the middle of the distribution. The reason is that only one value is possible for the 2-mers, i.e. at the beginning of the curve, then the range of possible values increases very quickly and classes are still reasonably populated to explore this range, while at the end of the distribution, classes are represented only by one or a few clusters, when not empty, thus the range of dispersion decreases quickly after a maximum. This dispersion is a feature usually disregarded, which is fully justified for approaches historically dedicated to low temperatures and high dilution situations. Nevertheless, it is clear that improving modelling of precipitation should also consider this aspect.

Macroscopic and microscopic critical sizes

Through the same example as in figure 7, figure 8 illustrates the confusing concept of critical size. First we compare the ratio P n,n+ 1 0 / P n,n-1 0 , for a given value of C 1 , with its expected values at equilibrium, as done in figure 6. On the same figure we report also the ratio β n / α n C 1 . The classical critical size n* is defined by the condition β n =α n in any case, but, in the limit of infinite dilution, this condition is equivalent to C 1 P n,n+ 1 0 = P n,n-1 0 because the second term in equation ( 5) is negligible in this case. A simple way to compare the conditions of criticability according these two criteria is indicated in figure 8 by a unique horizontal line of height 1/C 1 (normalized by the same factor as other quantities) which defines the sub-and super-critical ranges. Of course this defines two distinct critical sizes which here differ by a factor 2, approximately, which is still a small difference compared with alloys of high solubility limit (see Lépinoux (2009) for an example). Again, the examination of the first quantity shows that in the subcritical region, in average, clusters are in equilibrium, while in the supercritical range, they deviate so much that most classes remain close to or even under the stability threshold. Now, coming back to figure 7, it can be seen that not all clusters of size n>n* are supercritical or similarly not all clusters of size n<n* are subcritical, their state depending first of all on their morphology, not on their size. Now if one examines the second quantity, in average all classes of size larger than the macroscopic critical size are clearly super-critical. This value of macroscopic critical size compares well with the limit of agreement of P release with the equilibrium one already mentioned about figure 6c. Thus to summarize, the behaviour of P release is in good agreement with that of the macroscopic critical size while the behaviour of P capture /P release is in good agreement with the local critical size. A tentative explanation is proposed: -P release , as already mentioned is among other features one possible way to finely characterize the structure of clusters surface; it is very sensitive to their morphology. The agreement between the change of behaviour of P release around the macroscopic critical size suggests that the structure of clusters interfaces reflect the growth and decay mechanisms, associated to the definition of the macroscopic cluster size. Whatever these mechanisms it sounds consistent. -Like P release , P capture contains information about the first layer around clusters, the one where exchange takes place, but also on the next one in the matrix which is assumed empty. For the purpose of calculating the free energy of isolated clusters this is absolutely correct. And by Deviations of cluster morphology from equilibrium influence the properties of clusters and then the global precipitation kinetics. If they are more compact than at equilibrium, they are more stable, therefore they better resist to dissolution. Therefore, when dissolution prevails, poorly connected solute atoms are first released and the shape of clusters is slowly driven toward compact configurations, which decreases the release rate. In contrast, when coarsening prevails, solute atoms or local fluctuations are captured mostly at random, driving the cluster shapes toward less stable configurations, which, this time, decrease the coarsening rate. Thus, although the reasons are opposite, the two effects tend to slow down the precipitation kinetics.

F

COAGULATION

Obviously the morphological deviations of clusters should influence the precipitation kinetics, but one can wonder if it is an important contribution to the observed discrepancies between KMC simulations and CD. The interest of a simple framework like CD is that it is easy to test almost any assumption. Thanks to data reported in the previous section it is fairly easy to mimic the deviations or the ratio P n,n+ 1 0 / P n+1,n 0 from their equilibrium values. Surprisingly, if nothing else is changed in the CD scheme, morphological deviations of super-critical clusters have a minor effect on precipitation kinetics compared with their amplitude. Again this suggest that the main reason for observed differences between KMC and CD results, at least in the most supersaturated cases 2 and 3, is related to some kinetic mechanisms which are not accounted for in CD. The observed morphological deviations, mostly of super-critical clusters, are just a consequence of these mechanisms and not the main cause of discrepancy between KMC and CD, even if of course they do participate. Detailed observations of cluster morphology in the 3D space at various temperatures and concentrations suggests a possible mechanism which could be called "static-coagulation" by opposition to classical coagulation which assumes a non-zero mobility of clusters, depending on their size (see for instance ). An easy way to reveal this mechanism is to observe the growth of precipitates depending on the solute concentration. Figure 9 shows several snapshots of the growth of an isolated cluster with conditions: C 0 =2.525%, T=800 K. These conditions were chosen for computing purposes, to obtain a weakly super-saturated alloy at an intermediate temperature between that of case 2 and 3. When the size of the cluster is about 100, fluctuations are rather large compared with cluster size but the shape remains roughly cubic. At large size, i.e. more than 10000 solute atoms, {100} facets are still clearly visible although the global shape is more rounded. Although from time to time a large fluctuation is captured which seriously perturbs the shape of the cluster for a long time (see figure 9c), growth occurs mostly by capture of monomers and small fluctuations.

Figure 10 shows a completely different scenario at T=873 K, C 0 =3% (10a) and C 0 =5% (10b). These alloys are highly super-saturated which induces many super-critical clusters in the KMC simulation box. Only clusters containing more than 100 solute atoms are shown. Contrary to the previous case, here clusters look composed of several smaller clusters connected by bridges of various strength. Although the number of clusters increases and their average size too, it is difficult to predict which ones will survive as sub-clusters often dissociate and re-associate with their neighbours and the complexity of clusters increases with C 0 . This is fully consistent with the important deviation of super-critical clusters properties as indicated in figures 6 to 8. The quasi constant ratio P capture /P release in the range of size 20-60, in figure 7 for instance, can even be seen as the signature of some kind of self-similarity due to the intense activity of recombination and fragmentation of clusters preventing the growth of well-formed precipitates. Of course the existence of two sub-lattices increases this trend, impeding the merging of some close clusters. Coagulation based on mobility of small clusters is now well documented but the influence of the kind of static coagulation, requiring only monomer diffusion, has been largely neglected. In addition, it cannot be treated in a generic way, as the ability of clusters to reorganize after the capture of a fluctuation strongly depends on the details of the atomic potential for the considered alloy. In the present case, a complete reorganization is almost impossible due to strong repulsive interaction between first neighbours which prevents a vacancy from exploring a cluster in depth.

A variant of this mechanism which occurs mostly at the beginning of case 3 and at a much lesser extent in the very beginning of case 2 is what could be called "geometrically necessary coagulation". It results from the initially high concentration of monomers while "static coagulation" defined above results also from a high supersaturation. Indeed, when the solute concentration increases, the available space for diffusion of monomers decreases and early reorganization is impossible without forming clusters of size much larger than expected for that concentration of monomers. As a consequence, the concentration of small clusters is much lower than expected at equilibrium; nevertheless, after reaching a maximum of deviation, the two curves converge (see figure 2c). Figure 11 shows the proportion of frustrated sites for monomers, i.e. the proportion of atomic sites where a monomer cannot be located without bonding with other solute atom. This ratio strongly depends on the solute concentration. When C 0 =1%, whatever the temperature, when reported versus (1-C 1 / C 0 ) as previously, before slowly decreasing, this ratio exhibits a plateau. The beginning of precipitation already corresponds to the decreasing part of these curves (compare with figure 3). But for case 3, i.e. with C 0 =3%, instead of a plateau one observes a clearly increasing and rather long step, whose maximum around C 1 /C 0 =0.4 corresponds well with the maximum of discrepancy between KMC and CD cluster distributions (see Figure 2c). After that, the two curves converge and the fraction of frustrated sites quickly decreases. Such behaviour suggests that some rearrangements during the incubation stage are necessary then thermodynamics plays its normal role. Generally speaking, coagulation is a perturbation of the fundamental mechanism which remains the exchange of monomers. The late stage in case 2 is another illustration of this principle: when the supersaturation is low enough, clusters slowly recover their equilibrium properties.

As space is not a direct ingredient of the CD scheme, in its present state this method is not able to deal with the finite nature of the number of atomic sites. Thus, such an effect cannot be accounted for without serious modifications.

Of course these coagulation mechanisms are not very difficult to mimic in an empirical modified CD able to fit any KMC kinetics. However nothing worth noting could be learnt from such an empirical approach. Extending CD as a predictive tool for concentrated alloys requires such effects to be modelled in a self-consistent way.

CONCLUSION

A detailed procedure to compare KMC simulations with predictions of models treating precipitation at a meso or macro scale has been proposed and applied to CD. The first step consists of reporting global quantities like the concentration of precipitates and the precipitated fraction versus (1-C 1 /C 0 ) instead of versus the physical time. The advantage of this representation is to focus on thermodynamic properties to better detect possible discrepancies between the two methods and avoid some trivial misinterpretations. Indeed, as long as the thermodynamic states are not equivalent and their differences not understood, discussing their evolution versus time is premature. The second step consists of examining the evolution of cumulative cluster concentrations that are the fundamental signature of precipitation kinetics. Finally the third step is based on the analysis of cluster morphology, applying a technique already used to calculate the free energy of clusters at thermodynamic equilibrium. Direct observations of 3D configurations allow these analyses to be confirmed.

Two fundamental assumptions have been investigated in detail with the help of these various tools. It has been shown that in the first approximation the assumption that clusters are at thermodynamic equilibrium is correct in the sub-critical range, but super-critical clusters exhibit noticeable deviations of morphology and then of properties. In this context, "thermodynamical equilibrium"means that clusters of a given size exhibit the same properties, in average, than those of an isolated cluster free to explore the whole range of its possible configurations in an infinite medium.The use of the ratio P capture /P release to characterize the properties of clusters does not seem appropriate for highly supersaturated alloys. Again this is related to the existence of a competition between the usual growth mechanism based on the migration of monomers and the capture of other clusters formed at close distance. On the contrary, P release is able to detect the deviation of cluster morphology due to these unexpected captures. Two mechanisms, referred to as "static" and "geometrically necessary" coagulations, have been put into evidence; the distinction between the two mechanisms is of course mostly a question of convenience. These mechanisms, undoubtedly enhanced by the L1 2 structure of clusters studied here, are likely to be observed also in segregation and are rather difficult to model in a self-consistent way. Cluster Dynamics is definitely a remarkable tool when coupled with KMC simulations to explore the various facets of precipitation but should be used with caution to predict precipitation kinetics when the solute concentration exceeds some threshold, here of the order of 1% atomic. Accounting for all features revealed in the present work appears in contradiction with the expected simplicity of such a model. A preliminary exploration of a given problem with Kinetic Monte Carlo simulations and an analysis of the observed discrepancies following the procedure proposed here should allow to evaluate the magnitude of errors and decide whether the use of Cluster Dynamics is acceptable or not for that problem. Modelling these complex mechanisms in a self-consistent way remains a challenge and preserving the simplicity of classical CD seems impossible. Such a general scheme, based on the examination of higher solute concentration cases, will be reported later. Here the size of the KMC simulation box was 8 10 6 atomic sites which imposes a cut-off value of 1.25 10 -7 to cluster concentrations. For the two first sets of distributions this cut-off value is not a major drawback but the comparison becomes meaningless for the third case due to the finite size of the KMC box. Letters A, B and E refer to distributions shown in figures 2 and 3. NB: to simplify, the ratio is normalized by exp(-2T w /T) so that the first value is equal to 4.2 whatever the temperature, a value which can be easily checked (see Lépinoux, 2005). The solute concentration, a few 10 -3 , was chosen high enough to trigger precipitation in a reasonable amount of computation time and small enough to select only one precipitate in the KMC simulation box (10 6 atomic sites) at T=873 K. The macroscopic shape is roughly cubic with {100} faces. Although at such low solute concentration the precipitate remains fairly compact, growth is not monotonic and important changes of shape due to the capture of nearby fluctuations of various size can be observed. (e) color chart for solute atoms as a function of the number of links with other solute atoms. Although the size of clusters increases, the largest ones are not necessarily the most stable ones (cf. figure 9 for the color chart).

Figure 11: Evolution of the fraction of atomic sites where a monomer cannot be located without bonding with another solute atom, as a function of (1-C 1 )/C 0 where C 1 is the concentration in monomers and C 0 the total solute concentration. For C 0 =1% the first stage is a plateau, while for C 0 =3% a bump appears before a fast decrease.

  situations of high dilution.

  to the deviation of P n+1,n 0 higher than that of P n,n+ 1 0

  Athènes et al. (2000), Bréchet and Martin (2006) and Mao et al. (2007), Soisson and Chu-Chun (2007)

Figure 1 :

 1 Figure captions

Figure 2 :

 2 Figure 2: Comparison of KMC cumulative cluster distributions (symbols) with those expected at equilibrium (plain lines) for cases 1 (a), 2 (b) and 3 (c). In (a) letters A to E refer to particular distribution shown also in figures 1 and 3.

Figure 3 :

 3 Figure 3: Comparison of two CD solutions with KMC simulations: -(a) and (b) AlZr 1% at T=873 K (case 1) -(c) AlZr 1% at T=723 K (case 2) -(d) AlZr 3% at T=873 K (case 3) The reported quantities are the precipitated fraction (plain symbols) and the number of precipitates (open symbols) multiplied by a convenient constant to fit the window. Results are reported vs. time (a) or vs. (1-C 1 )/C 0 (b, c and d) where C 1 is the concentration in monomers and C 0 the total solute concentration. The two CD solutions are: CD 1, with constant free surface energy, dashed line (magenta on line) CD 2, the complete solution, plain line (red online) Letters A to E in (b) refer to distributions shown in figure 2 (a) and figure 1.

Figure 4 :

 4 Figure 4: Typical behavior of the capture and release factors measured on KMC clusters for early (a) and late (b) stages of precipitation, compared with expected values at equilibrium (plain lines).The intersection of the two curves defines the instantaneous local critical cluster size n*. NB: to simplify, both factors are normalized by exp(-T w /T) so that P 2,1 =10, an integer whose value can be found in(Lépinoux, 2005).

Figure 5 :

 5 Figure5: Evolution of the release factor for various values of the instantaneous local critical cluster size, for case 1 (a), case 2 (b) and case 3 (c). Symbols are related to KMC clusters and lines to expected values at thermodynamic equilibrium. As in figure4, the release factor is normalized by exp(-T w /T).

Figure 6 :

 6 Figure 6: Evolution of the ratio of the capture and release factors for various values of the local critical cluster size, for case 1 (a), case 2 (b) and case 3 (c). Symbols are related to KMC clusters and lines to expected values at thermodynamic equilibrium.

Figure 7 :

 7 Figure 7: The dispersion of cluster properties, here the ratio P capture / P release (normalized as in figure 6) as a function of the cluster size. Average values are represented by diamond symbols and individual values by small dots. The plain line represents the expected values at thermodynamic equilibrium (n*=19).

Figure 8 :

 8 Figure 8: Comparison of the ratios (P capture /P release ) and (β/αC 1 ), both normalized by exp(-2T w /T) as in previous figures. For this alloy at T=873 K, T w =1.0721. The height of the horizontal line defining the supercritical and subcritical ranges is: 1/[C 1 exp(2T w /T)]. Under present conditions its numerical value is: 17.955.

Figure 9 :

 9 Figure9: Typical growth of an isolated precipitate from a nucleus containing about 100 solute atoms (a) up to its final size about 15000 solute atoms (d), in equilibrium with the solid solution. The solute concentration, a few 10 -3 , was chosen high enough to trigger precipitation in a reasonable amount of computation time and small enough to select only one precipitate in the KMC simulation box (10 6 atomic sites) at T=873 K. The macroscopic shape is roughly cubic with {100} faces. Although at such low solute concentration the precipitate remains fairly compact, growth is not monotonic and important changes of shape due to the capture of nearby fluctuations of various size can be observed. (e) color chart for solute atoms as a function of the number of links with other solute atoms.

Figure 10 :

 10 Figure 10: Typial shapes of clusters observed at solute concentration of 1% (a) to 5% (b), T=873 K. Clusters are increasingly composed of aggregates of smaller clusters loosely interconnected.Although the size of clusters increases, the largest ones are not necessarily the most stable ones (cf. figure9for the color chart).

Figure 1 :Figure 2 :Figure 3 :

 123 Figure 1: A typicalcomparison of cluster distributions obtained with KMC (symbols) and CD (lines).Here the size of the KMC simulation box was 8 106 atomic sites which imposes a cut-off value of 1.25 10-7 to cluster concentrations. For the two first sets of distributions this cut-off value is not a major drawback but the comparison becomes meaningless for the the third case due to the finite size of the KMC box. Letters A, B and E refer to distributions shown in figures 2 and 3.215x279mm (600 x 600 DPI)

Figure 4 :Figure 5 :Figure 6 :

 456 Figure 4: Typical behavior of the capture and release factors measured on KMC clusters for early (a) and late (b) stages of precipitation, compared with expected values at equilibrium (plain lines). The intersection of the two curves defines the instantaneous local critical cluster size n*. NB: to simplify, both factors are normalized by exp(-Tw/T) so that P2,1=10, an integer whose value can be found thanks to tables provided in Lepinoux (2005). 215x279mm (600 x 600 DPI)

Figure 7 :Figure 8 :Figure 9 :Figure 10 :Figure 11 :

 7891011 Figure 7: The dispersion of cluster properties, here the ratio Pcapture / Prelease (normalized as in figure 6) as a function of the cluster size. Average values are represented by diamond symbols and individual values by small dots. The plain line represents the expected values at thermodynamical equilibrium (n*=19). 215x279mm (600 x 600 DPI)

  construction it is related to coefficients α and β of CD, as discussed in several papers (see for instance Lépinoux (2009)), which assume that clusters change of size by capture or release of monomers. Thus, the change of behaviour of P capture /P release around the local critical size instead of the global one seems consistent too. This also suggests that if local and global critical sizes can be clearly dissociated, describing growth and decay of clusters only by exchange of monomers is no longer correct.

	o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

http://mc.manuscriptcentral.com/pm-pml Philosophical Magazine & Philosophical Magazine Letters

Acknowledgments

This work greatly benefited from the joint research program "CPR Precipitation" (Arcelor, Alcan-Pechiney, CNRS and CEA) and GDR "Transdiff". Various discussions with Drs. G. Martin, F. Soisson, A. Finel, P. Guyot and C. Sigli are gratefully acknowledged. The author is especially grateful to Dr. E. Clouet for helpful discussions and for providing his KMC results and code.