Jérémie Chalopin
email: jeremie.chalopin@lif.univ-mrs.fr

Shantanu Das
email: shantanu.das@lif.univ-mrs.fr

Arnaud Labourel
email: arnaud.labourel@lif.univ-mrs.fr

Euripides Markou
email: emarkou@ucg.gr

Tight Bounds for Black Hole Search with Scattered Agents in Synchronous Rings *

Keywords: Distributed Algorithms, Fault Tolerance, Black Hole Search, Mobile Agents, Anonymous Networks, Identical tokens, Finite State Automata

We study the problem of locating a particularly dangerous node, the so-called black hole in a synchronous anonymous ring network with mobile agents. A black hole is a harmful stationary process residing in a node of the network and destroying destroys all mobile agents visiting that node without leaving any trace. Unlike most previous research on the black hole search problem which employed a colocated team of agents, we consider the more challenging scenario when the agents are identical and initially scattered within the network. Moreover, we solve the problem with agents that have constant-sized memory and carry a constant number of identical tokens, which can be placed at nodes of the network. In contrast, the only known solutions for the case of scattered agents searching for a black hole, use stronger models where the agents have non-constant memory, can write messages in whiteboards located at nodes or are allowed to mark both the edges and nodes of the network with tokens. This paper solves the problem for ring networks containing a single black hole. We are interested in the minimum resources (number of agents and tokens) necessary for locating all links incident to the black hole. We present deterministic algorithms for ring topologies and provide matching lower and upper bounds for the number of agents and the number of tokens required for deterministic solutions to the black hole search problem, in oriented or unoriented rings, using movable or unmovable tokens.

Introduction 1.Overview

We consider the problem of exploration in unsafe networks which contain malicious hosts of a highly harmful nature, called black holes. A black hole is a node which contains a stationary process destroying all mobile agents visiting this node, without leaving any trace [START_REF] Dobrev | Mobile search for a black hole in an anonymous ring[END_REF]. In the Black Hole Search (BHS) problem the goal for a team of agents is to locate the black hole within finite time, with the additional constraint that at least one of the agents must remain alive. In 1 particular, at least one agent must survive and the surviving agents must have located (or marked) all edges leading to the black hole. It is usually assumed that all the agents start from the same location and have distinct identities. In this paper, we do not make such an assumption and study the problem for identical agents starting from distinct locations within the network. We focus on minimizing the resources required to find the black hole.

The only way of locating a black hole is to have at least one agent visiting it. However, since any agent visiting a black hole is destroyed without leaving any trace, the location of the black hole must be deduced by some communication mechanism employed by the agents. Four such mechanisms have been proposed in the literature: a) the whiteboard model in which there is a whiteboard at each node of the network where the agents can leave messages, b) the 'pure' token model where the agents carry tokens which they can leave at nodes, c) the 'enhanced' token model in which the agents can leave tokens at nodes or edges, and d) the time-out mechanism (only for synchronous networks) in which one agent explores a new node while another waits for it at a safe node.

The most powerful inter-agent communication mechanism is having whiteboards at all nodes. Since access to a whiteboard is provided in mutual exclusion, this model could also provide the agents a symmetry-breaking mechanism: If the agents start at the same node, they can get distinct identities and then the distinct agents can assign different labels to all nodes. Hence in this model, if the agents are initially co-located, both the agents and the nodes can be assumed to be non-anonymous without any loss of generality. The BHS problem has been studied using whiteboards in asynchronous networks, with the objective of minimizing the number of agents required to locate the black hole. Note that in asynchronous networks, it is not possible to answer the question of whether or not a black hole exists in the network, since there is no bound on the time taken by an agent to traverse an edge. Assuming the existence of (exactly one) black hole, the minimum sized team of co-located agents that can locate the black hole depends on the maximum degree ∆ of a node in the network (unless the agents have a complete map of the network). In any case, the prior knowledge of the network size is essential to locate the black hole in finite time.

In the case of synchronous networks two co-located distinct agents can discover one black hole in any graph by using the time-out mechanism, without the need of whiteboards or tokens. Furthermore it is possible to detect whether a black hole actually exists or not in the network. Hence, with co-located distinct agents, the issue is not the feasibility but the time efficiency of black hole search (see [START_REF] Cooper | Searching for black-hole faults in a network using multiple agents[END_REF][START_REF] Cooper | Locating and repairing faults in a network with mobile agents[END_REF][START_REF] Czyzowicz | Complexity of searching for a black hole[END_REF][START_REF] Czyzowicz | Searching for a black hole in synchronous tree networks[END_REF][START_REF] Klasing | Hardness and approximation results for black hole search in arbitrary graphs[END_REF][START_REF] Klasing | Approximation bounds for black hole search problems[END_REF][START_REF] Kosowski | Synchronization helps robots to detect black holes in directed graphs[END_REF] for example). However when the agents are scattered in the network (as in our case), the time-out mechanism is not sufficient to solve the problem anymore.

Most of the previous results on black hole search used agents whose memory is at least logarithmic in the size of the network. This means that these algorithms are not scalable to networks of arbitrary size. This paper considers agents modeled as finite automata, i.e., having a constant number of states. This means that these agents can not remember or count the nodes of the network that they have explored. In this model, the agents cannot have prior knowledge of the size of the network. For synchronous ring networks of arbitrary size, containing exactly one black hole, we present deterministic algorithms for locating the black hole using scattered agents each having constant-sized memory. We are interested in minimizing both the number of agents and the number of tokens required for solving the BHS problem.

We use the 'pure' token model. While the whiteboard model is commonly used in unsafe networks, the token model has been mostly used for exploration of safe networks. Note that the 'pure' token model can be implemented with O(1)-bit whiteboards (assuming that only a constant number of tokens may be placed on a node at the same time), while the 'enhanced' token model can be implemented with O(log ∆)-bit whiteboards. In the previous results using the whiteboard model, the capacity of each whiteboard is always assumed to be of at least Ω(log n) bits, where n is the number of nodes of the network. Unlike the whiteboard model, we do not require any mutual exclusion mechanism at the nodes of the network. We distinguish movable tokens (which can be picked up from a node and placed on another) from unmovable tokens (which can not be picked up once they are placed on a node). For both types of tokens, we provide matching upper and lower bounds on both the number of agents and the number of tokens per agent, required for solving the black hole search problem in synchronous rings. Although our algorithms require only a constant size memory for each agent, the impossibility results presented in this paper hold even for agents having unbounded memory.

Related Works

The exploration of an unknown graph by one or more mobile agents is a classical problem initially formulated in 1951 by Shannon [START_REF] Shannon | Presentation of a maze-solving machine[END_REF] and it has been extensively studied since then (e.g., see [START_REF] Bender | The power of team exploration: Two robots can learn unlabeled directed graphs[END_REF][START_REF] Deng | Exploring an unknown graph[END_REF][START_REF] Fraigniaud | Collective tree exploration[END_REF]). In unsafe networks containing a single dangerous node (black hole), the problem of searching for it has been studied in the asynchronous model using whiteboards and given that all agents initially start at the same safe node (e.g., [START_REF] Dobrev | Optimal search for a black hole in common interconnection networks[END_REF][START_REF] Dobrev | Searching for a black hole in arbitrary networks: Optimal mobile agents protocols[END_REF][START_REF] Dobrev | Mobile search for a black hole in an anonymous ring[END_REF][START_REF] Dobrev | Improved bounds for optimal black hole search in a network with a map[END_REF]). It has also been studied using 'enhanced' tokens in [START_REF] Dobrev | Exploring a dangerous unknown graph using tokens[END_REF][START_REF] Dobrev | Black hole search in asynchronous rings using tokens[END_REF][START_REF] Shi | Black hole search with tokens in interconnected networks[END_REF] and in the 'pure' token model in [START_REF] Flocchini | Ping pong in dangerous graphs: Optimal black hole search with pure tokens[END_REF]. It has been proved that the problem can be solved with a minimal number of agents performing a polynomial number of moves. Notice that in an asynchronous network the number of the nodes of the network must be known to the agents otherwise the problem is unsolvable [START_REF] Dobrev | Mobile search for a black hole in an anonymous ring[END_REF]. If the network topology is unknown, at least ∆ + 1 agents are needed, where ∆ is the maximum node degree in the graph [START_REF] Dobrev | Searching for a black hole in arbitrary networks: Optimal mobile agents protocols[END_REF]. It is usually assumed that the network is bi-connected and the existence of one black hole is common knowledge.

In asynchronous networks, with scattered agents (not initially located at the same node), the problem has been investigated for arbitrary topologies [START_REF] Chalopin | Rendezvous of mobile agents in unknown graphs with faulty links[END_REF][START_REF] Flocchini | Map construction and exploration by mobile agents scattered in a dangerous network[END_REF] in the whiteboard model while in the 'enhanced' token model it has been studied for rings [START_REF] Dobrev | Scattered black hole search in an oriented ring using tokens[END_REF][START_REF] Dobrev | Using scattered mobile agents to locate a black hole in an un-oriened ring with tokens[END_REF] and for some interconnected networks [START_REF] Shi | Black hole search with tokens in interconnected networks[END_REF].

The issue of efficient black hole search has been studied in synchronous networks without whiteboards or tokens (only using the time-out mechanism) in [START_REF] Cooper | Searching for black-hole faults in a network using multiple agents[END_REF][START_REF] Cooper | Locating and repairing faults in a network with mobile agents[END_REF][START_REF] Czyzowicz | Complexity of searching for a black hole[END_REF][START_REF] Czyzowicz | Searching for a black hole in synchronous tree networks[END_REF][START_REF] Klasing | Hardness and approximation results for black hole search in arbitrary graphs[END_REF][START_REF] Klasing | Approximation bounds for black hole search problems[END_REF][START_REF] Kosowski | Synchronization helps robots to detect black holes in directed graphs[END_REF] under the condition that all distinct agents start at the same node.

The problem has also been studied for co-located agents in asynchronous and synchronous directed graphs with whiteboards in [START_REF] Czyzowicz | Black hole search in directed graphs[END_REF][START_REF] Kosowski | Synchronization helps robots to detect black holes in directed graphs[END_REF]. In [START_REF] Cooper | Locating and repairing faults in a network with mobile agents[END_REF] they study how to locate and repair faults (weaker than black holes) using co-located agents in synchronous known networks with whiteboards and in [START_REF] Glaus | Locating a black hole without the knowledge of incoming link[END_REF] they study the problem in asynchronous networks with whiteboards and co-located agents without the knowledge of incoming link. A different dangerous behavior is studied for co-located agents in [START_REF] Kràlovic | Periodic data retrieval problem in rings containing a malicious host[END_REF], where the authors consider a ring and assume black holes with Byzantine behavior, which do not always destroy a visiting agent.

