Nicolas Gastineau

Wahabou Abdou

Nader Mbarek

Olivier Togni

Distributed leader election and computation of local identifiers for programmable matter

come   L'archive ouverte pluridisciplinaire

Introduction

Programmable matter can be seen as modular robots (called modules or particles) able to fix to adjacent modules and send (receive) messages to (from) other modules fixed to the entity. Thus, the different modules form a geometric shape which is a network. Usually, a module can fix to another module using a finite number of ports (see Figure 1 for an example of spherical modules). Also, the modules know the ports that are in contact with other modules and have a knowledge about the geographic position of their ports. Moreover, the ports are supposed to be homogeneously distributed along the surface of each module. Such assumptions imply that the way how the modules are on a plane can be modeled by a grid. In this paper, we only consider modules on a plane surface, i.e. two dimensional grids. In this context, the geometric amoebot model [START_REF] Derakhshandeh | Brief announcement: amoebot -a new model for programmable matter[END_REF][START_REF] Derakhshandeh | An algorithmic framework for shape formation problems in self-organizing particle systems[END_REF][START_REF] Derakhshandeh | Leader election and shape formation with self-organizing programmable matter[END_REF][START_REF] Derakhshandeh | Universal shape formation for programmable Matter[END_REF][START_REF] Derakhshandeh | On the runtime of universal coating for Programmable Matter[END_REF][START_REF] Derakhshandeh | Universal coating for programmable matter[END_REF] aims to model the properties of a network for programmable matter.

Distributed algorithms aim to give a theoretical algorithmic framework in order to model the execution of an algorithm that runs on a network of computational elements that can cooperate in order to solve network problems. In distributed algorithm frameworks, it is often supposed that the different elements of the network do not have a unique identity, i.e., the network is anonymous. In anonymous networks, a natural question is how to perform a leader election, i.e., how to determine a singular element in an anonymous network. It is well known that for some network structures, the ring for example, there is no deterministic leader election algorithm [START_REF] Attiya | Distributed computing: fundamentals, simulations and advance topics[END_REF].

In 1999, Antoni Mazurkiewicz [START_REF] Mazurkiewicz | Distributed enumeration[END_REF] has presented a deterministic general algorithm to determine a leader (in the case it is possible to do so). In the situation where the elements have access to a random source, then it is also proven that no algorithm can correctly determine a leader in a ring with any probability α > 0 [START_REF] Itai | Symmetry breaking in distributed networks[END_REF]. Due to the assumption we make about the ports of the particles in the context of programmable matter (a particle knows the ports which are in contacts with other particles and knows the geographic position of its ports), the leader election problem becomes different than in the classical system. In particular, in the field of programmable matter, there exists a probabilistic algorithm that determine a leader (and in particular for a ring) with probability 1 [START_REF] Daymude | Improved leader election for self-organizing programmable matter[END_REF].

Several projects aim to build programmable matter prototypes. One of such projects [START_REF] Piranda | Geometrical Study of a Quasi-spherical Module for Building Programmable Matter[END_REF][START_REF] Tucci | Efficient scene encoding for programmable matter selfreconfiguration algorithms[END_REF], financed by the french National Agency for Research, aims to build cuboctahedral particles able to deform them-selves in order to move. This project can be split in two phases, one consists in manufacturing the hardware of prototype matters, the second consists in proposing algorithms for programmable matter. The final goal of this project is to sculpt a shape-memory polymer sheet with programmable matter. In the continuity of the algorithm phase of this project [START_REF] Piranda | Geometrical Study of a Quasi-spherical Module for Building Programmable Matter[END_REF], we propose algorithms for the self-configuration, i.e., in order to create identifiers and spanning trees.

In the context of programmable matter [START_REF] Bourgeois | Distributed intelligent MEMS: progresses and perspectives[END_REF][START_REF] Butler | Generic decentralized control for lattice-based self-reconfigurable robots[END_REF][START_REF] Lakhlef | Optimization of the logical topology for mobile MEMS networks[END_REF][START_REF] Naz | A distributed self-reconfiguration algorithm for cylindrical lattice-based modular robots[END_REF][START_REF] Tucci | Efficient scene encoding for programmable matter selfreconfiguration algorithms[END_REF][START_REF] Yim | Modular self-reconfigurable robot systems[END_REF], it is supposed that a network can contain several millions of modules and that each module has possibly a nano-centimeter size. These two facts lead us to believe that even a O(log(n))-space memory for each module, n being the number of modules, is not technically possible. Also, because of the large number of modules, it can be very challenging and time consuming to implement a unique identity to the modules when they are created. In this context, we suppose that the modules can not store a unique identity, i.e., that the network is anonymous. In this paper we propose deterministic O(1)-space memory algorithms to determine a leader in the network and to create k-local identifiers of the particles. A k-local identifier is a variable affected to each module of the network which is different for every two modules at distance at most k. Note that leader election [START_REF] Daymude | Improved leader election for self-organizing programmable matter[END_REF][START_REF] Di Luna | Shape Formation by Programmable Particles[END_REF] plays a significant role in numerous problems of programmable matter.

Our contribution is the following: we introduce a leader election algorithm based on local computations and simple to implement. This algorithm works when the structure the particles form has no hole (see Section 3). Also, since the algorithm can be described as a sequence of local computations, its limits (message complexity, required memory-space, etc) are easy to analyze. We present a distributed algorithm to construct a spanning tree in the context of programmable matter and, also, a distributed algorithm to re-organize the port numbers of the particles. Finally, we present an algorithm to assign a k-local identifier to each particle. In order to compute klocal identifiers, we suppose that we have done a leader election before. The k-local identifiers are determined using graph theoretical results about the coloring of the k th power of the grids. An advantage of the given k-local identifiers is that they are really simple to update in case the particles move and, consequently, the structure that the particles form changes.

This paper is organized as follows: in Section 2, we present our algorithmic framework in the context of distributed algorithms for programmable network. In the third section, we present our leader election algorithm. Finally, in Section 4, we present our algorithm to assign k-local identifiers to the particles (using the colorings from Appendix I).

Notation, definitions and our programmable matter algorithmic framework

The geometric amoebot model [START_REF] Derakhshandeh | Brief announcement: amoebot -a new model for programmable matter[END_REF][START_REF] Derakhshandeh | An algorithmic framework for shape formation problems in self-organizing particle systems[END_REF][START_REF] Derakhshandeh | Leader election and shape formation with self-organizing programmable matter[END_REF][START_REF] Derakhshandeh | Universal shape formation for programmable Matter[END_REF][START_REF] Derakhshandeh | On the runtime of universal coating for Programmable Matter[END_REF][START_REF] Derakhshandeh | Universal coating for programmable matter[END_REF] aims to model the computations that can occur in the context of programmable matter. In this paper, we use an algorithmic framework inspired by the geometric amoebot model. We assume that any structure the different particles can form is a subgraph of an infinite graph G. In this graph, V (G) represents all possible positions the particles can occupy and E(G) represents possible connections between particles. The set E(G) also represents the possible movements from a position to another position (for a particle). We suppose that two particles can bond each other, i.e., can communicate only in the case they are on adjacent positions. The two following paragraphs are dedicated to the notation and definitions we use for graphs.

For a graph G, we denote by V (G) the vertex set of G and by E(G) ⊆ V (G)×V (G) the edge set of G. We denote by d G (u, v), the usual distance between two vertices u and v in G. If we consider the distance in a subgraph H of G, the distance will be denoted by d H (u, v). The diameter of G,

denoted by diam(G), is max({d G (u, v)| u, v ∈ V (G)}). The set N G (u) = {v ∈ V (G)| uv ∈ E(G)}
is the set of neighbors of u. By ∆(G), we denote the maximum degree in G, i.e., the maximum cardinality of N G (u), for u ∈ V (G). Finally, we denote by G[S], for S ⊆ V (G), the subgaph induced by the vertices from S and by G -S the subgraph of G induced by the vertices from V (G) \ S.

In the remaining part of this paper, the graphs considered will be the infinite square, triangular and king grids. We denote by S the square grid, by T the triangular grid and by K the king grid. A subgraph of each of these three infinite graphs is represented in Figure 2. Moreover, we suppose that these three grids are represented on a plane as in Figure 2. For these grids, the considered vertex set is {(i, j)| i, j ∈ Z} and the edge sets are the following:

• E(S) = {(i, j)(i ± 1, j)| i, j ∈ Z} ∪ {(i, j)(i, j ± 1)| i, j ∈ Z}; • E(T) = E(S ) ∪ {(i, j)(i + 1, j -1)| i, j ∈ Z} ∪ {(i, j)(i -1, j + 1)| i, j ∈ Z}; • E(K) = E(T ) ∪ {(i, j)(i + 1, j + 1)| i, j ∈ Z} ∪ {(i, j)(i -1, j -1)| i, j ∈ Z}.
We also remind the distance between two vertices (i, j) and (i ′ , j ′ ) in the three different grids:

