Search

Rapporteur non membre du jury : Evangelos Kranakis; This manuscript presents a significant part of my research results in the past years, in the field of distributed computing in networks. The document is structured from the point of view of information available to the computing entities. First, I present my results concerning the advice framework, which allows to study quantitative questions about the a priori information given to the computing entities in order to solve a given problem. I address then the geometric setting, where the computing entities are mobile robots that acquire information about their environment through vision. The third part concerns the exploration of dynamic networks by a mobile entity (called agent in this context), and the impact of knowing the future topological changes. The next part also deals with distributed computing by mobile agents and considers various problems and the different ways of storing information on the network. Finally, the last group of presented results focuses on a particular type of information, the routing one, useful in many contexts to efficiently transfer information in a network.

We deal with the problem of maintaining a shortest-path tree rooted at some process r in a network that may be disconnected after topological changes. The goal is then to maintain a shortest-path tree rooted at r in its connected component, V_r, and make all processes of other components detecting that r is not part of their connected component. We propose, in the composite atomicity model, a silent self-stabilizing algorithm for this problem working in semi-anonymous networks, where edges have strictly positive weights. This algorithm does not require any a priori knowledge about global parameters of the network. We prove its correctness assuming the distributed unfair daemon, the most general daemon. Its stabilization time in rounds is at most 3nmax+D, where nmax is the maximum number of non-root processes in a connected component and D is the hop-diameter of V_r. Furthermore, if we additionally assume that edge weights are positive integers, then it stabilizes in a polynomial number of steps: namely, we exhibit a bound in O(maxi nmax^3 n), where maxi is the maximum weight of an edge and n is the number of processes., Discrete Mathematics & Theoretical Computer Science ; Vol. 19 no. 3 ; 1365-8050

International audience; Nous considérons les problèmes de décision qui sont résolus de manière répartie par des agents mobiles synchrones évoluant dans un réseau inconnu et anonyme. Chaque agent dispose d'un identifiant unique et d'une chaîne d'entrée, et ces agents doivent décider collectivement de la validité d'une propriété qui peut être basée sur les chaînes d'entrée, le graphe dans lequel les agents évoluent, et leurs positions de départ. Poursuivant un travail récent de Friagniaud et Pelc [LATIN 2012, LNCS 7256, p. 362–374], nous introduisons plusieurs nouvelles classes naturelles de calculabilité par agents mobiles, nous permettant d'obtenir une classification plus fine des problèmes inclus dans co-MAV ou MAV, cette dernière étant la classe des problèmes vérifiables lorsque les agents disposent d'un certificat approprié. Dans cet article, nous exhibons des résultats d'inclusion ou de séparation entre toutes ces classes. Nous déterminons également leurs propriétés de clôture vis-à-vis des opérations classiques de la théorie des ensembles. Notre principal outil technique, intéressant en soi, est un nouveau méta-protocole qui permet l'exécution essentiellement en parallèle d'un nombre potentiellement infini de protocoles d'agents mobiles, de façon similaire à la technique classique de déployeur universel (dovetailing) présente en calculabilité classique.

Many articles deal with the problem of maintaining a rooted shortest-path tree. However , after some edge deletions, some nodes can be disconnected from the connected component V r of some distinguished node r. In this case, an additional objective is to ensure the detection of the disconnection by the nodes that no longer belong to V r. We present a detailed analysis of a silent self-stabilizing algorithm. We prove that it solves this more demanding task in anonymous networks with the following properties: it runs without any knowledge on the network and under the unfair daemon, that is without any assumption on the asynchronous model. Moreover, it terminates in less than 2n + D rounds for a network of n nodes and hop-diameter D.

International audience

