Didier Dubois
email: dubois@irit.fr

Henri Prade
email: prade@irit.fr

Steven Schockaert
email: schockaerts1@cardiff.ac.uk

Extending Answer Set Programming using Generalized Possibilistic Logic

Answer set programming (ASP) is a form of logic programming in which negation-as-failure is defined in a purely declarative way, based on the notion of a stable model. This short paper briefly explains how a recent generalization of possibilistic logic (GPL) can be used to characterize the semantics of answer set programming. This characterization has several advantages over existing characterizations of the stable model semantics. First, unlike reduct-based approaches, it does not rely on a syntactic procedure: we can directly characterize answer sets based on the minimally specific models of a GPL theory. Second, GPL enables us to study extensions of ASP in an intuitive way: unlike in existing generalizations of ASP such as equilibrium logic and autoepistemic logic, all formulas in GPL have a meaning which is intuitively clear. Finally, being based on possibilistic logic, GPL offers a natural way of dealing with uncertainty in answer set programs.

Introduction

An answer set program is a set of rules of the form:

a 1 ∨ ... ∨ a n ← b 1 ∧ ... ∧ b m ∧ not c 1 ∧ ... ∧ not c r (1)
where a 1 , ..., a n , b 1 , ..., b m , c 1 , ..., c r are propositional literals, i.e. either atomic propositions from a given finite set At or the negation of such atomic propositions. We call a 1 ∨...∨a n the head of the rule while b 1 ∧ ... ∧ b m ∧ not c 1 ∧ ... ∧ not c r is called the body. An extended literal is a literal or an expression of the form not c i (with c i a literal). Intuitively, [START_REF] Bauters | Semantics for possibilistic answer set programs: Uncertain rules versus rules with uncertain conclusions[END_REF] states that if we cannot derive that any of c 1 , ..., c r are true and we can derive that all of b 1 , ..., b m are true, then we should assume that one of a 1 , ..., a n must be true. Formally, the semantics of an answer set program is defined in terms of the Gelfond-Lifschitz reduct [START_REF] Gelfond | The stable model semantics for logic programming[END_REF]. In particular, given a set of literals M , the reduct P M of an answer set program P is defined as follows:

P M = a 1 ∨ ... ∨ a n ← b 1 ∧ ... ∧ b m | M ∩ {c 1 , ..., c r } = ∅, (a 1 ∨ ... ∨ a n ← b 1 ∧ ... ∧ b m ∧ not c 1 ∧ ... ∧ not c r ) ∈ P
We say that M is a model of P M if for each rule a 1 ∨ ... ∨ a n ← b 1 ∧ ... ∧ b m in P M such that {b 1 , ..., b m } ⊆ M it holds that M ∩ {a 1 , ..., a n } = ∅. We say that M is an answer set of P M if M is a model of P M and there does not exist a model M ′ of P M such that M ′ ⊂ M . Intuitively, the condition not c i is satisfied if c i cannot be derived from the program. However, what literals can be derived depends on which assumptions we make about what other literals can be derived, which introduces a circular dependency. When using the Gelfond-Lifschitz reduct, this dependency is broken by making a guess M about what literals can be derived, and then verifying that M indeed coincides with the set of literals that can be derived.

A large number of equivalent characterizations of answer sets have been proposed [START_REF] Lifschitz | Twelve definitions of a stable model[END_REF]. For example, autoepistemic logic (AEL [START_REF] Moore | Semantical considerations on nonmonotonic logic[END_REF]), the logic of minimal belief and negation as failure (MBNF [START_REF] Lifschitz | Minimal belief and negation as failure[END_REF]) and equilibrium logic (EL [START_REF] Pearce | Equilibrium logic[END_REF]) can be used to define answer sets in a model-theoretic way. Moreover, MBNF and EL can be used to define answer sets of arbitrary propositional combinations of extended literals (e.g. containing disjunctions of rules, negation as failure in the head of rules, etc.).

In this paper, we show how a recent generalization of possibilistic logic (GPL [5; 7; 8]) can be used to characterize answer sets. This characterization has several advantages over existing characterizations, in particular w.r.t. how it enables us to extend ASP. For example, GPL has the advantage over MBNF and EL that its models can be naturally interpreted as the epistemic state of an agent, which allows us to give an intuitive interpretation to answer set programs in which not c 1 means that "the agent does not know that c 1 is true". As a result, even when the syntax of ASP is extended to arbitrary propositional combinations of extended literals, the corresponding GPL formulas still have an intuitive meaning. In contrast, the intuitive meaning of EL formulas is not always clear. Moreover, since every propositional formula in GPL is encapsulated by a modal operator (see Section 2), we can distinguish between situations in which "the agent knows that either a or b holds" from "either the agent knows a or the agent knows b", whereas EL can only model the latter. The GPL characterization also ensures that all answer sets are minimal, i.e. that there cannot be two answer sets M 1 and M 2 such that M 1 ⊂ M 2 . While this is true for any characterization of ASP when only rules of the form (1) are consid-ered, existing characterizations do not guarantee minimality when negation-as-failure is allowed in the head of rules [START_REF] Inoue | Negation as failure in the head[END_REF]. Finally, as the semantics of GPL is based on possibility distributions, the proposed characterization can be naturally extended to give a semantics to answer set programs in which rules can have uncertain conclusions.

In the next section, we briefly recall the syntax and semantics of GPL. Section 3 then explains how answer sets can be characterized using GPL, and how GPL can be used to define extensions of ASP. Finally, in Section 4 we consider uncertain answer set programs, and show how GPL can be used to define the possibilistic answer sets of such programs.

Generalized possibilistic logic

Let Λ k = {0, 1 k , ..., 1} be the considered set of certainty degrees and let Λ + k = Λ k \ {0}. GPL formulas are then defined as follows:

• If λ ∈ Λ + k and α is a propositional formula, then N λ (α) is a GPL formula;
• if α and β are GPL formulas, then so are ¬α and α ∧ β.

As usual, we use α → β and α ∨ β as abbreviations for ¬(α ∧ ¬β) and ¬(¬α ∧ ¬β). Furthermore we write Π λ (α) as an abbreviation for ¬N n(λ) (¬α), where n

(λ) = 1 -λ + 1 k for λ ∈ Λ + k .
GPL is useful to reason about the knowledge of another agent. Intuitively N λ (α) means that the agent knows α with certainty λ, while Π λ (α) means that the agent considers α possible to the degree λ. An expression of the form N λ (α) or Π λ (α) will be called a meta-literal.

The semantics of GPL is defined in terms of possibility distributions. Let π be a normalized possibility distribution over the set of possible worlds Ω, i.e. π is a mapping from Ω to [0, 1] such that π(ω) = 1 for at least one ω in Ω. Then π is said to satisfy the GPL formula N λ (α), written π |= N λ (α), iff

N (α) = min{1 -π(ω) | ω ∈ Ω, ω |= ¬α} ≥ λ
where N denotes the necessity measure from possibility theory. The satisfaction relation |= is extended to arbitrary GPL formulas in the usual way, i.e. π |= α ∧ β iff π |= α and π |= β, while π |= ¬α iff π |= α. A possibility distribution π is called a model of a set of GPL formulas Θ if π satisfies every formula in Θ. An axiomatization of GPL has been presented in [START_REF] Dubois | Stable models in generalized possibilistic logic[END_REF].

Let π 1 and π 2 be two possibility distributions over Ω. We say that π 1 is less specific than π 2 , written

π 1 π 2 , if π 1 (ω) ≥ π 2 (ω) for all ω ∈ Ω. If π 1 π 2 and π 1 = π 2 , we write π 1 ≺ π 2 .
We say that π is a minimally specific model of a set of GPL formulas Θ if π is a model of Θ and there is no model π ′ of Θ such that π ′ ≺ π. Let α be a GPL formula and let Θ be a set of GPL formulas. The following three inference relations are considered in GPL:

standard entailment Θ |= α iff α is satisfied by every model of Θ.
cautious entailment Θ |= c α iff α is satisfied by all minimally specific models of Θ.

brave entailment Θ |= b α iff α is satisfied by at least one minimally specific model of Θ.

The problems of checking whether Θ |= α, Θ |= c α and Θ |= b α hold are respectively coNP-complete, Π P 2 -complete and Σ P 2 -complete [START_REF] Dubois | Reasoning about uncertainty and explicit ignorance in generalized possibilistic logic[END_REF]. GPL generalizes standard possibilistic logic [4; 6] in that the latter only allows sets of meta-literals of the form N λ (α), which are usually written as weighted propositional formulas of the form (α, λ). At the semantic level, a theory in possibilistic logic corresponds to a single possibility distribution, which is the unique minimally specific model of that theory, whereas theories in GPL can have several minimally specific models.

Characterizing and extending ASP using GPL

Given an answer set program P , we let Θ P be the GPL theory which contains for each rule of the form (1) in P the following formula:

N 1 (b 1 ) ∧ ... ∧ N 1 (b m ) ∧ Π 1 (¬c 1 ) ∧ ... ∧ Π 1 (¬c r ) → N 1 (a 1 ) ∨ ... ∨ N 1 (a n ) (2)
In other words, the body of a rule of the form ( 1) is satisfied if the agent knows each b i with maximal certainty and moreover the agent considers ¬c j fully possible for each j. Note that Π 1 (¬c j ) is equivalent to ¬N 1 k (c j ). The transformation in (2) is by itself not enough, as ASP is based on the idea of forward chaining and in particular does not allow contrapositive reasoning (e.g. from the rule a ← b and the fact ¬a we should not derive ¬b). To see how forward chaining could be enforced using GPL, first note that there are three ways in which the formula (2) can be satisfied by a minimally specific model π of Θ P :

1. one of the meta-literals N 1 (b i ) is not satisfied by π;

2. one of the meta-literals Π 1 (c i ) is not satisfied by π, i.e. N 1 k (c i ) is satisfied by π; 3. one of the meta-literals N 1 (a i ) is satisfied by π.

The first case intuitively corresponds to an answer set which does not include b i , i.e. to a situation in which the rule (1) does not apply. The third case intuitively corresponds to an answer set in which a i has been included to make the rule (1) satisfied, i.e. to a situation in which a i has been derived using (non-deterministic) forward chaining. The second case, however, intuitively corresponds to a contrapositive inference, i.e.

(1) has been satisfied by making c i true. The latter inference is not allowed in ASP and the second case should thus be excluded. To this end, we take advantage of the fact that it is only in the second case that certainty degrees other than 0 or 1 are needed. Note that here we do not use degrees for modelling uncertainty, but intuitively for differentiating between literals that are assumed to be true and literals that can effectively be derived. In particular, it turns out that answer sets correspond to the minimally specific models of Θ P in which only the certainty degrees 0 and 1 occur. Formally, the requirement that only these certainty degrees occur is encoded by the GPL formula Φ, defined as follows:

Φ ≡ a∈At N 1 (a) ∨ N 1 (¬a) ∨ (Π 1 (a) ∧ Π 1 (¬a)) (3)
The formula Φ expresses that for every atom a, the agent is either fully certain about the truth value of a (in which case N 1 (a) ∨ N 1 (¬a) holds) or the agent is completely ignorant about a (in which case Π 1 (a) ∧ Π 1 (¬a) holds). It turns out that the answer sets of P correspond to the minimally specific models of Θ P that satisfy Φ. In particular, assuming that k ≥ 2 (i.e. |Λ k | ≥ 3), it holds that P has a consistent answer set iff

Θ P |= b Φ
Moreover, for each consistent answer set M of P , it holds that the following possibility distribution π M is a minimally specific model of Θ P which satisfies Φ:

π M (ω) = 1 if ω satisfies every literal in M 0 otherwise
Conversely, for every minimally specific model π of Θ P which satisfies Φ, it holds that the following set of literals M π is an answer set of P :

M π = {l | N (l) = 1}
where N is the necessity measure induced by π. Note that it follows that a literal l is included in at least one answer set of

P iff Θ P |= b Φ ∧ N 1 (l)
and that that l is included in all answer sets of P iff

Θ P |= c Φ → N 1 (l)
This means in particular that the main reasoning tasks from ASP correspond to the standard forms of GPL inference.

This characterization of answer sets in GPL can be straightforwardly generalized to arbitrary propositional combinations of extended literals. When negation-as-failure in the head is considered, however, our characterization deviates from the existing characterizations in terms of EL and MBNF. This is illustrated in the next example. Example 1. We consider a single atom a, in which case Ω = {∅, {a}}, where we identify models with the set of atoms they make true. Consider the formula a∨not a, and the corresponding GPL encoding N 1 (a) ∨ Π 1 (¬a). Clearly, the latter formula has a unique minimally specific model π, defined by π(∅) = π({a}) = 1. In other words, the only answer set we find for a ∨ not a is the empty set. However, both the characterization of ASP in MBNF [START_REF] Lifschitz | Minimal belief and negation as failure[END_REF] and the characterization in EL [START_REF] Pearce | Equilibrium logic[END_REF] find two answer sets for this example, viz. M 1 = ∅ and M 2 = {a}.

As the intuition behind the stable model semantics is based on the idea of minimal commitment, the GPL semantics appears more natural.

The use of the modal operators N λ in GPL allows us to further extend ASP. In the standard semantics of ASP, rules with disjunctions in the head intuitively correspond to a nondeterministic choice, e.g. a ∨ b ← c means that when the agent knows c then either it knows a or it knows b. When modelling epistemic reasoning, however, it often seems more natural to interpret a ∨ b as "the agent knows that either a or b is true (but may not know which is the case)". This latter reading was referred to as weak disjunction in [START_REF] Bauters | Characterizing and extending answer set semantics using possibility theory[END_REF], where the inference problems resulting from interpreting ASP rules in this way have been investigated. Using GPL, the ASP rule a∨b ← c can be modelled as N 1 (c) → N 1 (a∨b) when weak disjunction is considered, and as

N 1 (c) → N 1 (a) ∨ N 1 (b) otherwise.
Finally, the use of possibilistic logic enables us to consider uncertain answer set programs. This is discussed in more detail in the next section.

Modelling uncertain answer set programs

An uncertain ASP rule is an expression of the form

λ : a 1 ∨ ... ∨ a n ← b 1 ∧ ... ∧ b m ∧ not c 1 ∧ ... ∧ not c r (4)
where λ is a certainty degree from Λ +

k . An uncertain answer set program is a set of uncertain ASP rules. As has been observed in [START_REF] Bauters | Semantics for possibilistic answer set programs: Uncertain rules versus rules with uncertain conclusions[END_REF], there are two fundamentally different ways to interpret uncertain ASP rules. On the one hand, we may view λ as reflecting the certainty that the corresponding ASP rule is valid. This interpretation leads us to view an uncertain ASP program as a possibility distribution over classical ASP programs; at the semantic level, we can then consider a possibility distribution over classical answer sets. On the other hand, we may view λ as reflecting the certainty with which we can derive the head of the rule, given that its body is satisfied. This view leads to a semantics in which answer sets correspond to weighted epistemic states, which are modelled as possibility distributions. Note that a similar distinction is often made in first-order probabilistic logics [START_REF] Halpern | An analysis of first-order logics of probability[END_REF] and in firstorder conditional logics [START_REF] Friedman | First-order conditional logic for default reasoning revisited[END_REF]. The former interpretation of uncertain ASP programs has been considered in [START_REF] Bauters | Semantics for possibilistic answer set programs: Uncertain rules versus rules with uncertain conclusions[END_REF] and [START_REF] Hu | Towards a new semantics for possibilistic answer sets[END_REF]. The latter interpretation has been considered, among others, in [START_REF] Nicolas | Possibilistic uncertainty handling for answer set programming[END_REF], [START_REF] Bauters | Characterizing and extending answer set semantics using possibility theory[END_REF] and [START_REF] Confalonieri | Dealing with explicit preferences and uncertainty in answer set programming[END_REF].

Modelling the former type of uncertain ASP programs in GPL would require nested modalities, encapsulating formulas of the form (2) with a modality of the form N λ . As nested modalities are not allowed in GPL, this would require us to define a variant of GPL in which every (standard) GPL formula would be encapsulated by a modality, similar to how propositional formulas are encapsulated in standard GPL. At the semantic level, models would then correspond to possibility distributions over possibility distributions over possible worlds.

Here we focus on modelling the second type of uncertain ASP programs in GPL. Let us first consider rules without negation-as-failure:

l k : a 1 ∨ ... ∨ a n ← b 1 ∧ ... ∧ b m
The corresponding GPL formula is given by

l i=1 N i k (b 1 ) ∧ ... ∧ N i k (b m ) → N i k (a 1 ) ∨ ... ∨ N i k (a n )
Let P be an uncertain ASP program without negation-asfailure and let Θ P be the set of corresponding GPL formulas. It is not hard to see that a possibility distribution π is a possibilistic answer set of P in the sense of [START_REF] Bauters | Characterizing and extending answer set semantics using possibility theory[END_REF] iff π is a minimally specific model of Θ P . In absence of negation-asfailure, the semantics from [START_REF] Bauters | Semantics for possibilistic answer set programs: Uncertain rules versus rules with uncertain conclusions[END_REF] moreover coincides with the semantics from [START_REF] Nicolas | Possibilistic uncertainty handling for answer set programming[END_REF].

To deal with negation-as-failure, [START_REF] Bauters | Characterizing and extending answer set semantics using possibility theory[END_REF] and [START_REF] Nicolas | Possibilistic uncertainty handling for answer set programming[END_REF] rely on a generalization of the Gelfond-Lifschitz reduct. Consider a rule of the following form:

l k : a 1 ∨ ... ∨ a n ← b 1 ∧ ... ∧ b m ∧ not c 1 ∧ ... ∧ not c r
The reduct of this rule w.r.t. a possibility distribution π, according to the semantics from [START_REF] Bauters | Characterizing and extending answer set semantics using possibility theory[END_REF], is given by:

λ : a 1 ∨ ... ∨ a n ← b 1 ∧ ... ∧ b m (5)
where λ = min( l k , Π(¬c 1 ), ..., Π(¬c r )), for Π the possibility measure induced by π. The reduct considered in [START_REF] Nicolas | Possibilistic uncertainty handling for answer set programming[END_REF] boils down to choosing λ = l k if Π(¬c 1 ) = ...Π(¬c r ) = 1 and λ = 0 otherwise (where rules whose certainty is 0 are simply omitted).

Using GPL, we can avoid the use of a reduct, if we assume that k is even and only certainty degrees from { 2 k , 4 k , ..., 1} are used in the uncertain ASP program P . We can always ensure that this assumption is satisfied by replacing the set of certainty degrees Λ k by the set Λ 2k , since every element from Λ k is equal to l 2k for some even value of l. The GPL theory Θ P corresponding to P is then obtained by replacing every rule of the form (4) by the following formula:

l i=1 N i k (b 1 ) ∧ ... ∧ N i k (b m ) ∧ Π i k (¬c 1 ) ∧ ... ∧ Π i k (¬c r ) → N i k (a 1 ) ∨ ... ∨ N i k (a n ) (6)
where we assume λ = l k . We again need to exclude models which intuitively rely on contrapositive reasoning. Similar as in Section 3, these correspond to minimally specific models π which make (6) satisfied by making one of the meta-literals Π i k (¬c 1 ) false, i.e. by making a meta-literal N k-i+1 k ( c 1 ) true. Noting that ki + 1 is odd iff i is even, we find that it suffices to exclude models in which certainty degrees l k are used with l odd. Such models can be avoided by considering the following GPL formula Φ k