In all previous papers (apart from [START_REF] Flocchini | Ping pong in dangerous graphs: Optimal black hole search with pure tokens[END_REF]) studying the Black Hole Search problem using tokens, the 'enhanced' token model is used. The weakest 'pure' token model has only been used in [START_REF] Flocchini | Ping pong in dangerous graphs: Optimal black hole search with pure tokens[END_REF] for co-located agents in asynchronous networks. In all previous solutions to the problem using tokens, the agents are assumed to have non-constant memory.

Our Contributions

Unlike previous studies on BHS, we consider the scenario of anonymous (i.e., identical) agents that are initially scattered in an anonymous ring. We focus our attention on very simple mobile agents. The agents have constant-size memory, they carry a constant number of identical tokens which can be placed at nodes and, (apart from using the tokens), they can communicate with other agents only when they meet at the same node. We consider four different scenarios depending on whether the tokens are movable or not, and whether the agents agree on a common orientation. We present deterministic optimal algorithms and provide matching upper and lower bounds for the number of agents and the number of tokens required for solving BHS (See Table 1 for a summary of results). Surprisingly, the agreement on the ring orientation does not influence the number of agents needed in the case of movable tokens but is important in the case of unmovable tokens.

The lower bounds presented in this paper are very strong in the sense that they do not allow any trade-off between the number of agents and the number of tokens for solving the BHS problem. In particular we show that:

• Any constant number of agents, even having unlimited memory, cannot solve the BHS problem with less tokens than depicted in all cases of Table 1.

• Any number of agents less than that depicted in all cases of

Our Model

Our model consists of an anonymous, synchronous ring network with k ≥ 2 identical mobile agents that are initially located at distinct nodes called homebases. Each mobile agent owns a constant number t of identical tokens which can be placed at any node visited by the agent. The tokens are indistinguishable. Any token or agent at a given node is visible to all agents on the same node, but not visible to agents on other nodes. The agents follow the same deterministic algorithm and begin execution at the same time and being in the same initial state. In all our protocols a node may contain at most two tokens at the same time. At any node of the ring, the ports leading to the two incident edges are distinguishable and locally labelled (e.g. as 1 and 2) and an agent arriving at a node knows the port-label of the edge through which it arrived. In the special case of an oriented ring, the ports are consistently labelled as Left and Right (i.e., all ports going in the clockwise direction are labelled Left). In an unoriented ring, the local port-labeling at a node is arbitrary and each agent in its first step chooses one direction as Left and in every subsequent step, it translates the local port-labeling at a node into Left and Right according to its chosen orientation.

In a single time unit, each mobile agent completes one step which consists of the Look, Compute and Move stages (in this order). During the Look stage, an agent obtains information about the configuration of the current node (i.e., agents, tokens present at the node) and its own configuration (i.e., the port through which it arrived and the number of tokens it carries). During the Compute stage, an agent can perform any number of computations (i.e., computations are instantaneous in our model). During the Move stage, the agent may put or pick up a token at the current node and then either move to an adjacent node or remain at the current node. Since the agents are synchronous they perform each stage of each step at the same time. We call a token movable if it can be put on a node and picked up later by any mobile agent visiting the node. Otherwise we call the token unmovable in the sense that, once released, it can occupy only the node where it was released.

Formally we consider a mobile agent as a finite Moore automaton A = (S, S 0 , Σ, Λ, δ, φ), where S is a set of σ ≥ 2 states among which there is a specified state S 0 called the initial state; Σ ⊆ D × C v × C A is the set of possible configurations an agent can see when it enters a node; Λ ⊆ D × {put, pick, no action} is the set of possible actions by the agent; δ : S × Σ → S is the transition function; and φ : S → Λ is the output function. D = {left, right, none} is the set of possible directions through which the agent arrives at or leaves a node (none represents no move by the agent). C v = {0, 1} σ × {0, 1, 2} is the set of possible configurations at a node, consisting of a bit string that denotes for each possible state whether there is an agent in that state, and an integer that denotes the number of tokens at that node (in our protocols at most 2 tokens reside at a node at any time). Finally, C A = {1, 2} × {0, 1} is the set of possible configurations of an agent, i.e., its orientation and whether it carries any tokens or not.

Notice that all computations by the agents are independent of the size n of the network and the number k of agents. The agents have no knowledge of n or k. The agents only know the number of tokens they have. Since the agents are identical they face the same limitations on their knowledge of the network. There is exactly one black hole in the network. An agent can start from any node other than the black hole and no two agents are initially colocated * . Once an agent detects a link to the black hole, it marks the link permanently as dangerous (i.e., disables this link). We require that at the end of a black hole search scheme, all links incident to the black hole (and only those links) are marked dangerous and that there is at least one surviving agent. Note that our definition of a successful BHS scheme is slightly different from the original definition, since we consider finite state agents. The time complexity of a BHS scheme is the number of time units needed for completion of the scheme, assuming the worst-case location of the black hole and the worst-case initial placement of the scattered agents.

3 Impossibility Results

Oriented Rings

We first show that when the tokens are unmovable, any constant number of agents need at least two tokens to solve the BHS problem. Theorem 3.1 For any constant k, there exists no algorithm that solves BHS in all oriented rings containing one black hole and k or more scattered agents, when each agent is provided with only one unmovable token. The result holds even if the agents have unlimited memory.

Proof : Suppose there is a correct BHS algorithm that solves the problem with k or more agents in rings of any size. If the algorithm does not require any agent to put down its token, such an algorithm should work even if every agent puts its token on its homebase in the first step. So without loss of generality, we assume that an agent puts down its token after executing a finite number of steps of the algorithm (unless it encounters some agents, some tokens or the black hole within this time). Now consider the behavior of this agent when placed on an infinite line (with no other agent). Suppose the agent puts down its token at a distance of x (w.l.o.g. in the left direction) from its homebase. Further let p be the maximum distance that the agent has travelled from its homebase (in either direction) before it puts down its token (thus, x ≤ p). Now, consider a ring R 1 of size n = 2k(p + 1) with one black hole and k agents such that the agents are initially placed at a distance of 2(p + 1) apart (see Figure 1(a)). The black hole is located in the middle of a segment between two consecutive agents (i.e., it is at a distance (p + 1) from the closest agents). Since the agents start in the same state, they take the same actions and remain in identical states (until they encounter another agent, or a token or the black hole). As long as the agents do not travel any further than a distance p from their homebase, they will not see anything different from the agent on the infinite line. Thus, each agent will put its token x ≤ p places to the left of its homebase. Each agent will do so at the same time and in the same state. During the rest of the algorithm, an agent can only move, observe the tokens and possibly mark some link as dangerous. Due to the correctness of the algorithm, at some time τ , some agent will mark one link leading to the black hole as dangerous. Up to time τ , all surviving agents behave the same. If there are more than one surviving agent, all of them are in the same state β and still at a distance of 2(p + 1) apart. Thus, if one such agent marks a link as dangerous, the next agent would mark a link at a distance of 2(p + 1) away. So, one of the agents would have incorrectly marked a link-a contradiction to the correctness of the algorithm.

The remaining case to consider is when the agent that marks a link, is the last surviving agent. In this case, we can construct another ring R 2 of size n = 2(k + 1)(p + 1) with one black hole and (k + 1) agents initially placed the same distance apart as in the ring R 1 (see Figure 1(b)). In an execution of the same algorithm on ring R 2 , after exactly τ time steps, there will be two surviving agents both in the same state β and at a distance of 2(p + 1) from each other. Thus the two agents will mark as dangerous, two distinct links at a distance of 2(p + 1) apart. Hence the algorithm fails for the ring R 2 .

We now derive some lower bounds on the number of agents necessary to solve the BHS problem. The following result proves that at least one agent needs to be sacrificed for detecting each link leading to the black hole. Lemma 3.1 During any execution of any BHS algorithm, if a link to the black hole is correctly marked, then at least one agent must have entered the black hole through this link.

Proof : Suppose for the sake of contradiction that there exists a correct BHS algorithm such that during any execution of this algorithm one link incident to the black hole is marked before any agent traverses this link. Assume without loss of generality that the link is on the left of the black hole. Consider the ring of size n which leads to this execution. Now, add a vertex on the left of the black hole, obtaining a ring of size n + 1, while keeping the same initial positions for the agents. The agents will behave as in the ring of size n since they do not know the size of the ring and will see exactly the same configuration. Hence they will mark the left link of the new node as the link leading to the black hole. This contradicts with the correctness of the BHS algorithm. To solve the BHS problem in a ring, both links leading to the black hole need to be marked as dangerous. Thus, we immediately arrive at the following result.

Theorem 3.2 Two mobile agents carrying any number of movable (or unmovable) tokens each, cannot solve the BHS problem in an oriented ring, even if the agents have unlimited memory.

When the tokens are unmovable, even three agents are not sufficient to solve BHS as shown below.

Theorem 3.3 Three mobile agents carrying a constant number of unmovable tokens each, cannot solve the BHS problem in an oriented ring, even if agents have unlimited memory.

Proof : Suppose for the sake of contradiction that there exists an algorithm which solves the BHS problem for three agents each carrying a constant number t of unmovable tokens. Let x and y be two integers chosen by the adversary, such that 1 ≤ x, y ≤ 2t. Suppose the three agents are initially placed on a ring of size 8t + x + y such that the distance between the first and second and between the second and third agent is 4t. The black hole is between the third and the first agent at a distance x from one of them and at distance y from the other (as in Figure 2). By Lemma 3.1, at least one agent would fall into the black hole before any link to the black hole is identified. Consider the phase P of the algorithm from the start until the first time an agent falls into the black hole. Let us call this agent a. Assume without loss of generality that agent a enters the black hole by going right (i.e., after traveling a distance of x from its homebase). First, notice that the agents never meet each-other during phase P since they are always at a distance less than 2t from their homebases.

Suppose for the sake of contradiction that after agent a has vanished, the two surviving agents can identify the link used by agent a to enter the black hole without sacrificing another agent. This is only possible if, whenever agent a explores a new node to the right, it leaves a message encoding this fact and the only way to do this is by leaving another token. However, after t explored nodes agent a runs out of tokens. The adversary may then set x to be any value between t + 1 and 2t. The remaining agents would not have enough information to determine the position of the black hole from the left (without the sacrifice of another agent). However, by Lemma 3.1, at least one agent must enter the black hole from the other link (on the right). Thus either one of the links to the black hole is never marked or there are no surviving agents.

Unoriented Rings

