Keywords: Systèmes distribués, Algorithme distribué, Ensemble Maximal Indépendant, Réseaux Unidirectionels, Auto-stabilisation, Auto-stabilisation probabiliste

L'Auto-stabilisation d'un Ensemble Maximal Indépendant dans les Réseaux Unidirectionels est Difficile Résumé : Un algorithme distribué est auto-stabilisant si après que des fautes et des attaques ont frappé le système et l'ont placé dans un état global arbitraire, le système récupère en temps fini un fonctionnement correct sans intervention extérieure. Dans cet article, nous considérons le problème de la construction auto-stabilisante d'un ensemble maximal indépendant dans des réseaux uniformes et unidirectionels quelconques. Nous présentons un résultat négatif qui indique que dans les réseaux uniformes, l'auto-stabilisation déterministe de ce problème est impossible à résoudre. De plus, la propriété de silence (i.e. garantir qu'à partir d'un point de chaque exécution, les communications entre les noeuds du réseau sont fixées) est impossible à garantir, tant pour les variantes deterministes que probabilistes des protocoles.

Nos résultats positifs sont multiples. Nous présentons un protocole déterministe pour les réseaux unidirectionels identifiés quelconques qui présente une complexité en temps et en espace qui reste polynomiale, avec un ordonnancement asynchrone. Nous complétons l'étude avec des protocoles probabilistes dans le cas uniforme : le premier protocole requiert une mémoire infinie mais supporte un ordonnancement asynchrone, le deuxième protocole utilise une mémoire polynomiale mais requiert un ordonnancement synchrone. Les deux protocoles ont une compexité moyenne en temps polynomiale.

Introduction

One of the most versatile technique to ensure forward recovery of distributed systems is that of self-stabilization [START_REF] Edsger | Self-stabilizing systems in spite of distributed control[END_REF][START_REF] Dolev | Self-stabilization[END_REF]. A distributed algorithm is self-stabilizing if after faults and attacks hit the system and place it in some arbitrary global state, the system recovers from this catastrophic situation without external (e.g. human) intervention in finite time.

The vast majority of self-stabilizing solutions in the literature [START_REF] Dolev | Self-stabilization[END_REF] considers bidirectional communications capabilities, i.e. if a process u is able to send information to another process v, then v is always able to send information back to u. This assumption is valid in many cases, but can not capture the fact that asymmetric situations may occur, e.g. in wireless networks, it is possible that u is able to send information to v yet v can not send any information back to u (u may have a wider range antenna than v). Asymmetric situations, that we denote in the following under the term of unidirectional networks, preclude many common techniques in self-stabilization from being used, such as preserving local predicates (a process u may take an action that violates a predicate involving its outgoing neighbors without u knowing it, since u can not get any input from its outgoing neighbors). Related works Self-stabilizing solutions are considered easier to implement in bidirectional networks since detecting incorrect situations requires less memory and computing power [START_REF] Beauquier | Transient fault detectors[END_REF], recovering can be done locally [START_REF] Afek | Local stabilizer[END_REF], and Byzantine containment can be guaranteed [START_REF] Masuzawa | Bounding the impact of unbounded attacks in stabilization[END_REF][START_REF] Masuzawa | Stabilizing link-coloration of arbitrary networks with unbounded byzantine faults[END_REF][START_REF] Nesterenko | Tolerance to unbounded byzantine faults[END_REF].

Investigating the possibility of self-stabilization in unidirectional networks was recently emphasized in several papers [START_REF] Afek | Self-stabilizing unidirectional network algorithms by power supply[END_REF][START_REF] Cobb | Stabilization of routing in directed networks[END_REF][START_REF] Sajal | Self-stabilizing algorithms in dag structured networks[END_REF][START_REF] Delaët | Self-stabilization with r-operators revisited[END_REF][START_REF] Dolev | Self-stabilizing group communication in directed networks[END_REF][START_REF] Ducourthial | Self-stabilization with r-operators[END_REF][START_REF] Delaët | Tolerating transient and intermittent failures[END_REF][START_REF] Ducourthial | Self-stabilization with path algebra[END_REF][START_REF] Bernard | Optimal deterministic self-stabilizing vertex coloring in unidirectional anonymous networks[END_REF]. However, topology or knowledge about the system varies: [START_REF] Sajal | Self-stabilizing algorithms in dag structured networks[END_REF] considers acyclic unidirectional networks, where erroneous initial information may not loop; [START_REF] Afek | Self-stabilizing unidirectional network algorithms by power supply[END_REF][START_REF] Cobb | Stabilization of routing in directed networks[END_REF][START_REF] Delaët | Tolerating transient and intermittent failures[END_REF][START_REF] Dolev | Self-stabilizing group communication in directed networks[END_REF] assume unique identifiers and strongly connected so that global communication can be implemented; [START_REF] Delaët | Self-stabilization with r-operators revisited[END_REF][START_REF] Ducourthial | Self-stabilization with r-operators[END_REF][START_REF] Ducourthial | Self-stabilization with path algebra[END_REF] makes use of distinguished processes yet operate on arbitrary unidirectional networks.

Tackling arbitrary uniform unidirectional networks in the context of self-stabilization proved to be hard. In particular, [START_REF] Bernard | Optimal deterministic self-stabilizing vertex coloring in unidirectional anonymous networks[END_REF][START_REF] Bernard | Bounds for self-stabilization in unidirectional networks[END_REF] studied the self-stabilizing vertex coloring problem in unidirectional uniform networks (where adjacent nodes must ultimately output different colors). Deterministic and probabilistic solutions to the vertex coloring problem [START_REF] Gradinariu | Self-stabilizing vertex coloring of arbitrary graphs[END_REF][START_REF] Mitton | On fast randomized colorings in sensor networks[END_REF] in bidirectional networks have local complexity (∆ states per process are required, and O(∆) -resp. O(1)actions per process are needed to recover from arbitrary state in the case of a deterministic -resp. probabilistic-algorithm). By contrast, in unidirectional networks, [START_REF] Bernard | Optimal deterministic self-stabilizing vertex coloring in unidirectional anonymous networks[END_REF] proves a lower bound of n states per process (where n is the network size) and a recovery time of at least n(n -1)/2 actions in total (and thus Ω(n) actions per process) in the case of deterministic uniform algorithms, while [START_REF] Bernard | Bounds for self-stabilization in unidirectional networks[END_REF] provides a probabilistic solution that remains either local in space or local in time, but not both.

Our contribution In this paper, we consider the problem of constructing self-stabilizingly a maximal independent set in uniform unidirectional networks of arbitrary shape. It turns out that local maximization (i.e. maximal independent set) is strictly more difficult than local predicate maintainance (i.e. vertex coloring). On the negative side, we present evidence that in uniform networks, deterministic self-stabilization of this problem is impossible. Also, the silence property (i.e. having communication fixed from some point in every execution) is impossible to guarantee, either for deterministic or for probabilistic variants of protocols.

On the positive side, we present a deterministic protocol for networks with arbitrary unidirectional networks with unique identifiers that exhibits O(m log n) space complexity and O(D) time complexity in asynchronous scheduling, where n is the network size and D is the network diameter. We complement the study with probabilistic protocols for the uniform case: the first probabilistic protocol requires infinite memory but copes with asynchronous scheduling (stabilizing in time O(log n+log ℓ+D), where ℓ denotes the number of fake identifiers in the initial configuration), while the second probabilistic protocol has polynomial space complexity (in O(m log n)) but can only handle synchronous scheduling (stabilizing in time O((n + ℓ) log n)).

Outline The remaining of the paper is organized as follows: Section 2 presents the programming model and problem specification. Section 3 presents our negative results, while Section 4 details the protocols. Section 5 gives some concluding remarks and open questions.

Preliminaries

