Section: New Results

Overlays and distributed algorithms

Locally Fair Graph Exploration Strategies

Participants : David Ilcinkas, Ralf Klasing, Adrian Kosowski.

In [16] , we considered the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural counterparts for undirected graphs of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First (OF), always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First (LUF) which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph $G=(V,E)$ of diameter $D$ within time $O\left(D\right|E\left|\right)$, and in the long run traverses all edges of $G$ with the same frequency.

Black Hole Search in Directed Graphs

Participant : Adrian Kosowski.

In [21] we considered a team of agents which has to explore a graph $G$ where some nodes can be harmful. Robots are initially located at the so called home base node. The dangerous nodes are the so called black hole nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore $G$ in such a way that the minimum number of robots is wasted. The exploration ends if there is at least one surviving robot which knows all the edges leading to the black holes. As many variations of the problem have been considered so far, the solution and its measure heavily depend on the initial knowledge and the capabilities of the robots. We assume that $G$ is a directed graph, the robots are associated with unique identifiers, they know the number of nodes $n$ of $G$ (or at least an upper bound on $n$), and they know the number of edges $\Delta$ leading to the black holes. Each node is associated with a white board where robots can read and write information in a mutual exclusive way. A recently posed question (Czyzowicz et al. 2009) is whether some number of robots, expressed as a function of parameter Delta only, is sufficient to detect black holes in directed graphs of arbitrarily large order $n$. We give a positive answer to this question for the synchronous case, i.e., when the robots share a common clock, showing that $O(\Delta 2^{\Delta }$) robots are sufficient to solve the problem. This bound is nearly tight, since it is known that at least $2^{D}elta$ robots are required for some instances. Quite surprisingly, we also show that unlike in the case of undirected graphs, for the directed version of the problem, synchronization can sometimes make a difference: for $\Delta =2$, in the synchronous case 4 robots are always sufficient, whereas in the asynchronous case at least 5 robots are sometimes required.

Rendezvous for Location-Aware Agents

Participant : Adrian Kosowski.

In [35] we studied rendezvous of two anonymous agents, where each agent knows its own initial position in the environment. Their task is to meet each other as quickly as possible. The time of the rendezvous is measured by the number of synchronous rounds that agents need to use in the worst case in order to meet. In each round, an agent may make a simple move or it may stay motionless. We consider two types of environments, finite or infinite graphs and Euclidean spaces. A simple move traverses a single edge (in a graph) or at most a unit distance (in Euclidean space). The rendezvous consists in visiting by both agents the same point of the environment simultaneously (in the same round). In [35] , we propose several asymptotically optimal rendezvous algorithms. In particular, we show that in the line and trees as well as in multi-dimensional Euclidean spaces and grids the agents can rendezvous in time $O\left(d\right)$, where $d$ is the distance between the initial positions of the agents. The problem of location-aware rendezvous was studied before in the asynchronous model for Euclidean spaces and multi-dimensional grids, where the emphasis was on the length of the adopted rendezvous trajectory. We point out that, contrary to the asynchronous case, where the cost of rendezvous is dominated by the size of potentially large neighborhoods, the agents are able to meet in all graphs of at most $n$ nodes in time almost linear in $d$, namely, $O\left(d{log}^{2}n\right)$. We also determine an infinite family of graphs in which synchronized rendezvous takes time $\Omega \left(d\right)$.

Boundary Patrolling by Mobile Agents

Participant : Adrian Kosowski.

In the boundary patrolling problem, a set of $k$ mobile agents are placed on the boundary of a simply connected planar object represented by a cycle of unit length. Each agent has its own predefined maximal speed, and is capable of moving around this boundary without exceeding its maximal speed. The agents are required to protect the boundary from an intruder which attempts to penetrate to the interior of the object through a point of the boundary, unknown to the agents. The intruder needs some time interval of length $\tau$ to accomplish the intrusion. Will the intruder be able to penetrate into the object, or is there an algorithm allowing the agents to move perpetually along the boundary, so that no point of the boundary remains unprotected for a time period $\tau$? Such a problem may be solved by designing an algorithm which defines the motion of agents so as to minimize the idle time $I$, i.e., the longest time interval during which any fixed boundary point remains unvisited by some agent, with the obvious goal of achieving $I<\tau$. Depending on the type of the environment, this problem is known as either boundary patrolling or fence patrolling in the robotics literature. The most common heuristics adopted in the past include the cyclic strategy, where agents move in one direction around the cycle covering the environment, and the partition strategy, in which the environment is partitioned into sections patrolled separately by individual agents. We have obtained, to our knowledge, the first study of the fundamental problem of boundary patrolling by agents with distinct maximal speeds. In this scenario, we give special attention to the performance of the cyclic strategy and the partition strategy. In [36] , we propose general bounds and methods for analyzing these strategies, obtaining exact results for cases with 2, 3, and 4 agents. We show that there are cases when the cyclic strategy is optimal, cases when the partition strategy is optimal and, perhaps more surprisingly, novel, alternative methods have to be used to achieve optimality.

Rendezvous in trees

Participant : Adrian Kosowski.