Φ k ≡ a∈At k 2 i=1 N 2i-1 k (a) → N 2i k (a))
∧ (N 2i-1 k (¬a) → N 2i k (¬a) Note that Φ 2 is equivalent to the formula Φ defined in [START_REF] Confalonieri | Dealing with explicit preferences and uncertainty in answer set programming[END_REF]. We propose the following definition: φ is a possibilistic answer set of P iff π is a minimally specific model of Θ P which satisfies Φ k . As in Section 3, we can then formulate the main reasoning tasks for possibilistic ASP in terms of standard entailment in GPL. For example, checking whether the certainty of a is at least l k (with l even) in every possibilistic answer set of P corresponds to:

Θ P |= c Φ k → N l k (a)
We can show that the proposed definition of possibilistic answer set corresponds to the reduct-based definition from [START_REF] Bauters | Characterizing and extending answer set semantics using possibility theory[END_REF].

Conclusions

We have shown how generalized possibilistic logic (GPL) can be used to characterize answer sets without the need for a reduct operation, and how this characterization allows us to consider a range of different extensions of ASP in a natural way. In particular, the GPL characterization enables us to define answer sets for arbitrary propositional combinations of extended literals (while keeping the intuition of minimal commitment), for modelling weak disjunction, and for defining answer sets of uncertain programs.

Acknowledgment

Steven Schockaert has been supported by a grant from the Leverhulme Trust (RPG-2014-164).


F Mompiou
email: mompiou@cemes.fr

M. a , Ensslen C Legros
email: legros@cemes.fr

O Kraft

In situ TEM study of twin boundary migration in sub-micron Be fibers

Keywords: in situ TEM, twinning, fibers, dislocations, plasticity

Deformation twinning in hexagonal crystals is often considered as a way to palliate the lack of independent slip systems. This mechanism might be either exacerbated or shut down in small-scale crystals whose mechanical behavior can significantly deviate from bulk materials. Here, we show that sub-micron beryllium fibers initially free of dislocation and tensile tested in-situ in a transmission electron microscope (TEM) deform by a {10 12} 10 11 twin thickening. The propagation speed of the twin boundary seems to be entirely controlled by the nucleation of twinning dislocations directly from the surface. The shear produced is in agreement with the repeated lateral motion of twinning dislocations. We demonstrate that the activation volume (V) associated with the twin boundary propagation can be retrieved from the measure of the twin boundary speed as the stress decreases as in a classical relaxation mechanical test. The value of V ≈ 8.3 ± 3.3 × 10 -29 m 3 is comparable to the value expected from surface nucleation.

Introduction

Hexagonal close packed (hcp) metals are known for their particular mechanical properties such their high strength to weight ratio. In such anisotropic metals, the mechanical response strongly depends on the solicitation and texture. For instance, Hall-Petch effects appear to be dependent on the orientation and Peierls friction stress on the different slip systems [1]. Deformation twinning is often easier than the activation of non basal dislocation slip, which explains its importance in the deformation of many hexagonal metals [2] as it may be a way to enhance the ductility [3].

However, twinning also induces a strong strain hardening as twins act as barrier to dislocation motion and to further twin propagation [4,5]. In the recent years, the possibility of a fine tuning of the mechanical properties by incorporating twins in the microstructure, such as nanotwinned copper [6] or twinning induced plasticity (TWIP) steels [7], have been extensively used. In finely twinned copper for instance, the decrease of the twin separation distance down to few nanometers have led to a large increase of the strength while maintaining some ductility. However, a clear picture of the impact of twinning on the mechanical properties of metals is still lacking, especially at small scales [8,9], mainly because several competing mechanisms can be at play: twin nucleation, propagation and thickening, interaction between twins or with dislocations [10], de-twinning [11] etc. The kinetics of plastic deformation can be investigated by measuring the sensitivity of the stress to the strain rate and to the temperature to determine the activation parameters of rate controlling mechanisms. The activation volume V which is inversely proportional to the strain rate sensitivity is a measure of the volume of matter involved in the thermally activated process [12]. Such parameters (with the activation energy) are often used to discriminate between these various mechanisms but are often complex to obtain, especially during an in situ TEM experiment. In nanotwinned copper, it has been postulated from the low value of the activation volume (few b 3 , compared to value of several hundreds of b 3 for typical mechanisms in coarse grained) that twin transmission is the rate controlling deformation mechanism [13]. Moreover, because lattice dislocations can easily dissociate and eventually glide inside a coher-ent twin [10], contrary to grain boundaries where they usually decompose [14,15], ductility is enhanced compared to conventional nanocrystalline (nc) metals.

Beryllium deforms by dislocation slip on the basal and prismatic planes [16,17], but prismatic glide exhibits a strong anomalous increase of the yield stress with temperature close to the room temperature, which can be ascribed to strong friction stresses [18,19]. Twinning through gliding dislocations mechanisms have been proposed early in hcp metals [20][21][22][23]. For the {10 12} 10 11 twin, which is the activated system in Be, it involves dislocations of Burgers vector ≈ 0.12[10 11] associated with a step which height is 2 times the {10 12} interplanar spacing (zonal twinning dislocation) [2]. In a general context of interfacial defects, such dislocations with a step character have been coined disconnection by Hirth and Pond [24]. If twinning dislocations are well known, their propagation and especially their nucleation mechanism still remains partly understood. Both homogeneous or heterogeneous nucleation and propagation can be considered [2]. The first case is thought to arise when a combination of very high stress and very low surface and strain energy is satisfied. Although unlikely in conventional bulk crystals, this process may happen in dislocation free whiskers as suggested by early observations of Price in Zn [25], recent ones by Roos in Au [26] or in small Mg pillars [27]. Twin thickening by the spontaneous nucleation of twinning dislocations has also been envisaged to account for the observation of growing twins in Cu-Ge alloys without evidence of source operation or dislocation emission from grain boundaries [28]. Such high stress concentrations can also be found near crack tip where twin nucleation can be observed [29] or from grain boundaries and triple junctions [30], especially in nanograins where partial dislocation nucleation is thought to be less energetically costly than perfect dislocations [31,32]. From a theoretical point of view, it is now well established that dislocation nucleation from free surfaces can be facilitated by surface imperfections [33,34]. In the case of twinning dislocations, it has been suggested that the nucleation of a second twinning dislocation in an adjacent plane can be stimulated by the presence of the stacking fault of the first one [27,35]. Recent molecular dynamics simulations in Mg also indicate that twin thickened from the formation of twinning dislocations presumably from the surface [36].

Heterogeneous nucleation through the operation of a twinning dislocation source composed of a sessile dislocation intersecting the twin boundary, i.e. the pole mechanism has been proposed early in hcp metals [21]. More recently, Serra and Bacon have found that the de-composition of a lattice dislocation into a {10 12} twin creates a sessile disconnection that eventually acts as a source [37] which follows the twin boundary as it migrates. Recent mechanical modeling tends to indicate however that such decomposition of lattice dislocation into twinning dislocations (so-called slip-assisted twinning) is insufficient to account for the mechanical properties of hcp metals and so that direct twinning nucleation should also operate [38]. Thus, the twin thickening under a shear stress parallel to the twin boundary occurs by the repeated motion of twinning dislocations. A similar situation has also been found for grain boundaries, where the migration coupled to stress is due to the motion of disconnections [39][40][41]. This phenomenon which has been observed either in bicrystals [42,43] and polycrystals [44][45][46] plays an important role in the mechanical properties of nc metals by promoting grain growth.

In this paper, we report the observation of a single {10 12} 10 11 twin boundary migration in a submicron beryllium fiber deformed in tension in-situ in a transmission electron microscope (TEM). After presenting the microstructure and the experimental set-up, we show that the twin boundary did not propagate by the operation of a pole mechanism, but more presumably by the nucleation from the free surface. By measuring the twin boundary speed as the stress relaxed, we were able to retrieve the activation volume associated with this individual mechanism. We then discuss both the nucleation and motion of twin dislocation mechanisms to interpret the obtained value.

Experimental

Freestanding beryllium fibers where obtained from a directionally Al-2.4 at.%Be eutectic alloy with the same approach described in [47]. 3 by 1mm samples were first cut in a bulk ingot by an electrodischarging machine with the long direction parallel to the fiber length. They were then mechanically polished and etched by the Struers A2 electrolytic solution at -10 • C. This leads to the fast etching of the aluminium matrix which freed the Be fibers in a circular etched region as shown in figure 1a. In consequence, the fibers are freestanding in the middle of a TEM hole. Around the hole, the rest of the specimen is composed of the eutectic alloy. The figure 1 shows the geometry of the TEM hole with the fibers. The complete hole (figure 1a) is 450 µm large and no electron transparent zones can be observed on its borders meaning the eutectic alloy has been etched only in its center. The hole itself is composed of several tens of fibers of approximately the same diameter. Most of the fibers have only one end attached to the rest of the matrix. The area where we concentrate our investigation is located on the right side of the hole close to the edge and contains few fibers attached at both ends (figure 1). A GATAN straining holder was used at room temperature to deform the whole specimen containing the fibers. During this mechanical test, the displacement is imposed via a long steel rod to the sample fixed on a copper grid (see figure 1d). The copper grid is attached to the jaws by screws. The TEM sample itself is glued on the copper grid. In-situ observations were performed on a JEOL2010 operated at 200kV. Video sequences were recorded on a DVD by a MEGAVIEW III camera at 25fps. Tensile tests of individual fibers were performed in a Nova 200 scanning electron microscope/focused ion beam (SEM/FIB) equipped with a piezo-actuated platform and Femtotools load cells. Strain is calculated using a Matlab routine [48]. For more details about individual wire testing, one can refer to [49][50][51]. fibers by SEM show that the fibers have a circular cross section. The diameter of the fibers is almost constant over the whole fiber length. The majority of the fibers have a diameter of approximately 400 nm but fibers with diameter around 250 nm were also observed. The fibers are usually straight and no dislocations can be observed. Fibers which are detached at one end can be bent, and a high dislocation density can be observed in the bent area. This indicates that plastic deformation until fracture has occurred prior the experiments in a very limited area, similarly as observed in aluminium fibers [47]. More details on plastic deformation by dislocation slip will be given in a forthcoming article. Few {10 12} twin boundaries can also be observed. They are indicated in figure 1c by the label tw1 and tw2. Another twin can be observed in the area 2 where fibers are already broken (figure 1b). Lots of fibers stack together forming a large loose tangle in figure 1b. Figure 2 shows a closer view of the twin boundary tw1. Electron diffraction analysis has shown that most of the fibers have their c axis parallel to the fiber length while the twinned area present a c axis almost perpendicular (figure 2a), so that the (01 12) twin plane is making an angle of about 54 • with the straining axis T (figure 2b). In such configuration, the Schmid factor, s f = cos( n, T ) cos( s, T ) ≈ 0.47, with n the normal to (01 12) and b is the shear direction, i.e. parallel to [01 11 ], is close to the maximum value. Such configuration then favours the growth of the twin in tension.

Results

Most

Twin boundary migration

Twin boundary migration under stress has been observed after strain increment until the stress relaxed up to a critical value where the twin boundary remained immobile. After several increments, the twin boundary tw1 seen at its initial position (i) in a 400 nm large fiber (figure 1c) has moved to its final position (f), which represents a distance of about 8.5 µm, before being stopped definitely. A second twin boundary tw2 located on an adjacent fiber (diameter around 400 nm) in the lower part of area 1 (figure 1) started then to move. The motion of this twin boundary has been followed over 5 µm. Figure 3 shows bright field images, taken under the diffraction vector g = (10 11) t (the subscript t refers to the twinned area), extracted from a video sequence. They show the motion of the twin boundary tw1 over a short distance after a strain increment. The motion of the twin boundary can be easily followed by remarking fixed points located at the fiber surface and noted X 1 and X 2 (for the corresponding video see the supplementary materials). The twin boundary motion appears to be smooth with an average migration speed around 10 nm/s. Figure 3e is the image difference between figure 3d and figure 3c when the marker X 2 is set as a reference (see the uniform grey contrast of X 2 ). It can then be clearly seen that the twin boundary migration has produced a displacement of the lower part of the fiber of a distance d . This displacement linearly increases as the twin boundary migrates, as evidenced by the angle γ formed by the fiber sides on both sides of the twin boundary (figure 3e). As a consequence, the fiber is deformed by a shear strain also called coupling factor (β) for grain boundaries by Cahn et al. [52].

Since the twin plane is inclined only 6 • from the electron beam direction in figure 3, the shear strain can be directly obtained by measuring the inclination of the twin plane with respect to the fiber direction (angle i) and the angle γ:

β = d d ⊥ = sin γ sin i sin(i -γ) (1)
Taking i = 42 ± 1 • and γ = 5.4 ± 0.4 • leads to β = 0.237 ± 0.03. This value is very close to the value expected as explained below. The figure 4 shows the [1 210] projection of the dichromatic pattern of the twin. Black symbols correspond to the matrix (m) and white ones to the twinned crystal (t) while opened and close symbols indicate the lattice positions in two adjacent parallel planes along the [1 210] direction. In this configuration, the twin boundary (10 12) is edge on. The twin boundary migration is supposed to operate by the motion of b twin = b 2/2 disconnection [20,22,53]. The notation b p/q indicates that the disconnection has a step which height h in the white and black lattice is p and q in units of (10 12) lattice planes spacing [54]. Following the notation of Frank and Pond their Burgers vector is [55,56]:

b twin = 1 λ 2 + 2                   2 + λ 2 0 -2 -λ 2 λ(λ 2 -2)                   (2) with λ = 2

Dislocation nucleation

A closer inspection of the twin boundary at higher magnification, under g = (10 11) t , shows the presence of equally distributed dislocations with a spacing of 12 nm (figure 5). These dislocations are supposed to be secondary intrinsic dislocations that accommodate a slight misorientation from the 84.78 • perfect twin misorientation [57]. Indeed, the observed twin boundary presents a misorientation ≈ 85.2 • around [ 2110], so that the extra misorientation can be accommodated by a single set of edge dislocations as observed. During migration, these dislocations follow the twin boundary without moving laterally. However, blurred and rapidly oscillating contrasts (see the video in the supplementary materials) can be clearly identified close to the fiber surface (indicated in figure 5 by arrows). The apparition of a strong contrast (fig. 5b) and its spreading (fig. 5c) along the twin boundary plane can be followed during few seconds. Although difficult to interpret, it is associated with the motion of the twin boundary and appear only under stress, which is a strong indication of the nucleation of dislocation in an area close to the fiber surface. Figure 5d is the image difference c)-a). It shows that within the time interval where this strong contrast was observed, the twin boundary has progressed over a distance d ⊥ which can be determined by measuring the migration distance of the secondary dislocations. The value of d ⊥ ≈ 5.2 ± 0.8 nm approximately corresponds to the passage of 20 twinning dislocations, i.e. 20 times the step height h = 2d {10 12} = 0.265 nm. The nucleation rate is ṅ ≈ 5 dislocations per second, a value of the order of the dislocation production rate by spiral sources in Al fibers deformed homogeneously at low stress and strain rate (˙ ≈ 3 × 10 -6 s -1 , τ ≈ 100 -200 MPa) [47].