Program model A program consists of a set V of n processes. A process maintains a set of variables that it can read or update, that define its state. A process contains a set of constants that it can read but not update. A binary relation E is defined over distinct processes such that (i, j) ∈ E if and only if j can read the variables maintained by i; i is a predecessor of j, and j is a successor of i. The set of predecessors (resp. successors) of i is denoted by P.i (resp. S.i), and the union of predecessors and successors of i is denoted by N.i, the neighbors of i. The ancestors of process i is recursively defined as follows: predecessors of i are ancestors of i, and ancestors of each predecessor of i are also ancestors of i. The descendants of i are similarly defined using successors (instead of predecessors).

For processes i and j in V , d(i, j) denotes the distance (or the length of the shortest path) from i to j in the directed graph (V, E). We define, for convenience, the distance as d(i, i) = 0 and d(i, j) = ∞ if i is not reachable to j. The diameter D is defined as

D = max{d(i, j) | (i, j) ∈ V × V, d(i, j) = ∞}.
An action has the form name : guard -→ command . A guard is a Boolean predicate over the variables of the process and its predecessors. A command is a sequence of statements assigning new values to the variables of the process. We refer to a variable v and an action a of process i as v.i and a.i respectively. A parameter is used to define a set of actions as one parameterized action. Notice that actions of a process are completely independent of its successors.

A configuration of the program is the assignment of a value to every variable of each process from its corresponding domain. Each process contains a set of actions. In some configuration, an action is enabled if its guard is true in the configuration, and a process INRIA is enabled if it has at least one enabled action in the configuration. A computation is a maximal sequence of configurations γ 0 , γ 1 , . . . such that for each configuration γ i , the next configuration γ i+1 is obtained by executing the command of at least one action that is enabled in γ i . Maximality of a computation means that the computation is infinite or it terminates in a configuration where none of the actions are enabled. A program that only has terminating computations is silent.

A scheduler is a predicate on computations, that is, a scheduler is a set of possible computations, such that every computation in this set satisfies the scheduler predicate. We consider only weakly fair schedulers, where no process can remain enabled in a computation without executing any action. We distinguish three particular schedulers in the sequel of the paper: the distributed scheduler corresponds to predicate true (that is, all weakly fair computations are allowed). The locally central scheduler implies that in any configuration belonging to a computation satisfying the scheduler, no two enabled actions are executed simultaneously on neighboring processes. The synchronous scheduler implies that in any configuration belonging to a computation satisfying the scheduler, every enabled process executes one of its enabled actions.

The distributed and locally central schedulers model asynchronous distributed systems. In asynchronous distributed systems, time is usually measured by asynchronous rounds (simply called rounds). Let E = γ 0 , γ 1 , . . . be a computation. The first round of E is the minimum prefix of E, E 1 = γ 0 , γ 1 , . . . , γ k , such that every enabled process in γ 0 executes its action or becomes disabled in E 1 . Round t (t ≥ 2) is defined recursively, by applying the above definition of the first round to E ′ = γ k , γ k+1 , . . .. Intuitively, every process has a chance to update its state in every round.

A configuration conforms to a predicate if this predicate is true in this configuration; otherwise the configuration violates the predicate. By this definition every configuration conforms to predicate true and none conforms to false. Let R and S be predicates over the configurations of the program. Predicate R is closed with respect to the program actions if every configuration of the computation that starts in a configuration conforming to R also conforms to R. Predicate R converges to S if R and S are closed and any computation starting from a configuration conforming to R contains a configuration conforming to S. The program deterministically stabilizes to R if and only if true converges to R. The program probabilistically stabilizes to R if and only if true converges to R with probability 1.

Problem specification Each process i defines a function mis.i that takes as input the states of i and its predecessors, and outputs a value in {true, false}. The unidirectional maximal independent set (denoted by UMIS in the sequel) predicate is satisfied if and only if for every i ∈ V , either mis.i = true ∧ ∀j ∈ N.i, mis.j = false or mis.i = false ∧ ∃j ∈ N.i, mis.j = true.

Impossibility Results in anonymous networks

In this section, we consider anonymous and uniform networks, where processes of the same in-degree execute exactly the same code (note however that probabilistic protocols may exhibit different actual behaviors when making use of a random variable).

Theorem 1 There exists no silent self-stabilizing solution for the UMIS problem.

Proof.

Assume there exists such a solution and consider System A as depicted in Figure 1.(a). Since the protocol is silent, it reaches a terminal configuration where exactly one of the three processes, says a, has mis.a = true. Now consider the system in Figure 1.(b), with the states of the processes in the tail (that is b ′ and c ′ ) being the same as those in the 3-cycle (that is b and c). Both processes with state S ′ (b and b ′ ) have the same in-degree and the same predecessor; as the one in the cycle (b) is silent, the second one (b ′ ) is also silent. Both processes with state S ′′ (c ad c ′ ) have the same in-degree and the same predecessor state; as the one in the cycle (c) is silent, the second one (c ′ ) is also silent. As a result, both processes b ′ and c ′ in the tail of System B never move. Since the UMIS function is based solely on the current state, in-degree, and predecessor state, the UMIS function returns the same result for both processes b and b ′ in state S ′ and for both processes c and c ′ in state S ′′ . So, both processes b ′ and c ′ in the tail are not in the UMIS. Overall, System B describes a terminal configuration that is not a maximal independent set (the UMIS predicate does not hold at c ′ ).

2

Notice that the impossibility results of Theorem 1 holds even for probabilistic potential solutions. We now prove that relaxing the silence property still prevents the existence of deterministic solutions.

Theorem 2 There exists no deterministic self-stabilizing solution for the UMIS problem.

Proof.

Assume there exists such a solution and consider the two systems A and B that are depicted in Figure 1. We consider a computation of system A, that eventually Now, at any time, in System B, both processes b and b ′ are in the same state, with the same predecessors' states. As a result, the output of their mis function is the same. The same holds for processes c and c ′ . Since System A eventually ends up in a configuration from which all mis functions are stable, the same holds for system B, where mis.b ′ and mis.c ′ both return false. As a result, a UMIS is never constructed in System B. 2

Possibility Results

The previous impossibility results yield that for the deterministic case, only non uniform networks admit a self-stabilizing solution for the UMIS problem. In section 4.1, we present such a deterministic solution.

For anonymous and uniform networks, there remains the probabilistic case. We proved that probabilistic yet silent solutions are impossible, so both our solutions are non-silent. The one that is presented in Section 4.2 performs in asynchronous networks but requires unbounded memory, while the one that is presented in Section 4.3 performs in synchronous networks and uses O(m log n) memory per process.

Deterministic solution with identifiers

The intuition of the solution is as follows. Every process collects the predecessor information from all of its ancestors using the self-stabilizing approach given in [START_REF] Delaët | Tolerating transient and intermittent failures[END_REF][START_REF] Dolev | Superstabilizing protocols for dynamic distributed systems[END_REF][START_REF] Ducourthial | Self-stabilization with path algebra[END_REF]. From the collected information, each process i can reconstruct the exact topology of the subgraph consisting of all the ancestors and i itself. Then, depending on where the process is located, two possibilities can be considered:

1. The process is in a strongly connected component that includes all of its ancestors.

In the directed acyclic graph of strongly connected components, this process is in a source component. Then every process in the source component constructs the same topology. The MIS in this source component is constructed for example by giving processes priority in the descending order of identifiers (i.e., the process with maximal identifier has highest priority).

2. The process is in a non-source strongly connected component in the same acyclic graph of strongly connected components. Then, the same process as in the previous situation repeats, with the additional constraint that stronger priority is given to the processes in the upwards strongly connected components.

The detailed algorithm is given in Algorithm 4.1.

Algorithm

