Florent Becker Lifo

Adrian Kosowski
email: kosowski@labri.fr

Nicolas Nisse
email: nicolas.nisse@sophia.inria.fr

Ivan Rapaport
email: rapaport@dim.uchile.cl

Karol Suchan
email: karol.suchan@uai.cl

Allowing Each Node to Communicate Only Once in a Distributed System: Shared Whiteboard Models

Keywords: F.1.2 [Computation by Abstract Devices]: Modes of Computation-Parallelism and Concurrency Algorithms, Theory Distributed computing, local computation, graph properties, bounded communication

In this paper we study distributed algorithms on massive graphs where links represent a particular relationship between nodes (for instance, nodes may represent phone numbers and links may indicate telephone calls). Since such graphs are massive they need to be processed in a distributed and streaming way. When computing graph-theoretic properties, nodes become natural units for distributed computation. Links do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. Our goal is to model and analyze the computational power of such distributed systems where one computing unit is assigned to each node. Communication takes place on a whiteboard where each node is allowed to write at most one message. Every node can read the contents of the whiteboard and, when activated, can write one small message based on its local knowledge. When the protocol terminates its output is computed from the final contents of the whiteboard. We describe four synchronization models for accessing the whiteboard. We show that message size and synchronization power constitute two orthogonal hierarchies for these systems. We exhibit problems that separate these models, i.e., that can be solved in one model but not in a weaker one, even with increased message size. These problems are related to maximal independent set and connectivity. We also exhibit problems that require a given message size independently of the synchronization model.

INTRODUCTION

A distributed system is typically represented by a graph where links correspond to a particular relationship between nodes. For instance, nodes may represent phone numbers and links may indicate telephone calls. A classical approach is to view each node as a processor. Since nodes lack global knowledge, new algorithmic and complexity notions arise. In contrast with classical algorithmic theory -where the Turing machine is the consensus formal model of algorithm -in distributed systems many different models are considered. Under the paradigm that communication is much slower and more costly than local computations, complexity analysis of distributed algorithms mainly focuses on message passing. That is, an important performance measure is the number and the size of messages that are sent by nodes for performing some computation. Theoretical models were conceived for studying particular aspects of protocols such as faulttolerance, synchronism, locality, congestion, etc.

The particularity of this work lies in the fact that links between nodes do not necessarily represent communication channels between the computing units and therefore do not restrict the communication flow. In that sense our setting is similar to the "mud" (massive, unordered, distributed) model, where the authors tackle the problem of performing a computation when the data is distributed among many machines [START_REF] Feldman | On distributing symmetric streaming computations[END_REF]. Roughly, in such mud algorithms, pieces of data are processed independently in parallel and pairs of messages are aggregated in any order. Only one message is created by each node because in truly massive database "a common approach for dealing with large datasets is to stream over the input in one pass" [START_REF] Feldman | On distributing symmetric streaming computations[END_REF].

The problem we intend to model here is less general than the one addressed in [START_REF] Feldman | On distributing symmetric streaming computations[END_REF]. In fact, in our setting there exists an underlying graph and the information each node possesses is nothing but its neighborhood. The computation the nodes need to perform collectively is related to some property of the graph. In [START_REF] Becker | Adding a referee to an interconnection network: What can(not) be computed in one round[END_REF] the first simple model for studying such scenario was introduced. In that model, the total amount of local information that each node was allowed to provide was bounded by O(log n) bits. Each node transmitted its message to a central authority, the referee, that collected and used them in order to give the correct output.

The main question was whether this small amount of local information provided by each node was sufficient for the referee to decide some basic structural properties of the graph G. For instance, simple questions like "Does G contain a square (cycle of length 4)?" or "Is the diameter of G at most 3?" cannot be solved. On the other hand, the referee can decode the messages in order to have full knowledge of G when G belongs to one of many graph classes such as planar graphs, bounded treewidth graphs and, more generally, bounded degeneracy graphs.

In this paper we define extensions of the model in [START_REF] Becker | Adding a referee to an interconnection network: What can(not) be computed in one round[END_REF] and investigate their computational power. It is interesting to point out that despite being extremely natural, these models of computation have never been studied before.

Communication using a shared whiteboard. The computational model in [START_REF] Becker | Adding a referee to an interconnection network: What can(not) be computed in one round[END_REF] can be stated equivalently in the following form. Given a question about the graph, every node writes simultaneously one message (computed from its local knowledge) on a global zone of shared memory, a whiteboard, and then one must be able to answer the question using only the contents of the whiteboard.

In this paper we intend to give more power to the initial model of [START_REF] Becker | Adding a referee to an interconnection network: What can(not) be computed in one round[END_REF]. For this purpose, we relax the simultaneity constraint in different ways. Roughly, messages may be written sequentially on the whiteboard. This allows nodes to compute their messages taking into account the contents of the whiteboard, i.e., the messages, that have previously been written. In other words, in the new models we propose, nodes have more sophisticated ways to share information. Basically, the four models we now present aim at describing how the nodes can access the shared medium, in particular, differentiating synchronous and asynchronous networks.

We define a framework for synchronization without using a global clock. Instead, time is divided into rounds corresponding to observable events, i.e., whiteboard modifications. More precisely, a round terminates when a node writes a message on the whiteboard. Along the evolution of the system, the nodes may be in three states: awake, active or terminated. Initially, all nodes are awake. A node becoming active means that this node would like to write a message on the whiteboard. Metaphorically speaking, it "rises its hand to speak". To model the worst-case behavior, an adversary chooses, among the set of active nodes, the particular node which is going to write a message on the whiteboard. Afterwards, this node enters the terminated state. Therefore, a node is in state terminated when its message has been written on the whiteboard. In one round, several awake nodes may become active but exactly one active node becomes terminated. Note that a node may become active and terminated in one round. In our model, if a node is active in round i and it does not write a message then it must stay active in round i + 1. In other words, once a node raises its hand it cannot "change its mind" later. After the last round, when all nodes are terminated, all of them must be able to answer the question by using only the information stored on the whiteboard.

In this setting, we propose several scenarios leading to the definition of four computational models. A computational model is said simultaneous if all nodes become active (raise their hands) at the beginning of the process. On the other hand, the model is said free if, in every round, any awake node may decide to become active based on its knowledge and on its own protocol. The other criterion we use to distinguish models is the state-transition during which a node must create the message it will eventually write on the whiteboard. In the asynchronous scenario, the nodes must create their message as soon as they become active. In the synchronous scenario, every node is allowed to create its message later, when the adversary chooses it to write the message on the whiteboard. Thus, in the asynchronous case, there may be some delay between the creation of a message and the step when it is written. In particular, the order in which the messages are created and the order in which they are actually available on the whiteboard may differ. In this way, we can model real-world asynchronous systems where there are no guarantees on the time of communications.

Our results. In this work we define four families of systems, namely

SimAsync[f (n)], SimSync[f (n)], FreeAsync[f (n)]
and FreeSync[f (n)], which correspond to the four possible free/simultaneous, asynchronous/synchronous scenarios, parametrized by the amount f (n) of data (in bits) each node is allowed to write on the whiteboard. We show that these classes form a hierarchy from the point of view of message size as well as from the point of view of the synchronization mechanism. More precisely, for any

f (n) = o(n), we show that SimAsync[f (n)] ⊊ SimSync[f (n)] ⊊ FreeAsync[f (n)] ⊆ FreeSync[f (n)]
; the strictness of the last inclusion is left as an open problem. On the other hand, we also prove that when

g(n) = o(f (n)), FreeSync[g(n)] ⊊ SimAsync[f (n)]
. This means that message size and synchronization mechanisms are two orthogonal parameters with respect to the power of each instance of our model. Connectivity problems in general, and breadth-first search (BFS) in particular, are classical problem in distributed computing, and we examine their positions in our hierarchy. We show that BFS is in the class FreeSync[log n], and that for the bipartite case, it is in FreeAsync[log n]. We also show that for all f (n) = o(n), BFS is not in the class SimSync[f (n)] even in the bipartite case.