In an unoriented ring, even four agents do not suffice to solve the BHS problem with unmovable tokens. In fact we show a stronger result that it is not even possible to identify just one of the links to the black hole, using four agents. Theorem 3.4 In an unoriented ring, four agents carrying any constant number of unmovable tokens each, cannot correctly mark any link incident to the black hole, even when the agents have unlimited memory.

Proof : Suppose for the sake of contradiction that there exists an algorithm which marks one of the links incident to the black hole, using four agents each carrying t unmovable tokens. For some integer x, 1 ≤ x ≤ 2t, chosen by the adversary, suppose that the four agents and the black hole are initially placed as in Figure 3. The distance between two consecutive agents is 4t + 1 and the distance between the black hole and the closest agent on each side is x. Thus, the initial configuration is symmetric and the axis of symmetry crosses an edge and the black hole. The adversary can choose the orientations of the agents in such a way that the two agents closest to the black hole would fall into the black hole at the same time and before any agent meets another agent. Thus, the two surviving agents would continue to be in symmetric situation and they would take similar actions. Using the same argument as in proof of Theorem 3.3, the information left by the vanished agent is not sufficient for one agent to correctly identify any link incident to the black hole. Due to the symmetry of the resulting configuration (and the fact that agents cannot meet on an edge), the two remaining agents can never meet and will always be in the same state until they both fall into the black hole (without marking any of the links incident to the black hole).

BHS Scheme with Movable Tokens

We first consider the case when the agents have movable tokens. If each agent has a movable token it can perform a cautious walk [START_REF] Dobrev | Mobile search for a black hole in an anonymous ring[END_REF]. The Cautious-Walk procedure consists of the following actions: Put the token at the current node, move one step in the specified direction, return to pick up the token, and again move one step in the specified direction (carrying the token). After each invocation of the Cautious Walk, the agent looks at the configuration of the current node † and decides whether to continue performing Cautious Walk.

We show that only three agents are sufficient to solve BHS, when they have one movable token each. Algorithm 1 achieves this, both for oriented and unoriented rings. The procedure Mark-Link permanently marks as dangerous the specified link. Proof : Notice that all agents start at the same time executing Procedure CautiousWalk(dir) and at each time they are at the same phase of this procedure. Since the only time an agent checks the number of tokens it sees is after completing an execution of the procedure, if the agent sees at least one token (not including the one it carries) then, either (i) there is another agent (i.e., they were traveling in opposite directions) or (ii) there is no other agent (which means that the token was left by an agent that disappeared). In case (i) the agent continues executing Procedure CautiousWalk(dir). In case (ii) it is clear that the black hole resides at the next node in direction dir. In this case, the agent marks the edge to the black hole, reverses direction and repeats the process. Since the agents start from distinct locations at the same time, exactly two agents would fall into the black hole and both links to the black hole would be eventually marked.

BHS Scheme with Unmovable Tokens

For agents having only unmovable tokens, we use the technique of Paired Walk (called Probing in [START_REF] Cooper | Searching for black-hole faults in a network using multiple agents[END_REF]) for exploring new nodes. The procedure is executed by two co-located agents with different roles and the same orientation. One of the agents called the leader explores an unknown edge while the other agent, called follower waits for the leader. If the other endpoint of the edge is safe, the leader immediately returns to the previous node to inform the follower and then both move to this new node. On the other hand, if the leader does not return in two time steps, the follower knows that the next node is the black hole. (See Procedure Paired Walk ).

In order to use the Paired Walk technique, we need to gather two agents at the same node and then break the symmetry between them, so that distinct roles can be assigned to each of them. The basic idea of our algorithms is the following. We first identify the two homebases that are closest to the black hole (one on each side). These homebases are called gates. The gates divide the ring into two segments: one segment contains the black hole (thus, is dangerous); the other segment contains all other homebases (and is safe). Initially all agents are in the safe part and an agent can move to the dangerous part only when it passes through the gate node. We ensure that any agent reaching a gate node, waits for a partner agent in order to perform the Paired Walk procedure. We now present two BHS algorithms, one for oriented rings and the other for unoriented rings.

Procedure PairedWalk( isLeader)

if isLeader then Move one step in specified direction; Move one step back; Move one step in specified direction; else WAIT(2); if there is a leader then Move one step in specified direction;

Oriented Rings

In an oriented ring, all agents may move in the same direction (i.e., Left). During the first phase of the algorithm each agent places a token on its homebase, moves left until the next homebase (i.e., next node with a token) and then returns to its homebase to put down the second token. During this phase one agent will fall into the black hole and there will be a unique homebase with a single token (a "gate" node) and the other homebases will have two tokens each. However, the agents may not complete this phase of the algorithm at the same time. Thus during the algorithm, there may be multiple homebases that contain a single token. Whenever an agent reaches a "single token" node, it waits for a partner and then performs Paired Walk in the left direction. One of the agents of a pair (the leader) eventually falls into the black hole and the other agent (the follower) marks the edge leading to the black hole and returns to the gate node, waiting for another partner. When another agent arrives at this node, these two agents perform Paired Walk in the opposite direction to find the other incident link to the black hole. The algorithm sketched below ensures that exactly one leader agent falls into the black hole from each side while performing Paired Walk. (For the full algorithm, please see Algorithm 2)

Algorithm BHS-Ring-2:

During the algorithm, an agent a performs the following actions.

1. Agent a puts a token and moves left until the next node with a token (state CHECK-LEFT) and then returns to its homebase v (state GO-BACK) and puts its second token.

2. If there are no other agents at v, the agent moves left until it reaches a node containing exactly one token (state ALONE) and then waits for other agents arriving at this node (state WAITING).

3. Otherwise, if there is a WAITING (or ALONE) agent b at node v, the agents a and b form a (LEADER, FOLLOWER) pair.

4. If an ALONE agent meets a WAITING agent (and there are no other agents), they form a (LEADER, FOLLOWER) pair.

A LEADER agent performs

Paired Walk until it falls into the black hole or it sees a link marked dangerous. In the latter case it moves to the gate node (state SEARCHER) and participates in Paired Walk in the other direction (state RIGHT-FOLLOWER).

6. A FOLLOWER agent performs Paired Walk until the corresponding leader falls into the black hole or they see a link marked dangerous. In the former case, the agent (state RIGHT-LEADER) moves to the gate node and waits for a partner to start Paired Walk in the other direction.

7. When a WAITING agent a meets a RIGHT-LEADER, agent a becomes a RIGHT-FOLLOWER and participates in the Paired Walk.

8. The algorithm has some additional rules to ensure that no two LEADERs are created at the same node at the same time. No agent becomes a LEADER if there is already another LEADER at the same node (In this case, the agent become a SEARCHER and eventually a RIGHT-FOLLOWER when it reaches the gate node).

When the algorithm BHS-Ring-2 is executed by four or more agents starting from distinct locations, the following properties hold:

• Exactly one CHECK-LEFT agent falls into the black hole.

• There is at least one LEADER agent and each LEADER has exactly one FOLLOWER.

• No two LEADER agents are created at the same time on the same node and thus, two LEADERs can not reach the black hole at the same time.

• There is exactly one RIGHT-LEADER agent and it falls into the black hole through the edge on the left side of the black hole.

• An agent in any state other than CHECK-LEFT, LEADER, or RIGHT-LEADER, never enters the black hole.

Theorem 5.1 Algorithm BHS-Ring-2 correctly solves the black hole search problem in any oriented ring with 4 or more agents having constant memory and carrying two unmovable tokens each.

Proof : (Sketch) : Due to the above properties we know that at most three agents fall into the black hole. Thus there is at least one surviving agent at the end of the algorithm. Since there is at least one (LEADER, F OLLOW ER) pair moving in the left direction, one of the links to the black hole is discovered and marked by this pair of agents. The FOLLOWER agent of this pair becomes the RIGHT-LEADER. At this point, only two agents have been destroyed (one LEADER and one CHECK-LEFT agent). Thus there exists at least one other agent and this agent will eventually reach the gate node, i.e., the only node having a single token (Note that an agent may wait only at node containing a single token). Thus, this agent will become the RIGHT-FOLLOWER and perform a Paired Walk with the RIGHT-LEADER to discover the other link to the black hole.

Unoriented Rings

For unoriented rings, we need at least 5 agents with two unmovable tokens each. The algorithm for unoriented rings with unmovable tokens is similar to the one for oriented rings, except that each agent chooses an orientation. When two agents meet and one has to follow the other, we assume that the state of the agent contains information about the orientation of the agent (i.e., the port at the current node considered by the agent to be Left). Thus, when two agents meet at a node, one agent (e.g. the Follower) can orient itself according to the direction of the other agent (e.g. the Leader).

Algorithm BHS-Ring-3: Each agent puts one token on its homebase, goes on its left until it sees another token and then returns to its homebase. Now the agent goes on its right until it sees a token and then returns again to the homebase. The agent now puts its second token on its homebase. During this operation exactly two agents will fall into the black hole. Each surviving agent walks to its left until it sees a node u with a single token. At this point the agent has to wait, since either there is a black hole ahead, or u is the homebase of an agent b that has not returned yet to put its second token.

It may happen that two agents arrive at node u at the same time from opposite directions. In this case, both agents can wait until another agent arrives. Note that in this case, the ring is safe on both directions until the next homebase and thus, an agent b (whose homebase is u) would arrive within a finite time. When agent b arrives, only one of the waiting agents (the one having the same orientation as b) changes to state LEADER and pairs-up with agent b. A similar case occurs when an agent a is waiting and two agents (both ALONE) arrive from different directions. Among these two agents, the one having the same orientation as agent a pairs up with agent a and starts the Paired Walk procedure.

As before there can be multiple leader-follower pairs performing Paired Walk in different parts of the ring. Note that no two LEADERs can be created at the same node at the same time. Thus, two LEADERs may not enter into the black hole at the same time from the same direction. After the first LEADER enters the black hole from one direction, the corresponding FOLLOWER agent marks the link as a dangerous link and thus, no other agents enter the black hole from the same direction.

We ensure that each LEADER agent has exactly one FOLLOWER agent. When the LEADER agent falls into the black hole, the corresponding FOLLOWER agent becomes the RIGHT-LEADER. The objective of the RIGHT-LEADER is to discover the other link incident to the black hole. The RIGHT-LEADER agent moves to the other end of the ring until the node with one token. Since we assume there are at least five agents, there must be either an unpaired agent at one of the gates or, there must be another (LEADER, FOLLOWER) pair that has already detected and marked the other link leading to the black hole. If the RIGHT-LEADER does not find a RIGHT-FOLLOWER at the first gate, it performs a slow walk to the other gate and returns again to the former gate. During the slow walk, it moves at one-third the speed of any other agent (i.e., waits two steps after each move). This ensures that it will meet another agent in at least one of the two gates. These two agents now starts the Paired Walk procedure in the other direction.