Topology i := {(id i , P i , 0)} ∪ j∈P.i {(id, ID, dist + 1) | (id, ID, dist) ∈Topology j }; while ∃(id, ID, dist), (id ′ , ID ′ , dist ′ ) ∈ Topology i s.t. id = id ′ and dist < dist ′ remove (id ′ , ID ′ , dist ′ ) from Topology i ; while ∃(id, ID, dist), (id ′ , ID ′ , dist ′ ) ∈ Topology i s.t. id = id ′ and ID = ID ′
remove one of them (arbitrarily) from Topology i ; while ∃(id, ID, dist) ∈ Topology i s.t. id is unreachable to i in Topology i remove (id, ID, dist) from Topology i ; UMIS(Topology i ) WorkingTp i := Topology i ; UMIS i := ∅ while ∃(id i , P i , 0) ∈ WorkingTp i { Let W be a source strongly connected component of WorkingTp i ; for each id ∈ W in the descending order of identifiers if UMIS i ∪ {id} is an independent set

UMIS i := UMIS i ∪ {id}; WorkingTp i := WorkingTp i -W ; } if id i ∈ UMIS i
output true; else output false; actions of process i true -→ update(Topology i ); UMIS(Topology i );

INRIA Lemma 1 Let i be any process. At the end of the k-th round (k ≥ 1) and later, the topology stored in variable Topology i is correct up to distance k -1:

1. for every process j with d(j, i) ≤ k -1, Topology i stores the correct tuple (j, P.j, d(j, i)) of j, and 2. every tuple (id, ID, d) ∈ Topology i is the correct one (j, P.j, d(j, i)) of some process j

if d ≤ k -1.
Proof.

We prove the lemma by induction on k. Let us observe first that the lemma holds for k = 1 (inductive basis): Once i executes its action, Topology i always contains (i, P.i, 0) and any other tuple (id, ID, d) satisfies d ≥ 1.

Assuming that the lemma holds for k (inductive hypothesis), we now prove the lemma for k + 1 (inductive step). Any process u with d(u, i) ≤ k satisfies d(u, j) = d(u, i)-1 ≤ k -1 for some predecessor j of i. From the inductive hypothesis, Topology j contains the correct tuple (u, P.u, d(u, j)) of u at the end of the k-th round and later. Thus, i reads the correct tuple (u, P.u, d(u, j)) in Topology j and updates its distance correctly at every action in the (k + 1)-th round and later. The hypothesis also implies that any tuple (u, ID, d) contained in Topology v of any predecessor v of i after the end of the k-th round satisfies d ≥ d(u, i) -1 and is correct if d = d(u, i) -1. Thus, the correct tuple (u, P.u, d(u, i)) is never removed from Topology i in the (k + 1)-th round or later. The first claim of the lemma holds for k + 1.

Existence of tuple (id, ID, d) (d = 0) in Topology i at the end of the (k + 1)-th round or later implies that i reads (id, ID, d -1) in Topology j of some predecessor j of i. From the hypothesis, any tuple (id, ID, d -1) contained in Topology j after the end of the k-th round is correct (or id is an identifier of a really existing process, say v, ID is the identifier set of P.v and d = d(v, j) holds) if d -1 ≤ k -1. Thus, any tuple (id, ID, d) contained in Topology i at the end of the (k + 1)-th round or later is correct if d ≤ k. The second claim of the lemma holds for k + 1.

2

The following corollary is derived from Lemma 1.

Corollary 1 Let i be any process and D(i) be the maximum distance to i from all the ancestors of i. At the end of the (D(i) + 1)-th round and later, Topology i stores the exact topology of the subgraph consisting of all the ancestors of i and i itself.

Proof. Concerning Topology i at the end of the (D(i) + 1)-th round and later, Lemma 1 shows that the correct tuple (u, P u , d(u, i)) of every ancestor u of i is contained, and any tuple (id, ID, d) with d ≤ D(i) is correct. This implies that Topology i at the end of the (D(i) + 1)-th round and later can contain no tuple (id, ID, d) with d > D(i) since the process with identifier id is not reachable to i in Topology i and such a tuple is removed from Topology i if exists. Thus the corollary holds.

2

Theorem 3 Algorithm 4.1 presents a self-stabilizing deterministic UMIS algorithm in asynchronous networks with identifiers. Its convergence time is D + 1 rounds where D is the diameter of the network, and the memory space used at each node is O(m log n) bits.

Proof.

Let T opology be the exact topology of the network. It is obvious that UMIS(Topology) correctly finds a UMIS when executed until WorkingTP = ∅ holds. When Topology i stores the exact topology of the subgraph consisting of all ancestors of i, UMIS(Topology i ) selects i as a member of UMIS iff UMIS(Topology) selects i: whether process i is selected by UMIS(Topology) depends only on the topology of the subgraph consisting of all ancestors of i. Corollary 1 guarantees that Topology i of every process i stores such exact topology at the end of the (D + 1)-th round and later, and thus, the theorem holds. As the Topology variable may end up in containing an entry for every node, the over space needed is O(m log n) bits per process.

2

Notice that Algorithm 4.1 enables each process i to know eventually the exact topology of the subgraph consisting of all the ancestors of i. Algorithm 4.1 can be easily extended so that each process can eventually get the exact topology containing the input values of the ancestors if each process has a static input value. Such an extension results in a universal scheme since it can solve any non-reactive problem that is consistently solvable at each process using the topology and the input values of its ancestors.

Another observation is that Algorithm 4.1 can easily be modified to become silent. For simplicity of our presentation, every process always has an enabled action with guard true, and thus, Algorithm 4.1 is not silent. But, Algorithm 4.1 becomes silent by changing the guard so that the action becomes enabled only when Topology i needs to be updated.

Probabilistic solution with unbounded memory in asynchronous anonymous networks

In this subsection, we present a probabilistic self-stabilizing UMIS algorithm for asynchronous anonymous networks. The solution is based on a probabilistic unique naming of the processes and a deterministic UMIS algorithm that assumes unique process identifiers. In the naming algorithm, each process is given a name variable that can be arbitrary large (thus the unbounded memory requirement). The naming is unique with probability 1 after a bounded number of new name draws. The new name draw consists in appending a random bit at the end of the current identifier. Each time the process is activated, a new random bit is appended. In parallel, we essentially run the deterministic UMIS algorithm presented in the previous subsection. The main difference from the previous algorithm is in handling the process identifiers. The variable Topology of a particular process may contain several different identifiers of a same process since the identifier of the process continues to get longer and longer in every execution of the protocol. To circumvent the problem, we consider two distinct identifiers to be the same if one is a prefix of the other, and anytime such same identifiers conflict, only the longest one is retained. Another difference is that we do not need the distance information. The distance information is used in the previous algorithm to remove the fake tuples (i, ID, d) of process i such that ID = P.i, which may exist in the initial configuration. In our scheme, tuples with fake identifiers that are prefixes of identifiers of real processes are eventually removed in Algorithm 4.2 since the INRIA correct identifier eventually becomes longer than any fake identifier. Other tuples with fake identifiers are eventually disconnected from the constructed subgraph topology. The details of the algorithm are given in Algorithm 4.2; only the topology update part is described since the UMIS function is the same as in Algorithm 4. Proof Sketch: It is clear that the identifier of any process eventually becomes distinct from any other's with probability 1. We first show that every process has a unique identifier in O(log n) expected rounds. We consider, as the worst-case scenario, the case where all processes start with the same identifier and each process appends only a single bit to its identifier in every round.

The probability that every process has a unique identifier at the end of round k (i.e., n random strings of k bits are mutually distinct) is evaluated as follows when n is small compared to 2 k :

n-1 i=1 (1 - i 2 k ) ≈ n-1 i=1 exp(- i 2 k ) = exp(- n(n -1) 2 k+1 ) ≈ exp(- n 2 2 k+1 )
We introduce a discrete random variable X to represent the number of rounds required until every process has a unique identifier. When we consider the execution after round 2 log n to guarantee n is small compared to 2 k , the expected number of rounds is then bounded by