Related work.

The two main aspects of our approach, the locality and the fact that the nodes are allowed to send only one short message have been tackled before. In the classical model CON GEST [START_REF] Peleg | Distributed computing: a locality-sensitive approach[END_REF], where a network is represented by a graph whose nodes correspond to network processors and edges to inter-processor links, the n processors can send in each round a message of size O(log n) bits through each of its outgoing links. A restriction of the CON GEST model has been proposed by Grumbach and Wu to study frugal computation [START_REF] Grumbach | Logical locality entails frugal distributed computation over graphs[END_REF]. In this model, where the total amount of information traversing each link is bounded by O(log n) bits, they showed that any first order logic formula can be evaluated in any planar or bounded degree network [START_REF] Grumbach | Logical locality entails frugal distributed computation over graphs[END_REF]. Many variations to the CON GEST model have been proposed in order to focus on different aspects of distributed computing. In a seminal paper, Linial introduced the LOCAL model [START_REF]Locality in distributed graph algorithms[END_REF][START_REF] Peleg | Distributed computing: a locality-sensitive approach[END_REF]. In the LOCAL model, the restriction on the size of messages is removed so that every vertex is allowed to send unbounded size messages in every round. This model fo-cuses on the issue of locality in distributed systems, and more precisely on the question "What cannot be computed locally? " [START_REF] Kuhn | What cannot be computed locally![END_REF]. Difficult problems like minimum vertex cover and minimum dominating set cannot be well approximated when processors can locally exchange arbitrary long messages during a bounded number of rounds [START_REF] Kuhn | What cannot be computed locally![END_REF].

The idea of abstracting away from the cost of transmitting data throughout the network and to look at how much local information must be shared in order to compute some property is present in the the Simultaneous Message Model defined in [START_REF] Babai | Communication complexity of simultaneous messages[END_REF]. In such model the communication is global: n players must evaluate a function f (x1, . . . , xn) in which player i knows the whole input except xi. Each player directly transmits one message to a central authority, the referee, that collects and uses them in order to compute f (x1, . . . , xn). The Simulateouus Message Model is a variant of the more general Multiparty Communication model, where the n players communicate by writing messages on a common whiteboard [START_REF] Chandra | Multi-party protocols[END_REF].

COMMUNICATION MODELS

Our protocols work on simple undirected connected nnode graphs. In G = (V, E), each node v ∈ V has a unique identifier ID(v) between 1 and n. Typically, V = {v1, . . . , vn}, where vi is such that ID(vi) = i. Throughout the paper, a graph should be understood as a labeled graph. At each node v ∈ V there is an independent processing unit that knows its own identifier, the identifier of each of its neighbors and the total number of nodes n. Each node is in one of three states: awake, active or terminated. Initially, they are all awake.

All nodes execute the same algorithm. Roughly, if they are in the awake state, they must decide whether to become active, and if they are active, what to write on the whiteboard. Each node is allowed to write exactly one message on the whiteboard. Once they write the message they enter the terminated state. The size of these messages, in bits, is some

f (n) = o(n), typically O(log n).
Let Wn,s be the set of possible configurations of the whiteboard with at most n messages of size at most s bits each.

We first define synchronous protocols, then asynchronous protocols. Synchronous protocols rely on some external synchronization primitives to ensure that messages are delivered one by one, whereas asynchronous protocols have to deal with concurrent messages, which means that messages are created as soon as the nodes become active. We also distinguish between simultaneous and free protocols. In simultaneous protocols, nodes must be ready to speak at any time, whereas in free protocols, they can decide when to become active. We get the following four family of models, with f (n) representing the message size:

message
• actn: [1, n] × 2 [1,n] × W n,f (n) → {awake, active} is
the activation function, which depending on the node's identifier, its neighborhood and the contents of the whiteboard decides whether to become active or stay awake.

• msgn: [1, n] × 2 [1,n] × W n,f (n) → {0, 1} f (n)
is the message function, which depending on the node's identifier, its neighborhood and the contents of the whiteboard decides what to write on the whiteboard.

• outn: W n,f (n) → O is the output function.
Let FreeSync[f (n)] be the set of all synchronous protocols with message size at most O(f (n)). A configuration of a protocol corresponds to a configuration of the whiteboard in W n,f (n) together with a state in {awake, active, terminated} n (which must be interpreted as the state of each node). In the initial configuration, all nodes are awake and the whiteboard is empty.

A round corresponds to an observable transition of the protocol, which in practice occurs when a message is written on the whiteboard. In a round, awake nodes may decide to become active and one active node will write its message.

Definition 2. Consider the synchronous protocol

A = (actn, msgn, outn). Let G = (V, E) be an n-node graph. A round goes from configuration C to configuration C ′ if: • Any terminated node in C is also terminated in C ′ . • For any node vi ∈ V which is awake in C, its state in C ′ is actn(i, N (vi), WC )
, where N (vi) is the set of identifiers of vi's neighbors and WC is the content of the whiteboard in configuration C.

• The configuration of the whiteboard W C ′ is the same as WC but where the message msgn(j, N (vj), WC ) is attached provided that there exists at least one active node vj in C. In C ′ the node vj enters the terminated state. Every other active node stays active.

Definition 3. An execution of a protocol A is a (finite) sequence of configurations starting from the initial configuration where transitions are determined by rounds. The execution is successful if in the last configuration, all nodes are terminated. We say that the execution ends in a deadlock when we end up in a situation where there are no active nodes but the set of awake nodes is not empty. For a successful execution, where the last whiteboard configuration is W , we define the output to be outn(W ). Definition 4. For a function Fn defined from the set of n-node graphs to an output set O, we say that A computes Fn if for all G, all maximal executions of A are successful and output Fn(G). Therefore, we can assume that there is an adversary that chooses in each round which active node writes a message on the whiteboard. Definition 5. A protocol is simultaneous if all nodes are active from the beginning (the activation function is uniformly active). We note SimSync[f (n)] the set of simultaneous protocols. In this subclass of protocols there will never be deadlocks.

Asynchronous protocols

In asynchronous protocols nodes create their messages as soon as they become active. Therefore, if two nodes become active simultaneously, then the first message written on the whiteboard does not affect the second message. Definition 6. Let n be a positive integer. Let [1, n] = {1, . . . , n}. An asynchronous protocol with output set O and message size f (n) is a pair A = (act/msgn, outn) where:

• act/msgn: [1, n] × 2 [1,n] × W n,f (n) → {awake, active} × {0, 1} f (n)
is the activation/message function. Note that this transition is such that a (nonempty) message is created only when the node enters the active state.

• outn: W n,f (n) → O is the output function.
Let FreeAsync[f (n)] be the set of asynchronous protocols with message size O(f (n)).

The definition of configuration is similar to the synchronous case, except that since active nodes create their messages (following the act/msg function) before being chosen by the adversary for writing on the whiteboard (eventually), these messages are part of the configuration, despite the fact that they do not appear on the whiteboard.

We define rounds, executions, deadlocks, successful executions and computations as in the synchronous case. We also define the set SimAsync[f (n)] of simultaneous asynchronous protocols.

This paper aims at deciding what kind of problems can be solved in each of these models. For instance, [START_REF] Becker | Adding a referee to an interconnection network: What can(not) be computed in one round[END_REF] proves that deciding if a graph has degeneracy k, k ≥ 1, can be solved in SimAsync[log n]. On the negative side, deciding whether a graph contains a triangle as a subgraph and deciding whether a graph has diameter at most 3 cannot be solved in SimAsync[log n] [2].

A COMPUTING POWER LATTICE

First of all, we prove the following lemma that extends a result of [START_REF] Becker | Adding a referee to an interconnection network: What can(not) be computed in one round[END_REF]. Let BUILD be the problem that consists in computing the adjacency matrix of a graph.