A complete description of the algorithm can be found in Algorithm 3. The following properties can be verified:

1. Exactly two agents fall into the black hole before placing their second token.

2. There is at least one LEADER and each LEADER has a corresponding FOLLOWER.

3. There is either one or two RIGHT-LEADER agents (with opposite orientations).

4. At most one LEADER or RIGHT-LEADER enters the black hole from each direction.

5. An agent in any other state never enters the black hole after placing its second token. Due to the above properties, we know that at most 4 agents may fall into the black hole. We now show that both links to the black hole are actually discovered and marked as dangerous, during the algorithm. Theorem 5.2 Algorithm BHS-Ring-3 correctly solves the black hole search problem in unoriented ring with 5 or more agents having constant memory and carrying two unmovable tokens each.

Proof : (Sketch) Let v be the black hole and u and w be the gates. Assume nodes u, v and w appear in this order (say, in clockwise direction) with only non-homebase nodes between u and v and between v and w. Let us denote by d(u, v), d(v, w) and d(w, u) the distances between these nodes in the clockwise direction. Due to Property 2 above we know that there is at least one LEADER. Suppose there are two LEADERs moving in opposite directions. In this case, the two LEADER agents will fall into the black hole through distinct links, while executing the Paired Walk procedure. Thus, both links to the black hole will be marked by the corresponding FOLLOWER agents and BHS is solved.

The second scenario to consider is when there are multiple LEADER agents but they all have the same orientation. In this case, no two LEADERs are created at the same node at the same time. Only the first LEADER to reach the black hole falls into it and thus there will be exactly one RIGHT-LEADER agent (the FOLLOWER of the agent that falls into a black hole becomes RIGHT-LEADER). All the other LEADERs become RIGHT-FOLLOWER and they go to one of the gate nodes (say u) and wait for the RIGHT-LEADER. We need to show that the RIGHT-LEADER would meet at least one RIGHT-FOLLOWER. There is a time difference of at most d(w, u) between the RIGHT-LEADER and any RIGHT-FOLLOWER. The RIGHT-LEADER traverses a path of length 2(d(u, v) -1) + 2d(w, u) before reaching the node u for the second time. During this time any RIGHT-FOLLOWER agent would have certainly reached node u and would be waiting for the RIGHT-LEADER. Thus, the RIGHT-LEADER meets at least one RIGHT-FOLLOWER and they perform the Paired Walk in the other direction to discover the other link to the black hole.

The third and only other possible scenario is when there is only one LEADER agent (and thus only one FOLLOWER). We know that one of the links to the black hole would be discovered by this (LEADER, FOLLOWER) pair. The FOLLOWER agent would eventually become RIGHT-LEADER. We need to show that the RIGHT-LEADER would meet at least one RIGHT-FOLLOWER. Suppose (w.l.o.g.) that the RIGHT-LEADER was created on the same side of the black hole as node u. Since there are at least 5 agents, there must be an unpaired agent waiting for a partner. The WAITING agent could be waiting either at node u or at node w. Note that the RIGHT-LEADER moves from u to w, waiting two steps after each edge traversal. This takes time 3d(u, w). Since no other agent makes more than 3d(u, w) edge traversals before it starts waiting at the gate, the RIGHT-LEADER is guaranteed to find at least one waiting agent either at node w or at u when it returns. Thus this agent becomes RIGHT-FOLLOWER and joins the Paired Walk procedure. Hence, the second link to the black hole would be discovered by this pair of agents.

Conclusions

The results of this paper determine the minimum resources necessary for locating a black hole in synchronous ring networks. We presented algorithms that use the optimal number of agents and the optimal number of tokens per agent, while requiring only constant-size memory. Thus, all resources used by our algorithms are independent of the size of the network. Notice that all the algorithms presented in the paper have a time complexity of O(n) steps, so, they are asymptotically optimal for BHS in a ring. The main question answered by the paper is how the limitation on the memory of the agents influences the resources required for solving BHS. We show that the constant memory limitation has no influence on the resource requirements since the (matching) lower bounds hold even if the agents have unlimited memory. It would be interesting to investigate if similar tight results hold for BHS in other network topologies. We would also like to investigate the difference between 'pure' and 'enhanced' token model in terms of the minimum resources necessary for black hole search in higher degree networks.

Figure 1 :

 1 Figure 1: (a) An oriented ring R 1 with k agents and a black hole, (b) a larger oriented ring R 2 with k + 1 agents and one black hole.

Figure 2 :

 2 Figure 2: Three agents with t unmovable tokens each in an oriented ring.

Figure 3 :

 3 Figure 3: Four agents with t unmovable tokens each in an unoriented ring.

Algorithm 1 :

 1 BHS-Ring-1 /* BHS in any ring using k ≥ 3 agents having 1 movable token each */ repeat CautiousWalk (Left); until current node has a token and no agent or next link is marked Dangerous; Mark-Link(Left); repeat CautiousWalk (Right); until current node has a token and no agent or next link is marked Dangerous; Mark-Link(Right); Theorem 4.1 Algorithm 1 solves the BHS problem in an unoriented ring with k ≥ 3 agents having constant memory and one movable token each.

Table 1

 1

	cannot solve the BHS

Table 1 :

 1 Summary of results for BHS in synchronous rings

* Since there is no symmetry breaking mechanism at a node, two agents starting at the same node and in the same state, would behave as a single (merged) agent.

† Recall that only the tokens put on the node are counted, not the tokens carried by the agent itself.


R Keinj

T Bastogne
email: thierry.bastogne@cran.uhp-nancy.fr

P Vallois

Multinomial model-based formulations of TCP and NTCP for radiotherapy treatment planning

Keywords: Markov chain, multinomial model, tumor growth, radiotherapy

Hit and target models of tumour growth, typically assume that all surviving cells have a constant and homogeneous sensitivity during the radiotherapy period. In this study, we propose a new multinomial model based on a discrete-time Markov chain, able to take into account cell repair, cell damage heterogeneity and cell proliferation. The proposed model relies on the 'Hit paradigm' and 'Target' theory in radiobiology and assumes that a cancer cell contains m targets which must be all deactivated to produce cell death. The surviving cell population is then split up into m categories to introduce the variation of cancer cell radio-sensitivity according to their damage states. New expressions of the tumour control probability (TCP) and normal tissue complication probability (NTCP) are provided. Moreover, we show that hit and target models may be regarded as particular cases of the multinomial model. Numerical results should permit to keep the efficiency of treatment with a lower total radiation dose then that given by the typical hit models, which allows to decrease side effects.

Introduction

The aim of radiotherapy is to deliver enough radiation to the tumour to control it without irradiating normal tissue to a dose that will lead to serious complications (morbidity). Since radiation delivery at a precise point of cells is generally described as a random variable, the effects of the radioactive treatments on cancer and healthy cells are characterized by two probabilities: (i) the Tumour Control Probability (TCP) and (ii) the Normal Tissue Complication Probability (NTCP) [START_REF] Zaider | Tumour control probability: a formulation applicable to any temporal protocol of dose delivery[END_REF][START_REF] Dawson | Derivation of the tumour control probability (TCP) from a cell cycle model[END_REF][START_REF] Gay | A free program for calculating EUD-based NTCP and TCP in external beam radiotherapy[END_REF] . The optimum choice of radiation dose delivery technique in the treatment of a given tumour has to maximize the TCP so that at the same time the NTCP must be lower than an acceptable level.

The model-based probabilities TCP and NTCP are then used to choose the 'best' treatment plan. Since Holthusen in [START_REF] Holthusen | Erfahrungen über die Verträglichkeitsgrenze für Röntgenstrahlen und deren Nutzanwendung zur Verhütung von Schäden[END_REF] , TCP and NTCP dose functions have been used to determine the 'optimal' dose to be delivered by maximizing biological objective functions like T CP (1 -N T CP ). An evolution of this objective function is proposed in [START_REF] Kim | On the impact of functional imaging accuracy on selective boosting IMRT[END_REF] . In clinical radiotherapy a typical choice is T CP ≥ 0.5 and N T CP ≤ 0.05 [START_REF] Suntharaligam | Basic Radiobiology[END_REF] . Expressions for TCP and NTCP can be derived using survival curves [START_REF] Fowler | The Linear-quadratic Formula and Progress in Fractionated Radiotherapy[END_REF] , stochastic cell population-dynamic models [START_REF] Sachs | Simple ODE Models of Tumor Growth and Anti-Angiogenic or Radiation Treatment[END_REF][START_REF] Hillen | From cell population models to tumor control probability: including cell cycle effects[END_REF] or cell-cycle models 12 . Here, we focus on a popular class of models used in radiotherapy, i.e. the hit models coming from target theory.

Target theory and hit-modeling paradigm were introduced in the 1920s when biologists were beginning to develop quantum approaches to inactivation phenomena in irradiated biological tissue [START_REF] Dessauer | Uber einige Wirkungen von Strahlen[END_REF][START_REF] Blau | Uber einige Wirkungen von Strahlen[END_REF][START_REF] Crowther | Some considerations relative to the action of X-rays on tissue cells[END_REF] . The modeling of radiation effects on living cells were continued both theoretically and experimentally by K. C. Atwood and A. Norman [START_REF] Atwood | On the interpretation of multi-hit survival curves[END_REF] , D. E. Lea [START_REF] Lea | Actions of Radiations on Living Cells[END_REF] , E. C. Pollard and coworkers [START_REF] Pollard | The Direct Action of Ionizing Radiation on Enzymes and Antigen[END_REF][START_REF] Pollard | Radiation Inactivation of Enzymes, Nucleic Acids and Phage Particles[END_REF] . Since these seminal works, a lot of mathematical models expressing the interaction of radiation particles with biological cells have been proposed [START_REF] Fowler | Differences in Survival Curve Shapes for Formal Multi-target and Multi-hit Models[END_REF][START_REF] Sy | Analysis of a stochastic model of cell survival[END_REF][START_REF] Ditlov | The evolution of track theory throughout the history of the international solid state detector conferences[END_REF][23][START_REF] Chapman | Target Theory Revisited: Why Physicists are Essential for Radiobiology Research[END_REF][START_REF] Ditlov | Track theory and radiation effects[END_REF] . In target theory, a cell has different vital sites called targets which must be inactivated to kill the cell. For instance, it is accepted that the chromosomes are sensitive targets [START_REF] Dertinger | Molecular Radiation Biology[END_REF] but there is additional evidence that the nuclear membrane, or some cell organelles close to the nuclear membrane can also be regarded as targets [START_REF] Datta | Use of track-end alpha particles from 241 Am to study radiosensitive sites in CHO cells[END_REF] . Each target is deactivated when it is hit by a number of radiation particules. There are several classes of hit models classified by the number of targets and the number of hits. In these models, it is generally assumed that cells have homogeneous behaviour. In practice, there are at least three main reasons to put this hypothesis into question. The first cause of heterogeneity comes from the nonuniform spatial distribution of the radiation dose.