2 log n + ∞ i=2 log n P rob(X > i) = 2 log n + ∞ i=2 log n (1 -exp(- n 2 2 i+1 )) ≈ 2 log n + ∞ i=2 log n n 2 2 i+1 = 2 log n + O(1)
Thus, every process has a unique identifier in expected O(log n) rounds.

Processes may still have same identifiers as those contained in fake tuples. By a similar argument to the above, we can see additional O(log ℓ) expected rounds are sufficient to give each process an identifier distinct from any fake one. Then, all the fake identifiers are removed from Topology i of each process i since such identifiers either become unreachable to i in Topology i or become prefixes of real indentifiers.

After all identifiers become distinct from one another, the topology stored in Topology i of each process i becomes stable if the process identifiers are ignored (i.e., only process identifiers get longer and longer). On the other hand, once the identifier of a process u becomes lexicographically larger than that of a process v, u's identifier is lexicographically larger than v's afterward. This guarantees that every execution of UMIS(Topology i ) at process i after some point returns the same result concerning whether process i is a member of the UMIS or not. By similar discussion to the proof of Theorem 3 we can show that additional O(D) rounds are sufficient to get the stable UMIS solution once every process has a unique identifier.

Consequently, Algorithm 4.2 presents a self-stabilizing probabilistic UMIS algorithm and its expected convergence time is O(log n + log ℓ + D) rounds. 2

Probabilistic solution with bounded memory in synchronous anonymous networks

The algorithm in the previous section is based on global unique naming, however, selfstabilizing global unique naming in unidirectional networks inherently requires unbounded memory. The goal of this subsection is to achieve, with bounded memory, a local unique naming that gives each process an identifier that is different from that of any of its ancestors, and to compute a UMIS based on the previously computed local naming. Indeed, such a local naming is sufficient for each process to recognize the strongly connected component it belongs to. Once the component is recognized, a UMIS can be computed by a method similar to that of the deterministic algorithm presented in Section 4.1.

In our scheme to achieve local unique naming, each process extends its identifier by appending a random bit when it finds an ancestor with the same identifier as its own. To be able to perform such a detection, a process needs to distinguish any of its ancestors from itself even when they have the same identifier. The detection mechanism is basically executed as follows: each process draws a random number, and disseminates its identifier INRIA together with the random number to its descendants. When process i receives the same identifier as its own, it checks whether the attached random number is same as its own. If they are different, the process detects that this is a distinct process (that is, a real ancestor) with the same identifier as its own current identifier. When the process receives the same identifier with the same random number as its own for a given period of time, it draws a new random number and repeats the above procedure. Hence, as two different processes eventually draw different random numbers, eventually every process is able to detect an ancestor with the same identifier if such an ancestor exists.

The above method may cause false detection (or false positive) when a process receives its own identifier but with an old random number. To avoid such false detection, each identifier is relayed with a distance counter and is removed when the counter becomes sufficiently large. Moreover, the process repeats the detection checks while keeping sufficiently long periods of time between them. The details of the self-stabilizing probabilistic algorithm for the local naming are presented in Algorithm 4. Proof sketch: First we show that the algorithm is a self-stabilizing probabilistic local naming algorithm. For contradiction, we assume that two processes i and j (where j is an ancestor of i) keep a same identifier after a configuration. Without loss of generality, the distance from j to i is minimum among process pairs keeping same identifiers. Let j, u 1 , u 2 , . . . , u m , i be the shortest path from j to i. Since all processes in the path have mutually distinct identifiers except for a pair i and j, (id j , rnd j ) is not discarded in the intermediate processes and is delivered to i. Thus, eventually i detects id i = id j and rnd i = rnd j . Then i extends its identifier by adding a random bit, which is a contradiction. We evaluate the expected convergence time of the algorithm. By similar argument to the proof of Theorem 4, we can show that the expected number of bits added to a process identifier is O(log n). Notice that the number ℓ of fake identifiers has no influence to the evaluation, for the distance dist of a fake identifier is larger than the timer value (once the timer is reset) and thus is removed (because of dist > |{id | (id , * , * ) ∈ ID i }|) when function naming is executed. On the other hand, in the scenario where all processes start with a same identifier, the time between two executions of function naming at a process is O(n + ℓ). Thus, the expected convergence time is O((n + ℓ) log n) rounds.

2 Algorithm 4.4 presents a self-stabilizing UMIS algorithm in locally-named networks. Thus, the fair composition [START_REF] Dolev | Self-stabilization[END_REF] of the algorithm with the local-naming algorithm in Algorithm 4.3 provides a self-stabilizing UMIS algorithm in synchronous anonymous networks. For simplicity, we omit the code for removing fake initial information in Algorithm 4.4 since such fake initial information can be removed in a similar way to Algorithm 4.3. Proof sketch: It is obvious that variable Topology i of each process i after D rounds consists of tuples (id, P.(id)) from all the ancestors of i . Notice that the local naming allows two distinct processes to have a same identifier if they are mutually unreachable. Thus, Topology i may contain a same tuple (id, P ) of two or more distinct processes and/or may contain two tuples (id, P ) and (id, P ′ ) with a same id but different predecessor sets P and P ′ .

Each process constructs the following graph G i = (V i , E i ): V i = {id | (id, * ) ∈ Topology i } and E i = {(u, v) | (v, P ) ∈ Topology i s.t. u ∈ P }. In other words, G i can be obtained from the actual graph G as follows: First consider the subgraph G ′ i induced by the ancestors of i and i itself, and then merge the processes with the same identifier into a single process.

It is obvious that all processes in G i are reachable to i. What we have to show is that process j is reachable from i in G i (or j belongs to the strongly connected component of i) if and only if j is also reachable from i in G ′ i . The if part is obvious since G i is obtained from G ′ i by merging processes. The only if part holds as follows. Consider two distinct processes j INRIA the processes in the component become stable, where n ′ is the number of processes in the component.

The same argument can be applied to a source strongly connected component in the graph obtained from G by removing the components with stabilized UMIS outputs. By repeating the argument, we can show that the UMIS outputs of all the processes become stable in O(n) rounds. It is clear that the processes with the UMIS outputs of true form a UMIS.

2 From Lemmas 2 and 4, the following theorem holds.

Conclusion

Although in bidirectionnal networks, self-stabilizing maximal independent set is as difficult as vertex coloring [START_REF] Gradinariu | Self-stabilizing vertex coloring of arbitrary graphs[END_REF], this work proves that in unidirectionnal networks, the computing power and memory that is required to solve the problem varies greatly. Silent solutions to unidirectional uniform networks coloring require Θ(log n) (resp. Θ(log δ), where δ denotes the maximal degree of the communication graph) bits per process and have stabilization time Θ(n 2 ) (resp. Θ(1)) when deterministic (resp. probabilistic) solutions are considered. By contrast, deterministic maximal independent set construction in uniform networks is impossible, and silent maximal independent set construction is impossible, regardless of the deterministic or probabilistic nature of the protocols.

While we presented positive results for the deterministic case with identifiers, and the non-silent probabilistic cases, there remains the immediate open question of the possibility to devise a probabilistic solution with bounded memory in asynchronous setting.

Another interesting issue for further research related to global tasks. The global unique naming that we present in section 4.2 solves a truly global problem in networks where global communication is not feasible, by defining proper equivalences classes between various identifiers. The case of other classical global tasks in distributed systems (e.g. leader election) is worth investigating.

Figure 1 :

 1 Figure 1: Impossibility of self-stabilizing UMIS

  INRIA ends up in a stable output of the mis function for all processes a, b, and c (a being the one process with mis.a = true), and construct a sibling execution in System B as follows: processes b and b ′ (resp. c and c ′ ) in System B have the same initial states as b (resp. c) in System A, anytime process b (resp. c) is executed in System A, both processes b and b ′ (resp. c and c ′ ) are executed in System B, anytime a is executed in System A, a is also executed in System B.