Lemma 1. Let G be a family of n-node graphs, and g(n) be the number of graphs in G. Let f (n) = o(n), and C ∈ {SimAsync, SimSync, FreeAsync, FreeSync}. If the problem BUILD, when the input graphs are restricted to the class G, can be solved in the model

C[f (n)] then log g(n) = O(n(f (n) + log n)).
Proof. Consider any algorithm in one of the four considered models. In any model, at the end of the communication process, n messages of size O(f (n)) bits are written on B. Hence, at the end, accounting for the order of the messages, a total of O(nf (n) + log n) bits are available on the whiteboard. For the output function to distinguish two different graphs in G, we must have log g

(n) = O(n(f (n)+log n)).
For the ease of descriptions, in what follows we will not define explicitly the functions for activation, message creation and decision. Nevertheless, they always will be clear from the context.

In this section we intend to show that these models form a lattice in which the computational power grows strictly whenever either the syncronization model is enriched or the message size is increased. On the other hand, when one resource is increased but the other restricted then the resulting class is incomparable with the original. (neither is included in the other) The main result of this section is the following theorem:

Theorem 1. For all Ω(log n) = f (n) = o(n), SimAsync[f (n)] ⊊ SimSync[f (n)] ⊊ FreeAsync[f (n)] ⊆ FreeSync[f (n)].
We start with the following weaker result:

Lemma 2. For all f (n), SimAsync[f (n)] ⊆ SimSync[f (n)] ⊆ FreeAsync[f (n)] ⊆ FreeSync[f (n)]. Proof. SimAsync[f (n)] ⊆ SimSync[f (n)].
In the Sim-Sync model, any node applies directly the protocol of the SimAsync model. Nodes create their message initially, ignoring the messages present on the whiteboard when they write their own.

SimSync[f (n)] ⊆ FreeAsync[f (n)].
Recall that a problem is solved in the SimSync model if the nodes compute the output no matter the order chosen by the adversary. So we can translate a SimSync protocol into a FreeAsync one if we fix an order (for instance v1, . . . , vn) and use this order for a sequential activation of the nodes.

FreeAsync[f (n)] ⊆ FreeSync[f (n)].
The situation is that of the first inclusion. It suffices to force the protocols in FreeSync to create their messages based only on what was known at the moment when they became active.

SimAsync vs. SimSync

We consider here a "rooted" version of the Inclusion Maximal Independent Set problem. This problem, denoted by MIS(x), takes as input an n-node graph G = (V, E) together with an identifier ID(x), x ∈ V , and the desired output is any maximal (by inclusion) independent set containing x. Proof. Recall that in the SimSync model, all nodes are initially active and that the adversary chooses the ordering in which the nodes write their messages. Hence, an algorithm in this model must specify the message created by a node v, according to the local knowledge of v and the messages written on the whiteboard before v is chosen by the adversary.

The protocol is trivial (it is the greedy one). When node v is chosen by the adversary, the message of v is either its own ID (meaning that v belongs to the final independent set) or v writes "no" (otherwise). The choice of the message is done as follows. The message is

ID(v) either if v = x or if v / ∈ N (x)
and ID(y) does not appear on the whiteboard for any y ∈ N (v). Otherwise, the message of v is "no".

Clearly, at the end, the set of vertices with their IDs on the whiteboard consists of an inclusion maximal independent set containing x.

Theorem 3. For any f (n) = o(n), MIS(x) cannot be solved in the SimAsync[f (n)] model. Proof. Let f (n) = o(n).
We proceed by contradiction. Let us assume that there exists a protocol A for solving MIS(x) in the SimAsync[f (n)] model. Then we show how to design an algorithm A ′ to solve the BUILD Problem for any graph in this model, contradicting Lemma 1.

Let G = (V, E) be a graph with V = {v1, . . . , vn}. For any 1 ≤ i < j ≤ n, let G (x) i,j be obtained from G by adding a vertex x adjacent to every vertex in V with the exception of vi and vj. Note that {x, vi, vj} is the only inclusion maximal independent set containing x in G (x) i,j if and only if {vi, vj} / ∈ E. Indeed, if {vi, vj} ∈ E, there are two inclusion maximal independent sets containing x: {x, vi} and {x, vj}.

Recall that, in the SimAsync model, all nodes must create their message initially, i.e., while the whiteboard is still empty. Hence, the message created by a node only depends on its local knowledge Notice that, for a given k, the node v k only sees two different neighborhoods for all the possible G (x) ∈ E, the results follows. This would mean that from O(nf (n)) bits we can solve BUILD in the class of all graphs, a contradiction.

Corollary 1. For all Ω(log n) = f (n) = o(n), SimAsync[f (n)] ⊊ SimSync[f (n)].
We discuss now another problem that could possibly separate the two models. Given an (n-1)-regular 2n-node graph G, the 2-Cliques problem consists in deciding whether G is the disjoint union of two complete graphs with n vertices.

It is easy to show that 2-Cliques can be solved in the SimSync[log n] model. Indeed, a trivial protocol can partition the vertices into two cliques numbered 0 and 1 if the input consists of two cliques, or otherwise indicate that it is not the case. The first vertex u to be chosen by the adversary writes (ID(u), 0) on B. Then, each time a vertex v is chosen, it writes (ID(v), 0) if it "believes" to be in the same clique as u, and (ID(v), 1) otherwise. More precisely, let Sv be the subset of neighbors of v that have already written a message on the whiteboard. If Sv = ∅ then v writes 1. If all nodes in Sv have written that they belong to the the same clique c ∈ {0, 1} then v writes c, and v writes "no" otherwise. Clearly, G is the disjoint union of two cliques if and only if there is no message "no" on the whiteboard at the end of the communication process.

Proving that the problem 2-Cliques cannot be solved in the SimAsync[f (n)] model (either for f (n) = log n or for any other f (n)) is an interesting question because it would allow us to show that Connectivity (deciding whether a graph is connected or not) cannot be solved in the SimAsync model. Indeed, it is easy to show that an (n -1) regular 2n-node graph is the disjoint union of two cliques if and only if it is not connected. We leave this as an open question:

Open Problem 1. For which f (n) can 2-Cliques be solved in the SimAsync[f (n)] model? 3.2 SimSync vs. FreeAsync
We say that a graph is even-odd-bipartite if there are no edges between nodes having identifiers with the same parity. For separating models SimSync and FreeAsync, the problem we are going to introduce is EOB-BFS. In this problem, the input is an arbitrary n-node graph G and the output is a BFS-tree (or BFS-forest) if G is even-odd bipartite, and a negative answer otherwise. The root of the BFS-tree in each connected component of G will be the node with the smallest identifier in the respective component. Proof. Let G be the input graph. All nodes detecting that they have a neighbor with the same parity become active and create a message saying that this is an "invalid" graph. So we are going to define our algorithm assuming that G is indeed even-odd-bipartite.

The protocol will activate the nodes layer by layer in the BFS-forest. The first node to become active is v1, then all its neighbors, then all nodes at distance 2, and so on. When all nodes in layer k have written their messages, then the information appearing in the whiteboard will be sufficient to compute the number of edges crossing between layer k and layer k + 1 (if such number is 0 then that would mean that another connected component must be activated).

Initially, only v1 is active. Let N * v be the set of neighbors of v that have already written a message on the whiteboard. When node v becomes active it creates the message (i(v), l(v), p(v), d-1(v), d+1(v)) where:

i(v) is its ID l(v) = minw∈N * v l(w) + 1 p(v) is the node in N * v with minimum ID, or root if N * v is empty d-1(v) = |N * v | d+1(v) = d(v) -|N * v |, with d(v)
its degree l(v) represents the level of v, d-1(v) its degree towards the previous level, d+1(v) its degree towards the next level and p(v) its parent in the BFS-forest. The message created by v1 at the beginning is (1, 0, root, 0, d(v1)). Since v1 is the only active node the adversary is forced to choose it and v1 writes its message on the whiteboard. Then all the neighbors of v1 become active and, since we want all nodes of the same layer to become active simultaneously, the protocol works as follows. An arbitrary node v becomes active (and computes its message) if the next two conditions are satisfied:

1. A neighbor w of v has already written its message on the whiteboard.

2. Σu∈L l(w) d-1(u) = Σu∈L l(w)-1 d+1(u), where L k is the set of nodes in layer k that have already written a message.

The key argument is to see that the second condition for activation ensures that all edges from layer k -1 to layer k have been written their messages before layer k + 1 is activated.

Previous protocol works correctly if the graph has only one connected component. In order to avoid any deadlock we have to add another condition for becoming activated. The idea is to verify that a component has already been covered. More precisely, v becomes activated if the last message was written by a non-neighbor node w of v and the following three conditions are satisfied:

1. Σu∈L l(w) d+1(u) = 0. 2. Σu∈L l(w) d-1(u) = Σu∈L l(w)-1 d+1(u).
3. The ID of v is the minimum among the nodes that have not written a message yet.

These condition ensure that when the active connected component changes, exactly one node is activated. In the end, the output function corresponds to the forest indicated by the p(v) from each message.

Theorem 5. For any f (n) = o(n), EOB-BFS cannot be solved in the SimSync[f (n)] model.
Proof. We proceed by contradiction. Let us assume that there exists a protocol A for solving EOB-BFS in SimSync[f (n)] for some f (n) = o(n). The idea is to construct a protocol A ′ for solving the BUILD problem for even-odd-bipartite graphs in SimAsync[f (n)], in contradiction with Lemma 1. Note that there are 2 O(n 2 ) even-oddbipartite graphs with n vertices.

Let G = (V, E) be an even-odd-bipartite graph with V = {v1, . . . , vn-1}. Assume (w.l.o.g) that n is odd, and renumber the vertices so that V = {v2, . . . , vn}.

Let V ′ = {v1, vn+1, vn+2, . . . , v2n-1}. Let 3 ≤ i ≤ n odd. We are going to define the auxiliar even-odd-bipartite graph Gi = (V ∪ V ′ , E ∪ Ei) where the edges Ei are defined as follows: connect v1 with vi+n-2, vj with vj+n-2 for every 3 ≤ j ≤ n odd and vj with vj+n for every 2 ≤ j ≤ n -1 even.

Suppose now that we run A on Gi. A node vj is at level 3 of the BFS-tree rooted in v1 if and only if vi and vj are neighbors in G. Thus, if we simulate A on every Gi (i.e., for all 3 ≤ i ≤ n odd) at once, then we would solve BUILD in SimSync[f (n)].

Note that if we run A on each of the Gi's with the nodes activated in order (v2, v3, . . . , v2n-1, v1) then the messages written by the nodes in V = {v2, . . . , vn} will not depend on the choice of i. In fact, the neighbourhood of all of these nodes is the same in every Gi, and their messages can only depend on such neighborhoods and the previous messages.

We then define A ′ to be the protocol in which each node in G sends the message it would send in any of the Gi's when running A. Once all these messages have been collected, A ′ simulates A for every Gi in order to compute the neighbourhood of vi. Thus, EOB-BFS is not in FreeAsync

[f (n)]. Corollary 2. For all Ω(log n) = f (n) = o(n), SimSync[f (n)] ⊊ FreeAsync[f (n)].

Message size

Obviously, by increasing the size of the messages we make the system more powerful. What is more interesting is that this resource is orthogonal (independent) to the synchronization power. We have already seen in previous section that MIS

(x) ∈ SimSync[log n] but MIS(x) / ∈ SimAsync[o(n)].
In other words, there are problems that can not be solved if we go down in the sinchronization hierarchy no matter the extra length given to the size of the messages. Now we are going to prove a more general result. Theorem 6. Let f (n) = o(n). subgraph f is the problem where the input is an n-node graph G = (V, E) and the output is the subgraph obtained by removing all edges between nodes in {v f

(n)+1 , . . . , vn} ⊆ V . Let g(n) = o(f (n)). It fol- lows that subgraph f ∈ SimAsync[f (n)] but subgraph f / ∈ FreeSync[g(n)]. Proof. It is obvious that subgraph f ∈ SimAsync[f (n)].
In fact, each node sends a vector consisting of the f (n) first bits of its line in the adjacency matrix of the graph. Let

g(n) = o(f (n)). subgraph f cannot be in FreeSync[g(n)],
since that would allow us to solve BUILD for graphs of size n where {v f (n+1) , . . . , vn} are isolated nodes. This contradicts Lemma 1 because these graphs need 2 O(nf (n)) bits to be defined.

CONNECTIVITY AND RELATED PROB-LEMS

One of the main questions arising in distributed environments concerns connectivity. For instance, one important task in wireless networks consists in computing a connected spanning subgraph (e.g., a spanning tree) since the links of such subgraph are used for communication.

In Section 3 we proved that, in the FreeAsync[log n] model, it is possible to compute a BFS-forest for even-oddbipartite graphs (i.e., bipartite graphs where the bipartition is fully known to every node). In such model it is in fact possible to get a protocol which outputs a BFS-forest for all bipartite graphs without knowledge of the bipartition. In the case of a non-bipartite graph though, running this protocol can result in a deadlock: at some point, no more nodes are activated. With synchronzation, as we are going to see in the next theorem, we do not need the graph to be bipartite and BFS can be solved in the general case, for arbitrary input graphs. Formally, the input of problem BFS is an arbitrary n-node graph G and the output is a BFS-tree (or BFS-forest). The root of the BFS-tree in each connected component of G will be the node with the smallest identifier in the respective component. Proof. The protocol is very similar to the one we used for EOB-BFS, but we need to keep track of edges within a level (these edges do not exist in the bipartite case).

Initially, only v1 is active. Let N * v be the set of neighbors of v that have already written a message on the whiteboard. When node v becomes active it creates the message (i(v), l(v), p(v), d-1(v), d0(v), d+1(v)) where: where L k is the set of nodes in layer k that have already written a message on the whiteboard.

3. v is the node with the smallest ID that has not written a message on the whiteboard, the last message was written by a non-neighbor w, ∑ Condition 2, by counting the edges crossing from layer l(v) -1 to layer l(v) -2, ensures that all the nodes in layer l(v) -1 have sent their messages and the nodes of layer l(v) may become active. Condition 3 ensures that, when the active connected component changes (because there are no edges "going outside" the last layer), exactly one node is activated.

Corollary 3. There exists a protocol in FreeAsync[log] which, on any bipartite graph G, outputs a BFS-forest of G.

Proof. In a bipartite graph there are no edges between nodes in the same layer. In other words, we need to apply the protocol for the general case without computing d0(v). Thanks to this, all the information the nodes in layer k need to compute is available when k is activated.

Open Problem 2. Is it possible to solve Spanning-Tree or even Connectivity in the FreeAsync[f (n)] model? For which f (n)?

Open Problem 3. Is it true that for all (or some) f (n), FreeAsync[f (n)] ⊊ FreeSync[f (n)]? We conjecture that this is the case and that in fact BFS cannot be solved in the FreeAsync[f (n)] model for f = o(n).

Theorem 2 .

 2 MIS(x) can be solved in the SimSync[log n]model.

Theorem 4 .

 4 The problem EOB-BFS can be solved in the FreeAsync[log n] model.

Theorem 7 .

 7 BFS can be solved in the FreeSync[log n] model.

  l(v) = minw∈N * v l(w) + 1 p(v) is the node in N * v with minimum ID, or root if N * v is empty d-1(v) = |{w ∈ N * v : l(w) = l(v) -1}| d0(v) = |{w ∈ N * v : l(w) = l(v)}| d+1(v) = d(v) -d-1(v), with d(v) its degreeConsider nodes v at distance al least 2 from the root. These nodes v become active if the condition (1 ∧ 2) ∨ 3 is satisfied, where 1. A neighbor w of v has already written its message on the whiteboard

  {1, . . . , n}. A synchronous protocol with output set O and message size f (n) is a triplet A = (actn, msgn, outn) where:

		2.1 Synchronous protocols
		created when
		node becomes active
	all nodes initially active	SimAsync[f (n)]
	no node initially active	FreeAsync[f (n)]
		message created when
		node is chosen
	all nodes initially active	SimSync[f (n)]
	no node initially active	FreeSync[f (n)]