• d S ((i, j), (i ′ , j ′ )) = |i -i ′ | + |j -j ′ |; • d T ((i, j), (i ′ , j ′ )) = max(|i -i ′ |, |j -j ′ |), if (i ≥ i ′ ∧ j ≤ j ′ ) ∨ (i ≤ i ′ ∧ j ≥ j ′ ); |i -i ′ | + |j -j ′ |, otherwise; • d K ((i, j), (i ′ , j ′ )) = max(|i -i ′ |, |j -j ′ |).
Note that there is a way to draw the triangular grid in which each triangle is equilateral. However, we prefer to draw it as a subgraph of the king grid (see Figure 2) in order to have illustrations for which the vertex set {(i, j)| i, j ∈ Z} corresponds to the position of the vertices in the plane.

In both representation, the notion of distance coincide but is easier to observe in our chosen representation. However, note that the representation of the triangular grid in which each triangle is equilateral corresponds to the optimal way to pack unit disks in the plane (the position of the vertices in this representation corresponds to the center of the unit disk and an edge represents a contact between two disks). We also denote by i (mod p) or i (mod p) , depending on the context, the integer j such that j ≡ i (mod p) and 0 ≤ j < p. The remaining part of this subsection is dedicated to our programmable matter algorithmic framework.

We give the following properties about the particles and vertices of the graph:

• each particle occupies a single vertex and each vertex is occupied by at most one particle;

• the subgraph induced by the occupied vertices is supposed to be connected.

The subgraph induced by the occupied vertices of V (G) is called the particle graph and is denoted by P . The vertex occupied by a particle p is denoted by s(p). For a particle p, N

G (p) = {u ∈ V (G)| u ∈ N G (s(p))}.
The ports of a particle are the endpoints of communication. Each particle has ∆(G) ports in a regular grid G (∆(G) = 4 for G = S, ∆(G) = 6 for G = T and ∆(G) = 8 for G = K). The ports of a particle occupying a vertex u are represented by the edges incident with u. An edge between two vertices represents a possible communication between two particles p 1 and p 2 occupying these two vertices using each one a different port. A particle has the following properties:

• each particle is anonymous, i.e., it does not have an identifier;

• each particle has a collection of ports, each labeled by a different integer from {0, . . . , ∆(G)-1};

• the port numbers are given as a function of the position of the edges on a plane representation of the grids (see Figure 2);

• each particle knows the labels of the ports that can communicate with particles from the neighborhood;

• each particle knows the state of the neighbors.

In our algorithmic framework, we suppose that the particles have their ports labeled following the same clockwise order. Thus, consecutive port numbers correspond to consecutive edges around a vertex (as in the representation on the plane from Figure 2). Note that the particles do not have the same notion of orientation, i.e., there is possibly not a unique label for ports that correspond to edges going in the same cardinal direction. In the presented algorithms, the state of a particle will contain a variable corresponding to the status of the particle in the leader election algorithm and the information regarding its parents and childs for a constructed spanning tree.

The proposed algorithms in our algorithmic framework are results of successive local computations [START_REF] Bauderon | Graph relabelling systems: a tool for encoding, proving, studying and visualizing distributed algorithms[END_REF][START_REF] Rosenstiehl | Intelligent graphs, Graph theory and computing[END_REF]. In particular, the first presented leader election algorithm from Section 3 can be described by a graph relabeling system [START_REF] Bauderon | Graph relabelling systems: a tool for encoding, proving, studying and visualizing distributed algorithms[END_REF] which is a local computation system. In this paper, the correct execution of the different algorithms is only guaranteed if the algorithms are ran in the order depicted in Figure 3.

We suppose the following:

• each particle contains the same program and begins in the same state;

• the computation process is represented by successive local computations;

• no local computation occurs simultaneously on two particles at distance at most 2;

• during a local computation, a particle can perform a bounded number of computations and can send messages to its neighbors; • a round is a sequence of successive local computations for which each particle does at least one local computation;

• an algorithm finishes in k rounds if after any k successive rounds the algorithm is finished.

Note that the concept of rounds is used to bound the running time of the algorithms. In our algorithm framework we suppose that no two particles at distance at most 2 perform computations simultaneously in order to simplify the presentation of our results. However, this supposition can be removed by implementing, for example, a probabilistic leader election algorithm on the vertices at distance at most 2 of one of the two vertices, i.e., by computing a random value on the vertices at distance 2 and doing the local computation following the increasing order of the values. In order to compute the running time of an algorithm in case of a specific programmable matter prototype, the complexity of the algorithm should be computed using the required number of rounds and the required running time in order to avoid that two particles at distance at most 2 perform computations simultaneously.

Leader election

In this section we present a new leader election algorithm. This algorithm is very easy to implement but requires that the particle graph has a specific structure. In this algorithm, the required memory space is constant, the messages have constant size, the required computation power of the particle has been optimized and the required number of rounds is less than 2n (n being the number of particles).

A hole in a subgraph G ′ of a graph G among the three grids is a subgraph H of G satisfying three properties:

i) V (H) is finite, H is connected and |V (H)| ≥ 1; ii) V (H) ∩ V (G ′ ) = ∅; iii) every vertex u ∈ V (H) satisfies N G (u) ⊆ V (H) ∪ V (G ′ ).
Less formally, a subgraph G ′ of one of the three grids contains a hole if there is a finite space only containing vertices from V (G) \ V (G ′ ) which are surrounded by vertices of G ′ . A hole containing three vertices is illustrated in the left part of Figure 4. We call G ′ hole-free, when G ′ has no holes.

If the particle graph P on G is hole-free, then every particle p which satisfies |N G (p)∩V (P ))| < ∆(G) is at the geographical border of the shape of P . Moreover, we call the set of particles p which satisfy |N G (p) ∩ V (P ))| < ∆(G) and such that the vertices N G (p) -V (P ) are not all in a hole of P , the border of P . The right part of Figure 4 illustrates the border of P .

In addition, for a particle p occupying a vertex (i, j) of the square grid, the four vertices (i + 1, j + 1), (i -1, j + 1), (i + 1, j -1) and (i -1, j -1) are the corners of p and the set of corners is denoted by C(p). The extended neighborhood of a particle p, denoted by M G (p), is the set N G (p) if G is the triangular grid or king grid or the set N G (p) ∪ C(p) if G is the square grid. Note that we define the extended neighborhood differently for the square grid in order to be able to present a generic algorithm (Algorithm 1) that works for all the three grids. We give the following definition of S-contractible particle (see Figure 5) that will be used in our leader election algorithm. Definition 1. Let G be an infinite grid among S, T and K and let S ⊆ V (P ), for P the particle graph on G. A particle p is said to be S-contractible if it satisfies the following properties:

I) G[M G (p) ∩ S] is connected; II) |N G (p) ∩ S| < ∆(G), i.e.
, there exists a neighbor of p in G which is not occupied by a particle from S.

A particle p is an articulation of a connected subgraph G ′ of one of the three grids if G ′ -{s(p)} is not connected. Derakhshandeh et al. [START_REF] Derakhshandeh | Leader election and shape formation with self-organizing programmable matter[END_REF] proposed a randomized leader election algorithm in the geometric amoebot model in the case there is no particle which is an articulation. Our proposed leader election algorithm (Algorithm 1) works even if V (P ) contains a particle p which is an articulation. However, in contrast with the leader election algorithm from Derakhshandeh et al. [START_REF] Derakhshandeh | Leader election and shape formation with self-organizing programmable matter[END_REF], Algorithm 1 does not work if P has holes. In the remaining part of this paper, Algorithm 1 is called the S-contraction algorithm.

Recently, Daymude et al. [START_REF] Daymude | Improved leader election for self-organizing programmable matter[END_REF] have improved the algorithm from Derakhshandeh et al. [START_REF] Derakhshandeh | Leader election and shape formation with self-organizing programmable matter[END_REF] in order that it works when V (P ) contains an articulation. However, it remains challenging to implement it. Also, very recently, Di Luna et al. [START_REF] Di Luna | Shape Formation by Programmable Particles[END_REF] have introduced a leader election algorithm called consumption algorithm. The consumption and the S-contraction algorithms both consist in successively removing the candidacy of the particles on the border of P . However, one can easily notice that, in our algorithm, we possibly remove the candidacy of particles having four or five neighbors (which is not considered in the consumption algorithm). Also, the consumption algorithm does not work on square and king grids and the considered theoretical frameworks for the two algorithms are different.

In the S-contraction algorithm (Algorithm 1), the particles can be in three different states: C (candidate), N (not elected) and L (leader). We suppose that every particle begins in the state C.

Let 1 is illustrated by Figure 6. Note that, depending on the order in which the local computations occur, the result of the execution of the algorithm could be different. For example, between the configuration of Figure 6.c and that of Figure 6.d, we suppose that the local computations occur in this order: first a local computation occurs for the bottom left particle, second it occurs for the upper left particle, third it occurs for the upper right particle and fourth it occurs for the last particle (we only consider the particles which are in state C).

Algorithm 1 The S-contraction algorithm for a particle p and S the set of particles in state C. Theorem 1. Let S be the set of particles in state C and P be the particle graph on G. If P is hole-free, then at the end of the execution of the S-contraction algorithm, there will be exactly one particle in the state L.

In Appendix F, the proof of Theorem 1 is given. Also, a bound on the complexity of the Scontraction algorithm is given. In Appendix H, it is explained how to combine the S-contraction algorithm with a general leader election algorithm.

Assigning k-local identifiers to particles

In this section, we combine the results from Section 3 and Appendix I in order to correctly compute a k-local identifier. In a first subsection, we describe a way to create a spanning tree of particles and a way to change the ports numbering of the different particles. In a second subsection, we describe how to compute k-local identifiers based on the coloring functions from Appendix I.