Lemma 3

 3 In the algorithm presented in Algorithm 4.4, each process can exactly recognize the topology of the strongly connected component it belongs to in O(D) rounds where D is the diameter of the network.

Theorem 5

 5 Fair composition of algorithms presented in Algorithm 4.3 and Algorithm 4.4 provides a self-stabilizing probabilistic UMIS algorithm in synchronous anonymous networks. Its expected convergence time is O((n + ℓ) log n) rounds where ℓ is the number of fake identifiers in the initial configuration. The space complexity of the resulting protocol is O(n log n).

  4.1 Deterministic UMIS algorithm in asynchronous networks with identifiers

	constants of process i
	id i : identifier of i;
	P i : identifier set of P.i;
	variables of process i
	Topology

i : set of (id, ID, dist) tuples; // topology that i is currently aware of. // id: a process identifier // ID: identifier set of P.(id) // dist: distance from id to i in Topology i . function update(Topology i )

  1.

	Algorithm 4.2 Probabilistic UMIS algorithm in asynchronous anonymous networks
	variables of process i
	id i : identifier (binary string) of i;
	P i : identifier set of P.i;
	Topology i : set of (id, ID) tuples; // topology that i is currently aware of.
	// id: a process identifier
	// ID: identifier set of P.(id)
	function
	update(Topology i )
	id

i := append(id i , random bit); // append a random bit to the current id

Topology i := {(id i , P i )} ∪ j∈P.i Topology j ; while ∃(id, ID), (id ′ , ID ′ ) ∈ Topology i s.t. id ′ is a prefix of id remove (id ′ , ID ′ ) from Topology i ; while ∃(id, ID) ∈ Topology i s.t.

id is unreachable to i in Topology i remove (id, ID) from Topology i ; Theorem 4 Algorithm 4.2 presents a self-stabilizing probabilistic UMIS algorithm in asynchronous anonymous networks. Its expected convergence time is O(log n + log ℓ + D) rounds where D is the diameter of the network and ℓ is the number of fake identifiers in the initial configuration.

3 .

 3 Algorithm 4.3 Probabilistic local naming in synchronous anonymous networks variables of process i id i : identifier (binary string) of i; rnd i : random number selected from {1, 2, . . . , k}; // k (≥ 2) is a constant ID i : set of (id, rnd, dist) tuples; // identifiers that i is currently aware of. // id: a process identifier // rnd: random number of P.(id) // dist: distance that id traverses function update(ID i ) ID i := {(id i , rnd i , 0)} ∪ j∈P.i {(id, rnd, dist + 1) | (id, rnd, dist) ∈ID j }; while ∃(id, rnd, dist) ∈ ID i s.t. dist > |{id | (id, * , * ) ∈ID i }|; remove (id, rnd, dist) from ID i ; if timer > |{id | (id, * , * ) ∈ID i }| // timer is incremented by one every round naming(ID i ) naming(ID i ) if ∃(id i , rnd, * ) ∈ ID i s.t. rnd = rnd i id i := append(id i , random bit); // append a random bit to the current id rnd i := number randomly selected from {1, 2, . . . , k};

	Lemma 2 Algorithm 4.3 presents a self-stabilizing probabilistic local naming algorithm in
	synchronous anonymous networks. Its expected convergence time is O((n + ℓ) log n) rounds
	where ℓ is the number of fake identifiers in the initial configuration.
	reset timer; // reset timer to 0
	update(ID i );
	actions of process i
	true -→ update(ID i );

RR n 6880


Roberto Improta

Thierry Douki
email: thierry.douki@cea.fr

Chapter 1: Photoinduced processes in DNA: basic theoretic and experimental features

This chapter is intended to provide a concise overview on some basic and general concepts of photophysics/photochemistry useful for the understanding of the following chapters. After a general and easy introduction on the theoretical basis of the interaction between light and molecules, we shall briefly describe the principle of the most used steady-state and Time-resolved experimental spectroscopy techniques.

Then we shall introduce the most used analytical techniques to quantify and characterize the photodamage and describe the main biological phenomena associated with DNA damage and repair.

Introduction

This book describes the main processes triggered by the interaction of UV light with nucleic acids, either direct or indirect through the mediation of other compounds, and discuss some of the resulting biological consequences. It is not possible, obviously, to treat, even rapidly, all the scientific and technical aspects involved in the study of such Royal Society of Chemistry -Book Chapter Template a large variety of phenomena. On the other hand, it can be helpful for the readers to concisely review some basic features of the techniques, experimental or computational, most commonly used to investigate these processes, and the general concepts/models employed for their interpretation, focussing essentially on those most thoroughly used in the following chapters. This is the goal of the present introductory chapter. Some parts will be obvious to chemists and some to biologists. Hopefully, the all readers will share a common language and will be able to gather useful information from the whole volume.

Some theoretical basis

According to Quantum Mechanics (QM), the behaviour of atom and molecules is governed by the Hamiltonian operator, which contains all the energy terms associated to electrons and nuclei [START_REF] Atkins | Molecular Quantum[END_REF][START_REF] Szabo | Modern Quantum Chemistry: Introduction to Advanced Electronic Structure Theory[END_REF] . The solution of the associated Schrödinger equation, which allows predicting the time evolution of the system, is much simpler by resorting to the Born-Oppenheimer (BO) approximation, which provides the separation of the motion of electrons and nuclei, the latter being much heavier and, therefore, much slower. In this framework, for a molecule we can identify different electronic states (i.e. the solution of the electronic Hamiltonian) differing on the distribution of the electrons in the Molecular Orbitals (MO). It is then possible to compute for each molecule a ground electronic state with its equilibrium geometry, corresponding to the structure where the total energy (electron + nuclei) of the molecule reaches its minimum. Please remind that the total energy is negative so a decrease of the energy corresponds to a stabilization of the system. When the ground electronic state (sometimes labelled as Royal Society of Chemistry -Book Chapter Template GS) is a singlet (i.e. all the electrons are spin paired in their MOs) is very often labelled as S0.

Figure 1.1. Schematic description of some of the changes in the electronic states population induced by light irradiation of a molecule (using thymine as example).

As schematically depicted in Figure 1.1. When a molecule absorbs a photon of appropriate energy, i.e. corresponding to the energy difference between the 'ground' and an 'excited' electronic state, an electron is promoted to some vibrational level in the excited singlet manifold (S1, S2, S3 in order of increasing energy) [START_REF] Turro | Modern Molecular Photochemistry[END_REF] . However, not all the transitions are 'allowed', i.e. for symmetry reasons light absorption can populate some excited states (labelled as bright excited states) and not others (dark excited states). For example, in the molecule depicted above (thymine), the lowest energy bright excited state corresponds to S2 and can be described as due to a * (indicating that the transfer is from a  to a * MO symmetry of the involved MOs) transition. In thymine it involves the transfer of an electron from the Highest Occupied Molecular Orbital (HOMO, a  MO) to the lowest unoccupied MO (LUMO, a * MO). A similar transition is usually described as HOMO LUMO. S1, i.e. the lowest energy excited Royal Society of Chemistry -Book Chapter Template state in the ground state minimum, is a dark n*, involving a Lone Pair of the carbonyl oxygen, which is the second highest Occupied Molecular Orbital (HOMO-1) and the same * LUMO. This transition is usually labelled as HOMO-1 LUMO. In addition to excited states having the same multiplicity as the ground electronic state (a singlet in our example), we can have excited electronic states with different multiplicity, as the Triplets (T1, T2, T3 in order of increasing energy), where the two electrons in the 'half filled' MO's have the same spin. These excited states, which can be described by following a similar framework used below for the singlets, i.e. based on the occupied MO's, cannot be reached directly by light irradiation but, as discussed below, can also play a role in the photoactivated dynamics. We highlight that we have just described the different adiabatic states (S1, S2, T1, etc) according to their 'diabatic' nature, related to the occupancy of the different electronic states. The 'adiabatic' description simply denote the relative energy of the different 'adiabatic' electronic state for a give nuclear structure. As a consequence, the mapping between adiabatic and diabatic picture can thus depend on the considered geometry. In other words, as we'll see below, we can find nuclear arrangements where, in the example we have used, S1, i.e. the lowest energy adiabatic state, corresponds to a * transition, i.e. to a different diabatic state than in the ground state minimum.

