Oana Andrei

Hélène Kirchner

Strategic Port Graph Rewriting for Autonomic Computing

In this paper, we present a high-level formalism based on port graph rewriting, strategic rewriting, and rewriting calculus. We show that this formalism is suitable for modeling autonomic systems and we illustrate its expressivity for modeling properties of such systems using an example of a mail delivery system.

Introduction

Autonomic computing [START_REF] Kephart | The Vision of Autonomic Computing[END_REF] refers to self-manageable systems initially provided with some high-level instructions from administrators. This is a concept introduced in 2001 with an intended biological connotation: the simplest biological example is that of the human nervous system where the brain does not need to handle all lowlevel still vital functions of the body. The four mostimportant aspects of self-management as presented in [START_REF] Kephart | The Vision of Autonomic Computing[END_REF] are self-configuration, self-optimization, self-healing, and self-protection.

This idea of biologically inspired formalism gained much interest with the recent development of large scale distributed systems such as service infrastructures and Grids. For such systems, there is a crucial need for theories and formal frameworks to model computations, to define languages for programming and to establish foundations for verifying important properties of these systems. Several approaches contributed to this ambitious goal. Without exhaustivity, let us mention in particular the brane calculus [START_REF] Cardelli | Brane Calculi[END_REF][START_REF] Danos | Projective Brane Calculus[END_REF] and the bigraphical reactive systems [START_REF] Milner | Pure bigraphs: Structure and dynamics[END_REF], but also several calculi inspired from biology such as [START_REF] Regev | BioAmbients: an abstraction for biological compartments[END_REF][START_REF] Chabrier-Rivier | The Biochemical Abstract Machine BIOCHAM[END_REF][START_REF] Laneve | A simple calculus for proteins and cells[END_REF].