Definition 1. Let n be a positive integer. Let [1, n] =

  i,j , depending on whether k ∈ {i, j} or k / ∈ {i, j}. Therefore, we call m k the message that v k generates when k ∈ {i, j} (i.e., x and v k are not neighbors) and m ′ k the message v k generates when k / ∈ {i, j} (i.e., x and v k are neighbors). From the previous protocol A we are going to define another protocol A ′ in the SimAsync[f (n)] model which solves the BUILD Problem for any graph. Protocol A ′ works as follows. Every node v k generates the pair (m k , m ′ k ) of the two messages v k would send in A when it is adjacent to x and when it is not. Clearly, this consists of O(f (n)) bits. Now let us prove that any node can reconstruct G = (V, E) from the messages generated by A ′ . More precisely, for any 1 ≤ s < t ≤ n, any node can decide whether {vs, vt} ∈ E or not. It is enough for any node to simulate de decision function of A in G

	ms, mt and {m ′	(x) s,t by using messages

k : k ∈ {1, • • • , n} \ {s, t}}. Since the output of A is {x, vs,

vt} if and only if {vs, vt} /

ACKNOWLEDGMENTS

Partially supported by programs Fondap and Basal-CMM (I.R., K.S.), Fondecyt 1090156 (I.R.), Anillo ACT88 (K.S.), Fondecyt 11090390 (K.S) and FP7 STREP EULER (N.N.).


F V Fomin

F Giroire

A Jean-Marie

D Mazauric

N Nisse

To Satisfy Impatient Web surfers is Hard

Keywords: Prefetching, Cops and robber games, PSPACE-complete

Prefetching is a basic mechanism for faster data access and efficient computing. An important issue in prefetching is the tradeoff between the amount of network's resources wasted by the prefetching and the gain of time. For instance, in the Web, browsers may download documents in advance while a Web surfer is surfing on the Web. Since the Web surfer follows the hyperlinks in an unpredictable way, the choice of the Web pages to be prefetched must be computed online. The question is then to determine the minimum amount of resources used by prefetching that ensures that all documents accessed by the Web surfer have previously been loaded in the cache.

We model this problem as a two-players game similar to Cops and Robber Games in graphs. The first player, a fugitive, starts on a marked vertex of a (di)graph G. The second player, an observer, marks k ≥ 1 vertices, then the fugitive moves along one edge/arc of G to a new vertex, then the observer marks k vertices, etc. The observer wins if he prevents the fugitive to reach an unmarked vertex. The fugitive wins otherwise, i.e., if she succeed to enter an unmarked vertex. The surveillance number of a (di)graph is the minimum k ≥ 1 allowing the observer to win against any strategy of the fugitive.

We study the computational complexity of the game. We show that deciding whether the surveillance number of a chordal graph equals 2 is NPhard. Deciding if the surveillance number of a DAG equals 4 is PSPACEcomplete. Moreover, computing the surveillance number is NP-hard in split graphs. On the other hand, we provide polynomial time algorithms computing surveillance numbers of trees and interval graphs. Moreover, in the case of trees, we establish a combinatorial characterization, related to isoperimetry, of the surveillance number.

Introduction

Prefetching is a basic technique in computer science. It exploits the parallelism between the execution of one task and the transfer of information Due to lack of space, some proofs have been omitted or sketched, and can be found in [START_REF] Fomin | To satisfy impatient web surfers is hard[END_REF]. This work has been done during the visit of Fedor V. Fomin at the INRIA team-project MASCOTTE, INRIA Sophia-Antipolis, France.

necessary to the next task, in order to reduce waiting times. The classical instance of the problem occurs in CPU, where instructions and data are prefetched from the memory while previous instructions are executed. The modern instance occurs in the Web, where browsers may download documents connected to the currently viewed document (Web page, video, etc.) while it is being read or viewed. Accessing the next document appears to be instantaneous to the user, and gives the impression of a large navigation speed [1]. For this reason, link prefetching has been proposed as a draft Internet standard by Mozilla [START_REF]The economic impacts of unacceptable web-site download speeds[END_REF]. However, prefetching all documents that can be accessed in the current state may exceed networking capacities, or at least, result in a waste of bandwidth since most of the alternatives will not be used. Hence, it is necessary to balance the gain of time against the waste of networking resources. Local storage memory is also a potential issue, and prefetching is classically associated with the question of cache management. However, memory in modern computers is not scarce anymore, which makes network resources the critical ones.

The models developed so far in the literature to study prefetching problems are based on the execution digraph where the nodes represent the tasks (e.g., Web pages) and arcs model the fact that a task can be executed once another has been done (e.g., arcs represent hyperlinks that can be followed from a Web page). The execution of the program or the surfing of the Web then corresponds to a path in the execution digraph. The quantitative optimization of prefetching will then be based on some cost function defined on paths, reflecting for instance the inconvenience of waiting for some information while executing the tasks or surfing the Web, and possibly taking into account the consumption of network or memory resources. The related dimensioning problem consists in determining how much network bandwidth should be available so that the prefetching performance stays within some predetermined range.

It is quite likely that such optimization problems are very difficult to solve exactly. For instance, in Markovian models [START_REF] Joseph | Prefetching using Markov predictors[END_REF], where arcs of the execution digraph are associated with transition probabilities (modeling a random Web surfer), the prefetching problem can then be cast as an optimization problem in the Stochastic Dynamic Programming framework [START_REF] Grigoras | Optimizing hypervideo navigation using a Markov decision process approach[END_REF][START_REF] Morad | Optimisation en temps-réel du téléchargement de vidéos[END_REF]. Its exact solution requires a computational effort which is exponential with respect to the number of nodes in the execution digraph: this is the size of the state space of these Markov Decision models.

As a first step in the analysis of prefetching optimization, we therefore consider the following simpler problem. We consider a surfer evolving over the execution digraph, and we are concerned with perfect prefetching, i.e., ensuring that the Web surfer never accesses an document that has not been prefetched yet. In other words, the surfer is "impatient" in the sense that she does not tolerate waiting for information. Due to network's capacity (bandwidth) limitation, it is important to limit the number of Web pages that can be prefetched at each step. We aim at determining the minimum amount of Web pages to be prefetched at each step. In addition to being simpler than a fully specified optimization problem, this question does not need specific assumptions on the behavior of the Web surfer as in [START_REF] Grigoras | Optimizing hypervideo navigation using a Markov decision process approach[END_REF][START_REF] Morad | Optimisation en temps-réel du téléchargement de vidéos[END_REF].

Given an execution digraph D and a node v 0 ∈ V (D) corresponding to the Web page from which the surfer starts, the surveillance number of D starting in v 0 is the least number of Web pages prefetched at each step that avoid the Web surfer to wait (whatever the surfer does). Our results. We model the above prefetching problem as a Cop and Robber game (e.g., see [START_REF] Fomin | An annotated bibliography on guaranteed graph searching[END_REF][START_REF] Alspach | Searching and sweeping graphs: a brief survey[END_REF]). Using this framework, we prove that deciding whether the surveillance number of a chordal graph equals 2 is NP-hard. Then, we show that computing the surveillance number is NPhard in split graphs, a subclass of chordal graphs. In the case of digraphs, we show that deciding if the surveillance number of a DAG equals 4 is PSPACE-complete. On the other hand, we provide polynomial time algorithms that compute the surveillance number and a corresponding optimal strategy in trees and interval graphs. Moreover, in the case of trees, we establish a combinatorial characterization, related to isoperimetry, of the surveillance number. That is, we show that the surveillance number of a tree T starting in v 0 ∈ V (T ) equals max S

|N [S]|-1 |S|