The second cause is due to the differences between the cell types (necrotic, quiescent, proliferating, stem cells, etc.) and the nonuniform concentration of oxygen and nutrients. A third factor corresponds to a cell-to-cell variability of damages and to the variation of the cell sensitivity to radiation. The first two points may be handled by reducing the modeling scale to a voxel level, i.e. a sub-volume in which we can reasonably suppose that distribution doses and cell types are homogeneous. For the last point, the hit models typically assume that cell sensitivity to radiation is constant over the time course of radiotherapy. In other words, after a radiation dose, a surviving cell is thought to be about as viable as an unirradiated cell and all cells are supposed having the same survival probability. However, evidence suggests that the cell radiation sensitivity increases with the number of dose fraction and even the cell is still alive, it partially loses the ability to resist as an unirradiated cell. Our aim is to focus on this last issue and a triple objective is addressed:

• to propose an extension of hit models based on a Markov chain formalism able to describe the target reparation between two consecutive dose fractions of the radiation schedule, the heterogeneity of damages induced by radiations and the cell proliferation;

• to determine the TCP and NTCP;

• through numerical computations, we compare the multinomial model with typical hit models and we draw the optimal total dose from the TCP/NTCP curves.

This paper is structured as follows: we present a brief overview of hit models and target theory in Section 1. We give a detailed development of the tumour growth multinomial model in Section 2. In Section 3 we review existing classical TCP models. Based on the multinomial model, we propose a new expression of TCP in Section 3 and NTCP in Section 4. In Section 5, we integrate the cell proliferation into our approach. Numerical results are presented in Section 6. Finally, the main results, limits and perspectives of the multinomial model are drawn in Section 7.

Radiation, hit models and target theory

The main notations used thereafter are presented in Table 1.

Hit process

For a radiation dose u 0 , the number of delivered radiation particles is with ρ the number of radiation particles per unit dose and the subscript p corresponds to particules. Thereafter, n p is assumed to be an integer for simplification. The underlying assumptions 23 of the hit models are:

n p = u 0 ρ, (1.1)
(1) a cell has at least one critical target;

(2) the probability q h (the subscript h corresponds to hit) that a radiation particle hits a critical target is the same for all targets;

(3) the hit events are independent from each other.

Let N h be the random variable denoting the number of radiation particles that hit a given target. Then, N h ∼ B(n p , q h ) (binomial distribution) and the probability that exactly j radiation particles hit a given critical target is:

P r(N h = j) = ( np j )q j h (1 -q h ) np-j , j = 0, 1, 2, • • • , n p . (1.2)
If n p is large enough and q h is low, such as n p q h = λ ∈ [0, 10], the distribution of N h can be approximated by the Poisson distribution P(λ). Fixing

α = ρq h , (1.3)
then according to (1.1), λ = n p q h = αu 0 and the probability that exactly j radiation particles hit a target becomes

P r(N h = j) = (αu 0 ) j j! e -αu 0 , j = 0, 1, 2, • • • (1.4)
αu 0 is the expected number of primary lesions caused by the radiation dose u 0 and the parameter α can be interpreted as a characteristic of the damage process itself, i.e. radiosensitivity in its literal sense [START_REF] Hanin | Randomized multihit models and their identification[END_REF] . There are several classes of hit models classified by the numbers of targets and hits.

Single target-single-hit models

In single target-single-hit models, it is assumed that a cell has one lethal target and that the cell dies when its target is hit by one or more radiation particles.

Therefore, the cell dies with probability

q c := P (N h ≥ 1) = 1 -e -αu 0 .
(1.5)

Single target-multi-hit models

In single target-multi-hit models, the cell dies when the target is hit by at least h t radiation particles, where h t is a threshold number of cell inactivations also called extrapolation number. Therefore, the probability that the cell dies is

q c := P (N h ≥ h t ) = ∞ j=ht (αu 0 ) j j! e -αu 0 = 1-e -αu 0 -• • •- (αu 0 ) ht-1 (h t -1)! e -αu 0 . (1.6)

Linear-quadratic model

The linear-quadratic model considers that a cell contains one single target.

This model is based on a radiobiological approach 1 : after a radiation dose u 0 , the cell dies either by a single lethal event on the target which is represented by a linear component or by the combination of two sublethal events close enough in time and space, which is represented by a quadratic component.

Thus, the cell death probability after a radiation dose u 0 is defined as

q c = 1 -p c = 1 -e -(αu 0 +βu 2 0 ) , (1.7)
where α and β are two positive parameters.

Dawson and Hillen 4 provide a detailed explanation using radiation physics and leading to (1.7). Note that the linear quadratic (LQ) model has been gaining popularity these recent years 2 .

However, under the single-target assumption, the surviving cell population is homogeneous in terms of radiation injuries in cells. That is why we revisite in this paper the target modeling theory in a stochastic framework able to handle the heterogeneity of damages.

Multi-target-single-hit models

Here, the cell has m distinct targets and dies when the m targets have been inactivated. Each target can be deactivated by a single hit. According to (1.5), this event occurs with probability 1e -αu 0 . Under the assumption that the deactivation of targets are independent events, the probability that the cell dies is

q c = (1 -e -αu 0 ) m . (1.8)
Similarly to the single target models, the variation in cell radio-sensitivity has not been taken into account and all cells have the same survival probability

p c = 1 -q c .

Multinomial model of a tumor

Two main aspects of tumor growth are generally missing in the typical hit models: (i) the heterogeneity of damages induced by radiations in the cancer cell population after each dose fraction and (ii) the target reparation between two consecutive dose fractions. Thereafter, we thus propose to take these two issues into account in the multinomial model [START_REF] Keinj | A multinomial model of tumour growth treated by radiotherapy[END_REF] . In this section, we detail the multinomial model without the cell proliferation which will be introduced afterward in Section 5.

Radiation scheduling

We restrict our study to fractionated radiation schedules that have 5 dose fractions per week. More specifically, the first fraction is given on Monday morning, and there is no treatment on the weekends. The treatment is based on a static (i.e. fraction sizes do not vary over time) scheme illustrated in • the patient image data is acquired, typically fully 3-D Computed Tomography (CT) scans;

• based on this CT scan, the physician outlines the tumor and important normal structures on a computer like the gross target volume, the clinical target volume, and the planning target volume;

• each 3-D CT scan is decomposed into subvolumes called voxels. It is sup-posed that each voxel v received a uniform dose u 0,v per fraction, but the latter may vary from a voxel to another one.

Heterogeneity of cell states after radiations

We consider that a cell contains m targets. Each target can be made inactive by radiation particules and the cell death occurs when the m targets are deactivated. After a fraction of treatment, a cell may have m + 1 possible states:

• state i, the cell has i inactive targets, i ∈ {0, 1, . . . , m -1}, these are the m states of a surviving cell;

• state m, the cell having m inactive targets is a dead cell.

Figure 2 shows the case of a 3-target cell and the corresponding cell states. We adopt the convention that the first row and first column of a matrix will be noted by the index value 0. Denote P(i, j) the probability to deactivate j targets at time k+1 when i targets are disabled at time k. Let q the probability to inactivate a target after a dose fraction u 0 . Moreover, we suppose that the disabling of targets in the cell are independent events. Thus after applying a fraction dose, the possible states at time k + 1 of a cell in state i at time k are {i, i + 1, . . . , m}. The cell may switch at time k + 1 to the state j by the deactivation of ji target(s) among the mi active ones. Consequently,

Discrete-time Markov chain model of a cancer cell

P(i, j) = ( m-i j-i )q j-i (1 -q) m-j . (2.1)
Then, we obtain the general expression of the matrix P,

P(i, j) =                ( m-i j-i )q j-i (1 -q) m-j i ≤ j 0 j < i (2.2)
and the explicit expression is

P =                           (1 -q) m ( m 1 )q(1 -q) m-1 . . . q m 0 (1 -q) m-1 . . . q m-1 . . . . . . . . . 0 0 . . . q 0 0 . . . 1                           . (2.3)
Figure 3 shows the transition graph of the radiation process before taking the repair of inactive targets into account, for the case of a 3-target cell, i.e. m = 3.

The target deactivation parameter q is the probability to deactivate an active target after a radiation dose fraction u 0 . To connect this parameter with the real treatment schedule, we consider the following possibilities:

• If we assume that a target is deactivated when it is hit by one or more radiation particules, then according to (1.4), we have

q = P (N h ≥ 1) = 1 -e -αu 0 , (2.4)
where N h is the random number of radiation particules that hit a given target.

• According to the (LQ) model, recall that after a dose fraction u 0 a cell dies with probability q c = 1e -αu 0 -βu 2 0 . However, it is clear that in our model

q c = P(0, m) = q m . Consequently, q = (1 -e -αu 0 -βu 2 0 ) 1 m .
(2.5)

Reparation modeling in surviving cells.

We introduce now repair mechanisms of deactivated targets which occur between the application of two consecutive dose fractions. Let r the probability of an inactive target in a living cell to revive during the period that separates two consecutive dose fractions. We assume that any target can be repaired independently from each other. The possible states at time k + 1 of a cell in state i at time k are {0, 1, . . . , i}. Denote R(i, j) the probability that the cell switches at time k + 1 to the state j. Since ij targets among the i inactive targets are repaired, then

R(i, j) =                ( i j )r i-j (1 -r) j j ≤ i < m 0 i < j.
(2.6)

For i = m, R(m, m) = 1 and R(m, j) = 0 for all j = m. The explicit expression is R =                                  1 0 0 . . . 0 r 1 -r 0 . . . 0 r 2 ( 2 1 )r(1 -r) (1 -r) 2 . . . 0 . . . . . . . . . . . . r m-1 ( m-1 1 )r m-2 (1 -r) . . . . . . 0 0 0 0     
.

(2.7)

2.3.3 Transition matrix of (Z k ).
We model the dynamics of the Markov chain (Z k ) k∈N by taking firstly the effects of dose fractions and secondly repair mechanisms into account as follows

Π = PR, (2.8)
where P models the effects of dose fractions, and R describes repair mechanisms.

In the case of a 3-target cell,