After light absorption, our molecule is now on S2 electronic state. The process of light absorption is extremely rapid (≤1 fs) and the nuclei can be considered frozen on that time-scale, i.e. they still have the 'optimal' arrangement for S0. Within the BO approximation, as we discussed above for S0, we can associate to each electronic state a Potential Energy Surface, which tells how the energy of this state changes due to the motion of the nuclei. The molecule thus starts evolving on the S2 PES, i.e. the nuclei start readjusting to find the new minimum energy structure and the total energy Royal Society of Chemistry -Book Chapter Template of S2 starts decreasing, and can reach its minimum. In its minimum can be the * diabatic state is the lowest energy excited state (S1), whereas the n* state now corresponds to S2.

Figure 1.2. Jablonski diagram of the main photophysical processes in a molecule photoexcited on S2.

One possibility is then that the molecule emits light and so we have a radiative decay to S0. This process is known as fluorescence, when emission takes place from a single state, but eventually it can also happen from a triplet state called phosphorescence (Figure 1.2 straight arrows). The ratio between the photons absorbed and emitted is defined as Fluorescence Quantum Yield (often abbreviated as QY and sometimes as ). The concept of QY is very important in the study of radiation-induced processes and it is not limited to fluorescence, but it can be extended to any possible photoactivated event, as the ratio between the number of events occurring in the Royal Society of Chemistry -Book Chapter Template system and that of photon absorbed. For example, in Chapter 2, 3 etc, we shall often refer to the QY of the different photochemical processes.

As depicted in Figure 1.2 (curved arrows) a bright excited state can also decay nonradiatively by internal conversion to dark excited states (both singlet and triplets) or, directly, to S0. This process is usually described as 'internal conversion' (IC) or as intersystem crossing (ISC), depending if involves states with the same or with different spin multiplicity. The non-radiative decay is particularly effective in the proximity of the surface crossings, i.e. when two different PES are degenerate (Figure 1.3). In these regions, the BO approximation is not valid, and the so-called non-adiabatic coupling effects and, for singlet/triplets crossings, Spin-Orbit couplings need to be taken in account to correctly describe the evolution of the molecular system. For only two coordinates, the intersection between the PES of two states of different symmetry is a single point and the PES can adopt a typical 'conic' shape (with the degeneracy point being the vertex), giving account of the term 'conical intersection' (CI) usually adopted to define the lowest energy structure of a crossing seam between two singlet states. A similar structure for crossing between states of different multiplicity the more general label of minimum energy crossing point (MECP) can be used. The presence of an easily accessible crossing region with S0 on the PES of a bright excited state leads to a very fast and effective non-radiative ground state recovery, mirrored by an ultrashort excited state lifetime.

Strongly fluorescent molecules have QY close to 1 and radiative lifetime of several nanoseconds. The fluorescence QY of DNA and of its component is instead extremely low (10 -3 10 -4 ) and the lifetime of the bright excited states is of a few ps (at maximum).

Actually, for nucleobases an almost barrierless path on the PES of the bright excited states leads to a crossing region with S0 (see chapter 2). Moreover, for oligonucleotides, the bright excited state can decay to almost-dark excited states (for example transitions with Charge Transfer character) which then return to S0, non radiatively, by charge recombination. From the computational point of view, a full understanding of the photoactivated dynamics requires the complete characterization of the PES's of the electronic states, of their crossings, stationary points, and the characterization of the spectral signatures of such stationary points (e.g. absorption and emission spectra). This 'static' picture can already give useful insights on the most important excited state processes, and it is nowadays quite routinely applied to many systems, including oligonucleotides. On the other hand, the simulation of the excited state dynamics requires also the determination of the non-adiabatic couplings between the different electronic states and the application of dynamical methods, either semiclassical (i.e. the motion of the nuclei is described according the classical law of mechanics) or quantum dynamical (i.e. describing also the motion of the nuclei at a QM level). Thanks to the development of more accurate computational methods, efficient software and the continuously increasing computing power, the possibility of studying, at the computation level, the excited state dynamics of molecular systems has known impressive advances in the last years, as witnessed also by many chapters of this book. [START_REF] Improta | [END_REF] .

Notion of spectrum in photobiology

All photochemical reactions and photobiological processes are strongly dependent on the wavelength of the incident photons. The notion of spectrum is fundamental and is used in several ways.

Emission spectrum of the light source

The first major parameter that needs to be properly assessed in real-life or laboratory experiments is the characterization of the light source to which the samples of interest are exposed. This emission spectrum described the intensity of the radiation over a Royal Society of Chemistry -Book Chapter Template chosen range of wavelengths. This task is performed with more or less sophisticated radiometer. Obviously, values cannot be provided for the infinite number of wavelengths but on small wavelengths intervals the width of which defines the resolution of the measuring device, the radiometer. Not all light sources consist of mixture of radiation. For example, lasers emit photons at a single wavelength. They are referred to as monochromatic. A correct assessment of the emission spectra of sources used in photobiology is of paramount importance. For example, works on the effects of UVA can be completely misinterpreted if traces of contaminant UVB are present in the emitted radiation because photons in this wavelength can be as high as 2 or 3 orders of magnitude more biologically efficient than in the UVA.

Absorption spectrum

A first necessary step for a photochemical reaction or a photobiological process to be triggered is the absorption of a photon by a component often described as the chromophore. The ability of a molecule to absorb photons of different energies are shown by its absorption spectrum. They report the proportion of incident energy of a monochromatic radiation. The absorption is maximal when the absorbed energy corresponds to the energy of a transition between the ground state of the chromophore and one of its excited states. The transitions may for example, as anticipated in the previous section, correspond to be * (excitation of single bonds), * (excitation of double bonds) or n* (excitation of unpaired electrons). As a general trend, * are more energetic than * transitions. It should be stressed that the excitation energy decreases for conjugated double bonds and double bonds inserted in aromatic structures. The combination of these individual transitions constitute the complete Royal Society of Chemistry -Book Chapter Template absorption spectrum of the chromophore. For chemists, absorption at a specific wavelength is characterized by the molecular absorption coefficient  expressed in cm - 1 M -1 (with M in mole L -1 ).  is similar to the absorption cross section used by physicists.

The absorption coefficient is used in the beer lambert law to determine the transmitted energy:

𝐸 𝑡𝑟𝑎𝑛𝑠𝑚𝑖𝑡𝑡𝑒𝑑 = 𝐸 𝑖𝑛𝑐𝑖𝑑𝑒𝑛𝑡 × 10 𝜀×𝑙×𝑐
where l is the optical path,  the absorption coefficient and c the concentration of the solution.

This exponential function reflects that most the energy is deposited in the upper layers of the irradiated medium. This observation is of paramount importance in some experiments performed with intense light and highly absorbing media where significant heating or undesired multiphotonic processes can take place.

Action spectrum