where S is taken among all subtrees of T containing v 0 and N [S] denotes the closed neighborhood of S. We conclude with several open questions.

Preliminaries

For any (di)graph G = (V, E) considered in this paper, when v 0 ∈ V is fixed as the starting vertex, we assume that, for any v ∈ V , there is a (directed) path from v 0 to v. In particular, if G is an undirected graph, we assume that G is connected.

For S ⊆ V , let G[S]

The Surveillance Game

The surveillance problem deals with the following two players game in an n-node (di)graph G = (V, E) with a given starting vertex v 0 ∈ V . There are two players, fugitive and observer. The fugitive wants to escape the control of an observer whose purpose is to keep the fugitive under constant surveillance. Let k ≥ 1 be a fixed integer. The game starts when the fugitive stands at v 0 which is initially marked. Then, turn by turn, the observer controls, or marks, at most k vertices and then the fugitive either moves along an edge to a (out-)neighbor of her current position, or skip her move. In other words, at every step of the game the observer enlarges observable part of the graph by adding to it k, not necessarily adjacent, vertices. His task is to ensure that the fugitive is always in the observable area. Note that, once a vertex has been marked, it remains marked until the end of the game. The fugitive wins if, at some step, she reaches an unmarked vertex and the observer wins otherwise. That is, the game ends when either the fugitive enters an unmarked vertex (and then she wins) or all vertices have been marked (and then observer wins).

More formally, a k-strategy (for the observer) is a function σ that assigns a subset S ⊆ V , |S| ≤ k, to any configuration (M, f ) of the game where M ⊆ V is the set of the vertices that have already marked before this step of the game, f ∈ M is the current position of the fugitive, and S = σ(M, f ) is the set of vertices to be marked at this step. Clearly, we can restrict our investigation to the case where σ(M, f

) ⊂ V \ M and |σ(M, f )| = k or σ(M, f ) = V \ M .
That is, at each step, the observer has interest to mark as many unmarked vertices as possible. In particular, a game consists of at most n/k steps. A k-strategy is winning if it allows the observer to win whatever be the walk followed by the fugitive. Note that any winning strategy must ensure that N (f ) \ M ⊆ σ(M, f ) for any M ⊆ V , f ∈ M . The surveillance number of G, denoted by sn(G, v 0 ), is the least k such that there is a winning k-strategy in G starting from v 0 .

Restriction to induced paths

We define a restriction of the game that will be useful throughout this paper. In the monotone variant of the surveillance game, the fugitive is restricted to move at every step and to follow only induced paths in G. That is, for any > 0, after having followed a path

(v 0 , • • • , v ), the fugitive is not allowed reaching a vertex in N [{v 0 , • • • , v -1 }] anymore.
Let msn(G, v 0 ) be the smallest k such that there is a winning monotone k-strategy in G when the fugitive starts from v 0 . Due to lack of space, the proof of Theorem 1 is omitted and can be found in [START_REF] Fomin | To satisfy impatient web surfers is hard[END_REF].

Theorem 1. For any (di)graph G, v 0 ∈ V (G), sn(G, v 0 ) = msn(G, v 0 ) [3].
In other words, if the fugitive follows induced paths and moves at every step, the observer needs to mark the same amount of vertices at each step as he does when the fugitive has no restriction. This means that in the following proofs, we can always consider that the fugitive obeys these restrictions.

Difficult problems

In this section, we study the computational complexity of the decision version of the problem: given a graph G with v 0 ∈ V (G) and an integer k, the task is to decide whether sn(G, v 0 ) ≤ k. We start with the proof that the problem is NP-hard on chordal graphs. Let us remind that a graph is chordal if it contains no induced cycle of length at least 4.

Theorem 2. Deciding if sn(G, v 0 ) ≤ 2 is NP-hard in chordal graphs.
Proof. We use a reduction from the 3-Hitting Set Problem. In the 3-Hitting Set Problem, we are given a set I of elements, a set S of subsets of size 3 of I and k ∈ N as an input. The question is to decide whether there exists a set H ⊆ I of size at most k such that H ∩S = ∅ for all S ∈ S. The 3-Hitting Set Problem is the classical NP-complete problem [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF].

Let (I = {e 1 , • • • , e n }, S = {S 1 , • • • , S m })
and k ≥ 1 be an instance of the 3-Hitting Set Problem. We construct the chordal graph G as follows. Let P = {v 0 , • • • , v m+k-2 } be a path, K m be the complete graph with vertices {S 1 , • • • , S m } and e 1 , • • • , e n be n isolated vertices. We add an edge from v m+k-2 to all vertices of K m , and for each i ≤ n and j ≤ m, add an edge between e i and S j if and only if e i ∈ S j . Clearly, G is chordal.

First, we show that, if there exists a set H ⊆ I of size k such that H ∩S = ∅ for all S ∈ S, then sn(G, v 0 ) ≤ 2. The 2-strategy of the observer first consists in marking the vertices v 1 to v m+k-2 in order, then the vertices of K m and finally the vertices of H. This can be done in m+k -1 steps and in such a way that, at each step, all neighbors of the current position of the fugitive are marked. Because H is a hitting set of S, after the (m + k -1)-th step, each vertex S i , i ≤ m, has at most two unmarked neighbors, all other vertices have all their neighbors marked and only some vertices in e 1 , . . . , e n can be unmarked. Finally, from this step, the strategy of the observer consists in marking the unmarked neighbors of the current position of the fugitive. Clearly, the fugitive cannot win and, thus, there exists a winning 2-strategy. Now, assume that, for any H ⊆ I of size at most k, there is S ∈ S such that S ∩ H = ∅. The escape strategy for the fugitive first consists in going to v m+k-2 (this takes m+k-2 steps). Then, after the (m+k-1)-th step of the observer, all vertices of P and K m are marked-otherwise the fugitive either would have won earlier, or manage to reach a vertex of K m that is still unmarked. It means that the subset H of vertices among e 1 , • • • , e n that are marked at this step is of size at most k. Hence, when it is the turn of the fugitive who is occupying vertex v m+k-2 , there is S i ∈ V (K m ) with H ∩ S i = ∅, i.e., all three neighbors of S i are unmarked. Then, the fugitive goes to S i . The observer marks at most 2 of the neighbors of S i , and the fugitive can reach an unmarked vertex. Hence, sn(G, v 0 ) > 2.

The proof of the next Theorem is similar to the previous one. It is omitted due to lack of space and can be found in [START_REF] Fomin | To satisfy impatient web surfers is hard[END_REF]. A graph G = (V, E) is a split graph if there is a partition (A, B) of V such that A induces a clique and B induces an independent set. A split graph is chordal.

Theorem 3. The problem of deciding whether sn(G, v 0 ) ≤ k is NP-hard in split graphs (k is part of the input). Moreover, in this class of graphs, the game consists of at most 2 steps [START_REF] Fomin | To satisfy impatient web surfers is hard[END_REF].

For a set of boolean variables x 0 , y 0 , x 1 , y 1 , • • • , x n , y n and a boolean formula

F = C 1 ∧• • •∧C m , (C j is a 3-clause)
, the 3-QSAT problem aims at deciding whether the expression Φ = ∀x 0 ∃y 0 ∀x 1 ∃y 1 • • • ∀x n ∃y n F is true. 3-QSAT is PSPACE-complete [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]. Due to lack of space, we sketch the proof of next theorem. The proof of Theorem 4 can be found in [START_REF] Fomin | To satisfy impatient web surfers is hard[END_REF].

Theorem 4. The problem of deciding whether sn(G, v 0 ) ≤ 4 is PSPACEcomplete in Directed Acyclic Graphs [START_REF] Fomin | To satisfy impatient web surfers is hard[END_REF].

Sketch of the Proof. Let F = C 1 ∧ • • • ∧ C m be
a boolean formula with variables x 0 , y 0 , x 1 , y 1 , • • • , x n , y n and Φ = ∀x 0 ∃y 0 ∀x 1 ∃y 1 • • • ∀x n ∃y n F be an instance of the 3-QSAT Problem. Let D be the DAG built as follows.