Π =                    
(rq + q ) 3 -(rq) 3 3r qq 2 + 6rr q 2 q 3q 2 q r 2 q 3 rq 2 + 2r 2 qq r q 2 + 4rr qq 2r 2 qq q 2 r 2 q 2rr q r 2 q q 0 0 0 1

                   
(2.9)

where q = 1q and r = 1r. Figure 4 shows the transition graph corresponding to the Markov chain (Z k ) after taking the repair of inactive targets into account.

Probability distribution of Z k .

Set ν k = (ν 0 k , . . . , ν m k ) the probability distribution vector of Z k :

ν i k = P (Z k = i).
Using the Markov chain property, ν k may be expressed in terms of Π and ν 0 :

ν k = ν 0 Π k . (2.10)
If we assume that the cell is initially in state 0, then ν 0 = (1, 0, . . . , 0) and

ν i k = Π k (0, i) i ∈ {0, . . . , m}.
(2.11)

Comparison with hit models.

The multi-target-single-hit model is a special case of the multinomial model by considering that all sublethal damages are completely repaired between dose fractions, i.e. by taking the repair parameter r equal to 1. Indeed, when r = 1, a cell is either dead or in state 0, then the surviving cell population is homogeneous. This and assuming q verifies (2.4) lead to the case of the multi-target-single-hit model.

Similarly, if we fix the target number parameter m = 1 and the deactivation target parameter q equals to (2.5), we get the the linear quadratic model.

Multinomial model of the tumour

Consider a group of n 0 cells that compose the tumour. We divide the tumour into n t voxels. We suppose that a voxel v of the computerized tomography scan contains n v cells i.e.

n 0 = nt v=1 n v .
(2.12)

In each voxel v we assume that:

• cells behave independently and with the same dynamics (cf Section 2.3);

• the probability q v to deactivate a target in a cell is the same for all cells located in v;

• the probability of target repair r is constant and does not depend on v.

For each cell j, we associate a discrete-time Markov chain (Z

(j) k ), where Z (j) k
is the random number of deactivated targets. Therefore, the Markov chains