We suppose that Algorithms 2 and 3 are preceded by a leader election algorithm (which could be Algorithm 1). Then it follows that there is a single particle in a specific state (the leader) and all the remaining particles are in the same state (non elected).

Re-organizing the particles

By N + G (u) we denote the set of port numbers which can communicate with particles occupying vertices from N G (u). When there is a leader, we can easily compute a spanning tree using a distributed algorithm (see Appendix G). Now suppose that for each particle p, we have two set of ports parent(p) and child(p) which contains the port numbers of the particles in communication with its parent and with its children, respectively, in the spanning tree. In this way, the required memory in order to store where are the children and the parent of the particle in a spanning tree is constant (since the maximum degree is bounded in the considered grids).

In our proposed Algorithm 2, the goal is to change the way the port are numbered in order that every particle has its ports numbered by the same number going in the same cardinal direction in the different grids. This algorithm does not work if we do not have a leader among the different particles. The function r G used in Algorithm 2 is defined, depending the choice of G, as follows: r S (i) = (i + 2) (mod 4), r T (i) = (i + 3) (mod 6) and r K (i) = (i + 3) (mod 6).

Algorithm 2

The port renumbering algorithm for a particle p.

Case 1: State L. for each port a from child(p) send a message m a , containing a, through port a. Case 2: State N. if the particle receives the message m b , containing b, through the port a then change the port number a to r G (b) and changes the port numbers of the other ports following the clockwise order; update both parent(p) and child(p).

end if

The idea behind Algorithm 2 is to reproduce, in each particle, the way the ports are numbered in the leader particle. To achieve this goal, each particle p receives a message from its parent containing the port number of the parent connected to p and p renumbers its own ports in order that its port numbers are coherent with the sent number. Figure 7.a and Figure 7.b illustrate the port numbers of particles before and after the execution of Algorithm 2.

The k-local identifiers

Now, we aim to give to each particle a variable id, called its k-local identifier, such that every two particles p 1 and p 2 with the same identifier satisfy d G (s(p 1 ), s(p 2 )) > k. If we suppose that the particles have not a memory of at least log 2 (n) bits, for n = |P |, then it is not possible to record a unique variable for each particle. However, it is possible to have a k-local identifier in the three considered grids only using at most log 2 ((k + 1) 2 ) bits where k is a parameter given by the user. Our proposed Algorithm 3 presents an optimal way (in term of memory) to compute k-local identifiers. We suppose that the port renumbering algorithm (Algorithm 2) has been done before executing Algorithm 3.

Algorithm 3 consists in assigning a variable which corresponds to a color in a coloring of the k th power on the grid. More precisely, the function f k G consists in assigning a color depending the Cartesian coordinate of the vertices. Since the colors are given following a pattern, the 7.c) in the square grid (square: leader; thick line: edge of the spanning tree; small number: port number of a particle; big number: 4-identifier of a particle).

Algorithm 3

The k-local identifier algorithm for a particle p.

Case 1: State L. set i = 0, j = 0, id = 0; send i and j through each port from child(p). Case 2: State N. if the particle receives the integers i ′ and j ′ through the port a then set i = I k G (i ′ , a), j = I k G (j ′ , a), id = f k G (i, j); send i and j through each port from child(p).

end if

Cartesian coordinate can be stored relatively to the size of the patterns. In Algorithm 3, the leader affects to itself the color 0 and following the direction where the messages are transmitted, the particles reproduce the coloring patterns given in Appendix I. The functions f k G and I k G , J k G , used in Algorithm 3 are defined, depending on the choice of G, as follows:

f k S (i, j) = (i + kj) (mod m k ), f k K (i, j) = i (mod k+1) + (k + 1)j (mod k+1) and f k T (i, j) = (i (mod 3(k+1)/2) + j(3(k + 1)/2) + ⌊2j/(k + 1)⌋(k + 1)/2)) (mod m ′ k ) if k is odd or f k T (i, j) = (i + (3k/2 + 1)j) (mod m ′ k ) otherwise; I k G (i, a) = i if (a = 1; 3 ∧ G ∼ = S) ∨ (a = 1; 4 ∧ G ∼ = T) ∨ (a = 2; 6 ∧ G ∼ = K), I k S (i, a) = i + 1 (mod ⌈(k + 1) 2 /2⌉) if a = 0, I k S (i, a) = i -1 (mod ⌈(k + 1) 2 /2⌉) if a = 2, I k T (i, a) = i + 1 (mod ⌈3(k + 1) 2 /4⌉) if a = 0; 5, I k T (i, a) = i -1 (mod ⌈3(k + 1) 2 /4⌉) if a = 2; 3, I k K (i, a) = i + 1 (mod k + 1) if a = 0; 1; 7 and I k K (i, a) = i -1 (mod k + 1) if a = 3; 4; 5; J k G (j, a) = i if (a = 0; 2 ∧ G ∼ = S) ∨ (a = 0; 6 ∧ G ∼ = T) ∨ (a = 0; 4 ∧ G ∼ = K), J k S (j, a) = j + 1 (mod ⌈(k + 1) 2 /2⌉) if a = 1, J k S (j, a) = i -1 (mod ⌈(k + 1) 2 /2⌉) if a = 3, J k T (j, a) = i + 1 (mod ⌈3(k + 1) 2 /4⌉) if a = 1; 2, J k T (j, a) = i -1 (mod ⌈3(k + 1) 2 /4⌉) if a = 4; 5, J k K (j, a) = i + 1 (mod k + 1) if a = 1; 2; 3 and J k K (j, a) = i -1 (mod k + 1
) if a = 5; 6; 7. Note that the functions I k G and J k G are used to determine the Cartesian coordinate of a particle using the Cartesian coordinate of a neighbor and the port number of this neighbor.

Since the values of f k G (i, j) is bounded by 3(k + 1) 2 /4, if G is isomorphic to one of the three grids, the size of the messages will not exceed log 2 (3(k + 1) 2 /4). As for Algorithm 2, the number of sent messages is |V (P )| -1. Figure 7.c illustrates the obtained 4-identifiers after the execution of Algorithm 3.

Since the particles can move during the execution of an algorithm, the k-local identifiers may become not valid anymore ( i.e., there may be two particles p 1 and p 2 with the same k-local identifier and with d G (s(p 1 ), s(p 2 )) ≤ k) if the structure of the particle graph P on G changes. It is possible to keep a valid k-local identifier in case a particle moves in a direction of a port a by setting id

= f k G (I k G (i, r G (a)), J k G (j, r G (a)
)) as the new k-local identifier. It corresponds to update the variable id which corresponds to a color in a coloring of the k th power on the grid in function of the new position of the particle. Also, in the case a particle do ℓ movements, by storing the successive directions of movement of the particle during these ℓ movements, it is also possible to update the value of the k-local identifier in order that it remains valid.

Note that for both Algorithms 2 and 3 finish after at most h rounds, h being the height of the spanning tree. Also the number of sent messages in both Algorithms 2 and 3 is |V (G)| -1 (the number of edges in a spanning tree).

Conclusion

In this paper, we have presented a new leader election algorithm based on local computation. We have also presented an algorithm which affects a different variable for every two particles p 1 and p 2 at distance at most k. All the presented algorithms only require a O(1)-space memory. This complexity makes it possible to use our algorithms for programmable matter. Moreover, in case of movements of particles, there is no need of communication in order to update the k-local identifiers.

As future work, it would be interesting to determine a more general deterministic leader election algorithm in our algorithmic framework that can take into account fault tolerance. Also, it would be interesting to extend the presented results to 3D grids. Another interesting question could be to use our results to clustering the set of particles in several sets which induce subgraphs of small diameter.

Lemma 1. Let G be an infinite grid among S, T and K and let S ⊆ V (P ), for P the particle graph on G and S the set of vertices occupied by all the particles in the same fixed state. One round is sufficient in order that every particle determine if it is S-contractible or not if G is isomorphic to S. Otherwise, if G is isomorphic to T or K, no round is necessary.

Proof. Let N + (p) be the set of port labels on which p can communicate with particles from its neighborhood. In order to verify that M G (p) ∩ S is connected in the triangular or king grids, it suffices to verify that N + G (p) ∩ S forms an interval of consecutive integers (by considering that 0 and ∆(G) -1 are consecutive). For example, {0, 4, 5} contains successive integers in the triangular grid but that is not the case for {0, 2, 5}. Such verification in the triangular and king grids can be done during any local computation. Figure 5 illustrates three possible cases that could happen for a particle in the triangular grid. On the left part of Figure 5, the particle does not satisfy Property I) but satisfies Property II). On the middle part of Figure 5, the particle satisfies Property I) and does not satisfy Property II). Finally, on the right part of Figure 5, the particle satisfies both Properties I) and II).

In the square grid, in order to test if a particle p is such that M G (p) ∩ S is connected, it requires to receive N + G (p ′ ) ∩ S, from the particle p ′ in the neighborhood of p and afterward to test if N + G (p) only contains consecutive integers (by considering that 0 and 3 are consecutive) and then to verify, for any two successive particles p ′ and p ′′ from the neighborhood, that the vertex which corresponds to the corner adjacent to both p ′ and p ′′ is occupied by a particle.