We start with the set of vertices {u i , v i , x i , x i , x i , xi , y i , ȳ i , y i , ȳi } 0≤i≤n . For any 0 ≤ i ≤ n, there are arcs from v i to x i and x i , one arc from x i to x i and one arc from x i to xi . For any 0 ≤ i ≤ n, there are arcs from x i and x i to u i , arcs from u i to both y i and ȳ i and arcs from both of y i and ȳ i to both of y i and ȳi . Then, for any 0 ≤ i < n, there is one arc from u i to v i+1 . Add the directed path (w 1 , • • • , w m-1 ) with one arc from u n to w 1 and such that w m-1 has m out-neighbors C 1 , • • • , C m . For any j ≤ m and 0 ≤ i ≤ n, add one arc from C j to x i (resp., xi , y i , ȳi ) if x i (resp., xi , y i , ȳi ) appears in the clause C j . Finally, for any 0 j ≤ m add two out-neighbors leaves to each vertex in {v i , x i , x i , w k , C j }, and, for any 0 ≤ i ≤ n, add three out-neighbors leaves to each of y i and ȳ i . An example of such DAG is depicted in Figure 1.

≤ i ≤ n, k ≤ m -1,
Since |N + (v 0 )| = 4, sn(D, v 0 ) ≥ 4 and the first step of the observer, allowed to mark 4 vertices per step, consists in marking the 4 out-neighbors of v 0 . We sketch the proof that sn(D, v 0 ) = 4 if and only if Φ is true.

In [START_REF] Fomin | To satisfy impatient web surfers is hard[END_REF], we show that the only way for the fugitive to win against an observer who can mark 4 vertices at each step is by following the path

P = (v 0 , f 0 , u 0 , • • • , v i , f i , u i , • • • , v n , f n , u n , w 1 , w 2 , • • • , w m-1 )
, where f i ∈ {x i , x i } for any 0 ≤ i ≤ n. Moreover, during this game, the observer must have marked a i where a i = x i if f i = x i and a i = xi if f i = x i (otherwise the fugitive would have won before by going to a i ). On the other hand, we prove that, during the game, the observer can have marked exactly one vertex b i in {y i , ȳi }. Finally, after the (3n + m)-th step of the observer, the fugitive stands on w m-1 , all vertices in H = {C 1 , • • • , C m } are marked while the set of marked vertices in the out-neighbors of H is exactly {a 0 ; b 0 , • • • , a n , b n }. Now, if Φ is false, by the choice of the a i 's by the fugitive, there is a clause C j with its 5 out-neighbors unmarked: the fugitive goes to C j and will win at the next step. On the other hand, if Φ is true, by the choice of the b i 's by the observer, all C j 's have at most 4 unmarked out-neighbors. Whatever be the next moves of the fugitive, she will reach a marked vertex without out-neighbors.

Hence, deciding whether sn(G, v 0 ) ≤ 4 is PSPACE-hard in DAGs. The proof that this problem is in PSPACE can be found in [START_REF] Fomin | To satisfy impatient web surfers is hard[END_REF].

The following theorem provides an exponential algorithm computing sn(G, v 0 ). Here, we use a modified big-Oh notation that suppresses all polynomially bounded factors. For functions f and g we write

f (n) = O * (g(n)) if f (n) = O(g(n)poly(n))
, where poly(n) is a polynomial. Proof. For each k ≥ 1, we decide if sn(G, v 0 ) ≤ k. We consider the arena digraph G whose vertices are configurations of the game, i.e., the pairs (M, f ) where

v 0 , f ∈ M ⊆ V (G), N [f ] ⊆ M and |M \ {v 0 }| = ki for some i > 0 (or M = V (G)). Moreover, there is an arc from (M, f ) to (M , f ) if f ∈ N (f ) and M ⊂ M and |M | = |M | + k (or |V (G) \ M | ≤ k and M = V (G)). Note that |V (G)| ≤ n n-1 k i=1 n ki+1 ≤ 2 n n and that the amount of arcs in G is O * (2 n ).
We consider the following labelling process. Initially, all configurations (V (G), v), for any v ∈ V (G), are labeled with n-1 k , and all other configurations are labeled with ∞. Iteratively, a configuration (M, f ) with

|M | = ki + 1 is labeled i if, for any f ∈ N G (f ), then f ∈ M
and there is an out-neighbor (M , f ) of (M, f ) and that is labeled at most i + 1. We show that sn(G, v 0 ) ≤ k if and only if there is a configuration (M, v 0 ),

|M | = k + 1, labeled with 1.
We first show by induction on i, that the observer can win starting from any configuration labeled with n-1 k -i. If i = 0, the result holds trivially. Assume that the result holds for n-1 k -1 > i > 0. Let (M, f ) be a configuration labeled with n-1 k -(i + 1). For any f ∈ N (f ), by definition of the labelling process, there is a configuration (M , f ) outneighbor of (M, f ) and labeled with n-1 k -i. If the fugitive goes from f to f , then the observer marks the vertices in M \ M and the game reaches the configuration (M , f ). Hence, by the induction hypothesis, the observer wins. So, applying the result for i = n-1 k -1, the observer wins starting from any configuration (M, v 0 ), |M | = k + 1, labeled 1. To reach this configuration, the first step of the observer is to mark the k vertices in M \ {v 0 }. Therefore, sn(G, v 0 ) ≤ k. Now assume that sn(G, v 0 ) ≤ k. Let σ be a winning k-strategy for the observer. For any walk W = (v 0 , v 1 , • • • , v i ) followed by the fugitive, let M (W ) be the set of vertices marked by the observer (using σ) after the fugitive has followed W until v i and when it is the turn of the fugitive. By reverse induction on i, the labelling process labels (M (W ), v i ) with i + 1. This shows that ({v 0 } ∪ σ({v 0 }, v 0 ), v 0 ) is labeled with 1.

For each k, the algorithm runs in time proportional to the size of G, i.e. 2 n nk, and thus the total running time of the algorithm is O * (2 n ).

In this section, we give polynomial-time algorithms to compute the surveillance number of trees and interval graphs.

Keeping tree under surveillance

We first present a polynomial-time algorithm to compute sn(T, v 0 ) for any tree T = (V, E) rooted at v 0 ∈ V . Let k ≥ 0. We define the function f k : V (T ) → N in the following recursive way:

-f k (v) = 0 for any leaf v of T ; -for any v ∈ V (T ) with d children, f k (v) = max{0, d+ w∈C f k (w)-k}
where C is the set of children of v.

Lemma 1. Let T be a tree rooted in v 0 , f k (v 0 ) = 0 iff sn(T, v 0 ) ≤ k.
Proof. The result holds if T is reduced to one vertex. So we may assume that T has height at least 1. Recall that the height of T is the maximum length (number of edges) of a path between the root v 0 and a leaf of T . We prove by induction on the height of T that the observer cannot win the game marking at most k vertices per step, even if at most f k (v 0 ) -1 vertices in V (T ) \ {v 0 } are initially marked. Moreover, we prove that the observer can win, marking at most k vertices per step, if at most f k (v 0 ) vertices plus v 0 are initially marked.

If T has height 1 and v 0 has degree d, then f k (v 0 ) = max{0, d -k} and the result holds. Indeed, if v 0 and f k (v 0 ) other vertices are initially marked, then during its first step, the observer marks all remaining ≤ k vertices and wins. On the other hand, if v 0 and at most f k (v 0 ) -1 vertices are marked, then after the first step of the observer (when he has marked k other vertices), at least one neighbor of v 0 is still unmarked and the fugitive can go to it and wins. Now, assume that the result holds for any tree of height h ≥ 1. Let T rooted in v 0 and of height h + 1, we show the result holds.

Let (v 1 , • • • , v r ) be the children of v 0 and let T i be the subtree of T rooted in v i , 1 ≤ i ≤ r. By the induction hypothesis, for any 1 ≤ i ≤ r, there is a set