{(Z (j) k )} j∈{1,...,
= (ν 0 k , . . . , ν m k ). Consequently, P r(X k,v (0) = h 0 , . . . , X k,v (m) = h m ), is given by                nv! h 0 !...hm! (ν 0 k ) h 0 . . . (ν m k ) hm if m i=0 h i = n v 0 otherwise (2.13)
where h i , i ∈ {0, . . . , m}, are non-negative integers.

Note that the number X k,v (i) of cells in state i at time k follows the binomial distribution:

X k,v (i) ∼ B n v , Π k v (0, i) . (2.14)
Consequently, its average number is

E(X k,v (i)) = n v Π k v (0, i).
(2.15)

Number of surviving cells

In the multinomial model, the number of surviving cells in the voxel v after the k th dose fraction is given by

N k,v = X k,v (0) + . . . + X k,v (m -1) = n v -X k,v (m). (2.16) Since X k,v (m) ∼ B(n v , Π k v (0, m)), then N k,v ∼ B n v , 1 -Π k v (0, m) .
(2.17)

This implies that

E(N k,v ) = n v 1 -Π k v (0, m) , (2.18)
and

V ar(N k,v ) = n v 1 -Π k v (0, m) Π k v (0, m). (2.19)

Tumor Control Probability

The probability that no cancer cell remains in a tumor after radiation is known as the Tumor Control Probability (TCP). This probability may be useful to evaluate either the quality of a treatment planning or for its optimization.

Recall that the tumor is decomposed into n t voxels (cf Section 2.4) and these voxels are supposed to be independent, then the TCP at k is given by

T CP k = nt v=1 V CP k,v , (3.1)
where V CP k,v denotes the Voxel Control Probability at time k, i.e. the probability of having no cancer cell in the voxel v.

Expressions of VCP

The binomial and Poisson formulations of V CP , for a uniformly irradiated volume v (voxel), are generally used in radiotherapy planning [START_REF] Murno | The relation between tumor lethal doses and the radiosensitivity of tumor cells[END_REF][START_REF] Brahme | Dosimetric precision requirements in radiation therapy[END_REF][START_REF] Brenner | Dose, volume, and tumor-control predictions in radiotherapy[END_REF] . First, let p c,v (k) denote the probability that a cancer cell located in the voxel v survives after k dose fractions with magnitude u 0 . Since we have supposed that all cells behave independently, then the number of surviving cancer cells after the k th dose fraction follows a binomial distribution B(n v , p c,v (k)), and we obtain

V CP k,v = (1 -p c,v (k)) nv . (3.2)
When the distribution B(n v , p c,v (k)) may be approximated by the Poisson distribution P(n v p c,v (k)), we have

V CP k,v = e -nvpc,v(k) . (3.3)
The main drawback of hit models presented in Section 1 is to ignore the repair mechanism and the heterogeneous distribution of the cellular damages over the tumor and over time, since p c,v (k) is defined as

p c,v (k) = (p c,v ) k , (3.4)
where

p c,v = p c,v (
p c,v (k) = 1 -Π k v (0, m). (3.5)
Then, the multinomial V CP at time k is defined according to (3.2) as

V CP k,v = Π k v (0, m) nv . (3.6)
Therefore, according to (3.1) we obtain the TCP for the whole tumour : We restrict ourselves to the parallel architecture. It is supposed that organs are composed of functional subunits (FSUs) and that organ function is compromised when a certain critical fraction of these FSUs is damaged.

T CP k = nt v=1 Π k v (0, m) nv . ( 3
The Normal tissue Voxel Complication Probability, noted N V CP k,v , is defined as the probability that a complication appears in a normal tissue voxel v at time k. The Normal Tissue Complication Probability N T CP k in the whole tissue at time k is the probability that at least one voxel among the nt voxels of the normal tissue has been damaged. If we assume that radiation injury to voxels are independant events, then

N T CP k = 1 - nt v=1 (1 -N V CP k,v ). ( 4.1)
For a uniformly irradiated voxel with nv FSUs and a reserve capacity of (n-1)

FSUs, it is supposed that [START_REF] Jackson | Probability of radiation-induced complications for normal-tissues with parallel architecture subject to nonuniform irradiation[END_REF][START_REF] Niemierko | Modeling of normal tissue-response to radiation-the critical volume model[END_REF] :

• a complication appear if the number of damaged FSUs exceeds n;

• each FSU among the nv ones is damaged with a probability p F SU ;

• all FSUs behave independently.

Let N F SU be the random number of damaged FSUs among the nv ones after irradiation, then it has a Binomial distribution B(n v , p F SU ) and the probability of complication in the voxel v can be expressed mathematically as

N V CP v = P (N F SU ≥ n) = nv i=n ( nv i ) (p F SU ) i (1 -p F SU ) nv-i . (4.2)
Multinomial NVCP

In our model, we suppose that each FSU is one normal cell. Assume that the dynamic of normal cells is similar to the one of cancer cells and given by the multinomial model, defined in Section 2.4, but with different values of the parameters. Then, a normal cell contains m targets, each of them is deactivated with a probability q and it is repaired with a probability r. However, if the treatment plan is correctly designed, radiation doses are lower in the voxels of normal tissue than in the ones of the tumour. As a consequence, the probability that a radiation particle inactivates a target in a normal cell, is lower than for a cancer cell (q < q). Moreover, the repair mechanism for normal tissue cells is better for fractionated radiation than tumour cells for reasons which

are not yet explained. Consequently, the probability for an inactive target to be reactivated is greater for a normal cell than for a cancer cell (r > r).

For simplicity, we use the same notation, as for cancer cells, to denote the probability Πk v (0, m) that a normal cell, located in a voxel v, is in state m at time k (dead cell). Xk,v ( m) is the number of dead cells at time k among the nv initial cells in a normal voxel v. Obviously, Xk,v ( m) is the analogue of

X k,v (m)
(cf Section 2.4). Since the complication in the normal voxel v occurs when the dead cell number is larger than n, then the N V CP v expression at time k can be written as

N V CP k,v = P ( Xk,v ( m) ≥ n) = nv i=n ( nv i ) ( Πk v (0, m)) i (1 -Πk v (0, m)) nv-i . (4.3)
Note that, equation (4.3) is a special case of (4.2) for p F SU = Πk v (0, m). In particular, if complications only occur when all cells are killed i.e. nv = n, the the definitions of NVCP and VCP coincide and the normal voxel complication probability becomes

N V CP k,v = ( Πk v (0, m)) nv . (4.4)
Finally, integrating (4.3) in (4.1), we obtain the NTCP for the normal tissue in the irradiated zone.

First let us describe the new behavior of a given cell taking the reproduction phase into account. Once the k th dose fraction is applied, the cell may be damaged, thus repair mechanisms and proliferation follow until the k+1 th dose fraction. The damage and repair phases are again modelled as in Section 2.3.

We suppose that the cell may reproduce if only it remains in state 0 after the application of a dose fraction, which occurs with a probability P(0, 0) =

(1q) m . A cell that stays in state 0, divides and gives birth to two daughter cells in state 0 with probability µ or it remains unchanged with probability 1µ. It is convenient for our computation, in the case of cell division, to consider the mother cell is still alive and a new one (in state 0) is artificially added.

Consider a voxel v that contains n v cells in state 0. All cells behave as described previously and independently. Let S 1 be the random number of the additional cells in state 0 resulting from cell reproduction after applying the first dose fraction on the n v cells. Since a new cell is produced with a probability µ(1 -

q v ) m , then S 1 ∼ B n v , µ(1 -q v ) m . (5.1)
Consequently,

η 1 := E(S 1 ) = n v µ(1 -q v ) m .
(5.

2)

The number X p 1,v (0) of cells in state 0, at time k = 1, after including the cell proliferation becomes

X p 1,v (0) = X 1,v (0) + S 1 , (5.3)
where X 1,v (0) is the number of cells in state 0 after the first dose fraction and the repair phase, among the n v initial cells,

X 1,v (0) ∼ B n v , Π v (0, 0) .
We replace S 1 in the next steps by its mean value η 1 = E(S 1 ) and recall that these new cells are in state 0. We deduce that modeling the treatment effects, repair mechanisms and cell proliferation in the initial cell population of n v cells is considered to be equivalent to model the treatment effects and repair mechanisms on these cells and to add η 1 cells in state 0. This analysis can be repeated at each time k adding a number η k of cells in state 0 resulting from cell reproduction. The sequence η k is given recursively by

               η 0 = n v η k+1 = µ(1 -q v ) m k j=0 Π k-j v (0, 0)η j k ≥ 0 (5.4)
and the new expression of the VCP becomes Similary, red curves represent the NVCP with r = 0.5 (solid line) and r = 1 (dashed line). For each couple of VCP/NVCP curves, an optimal dose OD is estimated by maximizing the total dose with the constraint NVCP≤ 0.05.

V CP k+1 = k j=0 Π k+1-j v (0, m) η j k ≥ 0. ( 5
The optimal total doses OD1 and OD2 are deduced from the NVCP curves, as

OD1 = max{d, multinomial N V CP (d) ≤ 0.05}, OD2 = max{d, typical N V CP (d) ≤ 0.05}.
We observe that the optimal dose OD2 ≈ 46Gy derived from the typical VCP/NVCP curves (r = r = 1) is clearly greater than the optimal dose OD1 ≈ 27Gy corresponding to the multinomial VCP/NVCP curves calculated with r = 0.3 and r = 0.5.

The above numerical results show an important difference between the outcome of each couple of the VCP/NVCP curves. This is mainly due to heterogeneity of cell states and reparation process in cancer and normal cells, quantified by the multinomial modeling. As a therapeutical consequence, this approach may reduce the total radiation dose to be delivered and thus the risk of side effects.

VCP calculation for a clinical schedule

We present here a VCP calculation taking into account the proliferation of cells with a given real value of dose fraction u 0 . The VCP equation (5.5) was implemented in the Matlab environment using for the parameter q the relation

Conclusion

In this paper, we proposed a multinomial model suited to treatment in radiotherapy, which takes into account (i) the variety of cell responses according to their biological states and (ii) the repair mechanisms that occur between dose fractions. Moreover we included the proliferation of cells that may produce during the treatment period. The radio-sensitivity of cells due to their positions in the cell cycle and the angiogenesis process (tumour blood supply)

have not been considered in our model.

The new model is composed of only three parameters: the number m of critical targets which allows to quantify the heterogeneity of intracellular damages during the treatment plan, the probability q for a target to be deactivated by radiation and the probability r for an inactive target in an alive cell to be reactivated. The parameter q is related to the radiation dose u 0 through the intrinsic sensitivity of a target to radiation. Moreover, the multinomial model is a generalization of typical hit models. Based on the multinomial model, new expressions of the TCP and NTCP have been proposed for nonuniform radiations which permits to deduce the optimal total dose to be delivered. We point out the important influence of the repair parameter r which could lead to reduce both the total radiation dose to be delivered and the risk of side effects. q 2 0 3 2

(1q) 2 1

(1q) 3 q 1 3q(1q) 2 1q 3q 2 (1q)

2q(1q) q 3 3q 2 q ′ r ′2 0 3 1 (rq + q ′ ) 3 -(rq) [START_REF] Zaider | Tumour control probability: a formulation applicable to any temporal protocol of dose delivery[END_REF] r ′ q ′2 +4rr ′ qq ′ 2 r ′2 q ′ 3r ′ qq ′2 +6rr ′ q 2 q ′ rq ′2 +2r 2 qq ′ 2r ′2 qq ′ 2rr ′ q ′ q q 3 q 2 r 2 q ′

Figure 1

 1 Figure 1 by an impulse train u(k) in which u 0 denotes the magnitude of each dose fraction (typically u 0 = 2Gy) and k is the discrete time based on a daily sampling rate. Thus, d(k) = k i=0 u(i) is the cumulated dose of radiation up to time k. The treatment planning process is composed of the following steps:

  A discrete-time Markov chain model is proposed to describe the heterogeneity of cellular damages during the fractionated treatment. Let us first consider a single cell composed of m targets. Let Z k be the random variable describing the state of the cell at time k, Z k = i ∈ {0, 1, • • • , m} is the number of deactivated targets at time k. We suppose that (Z k ) is a discretetime Markov chain, i.e. the cell state at time k +1 only depends on the current state at time k and let Π the corresponding transition matrix. We determine thereafter the expression of Π which models both of effects of dose fractions and repair mechanisms.

2. 3 . 1

 31 Treatment effect modeling.

1 )

 1 is determined by equations (1.5),(1.6),(1.7) and(1.8) according to each model. The above relation(3.4) means that after each dose fraction a surviving cell has the same probability p c,v to survive after the next dose fraction.However, considering the multinomial model presented in Section 2.4, the cell radiation sensitivity increases with the number of dose fraction and for a cell initialy in state 0 we have

. 7 ) 4

 74 Normal Tissue Complication ProbabilityThe main undesirable effect due to radiotherapy is the irradiation of normal tissue. Normal organs and tissues have different responses to radiations due to their distinct architecture. Niemierko and Goitein 33 proposed a division of normal tissues into three different architectures: serial architecture (e.g. nerves or spinal cord), parallel architecture (e.g. kidney, liver or lung) and graduated response (e.g. skin or mucous membranes).

. 5 ) 6 analysis 6 . 1

 5661 Numerical Comparative analysis with typical VCP/NVCP Recall that we have observed that classical hit models are particular cases of the multinomial model by fixing the target reparation parameter r and r for cancer and normal cells respectively at r = r = 1 or by taking the single-target assumtion i.e. m = 1. Therefore the comparison between VCP/NVCP typical model vs VCP/NVCP multinomial model reduces to study the influence of the parameter r (and r) on the VCP/NVCP models. For simplicity we only consider one voxel. The multinomial VCP and NVCP equations (3.6) and (4.3) were implemented in the Matlab environment. The parameters were fixed to m = 3, q v = 0.7, n v = 10000 for cancer cells; m = 3, qv = 0.6 and n = nv = 1000 for normal cells. We chose parameter values avoiding numerical complications so that they permit to obtain numerical results without any specific biological interpretations. The values of the repair parameters for the multinomial VCP/NVCP curves are r = 0.3 and r = 0.5; and recall that r = r = 1 for the classical VCP/NVCP models. The radiation treatment is decomposed into 50 dose fractions. Note that V CP k,v and N V CP k,v given by (3.6) and (4.3) respectively, are functions of k. In practice, it is more convenient to express them in terms of the cumulated dose d(k) = ku 0 . Figure 5 presents the VCP/NVCP curves obtained as functions of the cumulated dose d. Blue lines denote the VCP curves; the solid and dashed lines correspond to r = 0.3 and r = 1 (typical assumption) respectively.

( 2 . 5 )

 25 depending on α and β (1.7). The parameters were fixed to m = 3, r = 0.3, µ = 1, n v = 10000 and we consider the couple (α, β) = (0.3, 0.03) used in 35 .

Figure 6

 6 Figure 6 displays the variation of the VCP as function of the cumulated dose d. The solid curve represents the VCP function for u 0 = 1Gy and the dashed one corresponds to u 0 = 2Gy. This shows the sensitivity of the VCP prediction to the u 0 values. It is expected that the efficiency of the treatment increases with the value of the dose fraction u 0 .

Figure 1 .

 1 Figure 1. Radiation static scheme: u(k) is an impulse train of dose fractions daily delivered, five days a week; d(k) is the cumulated dose of radiation.

Figure 2 .

 2 Figure 2. Heterogeneous states of a cell (m = 3) after radiation exposure.

Figure 3 .

 3 Figure 3. Transition graph of radiation process, with m = 3 and before taking target repair mechanisms into account.

1 Figure 4 .

 14 Figure 4. Transition graph of the Markov chain (Z k ) k∈N where m = 3 and after including the repair of inactive targets.

Figure 5 .Figure 6 .

 56 Figure 5. Calculated values of VCP and NVCP as functions of the cumulative dose d. Blue curves represent VCP functions: solid line for r = 0.3 and the dashed line for r = 1 (typical VCP). Red curves represent the NVCP functions, where r = 0.5 in solid line and r = 1 (typical NVCP) in dashed line. For r = r = 1, the corresponding optimal dose OD2, that maximizes the VCP with the constraint N V CP ≤ 0.05, is larger then the optimal dose OD1 obtained with the other VCP/NVCP functions.

Table 1

 1 Main notations

	Notations
	Not.	Definition
	k	discrete time
	n p	number of delivered radiation particles per a radiation dose u 0
	q h	probability that a radiation particle hits a target
	N h	number of radiation particles that hit a critical target
	q c	probability of cell death after radiation
	p c	survival probability of a cell after treatment
	v	voxel (subvolume) of a 3-D scan
	Z m	number of targets in a cancer cell
	q	probability to deactivate a target in a cancer cell
	r	probability for an inactived target to be reactivated in a cancer cell
	n 0	initial total number of cancer cells in the tumour
	n t	total number of tumour voxels
	n v	initial number of cancer cells in a tumour voxel v
	m	number of targets in a normal cell
	q	probability to deactivate a target in a normal cell
	r	probability for an inactive target to be reactivated in a normal cell
	n0	initial total number of normal cells in the irradiated zone
	nt	total number of normal tissue voxels
	nv	initial number of cells in a normal tissue voxel v
	n	the complication threshold number of dead normal cells

k number of deactivated targets in the cell Π transition matrix associated with the Markov chain (Z k ) P matrix associated with treatment effects R matrix associated with cell repair process X k,v (i) number of cancer cells in state i in the voxel v at time k Xk,v (i) number of normal cells in state i in the voxel v at time k

  nv} are independent and have the same transition matrix Π v .Let X k,v (i) be the random number of cells in state i ∈ {0, . . . , m}, at time k, among the n v initial cells in the voxel v. Since Z

	(1) k , . . . , Z	(nv) k	are i.i.d., and
	follow a categorial distribution, then X k,v (0), • • • , X k,v (m) follows a multi-
	nomial distribution with parameters n v and ν k


1

The Westerner in Chinese Advertisements, the Chinese in Western Advertisements: crossed views on added values.

Thomas Boutonnet

Sino-European Transcultural Encounters, International Conference organized by Sun Yat Sen University (Guangzhou, China) and Macau Inter-University Institute (Macau SAR, China)

15-17 May 2008

Powerpoint Slide 1 I must right away make two points clear. First of all: I will not talk about contemporary advertising in China and its general trends, but I will just talk about these specific Chinese street advertisements or billboards involving a western reference, mostly western people, in their visual aspect. Secondly: the assumptions and conclusions I will draw about these advertisements are definitely not exclusive to them. Of course, some other forms of advertisements in China could be vehicles for the very same values and purposes that I'm going to expose here.

Powerpoint Slide 2 ("Representations….") Since 1998, during all my visits to China, I have noticed that the representation of the Westerner (generally White) in Chinese street advertisements or billboards was often associated in one way or another with a certain idea of excellence, high quality, luxury or fashion. Similarly, the presence of a Chinese person (or Chinese references, or even oriental references, because this concept is still strongly linked to China) in Western commercials is most of the time associated with the concepts of mystery, wisdom, spirituality or eternity. By these representations, and beyond the formal differences, one single goal is targeted: to add value to a product, by using the Other (and by exploiting ignorance of the Other, stereotypes on the Other and common ideas on the Other) to create identity: a brand identity, and therefore, the consumer's identity.