If G is among T and K, then no round is required to know if a particle is in S or not (since a particle know the state of its neighbors). If G is isomorphic to S, then, in one round, which consists in sending the values of N + (p) ∩ S to the adjacent particles, every particle knows if it is S-contractible or not.

The following lemma is be useful in order to prove that our leader election algorithm works correctly.

Lemma 2. Let G be an infinite grid among S, T and K and let S ⊆ V (P ), for P the particle graph on G. Let p be an S-contractible particle. If S is connected and hole-free, then S -{s(p)} is connected and hole-free. To ensure that our leader election algorithm works correctly, it remains to prove that there always exists an S-contractible particle. That is what we do in the following Lemma. contains no cycle (G[A] is a forest). However, by definition, the leaves (the vertices of degree 1) are S-contractible. Thus, we obtain a contradiction with the fact that there is no S-contractible particle in S.

In the case P is hole-free, note that by Lemma 2 and Lemma 3 there is always a particle which is both on the border of G[S] and not an articulation of G[S].

Proof of Theorem 1. Note that before the execution of the algorithm, the set S is the set V (P ). Since P is hole-free and connected and by Lemma 2, S remains connected and hole-free during the execution of the algorithm. By Lemma 3, there is always a particle in S which is S-contractible (every particle on the border which is not an articulation is S-contractible). Thus, for every round, the number of particles in state C strictly decreases. Since |V (P )| is finite, we are sure that at some point, S will only contain one vertex. If at some point, S contains one vertex, there will be at least one elected leader.

Finally, note that the fact that there are two elected leaders contradicts the fact that S remains connected during the execution of the algorithm.

Let G ′ be a subgraph of G such that G ′ is hole-free, the radius of G ′ , denoted by r(G ′ ), is given by r(G ′ ) = min u∈V (G ′ ) {max v∈A (d G ′ (u, v))}, for A the set of the particles on the border of G ′ . Moreover, let h(T ) be the height of a tree T , i.e., h(T ) = min u∈V (T ) {max v∈V (T ), |NT (v)|=1 (d T (u, v))} and let mtree(G ′ ) be the maximum height among all induced subgraphs of G ′ which are trees, i.e., among the set

{G ′ [B]| B ⊆ V (G ′ ), G ′ [B] is a tree }.
In the following Proposition, we give a bound on the required number of rounds for the termination of Algorithm 1.

Proposition 1. Let S be the set of particles in state C and P be the particle graph on G. Moreover, let b G = r(P ) + mtree(P ) + 1 if G is isomorphic to T or K or b G = 2(r(P ) + mtree(P )) + 2 if G is isomorphic to S. If P is hole-free, then after b G (P ) rounds of the S-contraction algorithm on P , one particle will be the leader.

Proof. First, suppose G is isomorphic to T or K. Let S t be the set of particles in state C after the first t rounds. Note that after r(P ) + 1 rounds we are sure that every remaining particle u satisfies |N G (u) ∩ S r(S)+1 | < N G (u). This is due to the fact that each particle u on the border of S i , for i ≥ 0, is not in S i+1 if |N G (u) ∩ S r(S)+1 | < N G (u). Thus, by Lemma 2, G[S r(P )+1 ] is either a tree or empty. By definition, we have h(G[S r(P )+1 ]) ≤ mtree(P ). Note that in the case G[S t ] is not a trivial tree (a tree containing only one vertex), we have h(G[S t+1 ]) = h(G[S t ]) -1, for t ≥ r(P ) + 1. Therefore, we obtain that S t is empty if t ≥ r(P ) + mtree(P ) + 1.

Second, suppose G is isomorphic to S. Note that, by Lemma 1, one round is sufficient in order that every particle determines if it is S-contractible. Consequently, it is easy to observe that the required number of rounds in order that the S-contraction algorithm finishes for S is bounded by two times the required number of rounds in order that the S-contraction algorithm finishes for T or K.

G An example of algorithm in order to construct a spanning tree

Our proposed algorithm (Algorithm 4) for constructing a spanning tree consists in setting the particle in state L as the root and, afterward, constructing a spanning tree using a classical distributed spanning tree algorithm.

H Combining the S-contraction algorithm with a general leader election algorithm Daymude et al. [START_REF] Daymude | Improved leader election for self-organizing programmable matter[END_REF] introduced a leader election algorithm that works on every configuration of P . In this appendix we present a way to reduce the required number of rounds in order that this algorithm finishes its execution (by using the S-contraction algorithm). In the remaining part of this appendix, the leader election algorithm from [START_REF] Daymude | Improved leader election for self-organizing programmable matter[END_REF] will be called the general leader election verify if an agent is in b(H) by sending a message around the boundary and verifying when the message comes back to the initial particle if this message has been re-transmitted in the clockwise direction or not. As Figure 8 illustrates, the messages re-transmitted through the boundary of a hole are re-transmitted in the counterclockwise direction and the messages re-transmitted through the border of P are re-transmitted in the clockwise direction. In all these phases, the messages are re-transmitted around a boundary. The required number of rounds in order that the general leader election algorithm finishes its execution is O(ℓ), where ℓ is the number of particles in the border of P .

We do the following remark about the S-contraction algorithm that comes from the fact that for any S-contractible particle p of S, if G[S] is connected, then G[S \ {s(p)}] is also connected.

Remark 1. If the particle graph P has a hole then, after the execution of the S-contraction algorithm on the particle graph P on G there will remain particles in state C. Also, the graph induced by the particles in state C is connected.

In particular when P has one hole, the remaining particles in state C will form a ring in the triangular grid. Thus, it is possible to run the S-contraction algorithm and, afterward, execute the general leader election algorithm on the remaining particle in state C. Let S c be the set of particles in state C after the S-contraction algorithm on the particle graph P on G. Depending on the structure of P , it could happen that the number of particles in the border T [S c ] is smaller than in the border of P and that it speeds the execution of the general leader election algorithm. For example, that is always the case when P has at most one hole.

I Coloring the k th power of graph

The k th power of a graph G is the graph on the same vertex set than G and with edges connecting every two vertices u and v satisfying d G (u, v) ≤ k. Note that there is a correlation between this definition and the k th power of the adjacency matrix of G (the adjacency matrix of the k th power of G is easily obtained from this matrix). Our goal in this appendix is to determine an optimal coloring of the k th power of the square, triangular and king grids. We use these colorings in order to propose a distributed algorithm (supposing we have a leader) in order to assign k-local identifiers to the particles (see Section 4). A coloring of the k th power of a grid corresponds to assign a value to each vertex of the graph such that every two vertices with the same assigned value are at distance at least k + 1. An example of coloring of the k th power of the square grid is represented by Figures 9 and 10. In Figure 9, it is easy to notice that every two vertices with color 0 (or any other color) are at distance at least 4.

More formally, a k-coloring of a graph G is a map c from V (G) to {0, 1, . . . , k -1} which satisfies c(u) = c(v) for every uv ∈ E(G). The chromatic number χ(G) of G, is the smallest integer k such that there exists a k-coloring of G. The k th power G k of a graph G is the graph obtained from G by adding an edge between every two vertices satisfying d G (u, v) ≤ k. More details about the coloring of the k th power of graphs can be found in the survey from Kramer and Kramer [START_REF] Kramer | A survey on the distance-colouring of graphs[END_REF]. The results presented in this appendix are inspired by the previous works [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF][START_REF] Jacko | Distance coloring of the hexagonal lattice[END_REF][START_REF] Sevcikova | Distant chromatic number of the planar graphs[END_REF] about the coloring of the k th power of the grids.

Figure 1 :

 1 Figure 1: Five spherical particles forming a simple structure (circle: port of the particles).

Figure 2 :

 2 Figure 2: Subgraphs of the square (Figure 2.a), triangular (Figure 2.b) and king (Figure 2.c) grids, with the port numbers of two particles.

Figure 3 :

 3 Figure 3: An illustration of the algorithm dependency (arrow between algorithms/results: dependency of one algorithm to another algorithm/result).

Figure 4 :

 4 Figure4: A hole in P (on the left) and the border of P in the case P is hole-free (on the right; square: particle on the border of P ).

Figure 5 :

 5 Figure5: Two non S-contractible particles (at the center of the left and the middle drawing) and an S-contractible particle (at the center of the right drawing) in the triangular grid (square: particle in S; circle: particle not in S).

Figure 6 :

 6 Figure 6: An example of the execution of S-contraction algorithm after one round (Figure 6.a), two rounds (Figure 6.b), three rounds (Figure 6.c) and after four rounds (Figure 6.d; circle: non S-contractible particle; square: S-contractible particle; triangle: particle in state N; pentagon: particle in state L; S being the set of particles in state C).

Figure 7 :

 7 Figure 7: One spanning tree of particles, a possible numbering of the ports of the particles before (Figure 7.a) and after the execution of Algorithm 2 (Figure 7.b) and the 4-identifier obtained by executing Algorithm 3 (Figure7.c) in the square grid (square: leader; thick line: edge of the spanning tree; small number: port number of a particle; big number: 4-identifier of a particle).

  Proof. First, note that in all three grids, the fact that|N G (p) ∩ S| < |N G (p)| implies that there is a vertex v in N G (p) \ S.By contradiction, suppose we create a hole in G[S] by removing the vertex s(p) from S. This implies, since G[M G (p) ∩ S] is connected, that v was already in a hole from G[S]. Second, since G[M G (p) ∩ S] is connected, we are sure that the subgraph G[S \ {s(p)}] is connected.