Another connected approach is provided by chemical programming which uses the chemical reaction metaphor to express the coordination of computations. This metaphor describes computation in terms of a chemical solution in which molecules (representing data) interact freely accord-ing to reaction rules. Chemical solutions are represented by multisets (data-structure that allows several occurrences of the same element). Computation proceeds by rewritings, which consume and produce new elements according to conditions and transformation rules. The Gamma formalism was first proposed in [START_REF] Banatre | A new computational model and its discipline of programming[END_REF] and later extended to HOCL in [5,[START_REF] Banâtre | Programming Self-Organizing Systems with the Higher-Order Chemical Language[END_REF] for modeling self-organizing and autonomic systems or grids in particular.

Beyond the chemical programming idea, another approach presented in [START_REF] Chakravarti | Application-Specific Scheduling for the Organic Grid[END_REF], called the Organic Grid, is similarly a radical departure from current approaches and is inspired by the self-organization property of complex biological systems.

Our previous work on biochemical applications led us to consider the structure of port graph to model interactions between molecules or proteins [START_REF] Andrei | Graph Rewriting and Strategies for Modeling Biochemical Networks[END_REF][START_REF] Andrei | A Rewriting Calculus for Multigraphs with Ports[END_REF].

In this paper, we propose port graphs as a formal model for distributed resources and grid infrastructures. Each resource is modeled by a node with explicit connection points called ports. We model the lack of global information, the autonomous and distributed behavior of components by a multiset of port graphs and rewrite rules which are applied locally, concurrently, and non-deterministically. Hence the computations take place wherever it is possible and in parallel. This approach also provides a formal framework to reason about computations and to verify desirable properties. Moreover strategic port graph rewriting takes into account control on computations by allowing to chain rewrite rules. By lifting port graph rewriting to a calculus, we are able to express rules and strategies as port graphs and so to rewrite them as well. The calculus also permits the design of rules that create new rules. In addition, our graph-based formalism is visual, so hopefully easy to understand. We borrow various concepts from graph theory, in particular from graph transformations [START_REF] Corradini | Algebraic Approaches to Graph Transformation -Part I: Basic Concepts and Double Pushout Approach[END_REF], and different representations for graphs already intensively formalised, like the setbased or the categorical approaches.

The paper is structured as follows. Section 2 introduces the port graphs, while Section 3 introduces the port graph rewrite rules as port graphs and defines the matching and the rewriting relation for port graphs. Section 4 provides a presentation of abstract strategies in the context of abstract reduction systems, which can be easily adjusted for port graph rewriting system to obtain a definition of the strategic port graph rewriting. Having all ingredients, in Section 5 we give the main ideas of a high-level calculus for port graphs, and in Section 6 we show that this calculus is a suitable formalism for modeling autonomic systems. We illustrate the concepts and ideas presented in this paper with examples from a mail delivery system example borrowed from [START_REF] Banâtre | Chemical Specification of Autonomic Systems[END_REF]. In Section 7 we give some suggestions on expressing properties of a modeled system as strategies placed at the same level as the specification of the system.

Port Graphs

We refine the notion of multigraphs, which are graphs with multiple edges and loops, by adding explicit connection points, called ports, to nodes; then edges attach, more specifically, to ports of nodes. We represent graphically a node as a box with the identifier and the name placed outside the box and a port as a small point on the surface of the box.

Example 1

In order to illustrate our approach and the proposed concepts, we develop the example of a mail delivery system borrowed from [START_REF] Banâtre | Chemical Specification of Autonomic Systems[END_REF]. It consists of a network of several mail servers each with its own address domain; the clients send messages for other clients first to their server domain, which in turn forwards them to the network and recovers the messages sent to its clients. Servers are distributed resources with connections between them, when sending and receiving the messages.

In Fig. 1 we illustrate an initial configuration of the mail delivery system. The network is a node with several ports, each port being connected to at most one server. A server node has a handler port for connecting to the network, and several ports for the clients. A client node has a handler port for connecting to a server. All client, server and network nodes have two ports for the incoming and outgoing messages respectively. Messages are nodes with only one port and their names have the form (rec @ domain # m) where rec is the identifier of the recipient client, domain is the identifier of the server domain, and m the body of the message. If redundant, the domain and/or the client identifiers are removed (when arrived in the server domain or at the client). In the system, the server identified by 5 is disconnected from the network node, hence it is crashed.

Let N be a finite set of node names and P be a finite set of port names. A p-signature ∇ = N , P is a function associating to each node name from N a set of port names from P. Hence ∇ is a set of pairs of node name and set of port names.

Definition 1 (Port graph) A port-graph over a p-signature ∇ = N , P takes the form G = (V, E, ι, s, t, l) where:

• V is a finite set of nodes (also referred to as node identifiers);

• ι : V → ∇ assigns a name and a port set to each node, with ι(v) = (n, P );

• E ⊆ {(v ⌢ p, u ⌢ r) ∈ (V × P) 2 | p ∈ ∇(v), r ∈ ∇(u)} a finite multiset of edges;
• s, t : E → V × P the usual source and target functions;

• l = (l V , l E ) is the labeling function associating to each node v ∈ V the triple consisting of the identifier, the name, and the port set, l V (v) = v : n || P where ι(v) = (n, P ), and to each edge (v ⌢ p, u ⌢ r) ∈ E the couple formed by the source port and the target port,

l E ((v ⌢ p, u ⌢ r)) = (p, r).
Note that, by definition, the ports associated to a node are pairwise distinct. Let P = {a, b, c, . . .} and N = {A, B, C, . . .} the sets of constants denoting ports and names respectively. We consider variables ports and names as well, denoted by X P = {x, y, z, . . .} and X N = {X, Y, Z, . . .} respectively. We represent the node identifiers by non-empty sequences of integers. We denote by Var(G) the set of variables occurring in G.

Matching and Rewriting Port Graphs

The evolution of the distributed system is modeled via port graph transformations, themselves expressed by port graph rewrite rules and the generated rewriting relation. To support intuition, in the mail system example, rules express what happens when a client sends a mail to a client in the same network as we will show in Example 2.

Port Graph Rewrite Rule

Definition 2 (Port graph rewrite rule) A port graph rewrite rule L ⇒ R is a port-graph consisting of:

• two port-graphs L and R over the p-signature N ∪ X N , P ∪ X P called, as usual, the left-and righthand side respectively, such that all node identifiers are variables,

• one special "arrow" node, ⇒ that has a port for each port in L which is preserved in R, and the black hole port, named bh,

• edges from L to ⇒ mapping each port in L uniquely to a port of ⇒ if it is not deleted, and to the black hole port otherwise,

• edges from ⇒ to R, mapping each port different from the black hole to a port in R.

A port-graph rewrite systems is a finite set of port-graph rewrite rules.

The arrow node together with its adjacent edges embed the correspondence between elements of L and elements of R. We illustrate some port graph rewrite rules in Fig. 2.

We call a port graph that does not contain the arrow node, a concrete port graph. In particular, concrete port graphs correspond to configurations or patterns in a modeled system.

Example 2 We illustrate in Fig. 3 the basic rules for the mail system. Since the correspondence between the left-and right-hand sides of the rules are the identities, we simplify the graphs by not detailing the arrow node. A mail sent by a client goes to its server: if the mail is sent to a client in the same server domain then it goes to the input port by r1, otherwise to the outgoing port by r2. By rule r3 a server forwards a mail to a client if he is the recipient. Rule r4 specifies that a server forwards a mail to the network if its recipient is not in the domain, while rule r5 specifies that the network forwards a mail to the appropriate server according to the server domain information contained in the mail.

Matching

A port graph morphism assigns the nodes, ports, and edges of a given graph to the nodes, ports, and edges of another graph while preserving adjacency and the membership of port to nodes.

We say that the left-hand side L of a port graph rewrite rule matches a port graph G if there is a triple of the form (g, G -, B) where:

• g is a port-graph morphism such that g(L) is a sub- graph of G, • G -is the context graph, i.e., G -= G \ g(L), given by the set of nodes V G -= V G \ V g(L)
, and the set of edges In general, several solutions are provided for the matching problem, since there are several possibilities to choose match nodes and bridges. Intuitively this is because port graph matching involves list pattern matching on ports. One may decide to choose one solution according to some criterion, for instance the first solution. Of course, another choice may lead to another result.

E G -= {(u ⌢ p, v ⌢ r) ∈ E G | u, v ∈ V G -}. c k:Server i:Client h out j@k#m out c k:Server i:Client h out j@#m in c k:Server i:Client h out j@l#m out c k:Server i:Client h out j@l#m out if k<>l c k:Server i:Client h in i@#m in c k:Server i:Client h in m in out k:Server j@l#m h i:Network s out k:Server j@l#m h i:Network s i/o i/o in k:Server j@k#m h i:Network
An anti-pattern matching algorithm for graphs can be developed based in the anti-pattern matching on algebraic terms [START_REF] Kirchner | Anti-Pattern Matching[END_REF]. This allows us to use negative application conditions in graph rewrite rules, like the non-existence of certain nodes, edges, or subgraphs [START_REF] Habel | Graph Grammars with Negative Application Conditions[END_REF].

Rewriting

Let L ⇒ R be a port graph rewrite rule and G a concrete port graph such that there is a matching morphism g for L in G. The delicate point of applying L ⇒ R to G is to properly define the replacement of g(L) by g(R) in G and the way g(R) is reconnected with G.

The application of the port graph rewrite rule L ⇒ R to G can be decomposed in the following steps as illustrated in Fig. 4: (i) find the matching morphism g, the context G -, and the bridges B (their orientation is not important in the drawing); (ii) identify the left-hand side of the rule with the isomorphic subgraph in G; (iii) translate the bridges B following the instantiated arrow node to obtain B g ; (iv) remove the arrow node and the isomorphic subgraph g(L) which is now disconnected from the context graph.

If a bridge has an endpoint in g(L) that is changed by the rewrite rule, then it cannot be simply reconnected to g(R) during the replacement. However, the arrow node ⇒ together with the incident edges trace the change of this endpoint, providing the way of reconnecting which we call the arrow-translation.

Definition 3 (Port graph rewriting) Given a port-graph rewrite system R, an concrete port graph G rewrites to a port-graph G ′ , denoted by G → R G ′ , if there exists a port-graph rewrite rule L ⇒ R in R and a matching (g, G -, B) of L against G such that G = G -[g(L)] B and G ′ = G -[g(R)] Bg .
In order to emphasize the used rewrite rule, a rewrite step may also be denoted

G → L⇒R G ′ .
Of course, if a condition or a constraint is associated to the rewrite rule L ⇒ R, its satisfaction is required for applying the rewriting of G to

G ′ . L R G L R g(L) g(R) g(L) g(R) g(L) g(R) G - G - G - G - B B B g B g (1) (2) (3) (4)

Strategic Port Graph Rewriting

The port graph transformation of Definition 3 is an instance of the general framework of abstract reduction systems [START_REF]Term Rewriting Systems[END_REF][START_REF] Klop | Term Rewriting Systems[END_REF][START_REF] Klop | Reduction strategies and acyclicity[END_REF]. Definition 4 (Abstract reduction system) An abstract reduction system (ARS) is a labelled oriented graph (O, S). The nodes in O are called objects, the oriented edges in S are called steps.

Here an object of O is a set of port graphs and a step in S is a port graph rewriting step.

Definition 5 (Derivation) Let A be a given ARS A:

1. A reduction step is a labelled edge φ together with its source a and target b. This is written a φ A b, or simply a φ b when unambiguous.

A A-derivation is a path π in the graph A.

3. When it is finite, π can be written a 0 φ0 a 1 φ1 a 2 . . . φn-1 a n and we say that a 0 reduces to a n by the derivation π = φ 0 φ 1 . . . φ n-1 ; this is also denoted by a 0 π a n . The source of π is the object a 0 and its domain is defined as the singleton dom(π) = {a 0 }. The target of π is the object a n and the application of the derivation π to a 0 is the singleton denoted [π]( a 0 ) = {a n }.

4.

A derivation is empty when its source and target are the same. The empty derivation issued from a is denoted by id a .

5. The concatenation of two derivations π 1 and π 2 is defined when dom(π 1 ) = {a} and

[π 1 ](a) = dom(π 2 ). Then π 1 ; π 2 denotes the new A-derivation a π1 A b π2 A c and [π 1 ; π 2 ](a) = [π 2 ]([π 1 ](a)) = {c}.
Note that an A-derivation is the concatenation of its reduction steps. The notion of abstract strategy is introduced in [START_REF] Kirchner | Strategic computations and deductions[END_REF] and applies to port graph rewriting.

Definition 6 (Abstract strategy) For a given ARS A:

1. An abstract strategy ζ is a subset of the set of all derivations (finite or not) of A.

Applying the strategy ζ on an object a, denoted by

[ζ](a), consists of the set of all objects that can be reached from a using a derivation in ζ:

[ζ](a) = {b | ∃π ∈ ζ such that a π b} = {[π](a) | π ∈ ζ}.
When no derivation in ζ has for source a, we say that the strategy application on a fails. 4. The domain of a strategy is the set of objects that are source of a derivation in ζ:

dom(ζ) = δ∈ζ dom(δ)

The strategy that contains all empty derivations is

Id = {id a | a ∈ O}.
Note that, following from the previous definition, a strategy is not defined on all objects of the ARS, hence it is a partial function. A strategy that contains only infinite derivations from a source {a} applies to the object a and returns the empty set. The empty set of derivations is a strategy called F ail; its application always fails.

We can formalize strategic port graph rewriting in this context:

G → R G ′ that occurs in a derivation of ζ. This is also denoted G → ζ G ′ .
The formalisation of abstract reduction system and abstract strategies allows then to define properties like termination (all relevant derivations are of finite length) and confluence (all relevant derivations lead to the same object). Their precise definitions can be found in [START_REF] Kirchner | Strategic computations and deductions[END_REF]. Termination and confluence for Port Graph Rewriting can be based on criteria developed for graphs like the one in [START_REF] Plump | Processes, Terms and Cycles: Steps on the Road to Infinity, Essays Dedicated to Jan Willem Klop[END_REF]. Similar sufficient conditions for strategic port graph rewriting are yet to be explored.

A strategy can be described by enumerating all its elements or more suitably by a strategy language. Various approaches have been followed, yielding different strategy languages such as ELAN [START_REF] Kirchner | Designing Constraint Logic Programming Languages using Computational Systems[END_REF][START_REF] Borovanský | Rewriting with strategies in ELAN: a functional semantics[END_REF], Stratego [START_REF] Visser | Stratego: A Language for Program Transformation based on Rewriting Strategies[END_REF], TOM1 [START_REF] Balland | Tom: Piggybacking rewriting on java[END_REF]4] or more recently Maude [START_REF] Martí-Oliet | Towards a strategy language for Maude[END_REF]. All these languages share the concern to provide abstract ways to express control of rule applications, by using reflexivity and the meta-level for Maude, or the notion of rewriting strategies for ELAN or Stratego. Strategies such as bottom-up, top-down or leftmost-innermost are higher-order features that describe how rewrite rules should be applied. TOM, ELAN and Stratego provide flexible and expressive strategy languages where high-level strategies are defined by combining low level primitives. We describe below the main elements of the TOM strategy language that are of interest for the example developed in this paper.

Following [START_REF] Kirchner | Strategic computations and deductions[END_REF], we can distinguish two classes of constructs in the strategy language: the first class allows construction of derivations from the basic elements, namely the rewrite rules. The second class corresponds to constructs that express the control, especially left-biased choice (or first). Moreover, the capability of expressing recursion in the language brings even more expressive power. Elementary strategies. An elementary strategy is either Identity which corresponds to the set Id of all empty derivations, F ail which denotes the empty set of derivations F ail, or a set of rewrite rules R which represents one-step derivations with rules in R at the root position. Sequence(ζ 1 , ζ 2 ), also denoted by ζ 2 ; ζ 1 , is the concatenation of ζ 1 and ζ 2 whenever it exists: for a given port graph

G, [ζ 1 ; ζ 2 ](G) = [ζ 2 ]([ζ 1 ](G)

A Calculus of Port Graphs

We now have all ingredients for defining the rewriting calculus of port graphs (ρ pg -calculus). The ρ pg -calculus generalizes ρ-calculus [START_REF] Cirstea | The rewriting calculus -Part I and II[END_REF] and ρ g -calculus [START_REF] Bertolissi | A Rewriting Calculus for Cyclic Higher-order Term Graphs[END_REF]. It inherits from ρ-calculus the fact that it generalizes λ-calculus through a much greater abstraction power that considers for matching not only a variable like in λ-calculus but a port graph with variables.

Syntax

We give the syntax of the calculus in Fig. 5. The objects of the calculus are port graphs that can be either a variable, a concrete port graph, a port graph rewrite rule (also called abstraction), the application of an abstraction to a port graph, or a multiset of such entities. The formal definition of the concrete port graphs in P and examples are presented in Sect. 2.

Port Graphs

G ::= X (Variables) | P (Concrete port graphs) | A (Abstraction) | A@G (Application) | G G
(Juxtaposition) Abstractions A ::= P ⇒ P (Port graph rewrite rule)

Figure 5. Syntax of the ρ pg -calculus

The juxtaposition operator for constructing multisets of port graphs is associative and commutative, i.e.,

(G 1 G 2 ) G 3 = G 1 (G 2 G 3 ) and G 1 G 2 = G 2 G 1 , for any G 1 , G 2 , G 3 ∈ G.
In the same time, the juxtaposition operator models a random and concurrent choice of an abstraction A and a concrete port graph G such that the application of A on G is successful. The application operator is a particular node with ports, denoted @, and it models the effective interaction between an abstraction and a port graph by connecting them.

Basic Reduction Semantics

The semantics of the ρ pg -calculus corresponds to a system whose states consist of a multiset of concrete port graphs and port graph rewrite rules where any two entities interact non-deterministically as in a Brownian motion. Two juxtaposed port graphs are not reduced in the calculus, whereas the juxtaposition of an abstraction and a port graph gives rise to an application via the following rule:

A G -→ A@G (1)
The application operator @ is defined to apply an abstraction A to a concrete port graph G. All steps computing A@G, including matching and replacing, are expressible using port graphs by considering additional auxiliary nodes and extending the reduction relation with some graphical reduction rules. This mechanism is internalized in the calculus and we do not present it here since it is too technical for the purpose of this paper. A successful reduction of A@G yields a port graph G ′ such that G → A G ′ according to a chosen matching solution, while a matching failure returns the initial abstraction and port graph unchanged:

A@G -→ G ′ if G → A G ′ (2) A@G -→ A G otherwise (3)
Instead of having this highly non-deterministic and nonterminating behaviour of port graph rewrite rules application, one may want to introduce some control to compose or choose the rules to apply, possibly exploiting failure information. This is possible by defining strategies as port graph rewrite rules, and by introducing an explicit port graph reduced to a failure node.

In the following, when we want to emphasize the use of strategies as abstractions, the reduction rule (2) giving the basic semantics of the juxtaposition operator is written by replacing the abstraction A by a strategy S.

Failure Handling

A successful computation of S@G yields a concrete port graph G ′ such that G rewrites to G ′ by strategic port graph rewriting under the strategy S. If a failure occurs during the matching reduction rules, we handle it explicitly by considering a failure node, denoted by stk:

S@G -→ G ′ if G → S G ′ (4) S@G -→ stk otherwise (5)
In addition, the following two reductions concerning stk are necessary for defining the basic cases of the definitions of other strategies (like first and seq later on): S@stk -→ stk (6) S stk -→ S (7)

Strategies as Abstractions

In this section, we define strategies as objects of the calculus, using the basic constructs, as one can do in λ-calculus or γ-calculus. For such definition we use a similar approach to the one used in [START_REF] Cirstea | Rewrite strategies in the rewriting calculus[END_REF] where rewrite strategies are encoded by rewrite rules. Let us consider for the rewrite strategies given in Sect. 4 the following objects: id for Id, fail for F ail, first for F irst, seq for ; , try for T ry, repeat for Repeat. The application operator for strategies [ ]( ) from Sect. 4 corresponds to the application operator @. We also need to extend the syntax of the calculus by considering abstractions with arbitrary port graphs in the right-hand side, i.e., of the form P ⇒ G.

Let S, S 1 , S 2 denote strategies. We encode the strategies as the following port graph rewrite rules: id

X ⇒ X fail X ⇒ stk seq(S 1 , S 2 ) X ⇒ S 2 @(S 1 @X) first(S 1 , S 2 )
X ⇒ ((S 1 @X) (stk ⇒ S 2 @X)@(S 1 @X)) The two composed strategies T ry and Repeat are then easily defined as follows:

try(S)
first(S, id) repeat(S) try(seq(S, repeat(S)))

Refined Reduction Semantics

Building now on these strategy definitions, we can restate properly the main reduction rule modeling the interaction between two port graphs using a failure catching mechanism: if S@G reduces to the failure, i.e., to the stk node, then the strategy try(stk ⇒ S G) restores the initial port graphs subjects to reduction. S G -→ try(stk ⇒ S G)@(S@G) [START_REF] Banâtre | Chemical Specification of Autonomic Systems[END_REF] Due to the previous definitions of try and first, and assuming that S is itself built from basic rewrite rules and from the constructions of the strategy language, the righthand side of rule ( 8) is (or reduces to) a port graph expressed in the syntax defined in Figure 5 enriched with stk.

Two further refinements are worth considering, in order to handle multiple results and to ensure, whenever needed, persistency of abstractions.

Multiple results

The successful application of an abstraction or strategy to a concrete port graph produces a new concrete port graph, built according to one chosen matching solution. An alternative would be to consider a structure of all concrete port graphs corresponding to the different matching solutions.

For instance, we may consider the set structure with stk neutral element, and ≀ the associative and commutative constructor. Then an interaction S@G reduces either to stk or to a structure G 1 ≀ . . . ≀ G k with G i = stk, for every i = 1, . . . , k and the following reduction rule is necessary for defining the interaction of a strategy with such a structure:

S (G 1 ≀ G 2 ) -→ (S G 1 ) ≀ (S G 2 ) (9)
However we do not develop further this alternative in this paper.

Persistent Strategies

At this level of definition of the calculus, rules or strategies are consumed by a non-failing interaction with a concrete port graph. One advantage is that, since we work with multisets of port graphs, a rule or a strategy can be given a multiplicity, and each interaction between the rule or strategy and another port graph consumes one occurrence. This permits controlling the maximum number of times an interaction can take place.

But sometimes, it may be suitable to have persistency of the information concerning the available abstraction and thus the persistency of a given possible interaction. In this case, the abstraction should not be consumed by the reduction. For that purpose, we define the persistent strategy that applies a strategy given as argument and, if successful, replicates itself. Indeed a failure will remain a failure: S! X ⇒ first(stk ⇒ stk, Y ⇒ Y S!)@(S@X)

Strategies for Autonomic Computing

In autonomic computing, systems and their components reconfigure themselves automatically according to directives (rewrite rules and strategies) given initially by administrators. Based on these primary directives and their acquired knowledge along the execution, the systems and their components seek new ways of optimizing their performance and efficiency via new rewrite rules and strategies that they deduce and include in their own behavior. Since there is no ideal system, functioning problems and malicious attacks or failure cascades may occur, and the systems must be prepared to face them and solve them. Let us consider here four aspects that an autonomic system must handle, namely self-configuration, self-healing, self-protection and self-optimization. In the following, we show how these aspects can be handled by an autonomic mail delivery system, inspired from [START_REF] Banâtre | Chemical Specification of Autonomic Systems[END_REF] and modeled using the ρ pg -calculus. For this purpose some additional rewrite rules are defined. In addition to the previously presented concepts, we assume a few more information available in the nodes and ports, which corresponds to existing notions in graph theory. In particular, each port has a degree information that counts the number of incoming and outgoing edges connecting it to other nodes of the concrete port graph. In our running example, this information allows us to express, through conditions in the rules, that a port is saturated, or on the contrary that it has no incident edge.

Self-configuration

The self-configuration is simply described by the concurrent application of the five rules given in Fig. 3 using the reduction semantics introduced in Sect. 5.

Rule r6 in Fig. 6 specifies that a client recipient of a mail telling him to migrate to a server k ′ does so if the server k ′ has a free client port. We model a free client port on the server k ′ by a condition on its degree, specifying that there is no incident edge to that port. In a more visual way, we pictured this condition with a slashed edge. But how to deal with mails that will probably arrive later on the server k for the client i? The problem is solved by introducing in the system a new rule that will update the address of the migrating clients. It is possible that the application of a rewrite rule on a port graph introduces, besides modifying the port graph, a new rewrite rule. In addition, before a client migrates, he must get all mails addressed to him that are already on the server; this is modeled via the strategy first(repeat(r3), r6).

Another interesting problem may concern the operations of splitting and merging servers. Then biologically inspired port graph rules from Fig. 2 (a) and (c) could be applied as well for servers.

Self-healing

An autonomic system detects when a server crashes and the connection of the crashed server to the network is cut. It is expected to repair the problem of the clients connected to the crashed server and of the mails that were about to be sent from that particular server. Rule r7 creates a temporary server named TServer as a copy of the crashed server and connects it to the network (assuming there is a procedure checking if a server failed). The arrow node of the rule encodes the correspondence of all ports of the server node k, and consequently, all connections with the crashed server are recovered by the temporary server. Note that, for simplifying the graphical representation, we do not include all Since the server replacing the crashed one is temporary, all the clients must try rapidly to connect to not fully occupied servers in the system (rule r8). We graphically express that the server node j has a free client port, i.e., with no incident edges. The mails are forwarded to the network node via the rules r9 and r10. But all this must not happen before sending the mails already there to the clients of the crashed server (rule r11). Instead of simply adding all these rules to the system, we add the strategy r7; repeat(r11); repeat(first(r8, r9, r10)). By composing these rules in a strategy, the recovery from the server crash is assured. A rule should delete the temporary server when it no longer has clients nor pending messages.

Self-protection

When a spam arrives at a server node, the filtering rule r12 deletes it, assuming that the server has a procedure for deciding when a mail is a spam. The rules r13 and r14 are analogous to r12 but for a client node and a network node, assuming as well that both entities have their own spam detection procedure. In order to limit spam sending, the rule r14 should have a higher priority than r5, and the rule r12 a higher priority than r3. Then we replace r3 and r12 by try(r12); r3, and r5 and r13 by try(r14); r5.

When a client receives a mail and, based on a spam decision procedure, concludes that the mail is a spam, it deletes the mail and provides the server with a new rule specifying that from now on the server node should delete all mails of this kind. This behavior is specified by the rule r15 in

Self-optimization

Assuming that a server can determine when it is saturated, i.e., when it reaches the maximal load of incoming messages, a particular type of server for equilibrating the load of the saturated server is created by rule r16. Such an auxiliary server has a handler for connecting to the network node and to the saturated server node, and a port for incoming messages. We call a server with an associated server for equilibrating the load, an optimized server. Then, when the network has a message to dispatch to an optimized server, if the number of incoming messages in(k) on the optimized server is smaller that the incoming messages in(k.0) on its associated server, then the message goes to k (rule r17), else it goes to k.0 (rule r18). Since an auxiliary server is created due to an overload of incoming messages, it is obvious that the next message(s) from the network node will be dispatched to the auxiliary node; hence rule r18 will be executed before rule r17, which is expressed by the strategy first(r18, r17). A message is dispatched from k.0 to k (rule r19) when in(k) < in(k.0). If an optimised server fails, then the rule r20 creates a temporary server similarly to rule r7 which in addition recovers all messages on the auxiliary server which it deletes.

Embedding Runtime Verification

We have shown in Sect. 6 how a particular autonomic system can be modeled using the ρ pg -calculus. The model should also ensure formally that the intended self-managing specification of the system helps indeed preserving the properties of the system. Some properties can be verified by checking the presence of particular port graphs. Such properties can be easily encoded as concrete port graphs, abstractions, or strategies, hence as entities of the calculus. Consequently, the properties can be placed at the same level as the specification of the modeled system and they can be tested at any time.

An invariant of the system can be expressed as a port graph rewrite rule with identical sides, G ⇒ G, testing the presence of a port graph G. The failure of the invariant is handled by a failure port graph STK that does not allow the execution to continue. The strategy verifying such an invariant is then:

first(G ⇒ G, X ⇒ STK)! Such strategy is useful for instance to ensure, in our running example, the persistency of a given critical server of the network, or may be used also to check that there is always a minimal number of servers available in the network. From another perspective, we express the unwanted occurrence of a concrete port graph G in the system using the strategy:

(G ⇒ STK)! In practice, such strategies are employed in model checking applications to test unwanted situations.

In both cases above, instead of yielding the failure STK signalling that a property of the system is not satisfied, the problem can be "repaired" by associating to each property the necessary rules or strategies to be inserted in the system in case of failure. Such ideas need to be further explored

Conclusion

In this paper our main objective was to propose a formalism, the port graph calculus introduced in Section 5, for modeling autonomic systems.

From the computational point of view, we have shown that this calculus allows us to model concurrent interactions between port graph rewrite rules and concrete port graphs, as well as interactions between rewrite rules or interactions creating new rewrite rules. Thanks to strategies, some interactions may be designed with more control. The suitable balance between controlled and uncontrolled interactions is an interesting question to address for a given application.

Here again, biological systems may provide us with valuable intuitions.

From the verification point of view, we can take advantage of the classical techniques used in rewriting for checking properties of autonomic systems. For instance, confluence or critical pairs computations help detecting conflicts in a system evolution. Also some processes may be required to terminate when they are involved in computations. On the contrary, for known non-terminating processes, detecting periodicity of the processes may be of interest. Therefore, further work requires to address the verification of such properties for port graph rewriting. We have also outlined in this paper some ideas for runtime verification of properties in such systems, that need further exploration.

Figure 1 .

 1 Figure 1. A mail system configuration

Figure 2 .

 2 Figure 2. Some port graph rewrite rules: (a) splitting the node i in two; (b) deleting the node i; (c) merging the nodes i and j.

Figure 3 .

 3 Figure 3. Basic rules for the mail delivery system

Figure 4 .

 4 Figure 4. Rewriting steps

3 .

 3 Applying the strategy ζ on a set of objects consists in applying ζ to each element a of the set. The result is the union of [ζ](a) for all a.

Definition 7 (

 7 Strategic port graph rewriting) Given an abstract reduction system A = (O R , S R ) generated by a port graph rewrite system R, and a strategy ζ of A, a strategic port graph rewriting derivation (or port graph rewriting derivation under strategy ζ) is an element of ζ. A strategic port graph rewriting step under ζ is a rewriting step

Figure 6 .

 6 Figure 6. Rules for self-configuration and self-healing in the mail delivery system

Figure 7 .

 7 Figure 7. Rules for self-protection in the mail delivery system

Figure 8 .

 8 Figure 8. Rules for self-optimisation in the mail delivery system

  ). Control strategies. A few constructions are needed to build derivations, branching and to take into account the structure of the objects. first F irst(ζ 1 , ζ 2 ) applies the first strategy if it does not fail, otherwise it applies the second strategy; it fails if both strategies fail:[F irst(ζ 1 , ζ 2 )](G) = [ζ 1 ](G) if [ζ 1 ](G) does not fail else [ζ 2 ](G).fixpoint The µ recursion operator (comparable to rec in OCaml) is introduced to allow the recursive definition of strategies. µx.ζ applies the derivation in ζ with the variable x instantiated to µx.ζ, i.e., µx.ζ = ζ[x ← µx.ζ] All these strategies are then composed to build other useful strategies. A composed strategy is for instance T ry(ζ) = F irst(ζ, Id) which applies ζ if it can, and performs the identity strategy Id otherwise. Similarly, the Repeat combinator is used in combination with the fixpoint operator to iterate the application of a strategy: Repeat(ζ) = µx.T ry(ζ; x).

http://tom.loria.fr


M Léger

Elsa Lhotel
email: elsa.lhotel@neel.cnrs.fr

M Ciomaga Hatnean

J Ollivier

A R R Wildes

S Raymond

E Ressouche

G Balakrishnan

S Petit

Spin Dynamics and Unconventional Coulomb Phase in Nd2Zr2O7

come

Geometrical frustration is well known to be one of the key ingredients leading to unconventional states of matter, especially in magnetism [START_REF]Introduction to Frustrated Magnetism[END_REF][START_REF] Gardner | Magnetic pyrochlore oxides[END_REF]. Among them, spin ice and more generally Coulomb phases [START_REF] Henley | The "Coulomb phase" in frustrated systems[END_REF] have attracted significant interest. These can be considered as an original state of matter formed by disordered degenerate configurations where local degrees of freedom remain strongly constrained at the local scale by an organizing principle. In the case of spin ice, these degrees of freedom are Ising spins, sitting on the sites of a pyrochlore lattice formed of corner sharing tetrahedra and aligned along the axes which connect the corners of the tetrahedra to their center. The organizing principle, the "ice rule", states that each tetrahedron should have two spins pointing in and two out, in close analogy with the rule which controls the hydrogen position in water ice [START_REF] Harris | Geometrical frustration in the ferromagnetic pyrochlore Ho2Ti2O7[END_REF]. Importantly, the idea that this local constraint can be considered as the conservation law of an "emergent" magnetic flux (∇ • B = 0) was quickly imposed [START_REF] Isakov | Dipolar spin correlations in classical pyrochlore magnets[END_REF][START_REF] Henley | Power-law spin correlations in pyrochlore antiferromagnets[END_REF][START_REF] Castelnovo | Magnetic monopoles in spin ice[END_REF]. Quantum fluctuations can cause this flux to change with time, giving rise to an emergent electric field, and eventually to an emergent quantum electromagnetism [START_REF] Hermele | Pyrochlore photons: The U (1) spin liquid in a S = 1/2 threedimensional frustrated magnet[END_REF][START_REF] Shannon | Quantum ice: A quantum monte carlo study[END_REF][START_REF] Benton | Seeing the light: Experimental signatures of emergent electromagnetism in a quantum spin ice[END_REF]. This quantum spin ice state hosts spinon (monopole in the spin ice language [START_REF] Gingras | Quantum spin ice: a search for gapless quantum spin liquids in pyrochlore magnets[END_REF]) and photon like excitations. Despite much work, however, experimental evidence for this enigmatic physics remains elusive, with the possible exception of Pr 2 Hf 2 O 7 [START_REF] Sibille | Experimental signatures of emergent quantum electrodynamics in a quantum spin ice[END_REF]. Indeed, the conditions for the realisation of this so-called quantum spin ice state are drastic: transverse terms have to be sizable in the Hamiltonian to enable fluctuations out of the local Ising axes, but should remain small enough to prevent the stabilization of classical phases, called Higgs phases, characterized by ordered components perpendicular to these axes [START_REF] Gingras | Quantum spin ice: a search for gapless quantum spin liquids in pyrochlore magnets[END_REF][START_REF] Savary | Coulombic quantum liquids in spin-1/2 pyrochlores[END_REF][START_REF] Hao | Bosonic many-body theory of quantum spin ice[END_REF].

The pyrochlore material Nd 2 Zr 2 O 7 offers the opportunity to approach this issue. Recent studies suggest that below 1 K this compound hosts a correlated state, which could be a remarkable novel example of Coulomb phase [START_REF] Petit | Observation of magnetic fragmentation in spin ice[END_REF][START_REF] Xu | Order out of a Coulomb phase and Higgs transition: Frustrated transverse interactions in Nd2Zr2O7[END_REF]. This phase would be described by a "two in -two out" rule as in spin ice, but built on a pseudospin component different from the conventional 111 Ising one. The "all in -all out" (AIAO) ordering previously observed below T N ≈ 300 mK [START_REF] Lhotel | Fluctuations and all-in-all-out ordering in dipole-octupole Nd2Zr2O7[END_REF][START_REF] Xu | Magnetic structure and crystal-field states of the pyrochlore antiferromagnet Nd2Zr2O7[END_REF] would then correspond to the pseudospin ordering in directions perpendicular to the components responsible for the "high temperature" Coulomb phase. It was proposed that a Higgs mechanism may account for this transition [START_REF] Xu | Order out of a Coulomb phase and Higgs transition: Frustrated transverse interactions in Nd2Zr2O7[END_REF]. Such a process is invoked in U (1) quantum spin liquids when the deconfined spinon excitations undergo a Bose-Einstein condensation, resulting in a Higgs phase along with a gapped photon excitation [START_REF] Savary | Coulombic quantum liquids in spin-1/2 pyrochlores[END_REF][START_REF] Pekker | Amplitude / Higgs modes in condensed matter physics[END_REF][START_REF] Chang | Higgs transition from a magnetic Coulomb liquid to a ferromagnet in Yb2Ti2O7[END_REF].

In this letter, we show that the paramagnetic phase of Nd 2 Zr 2 O 7 does carry elastic spin ice-like correlations, and thus confirm the proposed Coulomb phase picture above T N . We present a detailed study of the spin dynamics as a function of temperature and explore the nature of this Coulomb phase above and close to the transition. The spin excitations of Nd 2 Zr 2 O 7 deep in the AIAO phase include a peculiar spectrum with a flat band at the energy E 0 ≈ 70 µeV characterized by a spin icelike Q-dependence [START_REF] Petit | Observation of magnetic fragmentation in spin ice[END_REF][START_REF] Lhotel | Evidence for dynamic kagome ice[END_REF][START_REF] Xu | Anisotropic exchange hamiltonian, magnetic phase diagram, and domain inversion of Nd2Zr2O7[END_REF]. Using neutron scattering experiments, we report the temperature dependence of the gap E 0 , and reveal that this gap persists above T N . This result is robust, and withstands a small substitution at the Zr site. The spectra recorded above T N do not show the spinon continuum expected in the Higgs scenario. Instead, we observe dispersive features reminiscent of the AIAO ordered phase superimposed on the Coulomb phase signal. This coexistence suggests that a strong exchange competition is at work in this temperature range, emphasizing the originality of the Coulomb phase above the transition.

The single crystal samples used in this work are the same as in our previous studies (labeled #1 [START_REF] Petit | Observation of magnetic fragmentation in spin ice[END_REF][START_REF] Lhotel | Fluctuations and all-in-all-out ordering in dipole-octupole Nd2Zr2O7[END_REF][START_REF] Lhotel | Evidence for dynamic kagome ice[END_REF] and #2 [START_REF] Lhotel | Evidence for dynamic kagome ice[END_REF]). In addition, a single crystal of Nd 2 (Zr 1-x Ti x ) 2 O 7 , with x = 2.4 % (Sample #3) was investigated (See details in the supplementary material [START_REF]See Supplementary Material: Single crystal growth, Neutron diffraction, Polarized neutron experiments, Inelastic neutron experiments[END_REF]). Their magnetic properties were measured in very low temperature SQUID magnetometers developed at the Institut Néel [START_REF] Paulsen | Dc magnetic measurements[END_REF]. The composition and magnetic structure at low temperature were determined using the D23 (CEA-CRG@ILL) neutron diffractometer [START_REF]See Supplementary Material: Single crystal growth, Neutron diffraction, Polarized neutron experiments, Inelastic neutron experiments[END_REF]. Polarized neutron scattering experiments were carried out at D7 (ILL) on Sample #1. Inelastic neutron scattering (INS) experiments were carried out on the IN5 (ILL) disk chopper time of flight spectrometer on all samples and on the triple axis spectrometer IN12 (CEA-CRG@ILL) for Sample #1. The INS data have been analyzed using the cefwave software developed at LLB.

The XYZ Hamiltonian proposed to describe the properties of Nd based pyrochlores due to the peculiar dipolaroctupolar character of the Nd 3+ ion [START_REF] Huang | Quantum spin ices and topological phases from dipolar-octupolar doublets on the pyrochlore lattice[END_REF], writes:

H = i,j J x τ x i τ x j + J y τ y i τ y j + J z τ z i τ z j + J xz (τ x i τ z j + τ z i τ x j )
(1) In this Hamiltonian, τ i is not the actual spin, but a pseudospin which resides on the rare-earth sites of the pyrochlore lattice. Its z component solely identifies to the usual magnetic moment and is directed along the local 111 directions of the tetrahedra of the pyrochlore lattice. This Hamiltonian can be rewritten by rotating the x and z axes in the (x, z) plane by an angle θ. In this (x, z) rotated frame, the relevant parameters of the Hamiltonian H are labeled Jx,y,z , leading to [START_REF] Huang | Quantum spin ices and topological phases from dipolar-octupolar doublets on the pyrochlore lattice[END_REF][START_REF] Benton | Quantum origins of moment fragmentation in Nd2Zr2O7[END_REF]:

H XYZ = i,j Jx τ x i τ x j + Jy τ ỹ i τ ỹ j + Jz τ z i τ z j with tan(2θ) = 2J xz J x -J z (2)
With time and maturation of the subject, the estimated parameters for Nd 2 Zr 2 O 7 have evolved. Determinations of the Ji parameters are based on the spin wave spectra measured at very low temperature in zero field [START_REF] Petit | Observation of magnetic fragmentation in spin ice[END_REF][START_REF] Xu | Anisotropic exchange hamiltonian, magnetic phase diagram, and domain inversion of Nd2Zr2O7[END_REF][START_REF] Benton | Quantum origins of moment fragmentation in Nd2Zr2O7[END_REF] or applied field [START_REF] Lhotel | Evidence for dynamic kagome ice[END_REF], while the angle θ is deduced from the Curie-Weiss temperature [START_REF] Benton | Quantum origins of moment fragmentation in Nd2Zr2O7[END_REF] and/or the ordered AIAO magnetic moment [START_REF] Lhotel | Evidence for dynamic kagome ice[END_REF][START_REF] Xu | Anisotropic exchange hamiltonian, magnetic phase diagram, and domain inversion of Nd2Zr2O7[END_REF]. The sets of reported parameters are summarized in Table I, where we have added the parameters refined here for the Nd 2 (Zr 1-x Ti x ) 2 O 7 sample (Sample #3) [START_REF]See Supplementary Material: Single crystal growth, Neutron diffraction, Polarized neutron experiments, Inelastic neutron experiments[END_REF] and have revisited the ones of Sample #1. Interestingly, very similar Ji parameters are obtained for the different samples, despite differences with regard to the amount of impurities as well as the Néel temperature and the ordered moment along z.

The J parameters lead to an ordered AIAO ground state, where the pseudospins point along the (local) direction z, turned around the z-axis towards the x-axis by the angle θ [START_REF] Benton | Quantum origins of moment fragmentation in Nd2Zr2O7[END_REF]. As shown by INS experiments, peculiar excitations are associated with this ground state. They manifest as an inelastic spin ice like flat mode at an energy E 0 ≈ 70 µeV, above which spin wave branches disperse (See Figure 4a for Sample #1) [START_REF] Petit | Observation of magnetic fragmentation in spin ice[END_REF]. This excitation spectrum is understood in the framework of the dynamic fragmentation [START_REF] Benton | Quantum origins of moment fragmentation in Nd2Zr2O7[END_REF][START_REF] Brooks-Bartlett | Magneticmoment fragmentation and monopole crystallization[END_REF] as the sum of a dynamic divergencefree contribution, giving rise to the flat mode at E 0 and of a dynamic curl-free contribution, which takes the form of the dispersing branches. These spin waves correspond to the propagation of magnetically charged excitations and have a spectral weight made of half-moons in reciprocal space [START_REF] Petit | Observation of magnetic fragmentation in spin ice[END_REF][START_REF] Yan | Half moons are pinch points with dispersion[END_REF].

Instantaneous spin-spin correlations S(Q) were measured in Sample #1 as a function of temperature between 60 mK and 1 K through polarized neutron scattering experiments and are displayed in Figure 1 [START_REF]See Supplementary Material: Single crystal growth, Neutron diffraction, Polarized neutron experiments, Inelastic neutron experiments[END_REF]. These measurements integrate over the neutron energy loss up to 3.5 meV, and thus contain both elastic and inelastic signals. At 1 K, a spin ice pattern can barely be observed, revealing the onset of a Coulomb phase. Upon cooling, the spin ice pattern becomes clearly visible below 600 mK. At 450 mK, the magnetic moment m 1 responsible for the spin ice-like diffuse scattering is estimated to 2.3 ± 0.2 µ B [START_REF]See Supplementary Material: Single crystal growth, Neutron diffraction, Polarized neutron experiments, Inelastic neutron experiments[END_REF], i.e. almost the full Nd moment [START_REF] Lhotel | Fluctuations and all-in-all-out ordering in dipole-octupole Nd2Zr2O7[END_REF][START_REF] Xu | Magnetic structure and crystal-field states of the pyrochlore antiferromagnet Nd2Zr2O7[END_REF]. In addition to this signal, below 800 mK, magnetic diffuse scattering spots appear around (220), (113) and symmetry related positions. Intensity on these positions increases with cooling until they transform into Bragg peaks below T N (285 mK in this sample) characteristic of the AIAO phase. At low temperature, the corresponding ordered magnetic moment is m 2 = m ord = 0.8 ± 0.05 µ B (from diffraction measurements [START_REF] Lhotel | Fluctuations and all-in-all-out ordering in dipole-octupole Nd2Zr2O7[END_REF]) and the magnetic contribution to the spin ice like diffuse scattering amounts to m 1 = 1.8 ± 0.2 µ B [START_REF]See Supplementary Material: Single crystal growth, Neutron diffraction, Polarized neutron experiments, Inelastic neutron experiments[END_REF] (see Figure 1d). The moment embedded in the spin ice correlations is thus at maximum around 300 mK (i.e. around T N ) and slightly decreases at lower temperature. The diffuse scattering observed in the vicinity of the Bragg peak positions above T N might arise from AIAO diffuse scattering just above the ordering transition, but could also be signatures of deconfined excitations, as proposed in Ref. [START_REF] Xu | Order out of a Coulomb phase and Higgs transition: Frustrated transverse interactions in Nd2Zr2O7[END_REF].

Sample / Ref. m ord (µ B ) T N (mK) Hamiltonian parameters (K) θ (rad) Jx Jy Jz Jx /| Jz | #1 0.8 ± 0.
To determine the spectral profile contained in those magnetic correlations, and especially the elastic or inelas-tic nature of the spin ice correlations associated to m 1 , INS measurements have been carried out on the three aforementioned samples (see Table I) as a function of temperature. To highlight the possible presence of an inelastic flat mode, the Q-integrated spectral function S(E) = dQS(Q, E) was computed. As this quantity is akin to a density of states, it enhances the contribution of the flat modes contained in the spectrum. Figure 2 displays S(E) at different temperatures. As previously shown [START_REF] Petit | Observation of magnetic fragmentation in spin ice[END_REF], the inelastic flat band is clearly seen at low temperature. It is still visible at finite energy close to T N (320 mK for Sample #2 and 315 mK for Sample #3) and above T N (340 mK for Sample #1), yet broadens significantly upon warming. At the highest temperatures, the signal looks almost quasielastic. To obtain a quantitative insight into the temperature evolution of the mode, data were fitted for the three samples (as shown in Figure 2a for Sample #1) to the following model [START_REF]See Supplementary Material: Single crystal growth, Neutron diffraction, Polarized neutron experiments, Inelastic neutron experiments[END_REF]:

S(E) = b + I c (E) + F (E, T ) × [S 0 (E) + S 1 (E)] (3)
b is a flat background, I c (E) is a Gaussian function centered at zero energy to account for the elastic incoherent scattering. F (E, T ) = 1 + n(E, T ) is the detailed balance factor (n is the Bose-Einstein distribution). S 0 (E) and S 1 (E) are two Lorentzian profiles, centered on the energy E 0,1 and of intensity I 0,1 , which represent respectively the flat band and the dispersive mode typical of the spin wave spectrum in Nd 2 Zr 2 O 7 .

The determined positions E 0 and intensities I 0 are shown in Figure 3 as a function of the temperature normalized to T N for the three samples. As anticipated from Figure 2, with increasing temperature, the band at E 0 softens and broadens while its intensity decreases. Nevertheless, E 0 is non-zero at T N and a persistent dynamical behaviour is observed in all samples at and above T N , up to about 2T N . Finally, the width of the features above the flat mode makes it hard to extract quantitative information from S 1 . However, close examination of S(Q, E) measured for Sample #1 above T N at 340 mK (see Figure 4) shows that, in all investigated directions, besides a strong quasielastic contribution (the inelastic mode being hardly discernible due to the energy resolu- tion and the color scale), weak features are present close to the position of the low temperature dispersions. These spin wave fingerprints, highlighted by arrows on Figure 4, are not expected in three dimensional paramagnets, but recall observations in low-dimensional magnets (see Ref. [START_REF] Chatterji | Spin dynamics of YMnO3 studied via inelastic neutron scattering and the anisotropic Hubbard model[END_REF] and references therein). They are not compatible with the excitation spectrum expected in the presence of monopole creation and hopping [START_REF] Xu | Order out of a Coulomb phase and Higgs transition: Frustrated transverse interactions in Nd2Zr2O7[END_REF].

Several striking features emerge from these measurements. INS experiments reveal that the intensity I 0 of the inelastic spin ice mode decreases when increasing temperature. Since D7 polarized experiments show that the full spin ice correlations, elastic and inelastic, are strongest around T N , the spin ice pattern observed above T N must contain a new spin ice contribution, likely elastic, and different from the inelastic mode at E 0 . This is confirmed by magnetization measurements, which point to ferromagnetic-like correlations, as expected for spin ice [START_REF]See Supplementary Material: Single crystal growth, Neutron diffraction, Polarized neutron experiments, Inelastic neutron experiments[END_REF]. This elastic signal could not be directly identified in the elastic line of the IN5 data [START_REF]See Supplementary Material: Single crystal growth, Neutron diffraction, Polarized neutron experiments, Inelastic neutron experiments[END_REF] certainly due to background issues, but we should stress that the D7 polarization analysis is definitely the most appropriate way to remove properly nuclear contributions and visualize small magnetic contributions. These results thus point to the coexistence of two spin ice-like contributions, an elastic and an inelastic one with different origins, and different temperature dependences.

These two contributions can be understood as the man-ifestation of the strong competition at play between the pseudospin components of Nd. The negative value of Jz (see Table I) promotes an AIAO phase built on τ z while the positive Jx favors a Coulomb phase, similar to a spin ice phase, but built on τ x. For Jx /| Jz | ≈ 2, the value determined for Nd 2 Zr 2 O 7 , the former is stabilized at low temperature and the latter at finite temperature, due to the large entropy associated to the Coulomb phase. In these two regimes, spin ice contributions are expected, an elastic one in the Coulomb phase at "high" temperature, and an inelastic one in the AIAO ordered phase (accompanied by dispersive excitations). Remarkably, the observable τ z , which corresponds to the magnetic dipolar moment along the local 111 axes, is a combination of the τ x and τ z components of the pseudospin. It thus holds the two competing contributions (AIAO and Coulomb), which contrasts with the conventional spin ice case where the z component carries elastic spin ice correlations only.

The present results shed light on the manner in which the system evolves from the "high" temperature Coulomb phase to the low temperature AIAO ordered phase. At high temperature, around 1 K, the elastic spin ice signal characteristic of the Coulomb phase of the τ x component appears first. Upon cooling, the inelastic spin ice contribution along with dispersive spin waves branches emerge above T N and coexist with the elastic one. They can naturally be considered as excitations stemming from the short-range AIAO correlations of the τ z component observed below 800 mK (see Figure 1).

The system enters the long-range AIAO ordered state at a temperature T N ≈ 300 mK. It corresponds to about | Jx |/4, thus to a temperature scale far above the one obtained theoretically for the stabilization of the quantum regime of spin ice, which is estimated to a few percents of the characteristic exchange interaction [START_REF] Savary | Spin liquid regimes at nonzero temperature in quantum spin ice[END_REF][START_REF] Huang | Dynamics of topological excitations in a model quantum spin ice[END_REF]. This indicates that the Coulomb phase remains in its thermal regime down to T N . Surprisingly, the ordering temperature is larger than semi-classical Monte-Carlo calculations predictions [START_REF] Xu | Order out of a Coulomb phase and Higgs transition: Frustrated transverse interactions in Nd2Zr2O7[END_REF]. At T N , the excitation spectrum is gapped, with the coexistence between the elastic spin ice component and the inelastic spectrum typical of AIAO ordering. The lack of a spinon continuum which would condense at T N seems to preclude a transition driven by a Higgs mechanism.

Deeper in the AIAO phase, the inelastic componenttogether with the AIAO ordering -develops at the expense of the elastic component. The weak maximum of the spin ice m 1 moment around T N can thus be interpreted as due to the rise of the inelastic spin ice mode along with the persistence of the elastic contribution of the Coulomb phase. The coexistence of the elastic and inelastic signals is consistent with MC calculations [START_REF] Xu | Order out of a Coulomb phase and Higgs transition: Frustrated transverse interactions in Nd2Zr2O7[END_REF], even if, close to T N , the two modes are less distinguishable in the experiments than in the calculations due to the strong broadening of the inelastic mode. Although some distribution is observed between the samples, the measured temperature dependence of the inelastic spin ice mode, described by the energy E 0 (T ) and intensity I 0 (T ), is also consistent with calculations [START_REF]See Supplementary Material: Single crystal growth, Neutron diffraction, Polarized neutron experiments, Inelastic neutron experiments[END_REF], despite a slightly stronger inelastic component in experiments above T N (see Figure 3).

In summary, we find that with increasing temperature, the now well-established flat spin ice band characteristic of the AIAO ground state in Nd 2 Zr 2 O 7 , softens while its intensity decreases. The energy of this mode remains however finite at and above T N and becomes overdamped with increasing the temperature further. At the same time, a new elastic spin ice component appears. The nature of the correlated phase above T N is thus highly unconventional with the coexistence of an (elastic) Coulomb phase and fragmented excitations, resulting from the competition between the different terms of the Hamiltonian. Our observations support a picture where the AIAO ordering arises from a thermal spin ice phase, a scenario which is well accounted for by semi-classical MC calculations from Ref. [START_REF] Xu | Order out of a Coulomb phase and Higgs transition: Frustrated transverse interactions in Nd2Zr2O7[END_REF], and is different from the proposed Higgs transition. When increasing the ratio Jx /| Jz |, reentrant behaviors are predicted [START_REF] Xu | Order out of a Coulomb phase and Higgs transition: Frustrated transverse interactions in Nd2Zr2O7[END_REF] while the system approaches a quantum spin liquid ground state [START_REF] Benton | Quantum origins of moment fragmentation in Nd2Zr2O7[END_REF]. Tuning the parameters of the Hamiltonian (2) with novel materials would thus be of high interest to understand the unusual behavior of Nd 2 Zr 2 O 7 and explore the frontiers between thermal and quantum regimes. Unfortunately, it was not possible to determine intensities in absolute units from the D7 measurements. To determine the magnetic moment responsible for the spin ice-like diffuse scattering, we had to proceed in an alternative manner. To this end, we carried out a series of calculations, assuming a "theoretical sample crystal" consisting of Ising spins (of length unity) located at the rare earth sites of a pyrochlore lattice of size L. In an unpolarized experiment, the neutron intensity is proportional to the spin-spin correlations:

S(Q) = i,j a,b=x,y,z m i,a δ ab - Q a Q b Q 2 m j,b e iQ.(Ri-Rj )
The SF P z mode gives access to M y = i,j

m i .y Q m j .y Q e iQ.(Ri-Rj ) .
We considered n spin ice configurations generated on this pyrochlore lattice (via a Monte-Carlo algorithm) leading to the average spin ice structure factor I 1 . We also considered the case where the spins are arranged in an all in -all out (AIAO) ordering, leading to magnetic Bragg peaks with a structure factor denoted hereafter I 2 . Both I 1 and I 2 have then been weighted by the square magnetic moment m 1 and m 2 of the spin ice and AIAO contributions respectively. From diffraction data performed on D23 at 60 mK, we know that m 2 = 0.8 µ B at low temperature. The quantity V (I 2 + (m 1 /m 2 ) 2 I 1 ) is then compared to the experimental data, where V is a scaling factor. V has been determined by comparing the integrated intensities of calculations with the actual experiment, based upon the Q = (1, 1, -3) integrated intensity (the integration has been performed in precisely the same conditions). A good agreement is found for m 1 = 1.8 ± 0.2 µ B , as shown in Figure S2.

The scaling factor V being determined, the same treatment was applied to the data measured at larger temperatures, showing that m 1 slightly increases up to m 1 = 2.3 ± 0.2 µ B at 450 mK while m 2 is zero at this temperature.

TIME OF FLIGHT INELASTIC SCATTERING MEASUREMENTS

Inelastic neutron scattering experiments were carried out on the IN5 disk chopper time of flight spectrometer (ILL, France). A good compromise between flux, energy resolution and accessible Q space was obtained with a wavelength λ = 6 or 6.5 Å. However, to ensure a better energy resolution ∆E = 20 µeV, necessary to fully resolve the dynamic spin ice mode at E 0 , experiments were also conducted with λ = 8.5 Å. The data were processed with the Mantid [START_REF] Arnold | Mantid -data analysis and visualization package for neutron scattering and µsr experiments[END_REF] and horace [START_REF] Ewings | Horace: Software for the analysis of data from single crystal spectroscopy experiments at time-of-flight neutron instruments[END_REF] softwares, transforming the recorded time of flight, sample rotation and scattering angle into energy transfer and Q-wave-vectors. The offset of the sample rotation was determined based on the Bragg peak positions. In all the experiments, the sample was rotated in steps of 1 degree and the counting time was about 10 minutes per sample position.

It should be noticed that a very long thermalization time was systematically necessary to cool down the sample to the lowest temperature. In addition, we realized that when warming up from the lowest temperature, the sample temperature was not necessarily the same as the temperature indicated by the thermometer. For this reason, when possible (depending on the ratio between the resolution and the temperature), we have refined the "true" temperature by fitting the negative energy part of the spectra. It leads to the temperatures indicated on Figures 2, 3 and 4 of the main text, which are quite different from the thermometer temperatures. These temperatures are summarized in Table S2.

INELASTIC SCATTERING MEASUREMENTS ON A TRIPLE AXIS SPECTROMETER

The temperature dependence of the spin dynamics in Sample #1 was also investigated on the cold TAS spectrometer IN12 (ILL, France). Scans at specific Q positions (0.5 0.5 2), (0 0 2.5) and (1.8 1.8 0) have been performed at different temperatures ranging from 50 up to 800 mK. Those positions were chosen since they probe different regions with respect to the dispersion. (0.5 0.5 2) essentially probes the flat spin ice band, (1.8 1.8 0) is sensitive to the zone boundary dispersive spin wave mode and (0.5 0.5 2) is somehow intermediate. A final wavevector k f = 1.05 Å-1 was used (in combination with nitrogen cooled Be filter) to ensure the best energy resolution, ∆E = 50 µeV. A magnetic field was also applied along [ 1 10]. After correction from the detailed balance factor, we computed the difference between data taken a given temperature T and the 800 mK data. Where applicable, we subtracted the data obtained at the same temperature but under a 1 T magnetic field. We could then extract the energy and intensity of the inelastic mode in the same way as for TOF measurements. The temperatures below T N were estimated from the intensity of the (220) magnetic Bragg peak. 113)). This is illustrated in Figure S3, which shows the dispersion along several reciprocal directions at 45 mK.

FIG. S3. Top: INS data taken at IN5 at 45 mK on the Sample #3 along high symmetry directions. Black and white dots are the energies E0 and E1 respectively, fitted according to the procedure described in the main text (see also equation (S1). Bottom: Spin wave calculations performed with the parameters given in Table 1 (main text).

To determine the parameters of the XYZ Hamiltonian

H XYZ = i,j Jx τ x i τ x j + Jy τ ỹ i τ ỹ j + Jz τ z i τ z j
(see also equation ( 2) of the main text), we use analytic calculations giving the energy of the spin ice band [START_REF] Benton | Quantum origins of moment fragmentation in Nd2Zr2O7[END_REF]:

E 0 = (3| Jz | -Jx )(3| Jz | -Jy )
as well as the energy of the dispersive modes at some high symmetry Q vectors [START_REF] Xu | Anisotropic exchange hamiltonian, magnetic phase diagram, and domain inversion of Nd2Zr2O7[END_REF]: the Hamiltonian (1):

Q = (110), ( 112
H = i,j J x τ x i τ x j + J y τ y i τ y j + J z τ z i τ z j + J xz (τ x i τ z j + τ z i τ x j )
The ground state configuration is first determined by solving this Hamiltonian at the mean field level, where the expectation values τ x,y,z j are determined in a self-consistent manner. Spin wave calculations are performed using a generalized susceptibility approach out of the obtained configurations. Finally, the neutron cross section is calculated from τ z i τ z j correlations. Notably, the simulations performed with the parameters of Table 1 (main text) reproduce quite well the data, as shown in Figure S3.

Temperature dependence of the spin dynamics

Inelastic data in Sample #3 were fitted in the whole measured Q space using the model described in the main text: Figure S4 shows the energy E 0 of the flat band at different temperatures in the form of a map over the sector probed by TOF measurements. Figure S5 displays the intensities I 0 (panel a, upper row) and I 1 (panel b, lower row). The map on the right of the same figure shows the energy E 1 of the dispersive spin wave mode. To check the overall consistency of the fitting procedure, dashed lines visualize the directions of the scans reported in Figure S3.

S(Q, E) = b + I c (E) + F (E, T ) × [S 0 (E) + S 1 (E)] (
Note that for Sample #1, the fit was carried out at selected Q values (Q = (0.8 0.8 0.8), (1. Finally, aiming at identifying a possible elastic contribution with the spin ice structure factor, Figure S6 shows the temperature evolution of the intensity of the incoherent elastic contribution, i.e. the dominant contribution I c (E = 0) in the spectrum, to which the 45 mK map was subtracted. Within experimental uncertainties, these maps are featureless and no spin ice pattern can be clearly distinguished. The main text of the present work compares the measured temperature dependence of E 0 and I 0 in our three samples with Monte Carlo calculations reported in Ref. [START_REF] Xu | Order out of a Coulomb phase and Higgs transition: Frustrated transverse interactions in Nd2Zr2O7[END_REF]. These calculations use effective exchange parameters from Ref. 22 (reference [22] of the main text), which are detailed in Table 1 of the main text. They give a Néel temperature of 0.18 K.

From these calculations, as illustrated in the Figure 3 of Ref. [START_REF] Xu | Order out of a Coulomb phase and Higgs transition: Frustrated transverse interactions in Nd2Zr2O7[END_REF], two contributions are obtained: a spin ice elastic contribution which projects onto the z axis with a factor sin 2 θ, as well as spin waves features characteristic of the AIAO phase, with especially a flat spin ice band. To compare quantitatively these results with our data, those theoretical curves have been fitted to two modes, following:

I(E) = I 0 e -4 log 2( E-E 0 ) δ 0 ) 2 + I 0 1 + ( E δ 0 ) 2 (S2)
The result of this fit is illustrated in Figures S7(b) and S7(c), which display respectively the intensity of the modes (I 0 and I 0 ) and the position E 0 of the flat spin ice band. Interestingly, this energy remains finite even above the calculated critical temperature T N = 0.18 K.

CORRELATIONS IN MAGNETIZATION MEASUREMENTS

In a paramagnet, isothermal magnetization curves scale as a function of the variable H/T . The deviations to this scaling give insight into the nature of the correlations that develop in the system. Upon cooling, if the magnetization curve increases faster (slower) than the higher temperature curve, it is the signature of the development of ferromagnetic-like (antiferromagnetic-like) correlations.

We have plotted the magnetization as a function of H/T for Nd 2 Zr 2 O 7 , measured in Sample #1. As shown in Figure S8, the M (H/T ) curves rise above the 4.2 K curves upon cooling down to 1 K, which indicates the development of ferromagnetic correlations, consistent with the elastic spin ice picture inferred from our neutron scattering measurements.

At 500 mK, the curves lie between the 1 and 4.2 K curves (not shown on the figure for clarity), showing the development of antiferromagnetic correlations compared to 1 K, but the persistence of global ferromagnetic correlations. These antiferromagnetic correlations will end in the all in -all out ordering at about 300 mK.

FIG. 1 .

 1 FIG. 1. (a-c) Magnetic instantaneous correlations in Sample #1 as a function of temperature. The 10 K dataset has been subtracted as a background reference. (d) "Spin ice" moment m1 and AIAO ordered moment m2 along z as a function of temperature [23]. Lines are guides to the eye.

FIG. 2 .

 2 FIG. 2. Spectral function S(E) at different temperatures [23] measured at a wavelength λ = 8.5 Å, hence an energy resolution of 20 µeV: (a) in Sample #1, integrated around Q = (0.8 0.8 0.8). The grey and red lines correspond to the fitted incoherent elastic Ic and inelastic S0 contributions respectively. (b) and (c): integrated over the measured Q range in Samples #2 (b) and #3 (c).

  FIG. 3.(a) E0 and (b) I0 as a function of reduced temperature T /TN obtained from measurements on IN5 (dotssee Figure2) and IN12 (triangles), together with results from Monte-Carlo (MC) calculations from Ref. 16 (red dots)[START_REF]See Supplementary Material: Single crystal growth, Neutron diffraction, Polarized neutron experiments, Inelastic neutron experiments[END_REF]. Lines are guides to the eye. The large I0 experimental value when E0 = 0 is the signature of the persistent quasielastic contribution above TN.

FIG. 4 .

 4 FIG. 4. INS spectra of Sample #1 along several high symmetry directions at 60 mK (a) and 340 mK (b), measured on IN5 with λ=6 Å. Red arrows highlight the dispersive modes and their fingerprints above TN.

  The work at the University of Warwick was supported by EPSRC, UK through Grant EP/T005963/1. M.L. and S.P. acknowledge financial support from the French Federation of Neutron Scattering (2FDN) and Université Grenoble-Alpes (UGA). M.L., E.L. and S.P. acknowledge financial support from ANR, France, Grant No. ANR-19-CE30-0040-02. S.P. and E.L. acknowledge F. Damay for helpful remarks and J. Xu for providing the data of his calculations. E.L. acknowledges C. Paulsen for the use of his magnetometers.

FIG

  FIG. S1. (a) Refinement of the crystal neutron structure factors at 10 K, giving a refined Ti content equal to 2.4 %. (b) Measured intensity on the magnetic peaks (220), (113), (351) and (260), and symmetry related peaks at 60 mK, obtained from the difference with the 10 K data, and compared to the refined intensity.

  SPIN DYNAMICS IN THE TI DOPED SAMPLE (SAMPLE #3) Determination of the parameters Inelastic neutron scattering data carried out carried out at IN5 (ILL) on a single crystal sample show little evolution compared to the pure sample. The inelastic flat spin ice mode is observed at E 0 ≈ 70 µeV, while the dispersing mode stemming from the pinch point positions unfolds towards the zone centers, for instance (220) or (

  FIG. S4. Temperature dependence of the flat spin ice band at E0 deduced from the fit in Sample #3, as described in the main text. The portion of (Q, E) space corresponds to the sector probed by TOF measurements with λ=8.5 Å.

  S1) b is a flat background (wavelength dependent), I c is a Gaussian function centered at zero energy to represent the elastic incoherent scattering. F (E, T ) = (1 + n(E)) is the detailed balance factor, and S 0 and S 1 are two Lorentzian profiles which represent respectively the flat band and the dispersive mode typical of the spin wave spectrum in Nd 2 Zr 2 O 7 .

  FIG. S5. (a) Temperature dependence of the intensity I0 of the flat spin ice band from the fit in Sample #3, as described in the main text. (b) shows the intensity I1 of the dispersive mode, and (c) shows its energy E1. Dashed lines correspond to the directions of the cuts shown in Figure S3. The portion of (Q, E) space corresponds to the sector probed by TOF measurements with λ = 8.5 Å.

  FIG. S6. Temperature dependence of the intensity of the incoherent scattering Ic(E = 0) in Sample #3. The portion of (Q, E) space corresponds to the sector probed by TOF measurements with λ = 8.5 Å.

  FIG. S8. Magnetization M vs H/T measured for Sample #1 with the field applied along: (a) [100], (b) [110] and (c) [111] at 1, 1.8 and 4.2 K.

TABLE S2 .

 S2 Estimated effective temperatures in the different experiments performed on IN5.

Spin dynamics and unconventional Coulomb phase in Nd 2 Zr 2 O 7

Supplementary Material

SINGLE CRYSTAL GROWTH

Single crystals of Nd 2 (Zr 1-x Ti x ) 2 O 7 (x = 0 and 0.025) were grown by the floating zone method, using a four-mirror xenon arc lamp optical image furnace [START_REF] Ciomaga Hatnean | Growth of single-crystals of rare-earth zirconate pyrochlores, Ln2Zr2O7 (with ln=la, nd, sm, and gd) by the floating zone technique[END_REF][START_REF] Ciomaga Hatnean | Zirconate pyrochlore frustrated magnets: crystal growth by the floating zone technique[END_REF]. A summary of the conditions used for each crystal growth is given in Table S1.

Crystal

Sample Two different pure Nd 2 Zr 2 O 7 samples had to be used in inelastic neutron scattering experiments, because the first one broke when warming up the dilution fridge after an experiment.

CHARACTERIZATION OF THE TI DOPED SAMPLE (SAMPLE #3)

We have studied a doped sample, in which a small content of Zr is replaced by Ti, slightly shrinking structure. The nominal composition of the studied sample is 2.5 % of Ti atoms. As shown below, this doping only slightly affects the magnetic properties of the magnetic Nd 3+ sublattice and the low temperature properties are qualitatively the same.

The value of the Ti content was refined by neutron diffraction, thanks to the significant contrast between Zr and Ti. A series of Bragg peak intensities was collected at 10 K on the single crystal neutron diffractometer D23 (CEA CRG-ILL). The data are in agreement with the pyrochlore structure (F d 3m space group), with a lattice parameter of 10.65 Å and the 48f oxygen atoms at the position x 48f = 0.336. The Ti content is found to be 2.4 %. The Fullprof refinement [START_REF] Rodríguez-Carvajal | Recent advances in magnetic structure determination by neutron powder diffraction[END_REF] of the structure factor is shown on Fig. S1(a).

The Néel temperature was determined from very low temperature magnetization measurements, and found to be T N = 375 mK.

The magnetic contribution raises below T N in neutron diffraction measurements on top of the crystalline peaks. The Fullprof refinement below T N confirms the same "all in -all out" (AIAO) magnetic structure as in the pure sample (Fig. S1(b)). At 60 mK, the refined ordered Nd 3+ magnetic moment is 1.19 ± 0.03 µ B .

MEASUREMENTS AND ANALYSIS OF POLARIZED NEUTRON SCATTERING EXPERIMENTS

In polarized neutron experiments carried out at D7 (ILL, France), we used the P z polarization mode, z being the axis normal to the scattering plane and parallel to [1 10]. We measured N + M z in the NSF channel, and M y in the SF channel. Here we use conventional notations: N is the crystalline structure factor, while M y and M z denote the spin-spin correlation functions between spin components parallel to y Q and z respectively. The y Q axis lies within the scattering plane, perpendicular both to Q and z. We used a wavelength λ = 4.85 Å. The sample was rotated by steps of 1 degree, and 2 positions of the detector bank have been combined. Standard corrections (vanadium and quartz) have been processed.

On Figure 1 of the main article, the noise has been reduced by a mean filtering. This image processing based treatment tends to reduce the variation between one pixel and the next. The idea of mean filtering is to replace each pixel value with the average value of its neighbors, including itself. This has the effect of eliminating pixel values which are unrepresentative of their surroundings.