The onset of a physiological or cellular response to exposure to light is much more complex than photochemical processes in molecules. To overcome these limitations, photobiologists often use action spectra that report the variation of extent of the studied response over a specific range of wavelengths. From a practical point of view, data are collected within a series of narrow wavelengths ranges and data are fitted to provide a continuous spectrum. A widely used example is the erythema action spectra defined by the CIE (Commission International de l'Eclairage) shown in Figure 1.4 A first use of action spectra is the comparison and the prediction of the effect of different broadband sources. In this case, the emission spectrum is multiplied by the action spectrum of interest, thereby yielding a "weighted emission spectrum". For example, the erythemal weighted emission spectrum is often used to convert physical doses into more biologically relevant units, which are fractions or multiples of erythemal doses. A second interest of action spectra is the identification of the cellular chromophores involved in photobiological responses. Indeed, the wavelength corresponding to the maximal amplitude of the studied effect is likely to correspond to a maximum of the absorption spectrum of the initial chromophore. This strategy is not always so straightforward since specific cellular features (attenuation of the incident light, local pH effects, structural constraints, etc.) may significantly affect the absorption properties of the chromophore by comparison with the pure molecule in solution.

Royal Society of Chemistry -Book Chapter Template

A Basic introduction to pump-probe spectroscopies

Independently of the computational developments, our knowledge of the photoactivated dynamics of NAs has hugely profited (as well as many other fields) from the impressing advances made by Time Resolved (TR) spectroscopies in the last decades. Though steady state spectra can provide interesting insights on the main photophysical and photochemical paths, it is clear that the possibility of monitoring how spectral signals change with time, often with < 100 fs resolution, opens new perspectives to our understanding of these complex phenomena. A detailed discussion of each technique, though limiting our discussion to those more commonly used to investigate nucleic acids, is outside the scope of the present book. In the following chapters, the interested reader can find some concise explanations on specific techniques. We here simply sketch some principles of pump-probe spectroscopies, which allow obtaining time-resolved signals. [START_REF] Shukla | Radiation Induced Molecular Phenomena in Nucleic Acids: A Comprehensive Theoretical and Experimental Analysis[END_REF][START_REF] Egelman | Comprehensive Biophysics[END_REF][START_REF] Cerullo | [END_REF] . In these techniques, at least two laser pulses interact with the system under investigation. After the first one, the pump, a certain percentage of the molecules populate an excited electronic state. Then a second pulse, the probe, is used to obtain information on the excited state dynamics. A transient spectrum is acquired by measuring the differential transmission, ΔT/T, of the probe with and without the excitation from the pump at a series of different time delays between the two pulses. Just to make some examples, once the pump has excited some of the molecules on the excited state PES depicted in Figure 1.5, the probe can further excite some of them to a higher lying electronic state (Sn), according to a process usually named as Excited State Absorption, ESA).

Consequently, in our spectra will have an absorption corresponding to the wavelength of the S1Sn transition. On other hand, for some wavelengths, the excited state will absorb 'less' than the ground electronic state. In these regions, considering that part Royal Society of Chemistry -Book Chapter Template of the ground state population is on the excited state (ground state bleaching) we shall record 'negative' absorption with respect our reference. Analogously, for wavelength close to those of the fluorescence maximum of the excited state, we can have stimulated emission, which also translates in a negative signal. By measuring this broadband spectrum with different pump-probe delay, it is thus possible to obtain TR information on different excited state processes. This information can be crossedchecked from that obtained by other techniques, for example Fluorescence UPconversion, monitoring the fluorescence of the sample, in order to more easily disentangle the excited state processes. Another important parameter is the energy of the pump and the probe. Since DNA absorbs in the UV, usually the pump falls in this spectral region. A probe in the UV will then provide information on electronic processes, as those described above. If the probe energy is sufficiently high, some of the molecules can be ionized (and we can measure a Time-resolved photoionization spectrum). At the other end of the spectrum, if the probe is in the IR region, it is possible to obtain indications on the vibrational spectra of the excited state minima, with positive/negative peaks depending if the excited state minimum absorbs more or less than the ground state minimum in a given region. In addition to these broadband spectra, it is possible to monitor the TR spectra at selected wavelengths, also obtaining very useful information. For example, monitoring the transient absorption spectrum at the wavelength where the GS strongly absorbs, we can measure the time necessary to recover the GS population and, therefore, on the excited state lifetime.

Royal Society of Chemistry -Book Chapter Template

Figure 1.5 Pictorial Scheme of the possible processes observed in a pump-probe experiments (see text for details). The energy or the wavelength is on the x scale. A

possible change in the signal with time from t=1 to t=2 is also pictorially shown.

Analytical tools for the detection of DNA damage

A large fraction of the scientific advances discussed in the present volume relies on the accurate quantification of DNA damage. Those are either dimeric photoproducts (cyclobutane pyrimidine dimers, CPD; pyrimidine (6-4) pyrimidone photoproducts, 64PP; Dewar valence isomers, Dew) or oxidation products (single strand breaks, SSB; 8-oxo-7,8-dihydroguanine, 8-oxoGua). The following section describes the most widely applied techniques, including immunological detection, electrophoresis-based assays and chromatography combined with mass spectrometry. Some techniques will Royal Society of Chemistry -Book Chapter Template not be described here. Early assays such a use of radiolabelled DNA are still used in specific cases. 32 P-post labelling also received some recent applications. Very recent approaches such as the use of next generation sequencing will be discussed in specific chapters of the volume.

Antibody-based assays

Immunological detection of dimeric photoproducts is a widely used approach in photobiology. This class of techniques relies on the production of polyclonal or monoclonal antibodies raised against UV-irradiated DNA or oligonucleotides 8,9 .

Precise characterization works allowed several groups to produce antibodies specific against each of the three main classes of bipyrimidine dimers, namely CPDs, 64PPs

and Dews. These antibodies are then used in different types of assays to reveal the presence of photoproducts. These techniques, when applied to isolated or extracted DNA, include among others radioimmunoassays, enzyme-linked immunosorbent assay and immuno-dot-blot. In whole cells, flow cytometry has also been used. A unique opportunity afforded by immunological assays is the possibility to localize the photoproducts in tissues, for instance in skin, by using immunohistochemistry. A limitation of immunological assays is that results are often obtained in arbitrary units rather than in absolute frequency of damage. Another drawback is that, for a given type of dimeric photoproduct, no difference is made between the TT, TC, CT and CC derivatives. Antibodies are also used for the quantification of oxidized bases such as 8-oxoGua by ELISA. However, the accuracy and the specificity of the results has been challenged.

Electrophoresis-based assays

Electrophoretic separation of biomolecules such as DNA and proteins is a powerful tool relying on large differences in molecular weight and electrical charge.

Consequently, electrophoretic techniques have been extensively used for the quantification of strand breaks in DNA. Pulsed field gel electrophoresis has long been the reference technique for double-strand breaks while the Comet assay has become a standard for the detection of SSB and alkali-labile sites 10 . Valuable data have also been obtained by alkaline gel elution. Such methods cannot be directly applied to dimeric photoproducts or oxidized bases, which are stable and do not induce DNA

cleavage. Yet, this type of damage can be converted into additional strand breaks by using purified repair enzymes as biochemical tools 11 . The most commonly used for detecting CPDs is the endonuclease V of phage T4. Detection of oxidized purine bases can be performed with the bacterial formamidopyrimidine DNA glycosylase (Fpg) and less frequently with the human oxidized guanine glycosylase 1 (OGG1), which is more specific than Fpg for 8-oxoGua. Oxidized pyrimidines are most frequently visualized by using the bacterial endonuclease III (EndoIII).

Chromatography-based assays

Chromatographic approaches have also been designed to quantify DNA damage.