Lemma 3 .

 3 Let S ⊆ V (P ), for P the particle graph on G. If G[S] is hole-free, then there always exists an S-contractible particle in S.Proof. Note that there exists a particle on the border of G[S] since S is finite. Let A be the set of particles on the border of G[S]. For any particle p, the fact that there are at least two connected componentsB 1 and B 2 in G[M G (p) ∩ S]implies that there is no path in G[S \ {s(p)}] between any vertex of B 1 and a vertex of B 2 , since it would imply the existence of a hole in G[S] containing a vertex from M G (p) \ S. Therefore, if p ∈ A and if p is not an S-contractible particle, then p is an articulation of G[S]. Now suppose, by contradiction, that there is no S-contractible particle in S. By the previous remark, the graph G[A] is connected and all particles of A are articulations of G[S]. However, a finite graph containing a cycle contains vertices which are not articulation of G[S]. Thus, G[A]

Figure 10 :

 10 Figure 10: A pattern for coloring the 4 th power of the square grid.

Acknowledgments

This work was supported by the French "Investissements d'Avenir" program, project ISITE-BFC (contract ANR-15-IDEX-03).

F Proof of Theorem 1 and bound on the complexity of the S-contraction algorithm

The three lemmas presented in this appendix are used in order to prove Theorem 1.

In the following lemma, we describe how to determine, in the context of programmable matter, if a particles is S-contractible or not.

Algorithm 4 A spanning-tree algorithm for a particle p. algorithm (to the best of our knowledge, it is the only leader election algorithm for programmable matter working on every configuration).

In order to simplify the presentation of the results, we only discuss the results for the triangular grid. However, by modifying the algorithms it is possible to make it work for the square and king grids also. We begin this appendix by describing how the general leader election algorithm works. This description will help the reader to convince itself that, in a lot of cases, combining the S-contraction algorithm with a general leader election algorithm could be a good idea.

For particle p and a port a of p connected to another particle, we denote by n(a) the port number of the first port of p connected to a particle after a in the clockwise order. The general leader election algorithm uses the fact that it is possible to send a message around a boundary. Sending a message around a boundary consists in sending and re-transmitting the message in the following way: for a particle p, if a message is received from the port a, then the particle re-transmits the message to the particle connected to p by the port n(a) of p. Figure 8 represents how the messages are transmitted in this case.

For each hole H of the particle graph P on G, we denote by b(H), the set of particles which are adjacent with a vertex of H. Also, when a particle is adjacent to vertices of different holes or when a particle belongs to the border of P , it is possible to decompose particles in agents, each agent corresponding to a different hole or to the border. Thus, an agent will be either adjacent to vertices of at most one hole or belong to the border but never both.

The general leader election algorithm can be summarized as the succession of four phases. A first phase consists in removing the candidacy of each particle having six neighbors. A second phase consists, for each hole H of P , to remove the candidacy of some agents of b(H) using a randomized procedure. Simultaneously, the same process is done for agents in the border of P . A third phase consists in verifying if there is only one candidate in b(H), for each hole H of P and only one candidate in the border of P . They calculate the relative positions of the candidates in order to do such verification. Finally, in the last phase, they verify if the remaining candidates agents are in b(H) or in border of P . The leader will be the candidate particle of the border of P . We can Appendix I.A Coloring the k th power of square grids

We give the following result from Fertin et al. [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF].

Theorem 2 ([12]). For any

Let m k = ⌈(k + 1) 2 /2⌉. In their paper, Fertin et al. define an optimal coloring c of the k th power of the square grid as follows: c((i, j)) = (i + kj) (mod m k ). In Figures 9 and10, we represent patterns for coloring the 3th and 4th powers of the square grid. These patterns have been obtained using the coloring from [START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF]. Note that since there is a pattern, a vertex (i, j) can determine its color only knowing i (mod m k ) and j (mod m k ). We recall the definition of

This function is used in order to assign k-local identifiers to particles.

Appendix I.B Coloring the k th power of triangular grids

The chromatic number of the k th power of the triangular grid has been determined by Sevcikova [START_REF] Sevcikova | Distant chromatic number of the planar graphs[END_REF].

We recall the definition of the following function:

Note that f k T (i, j) = f k T (i ′ , j ′ ), in the case i ≡ i ′ (mod m ′ k ) and j ≡ j ′ (mod m ′ k ). This function is used in order to assign k-local identifiers to particles.

Appendix I.C Coloring the k th power of king grid

To our knowledge, the chromatic number of the king grid has not been determined yet. However, in contrast with the triangular grid, the chromatic number of the k th power of the king grid is easy to determine. In this subsection, we determine the exact value of the chromatic number of the k th power of the king grid. 2 . Thus, since each vertex of K k must be colored differently in a coloring of the k th power of the king grid, we obtain that χ(K k ) ≥ (k + 1) 2 . We define the coloring function c((i, j)) = i (mod k+1) + (k + 1)j (mod k+1) . Note that we have d K (u, v) ≥ k + 1, for every two vertices u and v with the same color in K. Therefore, we obtain that χ(K k ) = (k + 1) 2 .

Note that since there is a pattern, a vertex (i, j) can determine its color only knowing i (mod (k + 1)) and j (mod (k + 1)). We recall the definition of the following function f k K (i, j) = i (mod k+1) + (k + 1)j (mod k+1) . Note that f k K (i, j) = f k K (i ′ , j ′ ), in the case i ≡ i ′ (mod k + 1) and j ≡ j ′ (mod k + 1). This function is used in order to assign k-local identifiers to particles.


Xiang Wang

Barbara Wicher

Yann Ferrand

Ivan Huc

Orchestrating Directional Molecular Motions: Kinetically Controlled Supramolecular Pathways of a Helical Host on Rod-like Guests

Keywords: foldaxane, pseudo-rotaxane, foldamer, double helix, dynamic self-assembly, molecular recognition, directional motion, molecular shuttle, supramolecular pathways

An aromatic oligoamide sequence was designed to fold and self-assemble into a double helical host having a cylindrical cavity complementary to linear oligo-carbamates guests. Formation of helical pseudo-rotaxane complexesfoldaxanesbetween the host and guests having binding stations of different affinities was evidenced by NMR and x-ray crystallography. Rod-like guests possessing two or three binding stations, long alkyl or oligoethylene glycol spacers or bulky barriers in-between the binding stations, and a single bulky stopper at one end, were synthesized. Kinetic investigations of the threading and translation of the double helix along multistation rods were monitored by 1 H NMR. Results show that multiple events may occur upon sliding of the host from the non-bulky end of the rod to reach the thermodynamically most stable state before unfolding-mediated dissociation has time to take place, including binding on intermediate stations and rapid sliding along non-binding spacers. Conversely, installing a kinetic barrier that blocks sliding allows for the deliberate integration of a helix dissociation re-association step in the supramolecular trajectory. Typical sliding processes can be monitored over the course of hours whereas steps involving unwinding/rewinding of the helix proceeded over the course of days. These results further demonstrate the interest of foldaxanes to design complex sequences of supramolecular events within networks of equilibria through the adjustment of the kinetics of the individual steps involved.

INTRODUCTION

A majority of the self-assembled artificial supramolecular architectures described to date form under thermodynamic control. Yet, a growing number of examples have been reported where kinetic control is essential to produce particular structures. 1 Controlling the kinetics of self-assembly processes is important to create artificial molecular machines 2 capable of directional motions. It is indeed the rates at which concommittent events take place that eventually determine in which order these events occur. Orchestrating the time scales of various molecular associations, dissociations and motions may thus allow for the design of sequences of events in a certain order between an initial state and a thermodynamically more stable state through a defined supramolecular trajectory. In the following, we report the design and characterization of such kinetically controlled supramolecular trajectories in the context of the association of aromatic amide helical foldamers with oligo-alkycarbamate rod-like guests to form helix-rod hostguest complexes termed foldaxanes. Foldaxane subcomponents may undergo several simultaneous dynamic processes. The generation of well-defined supramolecular pathways therefore required the integration of multiple parameters including foldamer helix folding; foldamer self-association into double helical dimers; equilibrium between parallel and anti-parallel forms of the duplexes; stabilization of the anti-parallel duplexes upon binding to rod-like guests to form foldaxane structures; availability of two foldaxane formation mechanisms (threading or direct winding around the rod) to create kinetic gradients; and availability of binding stations on the rods having different affinities for helix hosts to create thermodynamic gradients.

Foldaxane translation along molecular rods reproduce in model systems an important aspect of biomolecular machinery: the segregation on different timescales of several potentially reversible events. For instance biomolecular machines' subcomponentsproteins or nucleic acidsadopt folded conformation that are long lived, i.e. that do not undergo frequent spontaneously unfolding. Furthermore, these components self-assemble into larger supra-structures, e.g. the ribosome and multimeric protein complexes such as ATP synthase, that also are long lived and do not undergo spontaneous disassembly in the time frame required for their work regime. Thus, multiple motions can be implemented such as the disassembly of nucleic acid double helices by helicase, the transport of cargos within the cell by kinesin, or even the motility of entire cells through the motion of a flagellum as in spermatozoids on timescales much shorter than the assembly and dissociation time scales of the sub-components.