I i ⊆ V (T i ) \ {v i } of f k (v i )
vertices such that, if the vertices of I i and v i are initially marked in T i , then the observer can win in T i starting from v i , marking at most k vertices per step. On the contrary, if strictly less than f k (v i ) vertices are initially marked in V (T i ) \ {v i }, then the fugitive wins in T i against an observer marking ≤ k vertices per step.

In T , if f k (v 0 ) vertices can be marked initially in V (T ) \ {v 0 }, then a k-strategy consists of the following. The set of vertices that are initially marked union the vertices marked during the first step of the observer is

J = N [v 0 ] ∪ ( 1≤i≤r I i ). It is possible since |J| ≤ 1 + f k (v 0 ) + k.
Then the fugitive moves to some child v i (1 ≤ i ≤ r) of v 0 . Since the vertices of I i and v i are already marked, the observer will win in T i .

On the contrary, if strictly less than f k (v 0 ) vertices can be marked initially in V (T ) \ {v 0 }, then there is at least one child v i (1 ≤ i ≤ r) such that either v i is not marked after the first step of the observer, or at most f k (v i ) -1 vertices in V (T i ) \ {v i } are marked after the first step of the observer. In both cases, the fugitive will win in T i . Theorem 6. For any tree T rooted in v 0 , sn(T, v 0 ) can be computed in time O(n • log n).

We now give a combinatorial characterization of sn(T, v 0 ). Lemma 2. For any tree T rooted in v 0 and k < sn(T, v 0 ), there is S ⊆ V (T ) inducing a subtree of T containing v 0 such that

|N [S]|-1 |S| > k.
Proof. Let k < sn(T, v 0 ). By Lemma 1, f k (v 0 ) > 0. Let S be the inclusionmaximal subtree of T containing v 0 and such that f k (v) > 0 for all vertices in S. We show by induction on the height of

S that f k (v 0 ) = |N [S]| -1 - k|S|. If S = {v 0 } and v 0 has degree d, then f k (v 0 ) = d -k = |N [S]| -1 - k|S| > 0 because for any child v of v 0 , f k (v) = 0.
Assume that the result holds for any subtree of height h ≥ 0 and assume that S has height h+1. Let d be the degree of v 0 and let v 1 , • • • , v r , 1 ≤ r ≤ d, be the children of v 0 with f k (v i ) > 0. Let S i be the subtree of S rooted in v i , 1 ≤ i ≤ r, and let N [S i ] be the vertices of S i or in the neighborhood of S i in the subtree of T rooted in v i . By the induction hypothesis,

f k (v i ) = |N [S i ]| -1 -k|S i | for any 1 ≤ i ≤ r. Now, f k (v 0 ) = d -k + 1≤i≤r f k (v i ) = d -k + 1≤i≤r (|N [S i ]| -1 -k|S i |) = d -k + (|N [S]| -1 -(d -r)) -r -k(|S| -1) = |N [S]| -1 -k|S|.
Lemma 3. For any tree T rooted in v 0 , for any k ≥ sn(T, v 0 ), for any S ⊆ V (T ) inducing a subtree of T containing v 0 , we have

|N [S]|-1 |S| ≤ k.
Proof. We consider the following game. Initially, an unbounded number of fugitives are in v 0 which is initially marked. Then, at most k vertices of T \ {v 0 } are marked. At each turn, each fugitive can move along an edge of the tree, and then, for each vertex v that is reached for the first time by a fugitive, at most k vertices can be marked in T v the subtree of T rooted in v. The fugitives win if at least one fugitive reaches an unmarked vertex, they loose otherwise.

We first show that if k ≥ sn(T, v 0 ) then the fugitives loose in this game. Assume that k ≥ sn(T, v 0 ). Then there is a winning k-strategy σ for the "normal" surveillance game in T starting from v 0 . Recall that by Theorem 1, we can restrict the fugitive to follow an induced path. Since for any t ∈ V (T ), there is a unique induced path from v 0 to t, σ can be defined uniquely by the position of the fugitive. That is, in the case of trees, we can define a k-strategy as a function that assigns a subset σ(t) ⊆ V (T t ) (of size at most k) to any vertex t ∈ V (T ). Now, in the game with several fugitives, we consider the following strategy: each time a vertex t is reached for the first time by a fugitive, we mark the vertices in σ(t).The fugitives cannot win against such a strategy.

Finally, we show that if there is a subtree S containing v 0 such that

|N [S]|-1 |S| > k,

To keep an Interval Graph under surveillance

An interval graph G is the intersection graph of a set of real intervals. The proof of the following theorem is omitted and can be found in [START_REF] Fomin | To satisfy impatient web surfers is hard[END_REF]. Theorem 8. sn(G, v 0 ) can be computed in time O(n • ∆ 3 ) in the class of n-node interval graphs with maximum degree ∆. [START_REF] Fomin | To satisfy impatient web surfers is hard[END_REF]

Conclusion and further work

In [START_REF] Fomin | To satisfy impatient web surfers is hard[END_REF], we define a variant of the surveillance game by introducing an extra natural constraint. In the connected variant of the surveillance game, the observer is constrained to mark only vertices that have neighbors already marked, i.e., the set of marked vertices must always induce a connected subgraph. We then define csn(G, v 0 ) as the smallest k such that there is a winning connected k-strategy in G when the fugitive starts from v 0 .

In [START_REF] Fomin | To satisfy impatient web surfers is hard[END_REF], we show that there are graphs G and starting vertex v 0 for which csn(G, v 0 ) > sn(G, v 0 ). However, we prove that all results of this paper hold for the connected variant. In particular, in any graph G that is an interval graph or a tree, and for any v 0 ∈ V (G), csn(G, v 0 ) = sn(G, v 0 ). Moreover, in all graphs used for the complexity reductions in this paper, the surveillance number equals its connected counterpart.

The connected version of the game seems interesting since it is closer to the more realistic online version of the prefetching problem. In an online version, the observer has no global knowledge of the graph anymore but discovers progressively the neighbors of the vertices she marks.

To conclude, we ask some open questions:

-Does there exist a constant bounding the ratio (resp., the difference) between csn and sn in any graph? -What is the complexity of computing the surveillance number in the class of graphs with maximum degree 4? With bounded degree? With bounded treewidth? -Does there exists a constant c < 2 and an algorithm that computes sn(G, v 0 ) in time O(c n ) in general graphs G? -Is that true that, for any graph G and v 0 ∈ V (G), sn(G, v 0 ) = max S

|N [S]|-1 |S|

where S is taken among all subsets of V (G) containing v 0 and inducing a connected subgraph?

  be the subgraph induced by S in G. The open neighbourhood N (S) of a vertex subset S is the subset of vertices in V \ S having a neighbour in S and the closed neighbourhood is N [S] = N (S) ∪ S. If S = {v}, we use N (v) and N [v] instead of N ({v}) and N [{v}].

Fig. 1 .

 1 Fig.1. Reduction in proof of Th. 4. A small black node with an integer i beside and that is the out-neighbor of a vertex v corresponds to i leaves that are in N + (v).

Theorem 5 .

 5 sn(G, v 0 ) can be computed in time O * (2 n ) on n-node graphs.

Theorem 7 .

 7 then the fugitives win the new game. Indeed, the fugitives first occupy all vertices of S. At this step, at most k • |S| + 1 vertices have been marked (because S is connected and v 0 is marked and for each vertex in S at most k vertices in V (T )\{v 0 } are marked). Since |N [S]| > k•|S|+1, at least one unmarked vertex in N [S] will be reached by some fugitive during the next step.Hence,sn(T, v 0 ) ≥ max |N [S]|-1|S|where the maximum is taken over all S ⊆ V (T ) inducing a subtree of T containing v 0 . For any tree T rooted in v 0 , sn(T, v0 ) = max |N [S]|-1|S|where the maximum is taken over all subtrees S of T containing v 0 .