Twin nucleation

Although the first twin nucleation event has not been directly observed during in-situ experiments, figure 6 shows evidence of early twin formation and thickening. Figure 6a shows a twin lamella (tw) located somewhere along a fiber. From both sides of the twin boundaries, indicated by arrows, no dislocations or clear defects can be identified. Interestingly, a high dislocation density is visible in the twinned area, as expected from the orientation change. Indeed, whereas Schmid factors of prismatic slip systems has extremely low values in the matrix oriented along the c axis, they reached almost their maximum in the twinned area. The plastic zone is thus mainly confined in the twinned area. This observation tends to indicate that the twin has nucleated in the fiber oriented along its c axis, presumably from the surface, and eventually thickened through the entire fiber. This is reminiscent from the observation and MD simulation of long twin formation in gold nanowhiskers by the coalescence of individual twins nucleated from the surface [58]. Eventually plastic deformation due to prismatic slip has occurred.

Figure 6b shows a twin (tw) near a fractured fiber. Contrary to the case shown in figure 6a, the fiber is more heavily deformed, with twin boundaries distorted and numerous dislocations in the matrix. This situation probably results a deformation at higher strain rate during which only a thin twinned area underwent ductile fracture rapidly. In the absence of prismatic slip, as observed in figure 3, the value of ˙ p ≈ 5 × 10 -6 s -1 , extracted from the twin boundary speed gives an order of magnitude of the strain rate for homogeneous deformation.

Stress relaxation

As twin boundary migration seems to operate by nucleation from the surface and propagation of twinning dislocations, we propose in this section a method to measure the corresponding activation volume.

Activation volume measurement

Macroscopically, the activation volume can be measured during a relaxation stress by plotting the variation of the strain rate logarithm versus the stress logarithm according to [12,59]: If we consider that the dislocation density remain constant, the variation of the strain rate is equal to the variation of the dislocation speed. During in-situ experiment, the variation of the dislocation speed with the local stress, measured through the dislocation curvature, can be tentatively extracted leading to the determination of the activation volume. In the present case, it is not possible to measure locally the stress but a clear decrease of the twin boundary speed during the relaxation is recorded. In the following, we discuss the possibility of extracting the activation volume from the measure of the twin boundary speed during the relaxation.

V = kT ∂ ln ˙ p ∂σ T (3)

Fundamental of stress relaxation

From the above observations it can be supposed that a few fibers located in the right border of the hole and which are not in the tangles are able to deform plastically. A careful examination of the machine stiffness given in Annex Appendix A indicates that the testing machine, composed of the copper grid, the glue, the straining rod and the thicker parts of the eutectic alloy, can be considered as almost infinitely hard compared to the specimen composed of fibers of total length l 0 ≈ 230 ± 30 µm. Under these conditions, the relation between the engineering strain, ˙ , engineering plastic strain, ˙ p and the observed true stress rate, σ is given in a good approximation 1 by:

˙ ≈ ˙ p + σ E (4)
For a relaxation test, the imposed displacement is null, i.e. ˙ = 0 and then,

˙ p ≈ - σ E (5)
In the following we will assume that the relaxation curve i. e. σ vs. t, exhibits a logarithmic decay of the stress with time. This has been proven to be true for a wide range of materials [12]:

∆σ = - kT V ln 1 + t -t i t 0 ( 6
)
with V is the apparent activation volume and t 0 a time constant and t i the starting time of the relaxation. Combining equations 5 and 6 leads to:

˙ p ≈ kT EV 1 t + t 0 -t i (7)
1 we consider that the plastic strain of the specimen is small and then the true plastic strain is equal to engineering plastic strain

p = ∆l l 0 = d sin α l 0 = βd ⊥ sin α l 0 (8)
From equation 8, the plastic strain rate is given by:

˙ p = βd ⊥ sin α l 0 ∆t = β sin α l 0 v (9)
The relation between the twin boundary speed and time can thus be derived combining equations 7 and 9:

v = kT EV l 0 β sin α 1 t + t 0 -t i (10)
Then the activation volume can be derived by measuring the variation of the twin boundary speed with time.

Stress relaxation experiment in a TEM

During the stress relaxation, we have observed the motion of a twin boundary along the fiber, the speed of the twin boundary decreasing over the time. The speed was measured using a custom Python script tracking the boundary trajectory [60]. Figure 8 shows the plot of the twin boundary speed vs. time. At t ≈ 0 s a displacement was imposed until the twin boundary moves. After the twin boundary starts to migrate (t i ≈ 6 s) the displacement was stopped. The twin boundary continues to migrate with a speed decreasing which can be fitted by the equation:

v = a 1 t + t 0 -t i (11)
The two lines in figure 8 are possible data fit when selecting different time intervals, from t i to 40 s in for the full line and from t i to 15 s for the dashed line (early stage of the relaxation). In the overall, the fitting parameters are t 0 = 10 ± 6 s, a 1 =250 ± 60 nm. Combining equations 11 and 9 gives an estimate of the activation volume:

V = kT l 0 Ea 1 β sin α (12) Taking T = 300 K (kT = 4 × 10 -21 J), β = 0.2, E = 287 GPa, α = 53 • , l 0 ≈ 230 ± 30 µm leads to V ≈ 8.3 ± 3.3 × 10 -29 m 3 , which represents V ≈ 574±226b 3 .
This value is few times larger than the ones found for nanotwinned copper V nano-twin = 12 -20b 3 [13] and nanocrystalline aluminium [61] V ncAl = 10 -55b 3 , where plastic deformation involves mainly twin or grain boundaries.

Activation energy evaluation

Although the activation energy G cannot be measured directly here, an estimation can be made. Considering that the nucleation of twinning dislocations is thermally activated, the nucleation time t at the temperature T is given by: 1

t = A exp - G kT ( 13
)
where A is a constant related to the nucleation attempt frequency and to the entropy [62]. Considering that 1 × 10 11 s -1 < A ≈ ν < 5 × 10 11 s -1 (cf. Appendix B), and that 1/t = v/h yields at T = 300 K 0.56 eV< G <0.72 eV, i.e. around 25 kT.

Discussion

The activation volume estimated above can be tentatively explained by considering the different mechanisms involved in the twin nucleation and propagation. The activation volume is related to the variation of the free energy G associated with the process.

V = - ∂G ∂σ (14)

Twinning dislocation nucleation

The nucleation of a dislocation embryo from either a flat [63] or stepped surface [62][63][64], or from a corner [65,66] have been extensively studied by atomistic simulations and elastic calculations [62]. All these studies conclude that the activation energy takes the form:

G(T, σ) = G 0 (1 -T/T m ) (1 -σ/σ ath ) α (15)
where G 0 is a constant, T m is the surface disordering temperature [66] taken as half the melting temperature, σ ath the athermal stress and α a constant. The variation of the activation energy, normalized by µb 3 , and the activation volume, normalized by b 3 , as a function of stress have been redrawn from these studies as dotted lines in figure 9a and b, respectively. Although the stress was not retrieved in the present study, the yield stress of the fiber shown in figure 6b has been estimated by micromechanical testing to σ ≈ 1.7 ± 0.25 GPa (see the stressstrain curve in fig. 6c) for a strain rate of ˙ ≈ 7 × 10 -3 s -1 . It can be shown in Appendix B that for surface nucleation σ(˙ p = 5 × 10 -6 ) ≈ σ(˙ p = 7 × 10 -3 ) at T = 300 K. The value of activation energy and volume measured in the present study is reported in figure 9. Despite the scatter in the activation energy and volume from the atomistic studies due to the importance of the geometrical factor in the nucleation process [64], the experimental values 5×10 -29 m 3 (348b 3 )< V < 1.2×10 -28 m 3 (800b 3 ), although slightly higher compared to the values obtained by most of the atomistic simulations, are still comparable for instance with the work of [64]. It is interesting to note here that if the migration of the twin boundary is due to surface nucleation, it should not be influenced by the presence of specific nucleation site, such as a step, because of the continuous and regular migration of the twin boundary.

6.2. Atomic shuffling during twinning dislocation motion While moving laterally, atoms below the disconnection step have to be shuffled. This mechanism is supposed to be thermally activated so that the activation area associated corresponds to the area where atoms have to be rearranged (in red in figure 4). This area is A r = h × d t where h = 2d (10 12) = 0.265 nm is the step height. The activation volume is then given by V shu f f ling = A r × b twin = 7.5 × 10 -30 m 3 which is significantly smaller than the volume measured.