Translational molecular motionstypically the directional progression of a molecular shuttle along a molecular trackhave been the object of particular attention. For example, the elucidation of the kinesin I motion mechanism 3 inspired the development of artificial molecular walkers, [START_REF] Leigh | For recent reviews on artificial molecular walkers see: (a) von Delius[END_REF]5 designed to undergo a directional motion on a single molecular track through repetitive operations powered by an external source of fuel. Translation is also involved in the catalytic activity of DNA polymerase, a protein assembly that forms a pseudorotaxane-like complex with a DNA strand and moves along it while synthetizing a complementary sequence. Somewhat related to DNA polymerase are some artificial architectures in which a directional motion follows the threading of a macrocyclic molecule at one extremity of a rod possessing a stopper at the other extremity. Thus, pseudorotaxanes based on cyclodextrins 6 or other macrocyclic 7 architectures have been extensively used for the threading on oligomers or polymers. Some of these designs have even been shown to perform processive catalysis along the polymer track. 8 Our group has shown that multi-turn helical aromatic oligoamide foldamers may wind around dumbbell shape molecules and form stable pseudo-rotaxane complexes termed foldaxanes 9 akin to other helix-rod host-guest complexes. 10 These helical molecular tapes slowly wrap around oligocarbamate dumbbell rods then slide rapidly along them between two adjacent binding stations. The segregation of winding and sliding motion kinetics allowed for the construction of self-assembled molecular pistons 9a,b without having to rest on permanently interlocked architectures. 11 Herein, we report on our efforts at extending the scope of shuttling motions of helical aromatic oligoamide foldaxanes. We find that several sliding steps and processese.g. transient stops on intermediate binding stations and fast transit over rod segments deprived of binding stationshave time to proceed before dissociation through unwinding becomes significant. We also show that dissociation-reassociation can be purposely integrated in complex supramolecular trajectories to overcome a high kinetic barrier installed before a thermodynamic well that cannot be reached through sliding. These results further demonstrate the interest of foldaxanes to design complex sequences of supramolecular events within networks of equilibria through the adjustment of the kinetics of the individual steps involved.

Figure 1. (A)