International audience; Nous étudions le problème de l'exploration, par une entité mobile, d'une classe de graphes dynamiques appelés graphes périodiquement variables (PV-graphes). Ils sont définis par un ensemble de transporteurs suivant infiniment leur route respective le long des stations du réseau, et modélisent donc naturellement les réseaux de transport public. Flocchini, Mans et Santoro [FMS09] ont étudié ce problème dans le cas où l'agent doit toujours rester sur les transporteurs. Dans ce papier, nous étudions l'impact de la capacité d'attendre sur les stations. Nous prouvons que l'attente sur les stations permet à l'agent d'atteindre de meilleures complexités en pire cas : le nombre de mouvements est réduit d'un facteur multiplicatif d'au moins Theta(p), et la complexité en temps passe de Theta(kp^2) à Theta(np), où n est le nombre de stations, k le nombre de transporteurs, et p la période maximale (n

International audience; The behavior of rational selfish agents has been classically studied in the framework of strategic games in which each player has a set of possible actions, players choose actions simultaneously and the payoff for each player is determined by the matrix of the game. However, in many applications, players choose actions asynchronously, and simultaneity of this process is not guaranteed: it is possible that a player learns the action of another player before making its choice. Delays of choices are controled by the adversary and each player can only secure the worst-case payoff over the adversary's decisions. In this paper we consider such asynchronous versions of arbitrary two-person strategic games and we study how the presence of the asynchronous adversary influences the behavior of the players, assumed to be selfish but rational. We concentrate on deterministic (pure) strategies, and in particular, on the existence and characteristics of pure Nash equilibria in such games. It turns out that the rational behavior of players changes significantly if the decision process is asynchronous. We show that pure Nash equilibria often exist in the asynchronous version of the game even if there were no such equilibria in the synchronous game. We also show that a mere threat of asynchrony in the game may make social optimum a rational choice while it was not rational in the synchronous game.

National audience; Cet article traite de l'exploration d'un réseau par un agent mobile, ou {\em robot}, modélisé par un automate fini. Le réseau est anonyme, au sens que les nœuds ne disposent pas nécessairement d'un étiquetage global. Le robot ne dispose pas de connaissances préalables sur la topologie du réseau, ni même sur sa taille. Sa tâche consiste à traverser chacun des liens du réseau. Nous montrons que, pour tout robot à $K$ états, et pour tout $d\geq 3$, il existe un réseau de degré maximum $d$ et d'au plus $K+1$ nœuds que le robot ne réussit pas à explorer. Cette borne $K+1$ améliore toutes les bornes connues jusqu'aujourd'hui. Nous montrons également que, pour explorer tous les graphes de diamètre $D$ et de degré maximum $d$, un robot doit disposer de $\Omega(D\log{d})$ bits de mémoire, et ce même si l'on restreint l'exploration aux réseaux planaires. Enfin, nous montrons que cette borne est asymptotiquement optimale, en décrivant un algorithme qui permet à un robot possédant une mémoire de $O(D\log{d})$ bits d'explorer tous les réseaux de diamètre $D$ et de degré maximum $d$. Ceci nous permet donc de conclure que la complexité mémoire du problème de l'exploration de réseaux est $\Theta(D\log{d})$ bits.

International audience; Nous présentons un algorithme distribué construisant des tables de routage de taille sous-linéaire en n, le nombre de nœuds du réseau. Le temps de convergence est proportionnel au diamètre, ce qui est optimal. Par rapport à BGP, la complexité du nombre de messages échangés est améliorée jusqu'à un facteur n^1/2, alors que la longueur des routes induites par les tables est allongée d'un facteur garanti constant. Notre algorithme est conçu pour un environnement statique synchrone ou asynchrone et produit un schéma name-independent.

International audience; We study the problem of finding a destination node t by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by Hanusse et al [20, 21]. Each node of the network is able to give advice concerning the next node to visit so as to go closer to the target t. Unfortunately, exactly k of the nodes, called liars, give advice which is incorrect. It is known that for an n-node graph G of maximum degree Δ ≥ 3, reaching a target at a distance of d from the initial location may require an expected time of 2^Ω(min{d,k}), for any d,k = O(log n), even when G is a tree. This paper focuses on strategies which efficiently solve the search problem in scenarios in which, at each node, the agent may only choose between following the local advice, or randomly selecting an incident edge. The strategy which we put forward, called R/A, makes use of a timer (step counter) to alternate between phases of ignoring advice (R) and following advice (A) for a certain number of steps. No knowledge of parameters n, d, or k is required, and the agent need not know by which edge it entered the node of its current location. The performance of this strategy is studied for two classes of regular graphs with extremal values of expansion, namely, for rings and for random Δ-regular graphs (an important class of expanders). For the ring, R/A is shown to achieve an expected searching time of 2d+k^Θ(1) for a worst-case distribution of liars, which is polynomial in both d and k. For random Δ-regular graphs, the expected searching time of the R/A strategy is O(k^3 log^3 n) a.a.s. The polylogarithmic factor with respect to n cannot be dropped from this bound; in fact, we show that a lower time bound of Ω(log n) steps holds for all d,k = Ω(log logn) in random Ω-regular graphs a.a.s. and applies even to strategies which make use of some knowledge of the environment. Finally, we study oblivious strategies which do not use any memory (in particular, with no timer). Such strategies are essentially a form of a random walk, possibly biased by local advice. We show that such biased random walks sometimes achieve drastically worse performance than the R/A strategy. In particular, on the ring, no biased random walk can have a searching time which is polynomial in d and k.

National audience; Nous étudions la quantité de connaissance nécessaire sur le réseau pour résoudre efficacement une tâche sur celui-ci. L'impact de l'information disponible sur l'efficacité de la résolution des problèmes, comme la communication ou l'exploration, a déjà été étudié auparavant mais les hypothèses concernaient la disponibilité d'informations {\em particulières} sur le réseau, comme sa taille, son diamètre ou une carte de celui-ci. Au contraire, notre approche est {\em quantitative} : nous étudions le nombre minimum de bits d'information (taille d'oracle minimum) qui doivent être fournis à l'algorithme pour effectuer une tâche avec une certaine efficacité. Nous illustrons cette approche quantitative de l'information disponible par le problème de l'exploration d'arbres. Une entité mobile (robot) doit traverser toutes les arêtes d'un arbre inconnu, en utilisant aussi peu de traversées d'arêtes que possible. La qualité d'un algorithme d'exploration $\cA$ est mesuré par son {\em rapport compétitif}, i.e., par comparaison de son coût (nombre de traversées d'arêtes) à la longueur du plus court chemin contenant toutes les arêtes de l'arbre. Le parcours en profondeur d'abord a un rapport compétitif de 2 et en l'absence d'information sur l'arbre aucun algorithme ne peut faire mieux. Nous déterminons le nombre minimal de bits d'information qui doit être donné à un algorithme d'exploration afin d'obtenir un rapport compétitif strictement plus petit que 2. Notre résultat principal établit un seuil exact sur la taille de l'oracle, qui est approximativement $\log \log D$ bits, où $D$ est le diamètre de l'arbre. Plus précisément, pour toute constante $c$, nous construisons un algorithme d'exploration de rapport compétitif plus petit que 2, utilisant un oracle de taille au plus $\log \log D -c$, et nous montrons que tout algorithme utilisant un oracle de taille $\log \log D -g(D)$, pour toute fonction $g$ non bornée supérieurement, a un rapport compétitif au moins égal à 2.

National audience; Cet article traite de l'exploration d'un réseau par un agent mobile, ou {\em robot}, modélisé par un automate fini. Le robot ne dispose pas de connaissances préalables sur la topologie du réseau, ni même sur sa taille. Sa tâche consiste à explorer chacun des n{\oe}uds du réseau. Il a été montré que, pour tout robot $\cR$ à $K$ états, et pour tout $d\geq 3$, il existe un réseau de degré maximum $d$ et d'au plus $K+1$ n{\oe}uds que $\cR$ ne réussit pas à explorer. Ce papier s'intéresse à la possibilité d'aider le robot en ajoutant des étiquettes de petite taille aux n{\oe}uds grâce à un calcul préalable. Nous décrivons un algorithme d'exploration qui, étant donné des étiquettes appropriées sur 2~bits (en fait des étiquettes de trois valeurs différentes), permet à un robot d'explorer tous les réseaux. De plus, nous décrivons un algorithme linéaire calculant un tel étiquetage. Nous montrons également comment modifier notre méthode d'étiquetage afin qu'un robot puisse explorer tous les réseaux de degré constant, avec des étiquettes de seulement 1~bit (donc des étiquettes de deux valeurs différentes seulement). Autrement dit, alors qu'il n'existe pas de robot capable d'explorer tous les réseaux (non étiquetés) de degré maximum~3, il existe un robot $\cR^*$ et un moyen de colorier les n{\oe}uds en noir et blanc tel que $\cR^*$ réussit à explorer tous les réseaux coloriés de degré maximum~3.

International audience; We present a distributed asynchronous algorithm that, for every undirected weighted $n$-node graph $G$, constructs name-independent routing tables for $G$. The size of each table is $\tO(\sqrt{n}\,)$, whereas the length of any route is stretched by a factor of at most~$7$ w.r.t. the shortest path. At any step, the memory space of each node is $\tO(\sqrt{n}\,)$. The algorithm terminates in time $O(D)$, where $D$ is the hop-diameter of $G$. In synchronous scenarios and with uniform weights, it consumes $\tO(m\sqrt{n} + n^{3/2}\min\set{D,\sqrt{n}\,})$ messages, where $m$ is the number of edges of $G$. In the realistic case of sparse networks of poly-logarithmic diameter, the communication complexity of our scheme, that is $\tO(n^{3/2})$, improves by a factor of $\sqrt{n}$ the communication complexity of \emph{any} shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest.

In this paper, we study the T-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is T-interval-connected (T ≥ 1) if, for every window of T consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman (Kuhn et al. 14) (STOC 2010). We focus on the case when the underlying graph is a ring of size n, and we show that the worst-case time complexity for the exploration problem is 2n − T − Θ(1) time units if the agent knows the dynamics of the graph, and $n+ \frac {n}{\max \{1, T-1\} } (\delta -1) \pm {\Theta }(\delta )$ time units otherwise, where δ is the maximum time between two successive appearances of an edge.