Twinning dislocation interaction with solute atoms

Because the fiber may not be pure, solute atoms can act as pinning points on the twinning dislocation. In that case, the activation volume is given by [12]:

V solute = b 3 /c solute (16)
where c solute is the atomic concentration of solute atoms.

According to the Al-Be phase diagram [67], the concentration of Al solute atoms is expected to be much less than 60 ppm which leads to an activation volume V solute > 2 × 10 -26 m -3 much larger than expected. Although O atoms can also be present, their concentration is also presumably very low, ruling out the interaction of twinning dislocations with solute atoms as the controlling mechanism.

Friction stress acting on a twinning dislocation

In most hcp metals, dislocation motion is controlled by a friction force (Peierls-Nabarro stress) due to non planar dislocation core dissociation [12]. In beryllium, this friction stress leads to the locking and unlocking of screw dislocations in the prismatic plane. The stress anomaly in the range 80 -450 K has been explained by this phenomenon [19]. Although, this topic is poorly documented, twinning dislocation can also be sensible to a friction stress along the twin plane. Serra et al. have indeed shown that the size of twinning dislocation core in hcp metals greatly influences their mobility [68]. Similar conclusions have been drawn for rhombohedral twinning in sapphire where measured activation volume and enthalpy fit with a model of double kink pair nucleation along the twinning dislocation [69]. Serra et al. [68] have shown however that for {10 12} twin, twinning dislocation can move at 0 K at a small strain of 0.002, which gives in our case, considering a Schmid factor of s f = 0.5, a friction stress σ = 0.002E/s f ≈ 0.5 GPa, smaller than the yield stress. This indicates that the motion of a twinning dislocation through the nucleation and propagation of kinks along its line [12,70] is athermal in our observation and thus associated with activation volume equal to zero.

Conclusions

Tensile in-situ TEM experiments were performed on sub-micron beryllium fibers containing a low initial dislocation content. They revealed the thickening of a twin domain that occurred through the migration of a {10 12} twin boundary under stress. The motion of this twin boundary appeared continuous and associated with rapidly oscillating contrasts near the surface. The absence of dislocation in the fiber interior discard a twinning mechanism operating through a dislocation source (pole mechanism). The shear strain associated have been measured and found in agreement with the value expected from the motion of zonal twinning dislocations. We have therefore attributed this rapid contrast oscillation to repeated dislocation nucleation. In parallel, we provide a method to retrieve the activation volume associated with the twin boundary migration by measuring the twin boundary speed decrease during the stress relaxation. We found an experimental value of 8.3 ± 3.3 × 10 -29 m 3 , which is comparable to the value expected from dislocation surface nucleation. These experiments thus provide the first combination of a dynamic observation of a single migrating twin boundary in a sub-micron Be wire and the quantitative measurements of activation parameters associated with this movement. We show that the migration depends exclusively on the surface nucleation of dislocation at the location of the boundary. Further experiments focusing on the measure of activation parameters as a function of stress through micromechanical testing of individual fibers may provide a complete picture of this mode of deformation that is probably peculiar to sub-micron size crystals. Along with the present results, they should provide an excellent bench test for dedicated atomistic simulations and gain direct insights into the controlling mechanism ruling the plastic deformation of micro-and nanometer scale crystals.

1 K glue = t glue G glue A glue (A.5)
With t glue the thickness of the glue film, G glue the shear modulus and A glue the surface sheared. Combining equations A.2, A.4 and A.5 leads to:

1 C = 1 E + A 0 l 0        i l i E i A i + t glue G glue A glue        (A.6)
In the present situation, equation A.6 is the combination of the stiffness of the tensile rod, of the copper grid, of the eutectic alloy, of the glue (see figure 1):

1 C = 1 E + A 0 l 0 l rod E rod A rod + l grid E grid A grid + l eutectic E eutectic A eutectic + t glue G glue A glue (A.7)
The fiber gage length measured from TEM observation is l 0 = 230 ± 30 µm. Assuming the fiber cross-section is a disk of diameter d f =400 nm, the cross section area A f ≈ πd 2 f /4. Considering that 4 fibers deform plastically, the specimen cross-section is A 0 ≈ 4A f ≈ πd 2 f . The straining rod is cylindrical with a cross sectional area A rod = πd 2 rod /4, with d rod = 3 mm. The rod length is about 30 cm. The Young's modulus of the rod is close to E rod ≈ 200GPa = 0.7E. The copper grid cross section area is A grid = t grid w grid with t grid = 70 µm the grid thickness and w grid = 2.3 mm the grid width. The grid length is about 8 mm. The Young's modulus of the grid is E grid = 117 GPa= 0.4E. The part of the eutectic which has not been etched is also subjected to deformation. The stress will concentrate in the middle of the hole rim and in area perpendicular to the straining axis as shown in [71]. The hole rim is however not thin as a typical TEM specimen, so that the strain should be localized in the fibers. The thickness of the eutectic part is about 50 µm, 1 mm large and about 3 mm long. The Young's modulus of the eutectic can be estimated using the rule of mixture E c = i V i E i with V i = W i /ρ i i W i /ρ i the volume fraction of the i th element of weight fraction W i , density ρ i and Young's modulus E i . Since there is approximately 1.5 wt.% Be in the eutectic, the effective modulus is E eutectic ≈ 0.98E Al + 0.02E Be ≈ 74GPa ≈ 0.26E. The thickness of the glue is estimated to t g ≈ 10 µm. The area covered by the glue is approximately 1 mm large (the sample width) by 0.5 mm. The shear modulus of the glue is of the of 1 GPa i.e. G g ≈ 0.005E. We finally obtain from eq. A.7:

1 C ≈ 1 E + 1.5 × 10 -4 E + 3.2 × 10 -4 E + 3.2 × 10 -4 E + 8 × 10 -6 E ≈ 1 E (A.8)
Then, equation A.1 can be replaced by equation 4.

Appendix B. Variation of the stress with strain rate for surface nucleation

The variation of the stress with the plastic strain rate can be estimated in the case of surface nucleation by combining Eq. 3, 14 and 15, and by integration with respect to the stress between σ and σ ath :

σ = σ ath        1 - kT E 0 (1 -T/T m ) ln Cν ˙ p 1/α        (B.1)
where ν is a characteristic nucleation frequency and C = n s cos(θ) a geometrical factor that relates the nucleation rate to the plastic strain rate (n s being the number of dislocation surface sources per fiber unit length and θ the angle between the glide plane and the fiber surface).

Taking the values given in [64] for Al, i.e. T = 300 K, T m = 800 K, E 0 = 499.6 eV, ν = 10 11 s -1 , α = 7.02, and C = 0.011 leads to σ(7 10 -3 )/σ(5 10 -6 ) = 1.03. For Cu and according to [66], taking T = 300 K, T m = 692 K, E 0 = 4.8 eV, ν = 5.02 10 13 s -1 , α = 4.1 and C = 0.012, leads to σ(7 10 -3 )/σ(5 10 -6 ) = 1.17. In Be, although the activation parameters have not been determined, we can make the following assumptions: ν = ν D = 3×10 -13 s -1 , the Debye frequency, T m = 800 K, C = 0.012, α ranging from 4 to 7 and E 0 ranging from 4 to 500 eV. In all cases, this yields also to 1 < σ(7 10 -3 )/σ(5 10 -6 ) < 1.2.

Figure 1

 1 Figure 1: a) A selectively etched Al/Be eutectic forming a hole containing freestanding electron transparent Be fibers. b) is a zoom on the right side of the hole where fibers are attached from both sides to the rest of the eutectic. c) is a zoom in the region 1 shown in b) where the observations were performed. d) is a schematics of the straining device. The straining direction T is along the fiber direction.

  of the fibers in the area shown in figure 1c are about 200 µm long. End-on observations of broken

Figure 2

 2 Figure 2: a) Most of the fibers deformed along the straining axis T having their long direction parallel to their c -axis are hard to deform while the (01 12) twin is favourably oriented (b).

Figure 3

 3 Figure 3: a) to d) show the migration of a (01 12) twin boundary under stress. X 1 and X 2 are fiducial markers. e) is the image difference d)-c) when X 2 position is set as a reference. This allows the measure of both the migration distance (d ⊥ ) and the shear displacement (d ).

Figure 4 :

 4 Figure 4: Projection of the dichromatic pattern of the twin along the [2 11 0] direction. Black and white symbols corresponds to the twin and matrix respectively. Circle and square symbols indicate lattice positions in two adjacent planes along the [01 12] direction. The twinning dislocation has a Burgers vectors b twin = b 2/2 associated with a step h. The shaded red area corresponds to the area swept by the twinning dislocation while moving along the twin plane during the twin boundary migration.

  and a the lattice parameters). The norm of the Burgers vector is b twin = λ) 2 a ≈ 0.265 nm. The coupling factor arising from the motion of this disconnection is then β = b twin /h = 2-λ 2 √ 2λ = 0.1992, in agreement with the measured value.

Figure 5 :

 5 Figure 5: Diffraction contrast broadening (indicated by the arrow) increased from a) to b) and decreased from b) to c) near the fiber surface concomitantly with twin boundary migration. This can be interpreted by the emission of dislocations from the surface. Note the presence of secondary dislocations in the twin boundary dragged as the twin boundary migrated. d) is the image difference c)-a).

Figure 6 :

 6 Figure 6: a) and b) are post-mortem evidence of twins (tw) that have formed inside a fiber. c) is the engineering stress strain curve corresponding to a micromechanical test performed on the fiber at a strain rate of 3 × 10 -5 s -1 shown in b).

Figure 7 :

 7 Figure 7: Schematics of the deformation of the fiber containing a twin boundary (tw) that migrates perpendicular to the twinning plane, inclined of an angle 90 -α with respect to the straining axis, over a distance d ⊥ . This migration produces a shear displacement parallel to the twinning plane d .

Figure 8 :

 8 Figure 8: Variation of the twin boundary migration speed (v) as a function of time (t). Lines indicate two data fit for data ranging between t 0 and t=40 s (full line) or t=15 s (dashed line)

Figure 9 :

 9 Figure 9: Normalized activation energy (a) and activation volume (b) as a function of the stress. Full lines correspond to results of atomistic simulations of dislocation surface nucleation. The values of the present study are also indicated for comparison.

Acknowledgement

The authors would like to thank D. Caillard and S. Brochard for valuable discussions. They acknowledge J. Bonneville and A. Serra for their comments after the initial publication. M.L. would also like to thank the Humbolt Fundation for allowing him to spend time at KIT. C.E. and O.K. acknowledge the support by the Robert-Bosch Foundation. This work has been supported by the French National Research Agency under the "Investissement d'Avenir" program reference No. ANR-10-EQPX-38-01.

Appendix A. Effective modulus of the samplemachine system