Cartoon representation of the host-guest components and assembly. The host exists as an anti-parallel double helix. Rodlike guests possess carbonyl hydrogen bond acceptors (yellow or green sticks) defining two distinct binding stations having either a weak (station or a strong affinity (station for the host. Each rod has a non-bulky terminus on which the host can be threaded, a bulky stopper at the other extremity, and a spacer (blue spheroid) of varying size connecting the two stations. I, II and III stand for three distinct supramolecular states of the host. (B) Formula of the different spacers used in this study. (C) Cycle showing the sliding pathway followed by the host with a non-bulky spacer. (D) Cycle showing the winding pathway followed by the host with a bulky spacer.

RESULTS AND DISCUSSION

Design and synthesis. We have previously shown that single and double helical aromatic oligoamide foldamers may bind to rod-like guests bearing carbamate groups separated by n-alkyl segments. 9a-c Specifically, sequence 1 9c (Figure 2A) folds and self-assembles as an anti-parallel double helix presenting two pyridine trimers, one at each extremity, that both act as hydrogen bond donors to complex the carbonyl functions of a guest (Figure 1A). The combined sixteen 8-fluoroquinoline monomers of the two strands define a one nanometer-long cylindrical cavity that accommodates n-alkanes. A match between the host and the guest lengths is required for optimal binding. Since (1)2 is a dynamic structure capable of screwing-unscrewing motions, it may, to a limited extent, adjust its own length to that of the guest. 9b,c Yet, upon varying guest length sufficiently, foldaxane thermodynamic stability varies to a large extent: binding constants ranging from 97 L mol -1 to 2.9 10 4 L mol -1 have been measured upon increasing guest length from 6 to 12 methylene units. 9c We reasoned that several binding stations having an increasing affinity for (1)2 may be placed sequentially along a multi-station rod so as to create a thermodynamic binding gradient. To induce the directional movement of a helix along that gradient, we planned to introduce several design features: (i) a bulky stopper may be placed at one extremity of the guest while the other extremity would consist of a short linear alkane that can quickly thread itself into the helix cavity. In this way, loading the helix on the rod by threading can be programmed to occur exclusively at a defined extremity regardless of the location of the best binding station; (ii) the affinity of (1)2 for the first binding station (-station) on the rod should be high enough to favor a mostly associated state under measurement conditions (typically NMR tube concentration) yet low enough not to hamper its sliding to a subsequent binding station along the rod; (iii) binding affinities should incrementally increase along the rod to bias the direction of the helix motion and to facilitate monitoring the helix progression through the successive appearance of sufficiently populated bound states; (iv) spacers of different nature, length and bulkiness may be placed in-between binding stations to control the sliding rates of the helix. Bulky spacers may eventually block the helix and impose other supramolecular pathways towards the most stable foldaxane; (v) when the helix reaches the last binding station (-station), the bulky stopper then prevents unslippage and makes the thermodynamically most stable state be kinetically stable as well.

A series of rod-like guests having up to three binding stations separated by spacers of varied length, polarity and bulkiness were designed and synthesized (Figure 2B,C,D). Synthetic routes and experimental details are provided in the supporting information. Typically, carbamate functions were produced by reaction of a primary alcohol or amine with 4-nitrophenyl chloroformate. The resulting activated 4-nitrophenyl carbamates reacted with primary alcohols to produce carbamates in boiling chloroform. Conversely, the resulting activated 4-nitrophenyl carbonates reacted with primary amines to produce carbamates at room temperature. Binding stations having, 7, 8 or 11 methylenes were used depending on the desired binding affinity. These affinities have been determined previously using single station rods 9c (see below). Linear non hindered spacers between two binding stations were introduced to investigate whether they create a kinetic barrier to helix sliding along the rod. For instance, linear alkyl spacers of various length up to 18 methylenes (2, 3, 4 and 5) and oligoethylene glycol spacers of various length up to 17 atoms (2, 6 and 7) were all placed between the same two stations. Note that the shortest spacer of compound 2 is the same for both series. In addition, two rods having three binding stations were prepared (8, 9), which differ by the nature of the middle station, to generate more complex sliding pathways. In parallel rods bearing bulky spacers that hinder or forbid sliding motions were also synthesized. Benzene (10) and anthracene (11) were selected as bulky obstacles of varying size able to block the helix and to impose another supramolecular pathway, namely unwinding-winding, for the helix to reach the best binding station.

Self-assembly of 1 into double helical (1)2. The anti-parallel nature of (1)2 was assessed both in solution and in the solid state. As shown by 1 H NMR, duplex (1)2 exists as a mixture of parallel and antiparallel assemblies after purification on silica gel chromatography (Figure S1). Fortunately, the precipitation of the double helix from methanol provides (1)2 exclusively in its antiparallel configuration. X-ray quality crystals of (1)2 were obtained from the slow diffusion of n-hexane in a chloroform solution. The solid-state structure was solved and confirmed the antiparallel arrangement of (1)2 as well as the existence of a one nanometer-long cylindrical cavity lined with fluorine atoms (Figure 3A-C). 1 H NMR monitoring of freshly dissolved antiparallel (1)2 (4 mM in CDCl3 at 17°C) showed that the parallel/antiparallel equilibrium was slowly reached after 10 hours (Figures S1 andS2, final ratio antiparallel/parallel = 63/37). Only the antiparallel form of (1)2 binds to rod-like guests. Thus, in the presence of the guests, the antiparallel form is further stabilized and the parallel form does not appear anymore, being disfavored both kinetically and thermodynamically. The main advantage of isolating the pure antiparallel duplex by the precipitation method mentioned above is thus to avoid a slow antiparallel to parallel duplex conversion to interfere with, and become the rate limiting factor of, the various transformations to be studied here. Structural and thermodynamic study of foldaxane formation. Single station rods 12 and 13 possess one bulky stopper and one terminal n-butyl carbamate. Their binding to (1)2 was assessed to be compared to the recently measured binding of dumbbell-shaped guests having two benzyl-carbamates. 9c The two rods possess 8 and 11 methylenes, respectively, between their carbamate functions. Upon adding guests 12 and 13 to a CDCl3 solution containing antiparallel (1)2, single sets of wellresolved NMR signals were immediately observed as a result of the formation of (1)212 and (1)213 (Figures S3 andS4). Despite the absence of stoppers on the rod, exchange between free (1)2 and bound (1)2 was found to be slow on the NMR time scale. Association constants for (1)212 and (1)213 were measured accurately through the integral ratios of the free and bound host amide resonances to be Ka = 6.4 10 3 and 4.8 10 4 L mol -1 , respectively, at 17°C in CDCl3. These values are both about 40% higher than measured with bis-benzyl carbamate guests at 25°C. 9c The ratio between these association constants was confirmed in a competition experiment (Figure S5): the addition of rod 13 (1 equiv.) to foldaxane (1)212 caused the dissociation of (1)2 and its quick threading on 13 to form (1)213 (final ratio [(1)213]/[(1)212] = 79/21). The 7.5 fold difference between the two affinities was considered to be sufficient to create a gradient of affinity on multistation rod molecules. As shown in the subsequent steps of this study, the design of single station rods 12 and 13 as models of individual stations on multistation rods 2-11 proved to be valid except in the case of rod 2. The two stations of 2 are close to each other and both possess an enhanced affinity for 1 (vide infra). In this case, 14 is a better model than 12 of the first binding station of 2.

Figure 2.

Formula of aromatic oligoamide host 1 and of the various rod-like guests used in this study.

Structural insights were also gathered in the solid state. Crystals of (1)212 and (1)213 were obtained from the slow diffusion of n-hexane in a chloroform solution of each complex.

A close-up look at the two crystal structures confirmed different extents of the relative screwing of the two strands in each double helix. 9b,c This allows (1)2 to accommodate guests of different lengths by adjusting the positions of pyridine trimer pinchers so that they match with the positions of the carbonyl groups of the rod (Figures 3D,E). In solution, an indicator of the variable positioning of the two strands of 1 is the different chemical shift values of the protons in position 4 of the 2,6-pyridinedicarboxamide units which are found near 8.8 ppm in (1)213 and below 8.4 ppm in (1)212 (Figures S3 vs. S4, see also Figure 4A vs. 4C and Figure 2 in reference 9b). One may note that the terminal diamino pyridine unit of each strand is flipped out in the structure of (1)212. This has been observed previously in other duplexes involving terminal pyridine units even in the absence of guest. 9a,12 Directional sliding motion in double station rods. Foldaxane formation was then investigated with double station rods 2-7 (Figure 1A and2B). These rods all bear both a weak binding station (-station, 8 methylenes as in 12) and a strong binding station (-station 11 methylenes as in 13). In the parent compound of the series, guest 2, the two stations are separated by a single ethylene glycol unit (Figure 3F). Upon adding an excess [START_REF]With excess rod[END_REF] of rod 2 (10 equiv. with respect to (1)2) to a CDCl3 solution of antiparallel (1)2 NMR showed that a single new species was immediately and quantitatively formed that corresponds to the fast and quantitative threading of (1)2 on 2 (Figure 4B). Intense nOe correlations between the bound rod and the double helix clearly indicate that (1)2 is then located on the station (Figure S26). This [3]foldaxane was named (1)22 in reference to the weak binding station and represents a kinetically favored intermediate: the helix does not immediately reach the more favorable station. Upon standing at 17°C, (1)22 disappeared over the course of days and was replaced by another foldaxane species (Figure 4C-E) reflecting that (1)22 is not the most stable complex. The new species was assigned to be (1)22 in which the double helix (1)2 is positioned on the strong binding station near the bulky stopper. Most amide 1 H NMR resonances are slightly downfield shifted in (1)22with respect to (1)22which is consistent with chemical shift differences between the resonances of (1)212 and (1)213 (Figure S5). The equilibrium was reached after almost 3 days and the final ratio /was found to be 75/25 (Table 1) as expected from the ratio of association constants with 12 and 13.

X-ray-quality single crystals were obtained by slow diffusion of n-hexane into a CDCl3 solution of (1)2 and2 at thermodynamic equilibrium. Unexpectedly, despite the use of an excess of guest 2 to favor the crystallization of the [3]foldaxane (1)22, the resolution of the solid-state structure revealed a five component assembly made of two double helices threaded on rod 2 (Figure 3G-I). This structure confirms that (1)2 can complex both stations of 2 and provides an illustration of what both (1)22 (Figure 3I) and (1)22 (Figure 3H) may look The crystallization of [5]foldaxane (1)42 may have two non-exclusive explanations: (i) the undetected selective crystallization or precipitation of excess 2, if it occurs first, will enrich the mixture in (1)42; (ii) (1)42 may be much less soluble and much more prone to crystallization than (1)22, and may form crystals first even when it represents a minor component of the crystallization mixture. Table 1. Kinetic data for the sliding of the investigated complexes determined by 1 H NMR. Based on the experiments described above, the mechanism (sliding or winding/unwinding) of the transformation of (1)22 into (1)22 cannot be ascertained. However, sliding above an ethylene glycol spacer has been established previously 9a,b and there is no reason to dismiss it in this case (see the subsequent section for experimental proof that sliding prevails here as well). NMR monitoring then provides an estimate of the sliding rate. Assuming that pseudo-first order kinetics apply when sliding starts, i.e. when the reverse sliding back to (1)22 is negligible because there is little (1)22 formed, a pseudo-first order kinetic constant was calculated to be k = 1.2 10 -5 s -1 (Table 1, Figure 1 and Figure S6-S7).

We then examined the effect of elongating the central ethylene glycol spacer into longer alkanediols on the sliding rate of (1)2. Sliding along 3, 4 and 5 proceeded as it did along 2, with the quick formation of a complex on the  station followed by the slow migration of (1)2 to the  station (Figure 4G). Pseudofirst order rate constants were calculated (Table 1). In each of this three rods the spacer length was elongated to reach 6, 12 and 18 methylenes, respectively. Yet, the sliding was found to be 30 times faster on rod 3 than on rod 2 (k = 37.3 10 5 s -1 ). Further elongation somewhat decelerated the motion but sliding remained 8 times faster on the longest rod 5 than on 2. This non monotonous trend was also observed upon elongating the central ethylene glycol into oligo-ethylene glycols: when compared to the short ethylene glycol spacer of 2, sliding rates along tetraethylene glycol (6) and hexaethylene glycol (7) were found to be higher by 30 and 20 fold, respectively. If one excludes 2 and its very short spacer, elongating spacers eventually slows down sliding but the attenuation of the rate constant is not pronounced. Furthermore, sliding along oligoethyleneglycols is faster than along alkanes, despite the preference of the former to adopt multiple gauche conformations that are a priori not compatible with the narrow cavity of (1)2. For instance, sliding along rods 6 (resp. 7) was found to be 2-3 times faster than along 4 (resp. 5) despite their similar lengths (Table 1).

The distinctly slower sliding along 2 must in some manner relate to the proximity between the central carbamate functions of this rod. To explore what may slow down sliding from the to the -station of 2, we prepared rod 14 which possesses an station plus a single carbamate group connected by an ethylene glycol (Figure 5A). The relative affinity of 14 for (1)2 was assessed in a competition experiment: 12 and 14 were mixed in excess (2 equiv. each) with (1)2. The ratio [(1)214]/[(1)212] was calculated by integrating NMR signals and showed that the additional carbamate group of 14 is responsible for an enhancement of binding to (1)2 by a factor of 1.7 with respect to 12 (Figure 5C-D). A comparison between the x-ray structure of (1)212 and an energy minimized molecular model of (1)214 revealed the presence of an additional hydrogen bond between the NH of the terminal 8-fluoroquinoline of (1)2 and the extra carbamate carbonyl group at the extremity of 14 (Figure 5A,B). This interaction is possibly responsible for the higher binding to 14 and is unlikely to occur with spacers longer than an ethylene glycol between carbamate functions. Thus, the singular slow kinetics of sliding of (1)2 along two station rod 2 might arise from a higher affinity (1)2 with both the and -stations as compared to rods in which the and -stations are more distant.

Directional sliding motion in triple station rods. Rod design was taken one step further by placing an additional, -binding station, in-between the and -stations. Triple station rods 8 and 9 both possess the same and -stations as double station rods. In rod 8, the central -station has a weak affinity for antiparallel (1)2 (Ka = 1100 L mol -1 ). In rod 9, the central -station is identical to the -station. All stations are separated by an ethylene glycol spacer. Threading experiments with rods 8 and 9 were analyzed by 1 H and 19 F NMR. The determination of a pseudo-first order rate constant was not as straightforward as for the other rods due to binding to, and reverse sliding from, the -station. Instead, to compare with the others rods we monitored for each foldaxane the time required to reach 50% occupancy of (1)2 on the station ( in Table 1). When compared to rods 3-7, sliding kinetic of (1)2 to reach equilibrium (Table 1) was found to be at least 17 times slower. Both rods 8 and 9 showed a much longer sliding time (= 37 and 102 hours, respectively) to join the terminal -station. As expected, the final percentage of double helix on the terminal -station of 9 was found to be lowered by the competition binding between the and both and -stations. In the case of rod 8, at thermodynamic equilibrium, the final ratio was found to be only slightly altered due to weak competition of the intermediate binding site with the -station.

summary of the two sections above, when (1)2 is mixed with rods having two or three binding stations separated by linear non-hindered alkyl or ethylene glycol spacers, the quick formation of a kinetically favored intermediate is observed, followed by a slower migration to the best binding station. The kinetics of the overall process much depends on what is between the and -stations (length and chemical nature of the spacer, additional station), which is consistent with the hypothesis that the helix actually slides along the molecular track from the unhindered end to the bulkier side of the rod.

Threadingsliding vs. winding-unwinding mechanisms. To ascertain the sliding mechanism hypothesized above and to promote an alternate supramolecular pathway, we introduced double station rods 10 and 11 in which the spacers separating the two stations contain a bulky component (Figure 2C), either benzene or anthracene, that are a priori too large to pass through the cavity of (1)2 without a major distortion. In these designs, the helix may quickly thread onto the -station, but reaching the thermodynamically favored (1)210 and (1)211complexes requires a winding of the helix around the -station, presumably after its dissociation from the -station. Self-assembly processes were monitored as for other rods. As expected, upon mixing 10 with (1)2, a kinetically favored species assigned to (1)210 is quickly observed (Figure 6A,B). The emergence of a new set of resonances corresponding to (1)210 was considerably slower than with non-bulky spacers. Again, to compare the motion kinetics of (1)2 on rod equipped with bulky spacers the  value defined in Table 1 was used. The time to reach 50% of (1)2 on the station was found to be over 5 days (Figure 6C), a value which is almost 7 times larger than the one of the slowest linear foldaxane analog (1)22.

Foldaxane formation with (1)211 proceeded at the same rate as with (1)210 hinting at comparable mechanisms. Thus, a bulkier spacer does not further slow down binding to the station, suggesting that the benzene or anthracene moieties are not close to the helix during foldaxane formation. Sliding over the spacer at the cost of major distortions appears to be unlikely as it may be slower with the bulkier spacer. Furthermore, an additional experiment was performed in which single station foldaxane (1)212 was mixed with single station dumbbell rod 15. The latter matches exactly with the spacer and -station of 11, but it is not connected to any -station. As in previous studies, 9a the formation of (1)215 should occur via an unwindingrewinding mechanism. 1 H NMR monitoring of the mixture of (1)212 and 15 (Figure S23) showed that the rate of formation of (1)215 is very close to that of (1)210 and (1)211, suggesting that for these two as well, the helix unwinds and rewinds to move from the station to the station. These results altogether also confirm that the faster processes observed for rods 2-8 are dominated by sliding motions. In the case of triple station rod 9, reaching the  station is as slow as with 10 and 11, experimental results are thus not conclusive in this case as sliding and unwinding-rewinding cannot be distinguished and may both contribute.

CONCLUSION

Our results demonstrate how a clear sequence of events can be designed in a complex supramolecular system by exploiting the different time scales on which each of these events takes place. The anti-parallel form of dimer (1)2 was isolated by precipitation and then trapped in solution in foldaxane structures upon binding to rod-like guests before the parallel form of (1)2 had time to appear. Rod-like guest binding can be made to occur selectively through the kinetically favored less hindered end of the rod to produce a foldaxane on the first binding station, even though thermodynamically preferred binding stations may be available in the system. Once threading of the rod into (1)2 is achieved, sliding of (1)2 along the rod takes place at rates substantially faster than helix dissociation and re-association through an unwinding-rewinding mechanism. The sliding direction along the rod can be biased by installing a gradient of binding stations of increasing thermodynamic stability. Along the sliding path, small barriers can be installed such as long segments deprived of binding stations that do not significantly hamper motion. However, if a sufficiently large barrier is placed on the rod, sliding is blocked at the binding station that precedes the barrier and a slower dissociation and re-association through an unwinding-rewinding mechanism is imposed for (1)2 to reach a thermodynamically more favorable station placed further on the rod. These various kinetically controlled pathways illustrate the possible error correction mechanisms in the formation of multifoldaxanes from the loading of several foldamer helices onto multistation rods. 9c Further elaboration of controlled oriented foldaxane motions include the design of helical systems having different ends that can form a foldaxane only by threading the rod through one end and not the other. Such foldaxanes would thus have a front that can move towards one extremity of a rod and a back that can move towards the other extremity of the rod. Progress along these is currently being made in our laboratories and will be reported in due course.

Figure 3 .

 3 Figure 3. Structures in the solid state analyzed by single crystal x-ray crystallography of the antiparallel double helix of (1)2 and of its complexes with various oligocarbamate rods. (A-C) structure of (1)2: side views in tube (A) and CPK (B) representations and top view (C) in CPK representation. In (C), terminal pyridine trimers have been deleted to highlight the cavity of the helix; fluorine atoms are shown in light blue color. (D) Structure of the [3]foldaxane (1)212 in tube (double helix) and CPK (rod) representations. (E) Structure of the [3]foldaxane (1)213 in tube (double helix) and CPK (rod) representations. (F-I) Structure of (1)42. (F) Structure of the rod-like guest 2 as it exists in [5]foldaxane (1)42. (G) Side view of (1)42. The guest and the helices appear in CPK and tube representations, respectively. In (H) and (I) one double helix of (1)42 has been omitted on the strong binder or the weak binder stations, respectively to illustrate possible structures of (1)22 and (1)22, respectively. Only P helical enantiomers are shown. The structures belong to non-Sohncke (enantiogenic) space groups and thus also contain M enantiomers. Isobutoxy side chains and included solvent molecules have been omitted for clarity.

Figure 4 .

 4 Figure 4. Kinetic and thermodynamic characterization of foldaxane formation between (1)2 and double station rods 2-7. (A-E) Time dependent 1 H NMR spectra (400 MHz in CDCl3 at 290K, aromatic amide resonances region) showing the threading of 2 into (1)2 to form (1)22 and then (1)22. (A) initial antiparallel (1)2 (2 mM); (B) 15 min. after the addition of 2 (20 mM), then after (C) 20 hours, (D) 40 hours, (E) 56 hours at equilibrium. Resonances of the free double helix (1)2 are denoted with empty circles. Black circles and black squares indicate signals of (1)22 and (1)22, respectively. Stars denote aromatic resonances (protons in position 4 of 2,6-pyridine dicarboxamide rings). (F) Time traces of threading and sliding motion of (1)2 on rods 2 (+), 3 (▲), 4 (), 5 (), 6 (•) and 7 (). The concentration of host on each station was obtained through the integration of 1 H NMR amide resonances. (G) Schematic representation of the unidirectional sliding of the double helix along a double station rod.

  22 (1)23 (1)24 (1)25 (1)26 (1)27 (1)28 (1)29 (1)210 (1)211 (1)215

  a pseudo-first order kinetic constants k were calculated based on the integration of the 1 H NMR amide resonances corresponding to each complex (1)22 and (1)22. The slope extracted from the plot of -ln([(1)22]total) as function of time corresponds to the kinetic constant of the sliding process. Calculation was performed during the initial phase of the helix motion for which the back sliding can be considered negligible; b time required to reach 50% of (1)2 on the station corresponding to [(1)2station] = 1 mM; c competition experiment between (1)212 and (1)215. Double helix (1)2 is already threaded on 12 prior to the addition of a stoichiometric amount of 15; d proportion of (1)2 on rod 15. n. d.: not determined; n. a.: not applicable.

Figure 5 .

 5 Figure 5. (A) Formula of rod (top) and zoom on the binding pattern between rod 14 and the two strands of (1)2in an energy minimized model of (1)214 obtained by molecular mechanics (minimization with MMFFs force field) using Maestro v.6.5 (bottom); (B) Formula of rod 12 (top) and zoom on the binding pattern between rod 12 and the two strands of (1)2 as observed in the crystal structure (1)212 (bottom). The two strands of (1)2 are shown in tube representation and are colored in either salmon or light blue. The rod is shown in tube representation and color coding is as follow: carbon (grey), nitrogen (blue), oxygen (red) and hydrogen (white). Hydrogen bonds are shown in magenta. Excerpt of the 1 H NMR spectra (400 MHz, CDCl3, 298K) of the amide region of 1 (2 mM) in the presence of: (C) 2 equiv. of rod 12; (D) 2 equiv. of rod 14 and (E) 2 equiv. of both 12 and 14.

Figure 6 .

 6 Figure 6. Kinetic and thermodynamic characterization of foldaxane formation between (1)2 and triple and double station rods 8-11. (A-E) Time dependent 1 H NMR spectra (400 MHz in CDCl3 at 290K, aromatic amide resonances region) showing the fast threading of 10 into (1)2 to form (1)210and the slow conversion into (1)210. (A) 1 H NMR spectra of free (1)2 (2 mM); (B) 10 min. after the addition of 10 (20 mM), then after (C) 2 days, (D) 5 days and (E) 15 days at equilibrium. Black colored signals are those of the free (1)2 whereas red and blue resonances belong to (1)210 and (1)210, respectively. Green resonances were not assigned due to signal overlap. Stars denote aromatic resonances. (F) Time traces of the conversion of  into  complexes of (1)2 on rods 2 (+), 8 (), 9 (), 10 (+) and 11 (); unfolding-refolding of (1)2 from rod 12 to 15 (). Concentration of host on each station was assessed by 1 H NMR through the integration of the amide resonances

ACKNOWLEDGMENT

This work was supported by the China Scholarship Council (predoctoral fellowship to X.W.) and by the European Research Council under the European Union's Seventh Framework Programme (grant agreement no. ERC-2012-AdG-320892, post-doctoral fellowship to B.W.). The authors thank Brice Kauffmann (IECB-UMS 3033) for his help during data collection and resolution of the crystal structures.

ASSOCIATED CONTENT Supporting Information

The Supporting Information is available free of charge on the ACS Publications website at DOI: Experimental details for synthetic procedures, spectroscopic data (PDF). Crystallographic information files for (1)2, (1)212, (1)213, and (1)42 (CIF).

AUTHOR INFORMATION

Corresponding Authors *y.ferrand@iecb.u-bordeaux.fr *i.huc@iecb.u-bordeaux.fr Present Address † Department of Chemical Technology of Drugs, Poznan University of Medical Sciences, Grunwaldzka 6, 60-780 Poznan, Poland.

Notes

The authors declare no competing financial interest.