These techniques involve extraction of DNA, hydrolysis aimed at releasing damage and separation of the hydrolysed DNA mixture on a chromatographic system with appropriate detection 12 . This strategy is very specific and provide information on individual damage, often simultaneously in a single analysis. In addition, because the detection can be easily calibrated, results are quantitative. They are for example expressed in number of damage per million normal bases. The hydrolysis step can be Royal Society of Chemistry -Book Chapter Template performed under strong acidic conditions and releases damage as modified bases. A milder approach that prevents degradation of brittle lesions involves the combination of enzymes such as endonucleases, phosphodiesterases and phosphatase. Under these conditions, monomeric damage are released as nucleosides (base + 2deoxyribose) and dimeric photoproducts as dinucleoside monophosphates. The chromatographic system used for the separation of the hydrolysed mixture is most often high performance liquid chromatography, although gas chromatography following derivatisation into volatile compounds can be used. The most commonly used detection is mass spectrometry, and in particular tandem mass spectrometry used in the "multiple reaction monitoring" mode. This detection method provides two levels of specificity, one on the molecular mass and the other on the mass to charge ratio of specific fragments. These features, combined with chromatographic properties, insure unique specificity and make possible the simultaneous detection of several damage. The assay has been successfully applied to the three types of photoproducts for which TT, TC, CT and CC derivatives can be quantified individually.

Oxidized bases such as 8-oxoGua have also been detected by HPLC-MS/MS. In this case, a limitation comes from the possible induction of artifactual oxidation of DNA extraction step. The damage is too bulk or distorting, which leads to the blockage of the polymerase.

The replication fork is stalled which leads ultimately to the induction of DBS when the cell attempts to resume replication. If the cell does not die, DSB can be at the origin of chromosomal aberrations.

Consequences of mutations are the most drastic in genes coding for proteins but the effects in non-coding portions of DNA such as those involved in the formation of miRNA should be fully evaluated. The impact of a mutation in a gene is determined at Royal Society of Chemistry -Book Chapter Template two levels. It first should be briefly reminded that the genes have first to be translated into RNA, in a process that is based like replication on the complementarity between bases. A main difference is the presence of uracil instead of thymine and of ribose instead of 2-deoxyribose in RNA. The RNA strand is then spliced and some fragments (exons) are ligated and excreted from the nucleus to the cytoplasm. There, these messenger RNAs (mRNA) are used as templates for the synthesis of the proteins. The mRNA is read by triplet of bases (codon), each codon driving the incorporation of a specific amino acid as defined in the genetic code. In case of induction of a mutation in a gene, the sequence of the corresponding mRNA is not that expected and some codons do not exhibit the proper triplet of bases. Because some amino acids are coded by more than one codon, this may correspond to a silent mutation, which do not change the sequence of the protein. More often, the mutation changes the codon into one coding for another amino acid. Alternatively, the abnormal codon can be a stop codon, in which case the synthesized protein is truncated. When the protein is mutated or truncated in portions important for its structure or its enzymatic activity, the abnormal protein may lose or gain functions. If such events take place in proteins involved in the regulation of division, cells may gain a replication advantage. This process actually represent initiation, the first step of tumour development [START_REF] Alexandrov | [END_REF]15 .

Principle of DNA repair

Because of the drastic deleterious effects of DNA damage, all cell types are equipped with sets of proteins capable of restoring the original structure of DNA and most frequently the initial sequence in error-free repair events. DNA repair gathers very diverse biochemical processes. Some repair enzyme simply revert the damage back into the original bases. This is the case of photolyases encountered in bacteria, plants Royal Society of Chemistry -Book Chapter Template and some non-placental mammals. These enzymes use the energy of UVA or visible light to cleave the covalent bonds created by UVB in CPDs or 64PPs and restore unmodified pyrimidines. In contrast to this rather simple reaction, repair of doublestrand breaks requires, in non-homologous end-joining, the cleaning of the extremities of the broken DNA strands followed by their ligation in a process involving many proteins. NHEJ is thus error-prone because genetic information is lost. Alternatively, DSB can be repaired, when cells are in the S phase, by homologous recombination.

This pathway involves the invasion of a homologous sequence by the strand under repair. A correct fragment is thus synthesized and the complex junction resolved to yield two complete and repaired strands exhibiting the correct sequence.

As shown in the following chapters, UV-induced DNA damage mostly involve modification of the bases. In human cells, which do not contain photolyase activities, those are handled by excision-resynthesis pathways. Two main pathways are involved, namely base excision repair (BER) and nucleotide excision repair (NER).

BER is mostly active against small modified bases such as oxidation products 16 . The key enzymes in BER are DNA N-glycosylases (Fig. 1.7). Each of these proteins recognize a specific set of damaged bases (oxidized purines, oxidized pyrimidines, etc.). They cleave the covalent bond between the base and the 2-deoxyribe unit (the N-glycosidic bond) and leave an abasic site (AP sites). DNA is then cleaved at AP sites by AP endonucleases or the initial DNA glycosylase when it is bifunctional. The gap left in the double strand can be either filled by incorporation of one nucleotide based on the complementarity with the undamaged strand. This is the short patch pathway of BER. Alternatively, a small strand of DNA can be synthetized under the damaged portion, which is then cleaved. This is known as the long patch pathway of BER. Interestingly, the mechanism of BER is associated with the induction of strand Royal Society of Chemistry -Book Chapter Template breaks. Therefore, BER is also the main repair mechanism of this class of lesions. It may be added that other scaffold proteins are present during the whole repair event.

Figure 1.7 Basic steps in base excision repair

The other excision/resynthesis repair pathway involved in the removal of UV-induced damage is nucleotide excision repair (NER) 17,18 . NER is mostly active against bulky

Figure 1 . 3 .

 13 Figure 1.3. Schematic picture of the Potential Energy Surfaces of the ground (S0)

Figure 1 . 3 .

 13 Figure 1.3. shows another possible outcome of the photoactivated dynamics, i.e. that

Figure 1 . 4 :

 14 Figure 1.4: CIE action spectrum for induction of erythema shown in a) linear or b)

1. 6 . 1 . 6 . 1 From

 6161 Basic biological phenomena associated with DNA damage DNA damage to abnormal proteins DNA has two main functions in cells, namely the storage of the genetic information required for protein synthesis and the transmission of this information to daughter cells during division. These two functions rely on basic biochemical events: replication and Royal Society of Chemistry -Book Chapter Template transcription 13 . Replication involves a complex series of enzymes that use each strand of DNA as a template for the synthesis of a new double-strand. The synthesis of DNA occurs in the replication fork, a structure where the two original strands are separated and the replication machinery is bound to synthesize the new strands. Because DNA synthesis always proceed from the 5'-end to the 3'-end, one of the original strand (leading strand) is replicated in a continuous way by DNA-polymerases. The other strand (lagging strand) has to be synthesized by fragments. Those are first initiated by small transient pieces of RNA that are then extended into DNA Okasaki fragments. RNA is removed and the DNA fragments are ligated to yield a continuous DNA strand. The replication of these DNA strands rely on the formation of base pairs, and thus on the complementarity between adenine and thymine on the one hand, and guanine and cytosine on the other hand. Consequently, any modification of the chemical structure of the bases, namely a damage, can interfere with this process. A first consequence may be errors in the incorporated base opposite the damage upon replication and a change in the local sequence of the DNA (Fig. 1.6). This constitutes a mutation. A second possible effect is the blockage of the DNA-polymerases at the site of the damage. Stalled replication fork are converted by cells into double strand breaks (DSB) that can either be lethal or lead to chromosomal damage. It should be stressed that all the following generations of cells will bear the same mutations. Indeed, even at a mutated site, DNA is constituted of normal bases in correct base pairing and does not represent an abnormal chemical structure that could be detected by the repair machinery. Royal Society of Chemistry -Book Chapter Template

Figure 1 . 6 :

 16 Figure 1.6: Mutagenic events at a damaged site in DNA during replication by a DNA

  photoproduct in an active gene, a very fast repair process is triggered by binding of

Figure 1 . 8 :

 18 Figure 1.8: Basic steps in nucleotide excision repair. Transcription-coupled repaired

Acknowledgments

Royal Society of Chemistry -Book Chapter Template RI thanks Dr. Lara Martìnez-Fernàndez for helpful discussions and help with the figures

ABBREVIATIONS

Abbreviations must be defined at first mention in the chapter and abbreviated thereafter. A list of abbreviations may be provided at the end of the chapter if necessary.