In the rendezvous problem in trees, two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We consider deterministic algorithms for this rendezvous task. In [51] we have presented a tight trade-off between the optimal time of completing rendezvous and the size of memory of the agents. For agents with $k$ memory bits, we show that optimal rendezvous time is $\Theta (n+n^2/k)$ in $n$-node trees. More precisely, if $k\ge clogn$, for some constant $c$, we design agents accomplishing rendezvous in arbitrary trees of unknown size $n$ in time $O(n+n^2/k)$, starting with arbitrary delay. We also show that no pair of agents can accomplish rendezvous in time $o(n+n^2/k)$, even in the class of lines of known length and even with simultaneous start. Finally, we prove that at least logarithmic memory is necessary for rendezvous, even for agents starting simultaneously in a $n$-node line.

How many oblivious robots can explore a line

Participant : David Ilcinkas.

In [20] we consider the problem of exploring an anonymous line by a team of $k$ identical, oblivious, asynchronous deterministic mobile robots that can view the environment but cannot communicate. We completely characterize sizes of teams of robots capable of exploring a $n$-node line. For $k<n$, exploration by $k$ robots turns out to be possible, if and only if either $k=3$, or $k\ge 5$, or $k=4$ and $n$ is odd. For all values of $k$ for which exploration is possible, we give an exploration algorithm. For all others, we prove an impossibility result.

Asynchronous deterministic rendezvous in bounded terrains

Participant : David Ilcinkas.

Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Robots are modeled as points, and each of them is equipped with a compass. Compasses of robots may be incoherent. Robots construct their routes, but the actual walk of each robot is decided by the adversary that may, e.g., speed up or slow down the robot. In [18] , we consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both robots agree, or not, (3) robots have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the robots' trajectories until they meet. For each scenario we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight.

On the Power of Waiting when Exploring Public Transportation Systems

Participants : David Ilcinkas, Ahmed Mouhamadou Wade.

We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely the periodically-varying graphs (the PV-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network. Flocchini, Mans, and Santoro  [58] (ISAAC 2009) studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal number of steps (and thus of moves) to explore a $n$-node PV-graph of $k$ carriers and maximal period $p$ is in $\Theta (k·p^2)$ in the general case.

In [46] , we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the worst-case optimal number of moves by a multiplicative factor of at least $\Theta \left(p\right)$, while the time complexity is reduced to $\Theta (n·p)$. (In any connected PV-graph, we have $n\le k·p$.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected PV-graphs). Finally this new ability allows the agent to completely map the PV-graph, in addition to just explore it.

The impact of edge deletions on the number of errors in networks

Participants : Christian Glacet, Nicolas Hanusse, David Ilcinkas.

In [41] , we deal with an error model in distributed networks. For a target $t$, every node is assumed to give an advice, i.e. to point to a neighbor that take closer to the destination. Any node giving a bad advice is called a liar. Starting from a situation without any liar, we study the impact of topology changes on the number of liars.

More precisely, we establish a relationship between the number of liars and the number of distance changes after one edge deletion. Whenever $\ell$ deleted edges are chosen uniformly at random, for any graph with $n$ nodes, $m$ edges and diameter $D$, we prove that the expected number of liars and distance changes is $O\left(\frac{{\ell }^{2}Dn}{m}\right)$ in the resulting graph. The result is tight for $\ell =1$. For some specific topologies, we give more precise bounds.

Computations in interconnection networks with a shared whiteboard

Participant : Adrian Kosowski.

In [52] , We study the computational power of graph-based models of distributed computing in which each node additionally has access to a global whiteboard. A node can read the contents of the whiteboard and, when activated, can write one message of $O(logn)$ bits on it. A message is only based on the local knowledge of the node and the current content of the whiteboard. When the protocol terminates, each node computes the output based on the final contents of the whiteboard in order to answer some question on the network's topology. We propose a framework to formally define several scenarios modelling how nodes access the whiteboard, in a synchronous way or not. This extends the work of Becker et al. where nodes were imposed to create their messages only based on their local knowledge (i.e., with the whiteboard empty). We prove that the four models studied have increasing power of computation: any problem that can be solved in the weakest one can be solved in the second, and so on. Moreover, we exhibit problems that separate models, i.e., that can be solved in one model but not in a weaker one. These problems are related to Maximal Independent Set and detection of cycles. Finally we investigate problems related to connectivity as the construction of spanning- or BFS-tree in our different models.

Network Verification

Participant : Ralf Klasing.

In [27] , we address the problem of verifying the accuracy of a map of a network by making as few measurements as possible on the nodes of the network. In the past, this task has been formalized as an optimization problem that, given a graph $G=(V,E)$, asks for finding a minimum-size subset $Q$ of vertices of $G$ such that the information returned by the queries on $Q$ uniquely identifies $G$. Previously, two global query models have been studied. In [27] , we propose a query model that uses only local knowledge about the network. Quite naturally, we assume that a query at a given node $q$ returns the associated routing table, namely a set of entries which provides, for each destination node, a corresponding (set of) first-hop node(s) along an underlying shortest path. First, we show that any network of $n$ nodes needs $\Omega (loglogn)$ queries to be verified. Then, we prove that there is no $o(logn)$ approximation algorithm for the problem, unless $\mathsf{\text{P}}=\mathsf{\text{NP}}$, even for graphs with diameter 2. On the positive side, we provide an $O(logn)$-approximation algorithm to verify a network of diameter 2, and we give exact polynomial-time algorithms for paths, trees and cycles of even length.