The relation between the engineering strain, ˙ , engineering plastic strain, ˙ p and the observed true stress rate, σ is given by:

In this equation, C is the effective modulus of the sample-machine system:

where E is the Young's modulus of the specimen and

and K the machine stiffness. The machine stiffness is a combination of the different stiffness of the elements composing the machine (see figure 1). For elements deforming in tension:

with E i , A i and l i are the Young's modulus, the crosssection area and the length of the i th element, respectively. Because the sample is glued on the copper grid, the cyanoacrylate glue also deforms mainly by shear. The shear stiffness of the glue is:


Carlos Baquero

Paulo Sérgio Almeida

Ali Shoker

Making Operation-based CRDTs Operation-based

Conflict-free Replicated Datatypes (CRDT) are usually classified as either state-based or operation-based. However, the standard definition of op-based CRDTs is very encompassing, allowing even sending the full-state, blurring the distinction. We introduce pure op-based CRDTs, that can only send operations to other replicas, drawing a clear distinction from state-based ones. Datatypes with commutative operations can be trivially implemented as pure op-based CRDTs using standard reliable causal delivery. We propose an extended API -tagged reliable causal broadcast -that provides causality information upon delivery, and show how it can be used to also implement other datatypes having non-commutative operations, through the use of a PO-Log -a partially ordered log of operations -inside the datatype. A semantically-based PO-Log compaction framework, using both causality and what we denote by causal stability, allows obtaining very compact replica state for pure op-based CRDTs, while also benefiting from small message sizes.

Introduction

Eventual consistency [START_REF] Vogels | Eventually consistent[END_REF] is a relaxed consistency model that is often adopted by large-scale distributed systems [START_REF] Cribbs | Data structures in Riak[END_REF][START_REF] Bailis | Eventual consistency today: Limitations, extensions, and beyond[END_REF][START_REF] Terry | Managing update conflicts in Bayou, a weakly connected replicated storage system[END_REF][START_REF] Decandia | Dynamo: Amazon's highly available key-value store[END_REF] where losing availability is normally not an option, whereas delayed consistency is acceptable. In eventually consistent systems, data replicas are allowed to temporarily diverge, provided that they can eventually be reconciled into a common consistent state. Reconciliation (or merging) used to be error-prone, being application-dependent, until new datatypedependent models like the Conflict-free Replicated DataTypes (CRDTs) [START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF][START_REF] Shapiro | Conflict-free replicated data types[END_REF] were recently introduced. CRDTs allow both researchers and practitioners to design correct replicated datatypes that are always available, and are guaranteed to eventually converge once all operations are known to all replicas. Though CRDTs have been successfully deployed in practice [START_REF] Cribbs | Data structures in Riak[END_REF], a lot of work is still required to improve their designs and performance.

CRDTs support two complementary designs: operation-based (or simply, opbased) and state-based. In principle, op-based designs are supposed to disseminate operations, while state-based designs disseminate object states. In op-based designs [START_REF] Letia | CRDTs: Consistency without concurrency control[END_REF][START_REF] Shapiro | Conflict-free replicated data types[END_REF], the execution of an operation is done in two phases: prepare and effect. The former is performed only on the local replica and looks at the operation and current state to produce a message that aims to represent the operation, which is then shipped to all replicas. Once received, the representation of the operation is applied remotely using effect. Different replicas are guaranteed to converge as long as messages are disseminated through a reliable causal broadcast messaging middleware, and effect is designed to be commutative for concurrent operations. On the other hand, in a state-based design [START_REF] Baquero | Using structural characteristics for autonomous operation[END_REF][START_REF] Shapiro | Conflict-free replicated data types[END_REF], an operation is only executed on the local replica state. A replica propagates its local changes to other replicas through shipping its entire state. A received state is incorporated with the local state via a merge function that, deterministically, reconciles the merged states. To maintain convergence, merge is defined as a join: a least upper bound over a join-semilattice [START_REF] Baquero | Using structural characteristics for autonomous operation[END_REF][START_REF] Shapiro | Conflict-free replicated data types[END_REF].

Typically, state-based CRDTs support ad hoc dissemination of states and can handle duplicate and out-of-order delivery of messages without breaking causal consistency; however, they impose complex state designs and store extra meta-data. On the other hand, in the systems where the message dissemination layer guarantees reliable causal broadcast, operation-based CRDTs have more advantages as they can allow for simpler implementations, concise replica state, and smaller messages.

In standard op-based CRDTs the designer is given much freedom in defining prepare, namely using the state in an arbitrary way. This is needed to have the effects of concurrently invoked data-type operations commute, and thus provide replica convergence despite the absence of causality information in current causal delivery APIs. This forces current op-based designs to include causality information in the state to be used in prepare, sent in messages, and subsequently used in effect. The designer ends up intervening in many components (the state, prepare, effect, and query functions) in an ad hoc way. This can result in large complex state structures and also large messages.

Currently, a prepare not only builds messages that duplicate the information already present in the middleware (even if it is not currently made available), but causality meta-data is often incorporated in the object state, hence, reusing design choices similar to those used in state-based approaches. Such designs, made to work assuming little messaging guarantees, impose larger state size and do not fully exploit causal delivery guarantees. This freedom in current op-based designs is against the spirit of 'sending operations', and leads to confusion with the state-based approach. Indeed, in the current op-based framework, a prepare can return the full state, and an effect can do a full state-merge (which mimics a state-based CRDT) [START_REF] Baquero | Using structural characteristics for autonomous operation[END_REF][START_REF] Shapiro | Conflict-free replicated data types[END_REF].

We believe that the above weaknesses can be avoided if the causality metadata can be provided by the messaging middleware. Causal broadcast implementations already posses that information internally, but it is not exposed to clients. In this paper we propose and exploit such an extended API to achieve both simplicity and efficiency in defining op-based CRDTs.

We introduce a Pure Op-Based CRDT framework, in which prepare cannot inspect the state, being limited to returning the operation (including potential parameters). The entire logic of executing the operation in each replica is delegated to effect, which is also made generic (i.e., not datatype dependent). For pure op-based CRDTs, we propose that the object state is a partially ordered log of operations -a PO-Log . Causality information is provided by an extended messaging API: tagged reliable causal broadcast (TRCB). We use this information to preserve convergence and also design compact and efficient CRDTs through a semantically based PO-Log compaction framework, which makes use of a datatype-specific obsolescence relation, defined over timestamp-operation pairs. Furthermore, we propose an extension that improves the design and implementation of op-based CRDTs through decomposing the state into two components: a PO-Log (as before), and a causality-stripped-component which, in many cases, will be simply a standard sequential datatype. The idea is that operations are kept only transiently in the PO-Log, but once they become causally stable, causality meta-data is stripped, and the operations are stored in the sequential datatype. This reduces the storage overhead to a level that was never achieved before in CRDTs, neither state-based nor op-based.

2 System Model and Notations

System and Fault Models

The system is composed of a fixed set of nodes, each with a globally unique identifier in a set I. Nodes execute operations at different speeds and communicate using asynchronous message passing, abstracted by reliable causal broadcast (or gossip in the brief discussion about state-based CRDTs). Messages can be lost, reordered or duplicated, and the system can experience arbitrary, but transient, partitions. A node can fail by crashing and can recover later on; upon recovery, the last durable state of a node is assumed to be intact (not destroyed). We do not consider Byzantine faults. A fixed membership is assumed for causal broadcast: messages towards a node that is temporarily crashed or partitioned are buffered until it becomes reachable.

For presentation purposes, and without loss of generality, we consider a single object that is replicated at each node; each replica initially starts with the same state. Once a datatype operation is locally applied on a replica, the latter can diverge from the other replicas, but it may eventually convergence as new operations arrive. A local operation is applied atomically on a given replica.

Definitions and Notations

Σ denotes the type of the state. P(V ) denotes a power set (the set of all subsets of V ). The initial state of a replica i is denoted by σ 0 i ∈ Σ. Operations are taken from a set O and can include arguments (in which case they are surrounded by brackets, e.g., inc and [add, v]). We use total functions K → V and maps (partial functions) K → V from keys to values, both represented as sets of pairs (k, v). Given a function m, the notation m{k → v} maps k to v, and behaves like m on other keys, e.g., Fig. 1a. State-Based CRDTs. These CRDTs maintain a state representation of an object, which evolves according to a well defined partial order. A state evolves via executing datatype operations or through applying a join operation, which merges any two states, thus resolving conflicting states. State-based replicas of an object converge by always shipping the entire local state, and applying the join operation on received states. State-based CRDTs are costly as the entire replica state must be shipped, but they demand less guarantees from the network because joins are designed to be commutative, idempotent, and associative. Figure 1a represents a state-based increment-only counter. In this paper we do not address state-based CRDTs.

Σ = I → N σ 0 i = {(r, 0) | r ∈ I} apply i (inc, m) = m{i → m(i) + 1} evali(rd, m) = r∈I m(r) merge i (m, m ) = {(r, max(m(r), m (r))) | r ∈ I} (a) State-based counter Σ = N σ 0 i = 0 prepare i (inc, n) = inc effecti(inc, n) = n + 1 evali(rd, n) = n (b) Op-based counter
Operation-Based CRDTs. In op-based CRDTs, representations of operations issued at each node are reliably broadcast to all replicas. Once all replicas receive all issued operations (on all nodes), they eventually converge to a single state, if: (a) operations are broadcast via a reliable causal broadcast, and (b) 'applying' representations of concurrently issued operations is commutative. Op-based CRDTs can often have a simple and compact state since they can rely on the exactly-once delivery properties of the broadcast service, and thus do not have to explicitly handle non-idempotent operations. Figure 1b represents an op-based increment-only counter. The state contains a simple integer counter that is incremented for each inc operation that is delivered.

The API of the underlying middleware at each node i provides an interface method cbcast i (m) that sends a message m using causal broadcast. When applying an operation o at some node i with state σ, function prepare i (o, σ) is called returning a message m. This message is then broadcast by calling cbcast i (m). Once m is delivered to each destination node j, effect j (m, σ) is called, returning the new replica state σ . For each node that broadcasts a given operation, the broadcast, the corresponding local delivery, and the effect on the local state are executed atomically. When a query operation q is performed, eval i (q, σ) is invoked. eval takes the query and the state as input and may return a result (leaving the state unchanged). In this section we introduce pure op-based CRDTs and discuss what datatypes can be implemented as pure using standard causal broadcast.

Σ = N × P(I × N × V ) σ 0 i = (0, {}) prepare i ([add, v], (n, s)) = [add, v, i, n + 1] effecti([add, v, i , n ], (n, s)) = (n if i = i otherwise n, s ∪ {(v, i , n )}) prepare i [rmv, v], (n, s)) = [rmv, {(v , i , n ) ∈ s | v = v}] effecti([rmv, r], (n, s)) = (n, s \ r) eval(rd, (n, s)) = {v | (v, i , n ) ∈ s}
Definition 1 (Pure op-based CRDT). An op-based CRDT is pure if messages contain only the operation (including arguments, if any). Given operation o and state σ, prepare is always defined as:

prepare(o, σ) = o.
This means that prepare cannot build an arbitrary message depending on the current state; in fact, in pure op-based CRDTs the operation can be immediately broadcast without even reading the replica state. As an example, the counter in Fig. 1b is pure op-based, while the observed-remove set implementation (from [START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF]) in Fig. 2 is not, because in a remove operation prepare builds a set of triples present in the current state, to be removed from the state at each replica when performing effect.

Pure Implementations of Commutative Datatypes

As we discuss now, the pure model of op-based CRDTs can be directly applied, using standard reliable causal broadcast [START_REF] Birman | Lightweight causal and atomic group multicast[END_REF], to implement datatypes whose operations are commutative.

Definition 2 (Commutative datatype).

A concurrent datatype is commutative if (a) for any operations f and g, their (sequential) invocation commutes: f (g(σ)) = g(f (σ)), and (b) concurrent invocations are defined as equivalent to some linearization.

Commutative datatypes reflect a principle of permutation equivalence [START_REF] Bieniusa | Brief announcement: Semantics of eventually consistent replicated sets[END_REF] stating that "If all sequential permutations of updates lead to equivalent states, then it should also hold that concurrent executions of the updates lead to equivalent states".

As the extension to concurrent scenarios follows directly from their sequential definition, with no room for design choices, commutative datatypes can have a

Σ = N σ 0 i = 0 prepare i (o, σ) = o effecti(inc, n) = n + 1 effecti(dec, n) = n -1 evali(rd, n) = n (a) Pure PN-counter Σ = P(V ) σ 0 i = {} prepare i (o, σ) = o effecti([add, v], s) = s ∪ {v} evali(rd, s) = s (b) Pure grow-only set
Fig. 3: Pure op-based CRDTs for commutative datatypes standard sequential specification and implementation. As such, a pure op-based CRDT implementation is trivial: as when using the standard causal broadcast, the message returned from prepare, containing the operation, will arrive exactly once at each replica, it is enough to make effect consist simply in applying the received operation to the state, over a standard sequential datatype, i.e., defining for any datatype operation o:

effect i (o, σ) = o(σ).
Two examples of commutative datatypes, presented in Fig. 3, are: a PNcounter with inc and dec operations; a grow-only set (G-set) with add operation. Both cases use a standard sequential datatype for the replica state, and applying effect is just invoking the corresponding operation in the sequential datatype. Both these examples explore commutativity and rely on the exactly-once delivery, leading to a trivial pure implementation.

Non-commutative Datatypes

In the case where datatype operations are not commutative, such as a set with add and rmv operations, where add(v, rmv(v, s)) = rmv(v, add(v, s)), we have two reasons that prevent effect from being simply applying the operation over a sequential datatype.

One reason is that, even when the semantics of concurrent invocations can be defined as equivalent to some linearization of those operations, the messages corresponding to concurrent operations will be, in general, delivered in different orders in different replicas. Therefore, as the operations do not commute, simply applying them in different orders in different replicas makes replicas diverge. Under the assumption of causal delivery and the aim of convergence, effect must always be commutative, and therefore, cannot be defined directly as operations that are not commutative themselves. It must be defined in some other way.

The other reason is that it is useful to specify concurrent datatypes in which the outcomes of concurrent executions are not equivalent to some linearization. The best example is the multi-value register, where two concurrent writes make state: σi ∈ Σ on operation i (o):

tcbcasti(prepare(o, σi)) on tcdeliveri(m, t):

σi := effect(m, t, σi) on tcstablei(t):

σi := stable(t, σi)

Algorithm 1: Distributed algorithm for node i using tagged causal broadcast a read in their causal future return a set with both values written. This outcome could not arise under a sequential specification.

In general, a concurrent datatype will have a specification depending on the partial order of operations over the datatype. Given that such information about that partial order is already present in metadata in causal delivery middleware, we propose an approach for pure op-based CRDTs for general non-commutative datatypes that leverages this metadata, now exposed by an extended causal delivery API, what we call tagged reliable causal broadcast.

Tagged Reliable Causal Broadcast (TRCB)

A common implementation strategy for a reliable causal broadcast service [START_REF] Schmuck | The use of efficient broadcast protocols in asynchronous distributed systems[END_REF] is to assign a vector clock to each message broadcast and use the causality information in the vector clock to decide at each destination when a message can be delivered. If a message arrives at a given destination before causally preceding messages have been delivered, the service delays delivery of that message until those messages arrive and are delivered. Unlike totally ordered broadcast, which requires a global consensus on the delivery order, causal broadcast can progress with local decisions. For general datatypes, causal consistency is likely the strongest consistency criteria compatible with an always-available system that eventually converges [START_REF] Mahajan | Consistency, availability, and convergence[END_REF].

By leveraging this information, we can specify a reliable causal broadcast service with an extended API, and refer to its broadcast operation at each replica i as tcbcast i (m). Algorithm 1, running on each node i, shows how the events triggered by the tagged causal delivery service are used to invoke the generic functions for pure op-based CRDTs: prepare, effect and stable; these functions, in different variants, will be discussed in the following sections. This extended service provides nodes with information about two aspects.

Partial order

The first salient difference is that message delivery on each node i, given by the event tcdeliver i (m, t), provides not only the message m itself, but also the vector clock timestamp t corresponding to m. When implementing pure opbased CRDTs, in which only the operations are sent in messages, we can use the timestamp supplied by the service upon delivery in the definition of effect; i.e., we can have effect(o, t, s) as a function of the operation, the timestamp and the current state.

As we will see in the next section, this information about the partial order can be embedded in the state in a general way so that effect is commutative and reference implementations of general possibly non-commutative datatypes can be obtained, following their specification. Moreover, in Sect. 6 we will see how realistic efficient pure CRDTs can be obtained, in which the use of this causality information, together with the semantics of the datatype operations is essential.

Causal stability

Definition 3 (Causal Stability). A clock t, and corresponding message, is causally stable at node i when all messages subsequently delivered at i will have timestamp t ≥ t;

This implies that no message with a timestamp t concurrent with t can be delivered at i when t is causally stable at i. This notion differs from classic message stability [START_REF] Birman | Lightweight causal and atomic group multicast[END_REF] in which a message is stable if it has been received by all nodes. Here we not only need this to happen but also that no further concurrent messages may be delivered. Therefore, causal stability is a stronger notion, implying classic message stability.

The extended API will provide an event tcstable i (t) which will be triggered when it is determined that t is stable at i. The middleware at node i can check if timestamp t is causally stable at i by checking if a message with timestamp t ≥ t has already been delivered at i from every other other node j, i.e.:

tcstable i (t) when ∀j ∈ I \ {i} • ∃t ∈ delivered i () • origin(t ) = j ∧ t ≤ t ,
where delivered i () returns the set of messages that have been delivered at node i, while origin(t) denotes the node from where the message corresponding to t has been sent. To evaluate this clause efficiently, the middleware only needs to keep the most recently delivered timestamp from each origin [START_REF] Wuu | Efficient solutions to the replicated log and dictionary problems[END_REF].

We will see in Sect. 6 how causal stability can be used to reduce CRDT state size, by stripping causality information from causally stable operations.

Pure CRDTs Based on a Partially Ordered Log

Having a tagged causal broadcast service, it is now possible to obtain a universal mechanism for obtaining pure reference implementations for any (possibly non-commutative) concurrent datatype in which semantics are defined over the partial order of operations.

The reference mechanism, presented in Fig. 4, uses a uniform notion of state for a replica: a partially ordered log of operations, what we call a PO-Log. This uses the ordering information offered by the messaging middleware to keep information about concurrent operations, not trying to impose a local total-order over them, contrary to a classic sequential log. The PO-Log can be defined as a map (a partial function) T → O from message timestamps (as given by the tagged causal broadcast service) to the corresponding operation. Here we have a universal datatype-independent definition of effect as:

Σ = T → O σ 0 i = {} prepare(o, s) = o effect(o, t, s) = s ∪ {(t, o)} eval(q, s) = [
Σ = T → O σ 0 i = {} prepare(o, s) = o (with o either [add, v] or [rmv, v]) effect(o, t, s) = s ∪ {(t, o)} eval(rd, s) = {v | (t, [add, v]) ∈ s ∧ ∃(t , [rmv, v]) ∈ s • t < t }
effect(o, t, s) = s ∪ {(t, o)},
which is trivially commutative, as needed. Only the query functions will need datatype-specific definitions according to desired semantics. Their definition over the PO-Log will typically be a direct transposition of their specification.

Figure 5 shows a pure PO-Log based implementation of an add-wins observedremove set over the new tcbcast service. The add-wins semantic is defined in the rd query function: the set of values reported to be in the set are those values that have been added with no rmv causally in the future of the add. Another example, shown in Fig. 6, is a multi-value register. Here a read reports the set of all concurrently written values that have not been subsequently overwritten.

These reference implementations are not realistic to be actually used, namely because state size in each replica is linear with the number of operations. They are a starting point from which actual efficient implementations can be derived, by semantically based PO-Log compaction, as we show in the next section. But they are relevant, as they provide a clear description of the concurrent semantics of the replicated datatype. This is possible since we are capturing the partial ordered set of all operations delivered to each replica. (A similar approach to express the semantics is found in [START_REF] Burckhardt | Replicated data types: specification, verification, optimality[END_REF] when relating to the visibility relation.)

Semantically Based PO-Log Compaction

We now show how PO-Log based CRDTs can be made efficient by performing PO-Log compaction. There are two ingredients that we explore. The first one is

Σ = T → O σ 0 i = {} prepare([wr, v], s) = [wr, v] effect([wr, v], t, s) = s ∪ {(t, [wr, v])} eval(rd, s) = {v | (t, [wr, v]) ∈ s ∧ ∃(t , [wr, v ]) ∈ s • t < t }
Σ = T → O σ 0 i = {} prepare(o, s) = o effect(o, t, s) = {x ∈ s | ¬ obsolete(x, (t, o))} ∪ {(t, o) | x ∈ s ⇒ ¬ obsolete((t, o), x)}

obsolete() = [datatype-specific relation to identify obsolete operations]

eval(q, s) = [datatype-specific query function over partial order] Fig. 7: Reference implementation for PO-Log compaction to prune the PO-Log after each operation is delivered in the effect, so as to keep the minimum number of operations such that all queries return the same result as when the full PO-Log is present. The second one is to explore causal stability information, to discard timestamp information for elements once they become stable, possibly merging some elements.

Exploring Causality Information

As the possibility of discarding operations while preserving semantics is datatype dependent, we propose a unified framework which includes the PO-Log, prepare, and a more sophisticated effect which makes use of a datatype-specific relation to discard operations made irrelevant by newer arrivals, according to both operation content and corresponding timestamp, as shown in Fig. 7.

This relation between pairs timestamp-operation -obsolete((t, o), (t , o ))is used by effect in the following way: when a new pair (t, o) is delivered to a replica, effect discards from the PO-Log all elements x such that obsolete(x, (t, o)) holds; also, the delivered pair (t, o) is only inserted into the PO-Log if it is not redundant itself, according to the current elements, i.e., if for any current x in the PO-Log obsolete((t, o), x) is false. This relation is not restricted to be a partial-order, but can be a more general relation, allowing, e.g., a newly arrived operation to discard others in the PO-Log without necessarily being itself added.

It is easy to see by simple induction that this execution mechanism provides the invariant that for any two different pairs p 1 and p 2 in the PO-Log, obsolete(p 1 , p 2 ) is false. This invariant allows reasoning about the datatype, namely to be able to write simplified query functions that give the same result over the compact PO-Log as the original query functions over the full PO-Log. An observed-remove add-wins set using the PO-Log compaction framework can be seen in Fig. 8 (which presents only the datatype-specific functions). Here it can be clearly seen that obsolete was defined directly according to the essence of the datatype: a subsequent add obsoletes a previous add of the same value; a rmv obsoletes an add of the same value. The more interesting rule is that any rmv is made obsolete by any other timestamp-operation pair; this implies that a rmv can only exist as the single element of a PO-Log (if it was inserted into an empty PO-Log), being discarded once other operation arrives (including another rmv), and never being inserted into a non-empty PO-Log. This reflects the add-wins nature, in which the role of a rmv is basically to discard same-value additions in its causal past. Under the now compacted PO-Log, the query function rd can be defined in a simple way, and clearly seen to give the same result as the original one over the full PO-Log (in Fig. 5).

obsolete((t, [add, v]), (t , [add, v ])) = t < t ∧ v = v obsolete((t, [add, v]), (t , [rmv, v ])) = t < t ∧ v = v obsolete((t, [rmv, v]), x) = true eval(rd, s) = {v | (t, [add, v]) ∈ s}
Another example where PO-Log compaction leads to an efficient datatype is the multi-value register, in Fig. 9, where it is obvious the effect of a write in making all writes in its causal past obsolete, regardless of value written. The set of concurrent writes that have not been made obsolete will be returned in a read, which is equivalent to the original definition in Fig. 6 over the full PO-Log.

Exploring Causal Stability Information

The second component of PO-Log compaction involves using causal stability to strip logical clocks from the PO-Log. From the definition of causal stability, if some pair (t, o) is in the PO-Log, with t causally stable, all future deliveries (t , o ) used in effect will be causally in the future, i.e., t > t.

Because effect only compares, through obsolete, new arrivals and PO-Log elements -but never PO-Log elements among themselves -and for a stable t, all future deliveries will be causally in its future, the value of t is no longer needed, and it can be replaced by any timestamp that is less than all other In practice this means that, instead of having timestamps that are maps or vectors with size linear on the number of replicas, we can have a special marker denoting bottom (e.g. a null pointer). This greatly diminishes the size of a replica state for two reasons. For some CRDTs where size may be a problem, like sets of integers, values may take considerably less space than timestamps, which constitute the great percentage of state size; stripping a timestamp from an element can be a huge improvement per element. The second reason is that, again in such scenarios with large states, the percentage of elements in the PO-Log that are not yet causally stable will be quite small, with most already stable. This means that this optimization, which gives good results per element, will be applied to most elements, leading to a large overall improvement.

Σ = P(O) × (T → O) σ 0 i = (
Instead of being a map T → O, the PO-Log is split in P(O) × (T → O), detaching into a plain set all operations that have stable timestamps (i.e., making the ⊥ timestamp implicit). A new framework using the split PO-Log is presented in Fig. 10. In effect a new delivery possibly discards elements both from the set of operations and the partially ordered set of operations; elements from the latter are used to decide on the addition of the new delivery, as before. (The possibility of a stable operation obsoleting a new arrival, in its causal future, is not considered, but this can easily be changed if some example shows its usefulness.) In stable, the operation corresponding to a stable timestamp is fetched, to be added to the set and the corresponding entry removed from the map.

The PO-Log split allows implementations tailored to specific datatypes to achieve further improvements. As an example, an or-set will have only (t, [add, v]) entries in its PO-Log (except for the singleton {(t, [rmv, v]}) which can be prevented by a special rule); when elements become causally stable, only the value v needs to be migrated and not the operation name. The set component of the split PO-Log becomes a plain set of values, allowing traditional implementations of sets to be used; e.g., a bitmap if the datatype is for a dense set of integers.

By exploiting both causality and causal stability information, made available by the proposed tagged causal delivery API, we have paved the way for these optimizations that allow pure op-based CRDTs that are much more suitable for large datatypes than current designs.

Related Work

Weakly Consistent Replication. The design of replicated systems that are always available and eventually converge can be traced back to historical designs in [START_REF] Wuu | Efficient solutions to the replicated log and dictionary problems[END_REF][START_REF] Johnson | The maintenance of duplicate databases. Internet Request for Comments RFC 677[END_REF][START_REF] Quarterman | Notable computer networks[END_REF], among others. Lazy Replication [START_REF] Ladin | Providing high availability using lazy replication[END_REF] allows enforcing causal consistency, but may apply concurrent operations in different orders in different replicas, possibly leading to divergence if operations are not commutative; TSAE [START_REF] Golding | Weak-consistency group communication and membership[END_REF] also either applies concurrent operations in possibly different orders, or allows enforcing a total order compatible with causality, at the cost of delaying message delivery. Both these systems use a message log, the former with complete causality information, but the log is pre-delivery, unseen by the application: operations are applied sequentially to the current state and queries use only the state. In our framework the PO-Log is post-delivery, being part of the datatype state, maintains causality information and is used in query operations.

Conflict-Free Replicated Data Types. The formalization of the commutativity requirements for concurrent operations in replicated datatypes was introduced in [START_REF] Letia | CRDTs: Consistency without concurrency control[END_REF][START_REF] Roh | Replicated Abstract Data Types: Building blocks for collaborative applications[END_REF], and that of the state based semi-lattices was presented in [START_REF] Baquero | Using structural characteristics for autonomous operation[END_REF]. Afterwards, the integration of the two models with many extensions was presented in Conflict-free Replicated Datatypes [START_REF] Shapiro | A comprehensive study of Convergent and Commutative Replicated Data Types[END_REF][START_REF] Shapiro | Conflict-free replicated data types[END_REF]. Currently, CRDTs have made their way into the industry through designing highly available scalable systems in cloud databases like RIAK [START_REF] Cribbs | Data structures in Riak[END_REF], and mobile gaming industry such as Rovio [START_REF]Rovio gaming[END_REF].

Message Stability. The notion of message stability was defined in [START_REF] Birman | Lightweight causal and atomic group multicast[END_REF] to represent a message that has been received by all recipients; each replica can discard any message it knows to be stable after delivering it. Similar notions are used in Lazy Replication [START_REF] Ladin | Providing high availability using lazy replication[END_REF] and TSAE [START_REF] Golding | Weak-consistency group communication and membership[END_REF]. In all these cases the aim is message garbage collection. Our definition of causal stability is the stronger notion that no more concurrent messages will be delivered ; we use it inside the datatype to discard causality information while keeping the operation. Causal stability is close to what is used in the mechanics of Replicated Growable Arrays (RGA) [START_REF] Roh | Replicated Abstract Data Types: Building blocks for collaborative applications[END_REF], although no definition is presented there.

Message Obsolescence. Semantically reliable multicast [START_REF] Pereira | Semantically reliable multicast: Definition, implementation, and performance evaluation[END_REF] uses the concept of message obsolescence to avoid delivering messages made redundant by some newly arrived message, where obsolescence is a strict partial order that is a subset of causality, possibly relating messages from the same sender or totally ordered messsages from different senders. Our obsolescence relation is more general, being defined on clock-operation pairs, and can relate concurrent messages. Also, it is defined per-datatype, being used inside each datatype, post-delivery.

In this paper we improved the CRDT model by introducing the stricter notion of pure op-based, and establishing a clear frontier with state-based models. We have shown which pure datatypes are possible over off-the-shelf causal delivery middleware and then introduce an extended API, tagged reliable broadcast, that supports the remaining datatypes, those non-commutative in their sequential specifications. Supported by this API, that conveys causal information present in the middleware, we were able to define a partially ordered log, named PO-Log, that supports a clear semantic description and abstract implementation of each concurrent datatype.

To obtain efficient implementations we developed a framework for semantic compaction of a PO-Log and, in a final step, resorted to a notion of causal stability to determine when it is safe to strip PO-Log entries of their causal order metadata. This final step allows eventually moving all data to a standard sequential datatype, or a local database, and harvest the efficiency gains of reusing existing optimized data structures and database engines.

Having exemplified the framework with relevant non-trivial datatypes (replicated sets and registers) we expect that future research, and the existing developer community, can apply these techniques to other derived datatypes, such a maps, graphs, and sequences.

Fig. 1 :

 1 Fig. 1: Counter CRDT in both state-based and op-based approaches

Fig. 2 :

 2 Fig. 2: Standard op-based observed-remove add-wins set

Fig. 4 :

 4 Fig. 4: PO-Log based reference implementation for pure op-based CRDTs

Fig. 5 :

 5 Fig. 5: PO-Log based observed-remove add-wins set

Fig. 6 :

 6 Fig. 6: PO-Log based multi-value register

Fig. 8 :

 8 Fig. 8: Observed-remove add-wins set with PO-Log compaction

  {}, {}) prepare(o, (s, p)) = o effect(o, t, (s, p)) = (s , p ), wheres = {x ∈ s | ¬ obsolete((⊥, x), (t, o))} p = {x ∈ p | ¬ obsolete(x, (t, o))} ∪ {(t, o) | x ∈ p ⇒ ¬ obsolete((t, o), x)} stable(t, (s, p)) = (s ∪ p(t), p \ {(t, p(t))})obsolete() = [datatype-specific relation to identify obsolete operations] eval(q, (s, p)) = [datatype-specific query function overPO-Log ]

Fig. 10 :

 10 Fig. 10: Full PO-Log compaction framework exploring causal stability

Acknowledgments. We thank Marek Zawirski, Ricardo Gonçalves and anonymous reviewers for comments that helped improve this work. Project Norte-01-0124-FEDER-000058 is co-financed by the North Portugal Regional Operational Programme (ON.2 O Novo Norte), under the National Strategic Reference Framework (NSRF), through the European Regional Development Fund (ERDF). Project FCOMP-01-0124-FEDER-037281 financed by National Funds by FCT, and by ERDF. Funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement 609551, SyncFree project.