We will first see what is added, as a value, by using the representation of the Other in advertisement. And we will then see what we learn about our post-modern societies: I will show that this phenomenon contributes to and tends to reinforce the commodification of culture; and also reveals an strong trend in our contemporary societies: the omnipresence of the middle class as a new social norm.

Powerpoint Slide 3 (Part 1)

This association between the icon of the Foreigner or the White and the idea of excellence or high quality can be explained by the rise and the development of a mass consumer society in China in the early nineties. At the beginning of the twentieth century, when West was synonymous with civilization, the White was already linked to modernity in China. But the Nineties, characterized by the powerful growth of the private sector and the service industry, generalized a materialist ideal of life based on the desire to have and show. An ideal of life traditionally represented by the United States, the American/Californian way of life, based on mass consumption, and the American Dream, qualified by Jack Solomon 1 as a constant desire for social success and material rewards.

Powerpoint Slide 4 (Houshi Boss Ad)

This advertisement is a perfect demonstration of my topic. Here we have a character, who can be described as a white, male adult, most probably urban, he seems to be very confident, he radiates an almost physical confidence, strengthened by the ambition we can discern in his eyes looking towards the outside the visual field (maybe towards the future) and the serenity suggested by the glasses removed from his eyes.

Powerpoint Slide 5 ("Westernity")

The glass of alcohol close to him gives him a wise and grown dimension. And the tag line, written in a dubious English, mentions what the visual already convinces us of : I believe muself. Of course, all of this would be nothing without the briefcase, without the briefcase there can't be any boss. All of this forms a kind of paradigm where one can find, pell mell, mixed values such as success, confidence, manliness, and wealth, all linked to the White, a mix which can also be called Westernity (in reference to the sinité or Chineseness of Roland Barthes, a term he used to identify this China seen by the Westerners as a special compound of small bells, rickshaws and opium dens Powerpoint Slide 6 (Beijing Hospital Ad)

In this other advertisement, for a hospital in Beijing specialized in the treatment of urinary pathologies, the slogan, A good health is the key for a perfect home, is illustrated by what would be a perfect home : the home of a white man, a virile man (it is tempting, besides, to think that this hospital offers manliness), and obviously radiating success, confidence and ambition, as shown by his thumb up. The icon of the white successful man is supposed to illustrate the perfection.

Powerpoint Slide 7 ("While you cannot change…")

It is still useful to remind that advertisement has, before anything else, the purpose to stimulate and cause the act of purchasing, by associating some values and an imaginary to the product. Quoting the words of Professor James Twitchell, While you cannot change what a product is, you can change what it means 2 . The merchandise, through advertising, creates little stories of day-to-day life ; put all together end-to-end these stories form the History of the consumer. Advertisement has a legitimate inclination to put into scenery a world where consumption is a source of positive change and satisfaction, and where purchasing is the core of existence. Therefore, advertisement cannot do anything but praise the middle class, it emphasizes the middle class, contributes to creating its universe, because the middle class has the capacity of consumption. Publicizing the life of the poor, who do not have neither the power nor the intent to purchase, would be senseless. The merchandise, by means of advertising, has everything to gain by disseminating the myth of the middle class as a social accomplishment. And it reaches its goal by conveying standards, conventions which will impose the middle class as an ideal to achieve.

Powerpoint Slide 8 ("The purpose of White…") 1 Jack Solomon, Masters of Desire: The Culture of American Advertising, 1996. 2 James Twitchell, Twenty ads that shook the world, New York, Three Rivers Press, 2000.

The consumer society, developed in the nineties, and the constitution of a middle class, have accompanied China to shift into a modernity in which accession to middle class is shown as a sign, and the goal, of a social accomplishment. The purpose of the White in these Chinese advertisements is to embody high-quality, excellence, perfection, and also a certain idea of social accomplishment, implying materialist success. The White, who has, in Chinese imaginary, already reached this ideal (most of the representations, movies, soap-operas, images, show the White in an ideal financial situation), serves this propaganda of the middle class as a social accomplishment.

Powerpoint Slide 9 ("An added value…")

As we can see, these representations of the Westerner are carrying and adding value, an ideological value. An added value supposedly missing or lacking for the Chinese, and whose quest would be supposed to perfect an existence still unbalanced: the White way of life.

We can draw similar conclusions about the purpose of the Chinese in Western advertising. The role of the Westerner is to represent Westernality, the role of the Chinese will be to stand for Orientality, that is to say all notions and features associated to the Chinese in a vision perfectly matching the criteria of Orientalism as defined by Edward Said.

Let's take a look at these two advertisements.

Powerpoint Slide 10 (Tea set Ad : These porcelains symbolise the heritage of eternal China) This first ad is an advertisement for a home accessories company, selling, among others things, tea sets. A very basic analysis let us find, only in the words used in the tag line, almost all the stereotypes and commonplaces about China : eternity, red colour, and the notions of symbol and heritage. We are dealing with a very basic, crude orientalism. And those stereotypes will probably help us better understand the next advertisement.

Powerpoint Slide 11 (IWC Ad : We don't know the lifetime of a IWC. But we've only existed for 140 years)

Powerpoint Slide 12 (Born 120 years ago !)

There is no rational explanation to the presence of this old person, inevitably Asiatic or Chinese, in this ad. The watch is not from China, its name is not linked to China by any way, and nothing in its design seems to refer to a potential Chinese aesthetic. The explanation is to be found in what this character is evoking for a Westerner: he is the iconic representation of the wise, the kung-fu Chinese master, the one who has the knowledge and hands it over to his follower. He IS, he embodies this notion of eternity, of longevity, long tradition, notions that this advertisement wants obviously associate to this watch.

Powerpoint Slide 13 ("The Westerner…..")

The Chinese Other representation in a western advertisement involves also some values, a fullness, that the Westerner does not have yet or does not have anymore, and whose pursuit would be supposed to perfect an existence still unbalanced : the Chinese wisdom and spirituality for the Westerner. The Westerner is evolving in a society which has already reached the limits of materialism, and which is looking for a certain idea of happiness, not anymore in consumption (as we can see in China), but mostly in the joy (and therefore in the consumption) of certain values, like spirituality, escaping, free time, discovery of the Other, all of them are concepts very used in advertisements in France. Confirming the statement of French professor Genevieve Cornu, Powerpoint Slide 14 ("Advertisement is the place…") saying that advertisement is the place where are expressed the deep trends of a period, the modern concerns, myths and sensibilities 3 . Advertisement, whose goal is to cause the purchase, is suggesting that a perfect and ideal life can be so only after the consumption of the product or the service which will precisely remedy to the lacks and the misbalance of your life. Because, let's not forget, and I'm still quoting professor Cornu, that we don't buy a product but the values attached to it. In this capacity, the advertising image offers to see human models corresponding to the dominating social values. (…) It works thanks to a "mimetic desire" forcing us to look like the model offered. (….) Advertisement reflects the dominating ideology, stereotypes which are often very volatile and episodic.

Powerpoint Slide 15 (Part 2)

As the French theorist Guy Debord demonstrated in his major work Society of Spectacle, we are living in what he calls a spectacle market economy, where to Be requires to Have and to Show.

Powerpoint Slide 16 ("We are living….") And, actually, the globalization, the predominance of the icon, of the image and of the representation on the real narrowed the culture to what it can be sold (that is to say, its simplified, folklorised, picturesque form, its iconic form, because they are sellable and bankable forms, and they don't need any kind of understanding). And advertising, by representing and using the Other, contributes to this commodification of cultures. Because the advertising image is often a mix of allusions and pictorial references exposed as an emblem, pieces torn off their scientific or historical contexts and carrying emotional values. It tends to short-circuit the thought and the understanding, too sophisticated, and prefers ingraining simplistic images and imagined representations in the spirits. By a negative side effect, advertising encourages to show what the Other is expected to be instead of showing what the Other is: a performative imaginary, or a known unknown, as exposed in Florent Villard's work about representation of China by the French tourism industry.

Powerpoint Slide 17 ("Spectacular…") But these advertisements also reveals a strong trend in our contemporary societies : more than a westernization of China, a often debated topic, we can observe, in terms of representation, icons and spectacle, the middleclassification of China, that is to say : the omnipresence of the middle class as a new social norm, as it can be seen in quite all other places and countries in the World nowadays. It is noticeable in China, when we see all these advertisements featuring Westerners as we just saw, because those westerners are here to represent this middle class. But it's even more noticeable when Chinese advertisements are featuring Chinese persons… Powerpoint Slide 18 (Beijing Airport Ad) …whose faces or behaviour seem to become "westernized", where there are no more signs of culture, because the consumer does not have culture or does not need culture. This is exactly the meaning of this statement by Genevieve Cornu, when she says that advertisement's image supposes a kind of cultural blur, geographical and historical imprecision, letting us evolving in a mythic imaginary. Advertisements make the consumer believe that they are reflecting reality, while they only create a world which is making allusions to reality, where the purpose, the aim is the consumption.

Because happiness is all about consumption as this advertisement is telling us 3 Geneviève Cornu, Sémiologie de l'image dans la publicité, Paris, Les éditions d 'organisation, 1991 Powerpoint Slide 19 (Happiness loans ) and we can see how relevant is this statement of professor Gregory Lee, when he's saying that the "necessity to give free rein to the power of imagination, to promote creativity (…) as intrinsic vector of a new art of living, is now more and more urging".

Conclusion

As a conclusion of my speech, I would sum up and say that the role of the White in Chinese ad, beyond his main purpose, reveals a "middleclassification" of our contemporary societies in terms of representations.

Powerpoint Slide 20 (Ideal Home Ad) It reveals a kind of leveling (still going on) of living conditions, where the standard would be that of Western consumerism, and where some folk representations supposed to differentiate cultures from others would be preserved at the local level. Across these crossed views of seemingly insignificant things, we discover a deeply strong trend of our time in terms of representations and spectacle: the accession (however very restricted) to the middle class as a standard, and the preservation of the cultures in the shape of clichés and easily identifiable stereotypes as added value and wealth. The Middle class and the end of cultural diversity are for me two faces of the same phenomenon, and we could see here an attempt to define post-modernity.

Powerpoint Slide 21 (Billeter Quote Pub Carrefour) And I will conclude this speech by these words of Jean-François Billeter about China "the dominating imaginary is from now on the same as elsewhere. It is likewise poor, and likewise dangerous because of this very poorness" Powerpoint Slide 22 (Thank you)