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.

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.

International audience; Cet article étudie les schémas de routage compacts qui sont très efficaces en termes de mémoires utilisées pour le stockage des tables de routage dans les graphes de type Internet. Nous proposons un nouveau schéma de routage compact avec indépendance des noms, dont la mémoire moyenne par noeud est prouvée comme étant bornée par √n, et pour lequel l'étirement maximum de toute route est au plus 7. Ces bornes sont données pour la classe RPLG (Random Power Low Graphs) et sont vraies avec forte probabilité. De plus, nous montrons expérimentalement que notre schéma est tr es efficace en termes d'étirement et de mémoire dans les graphes de type Internet (CAIDA et d'autres cartes). Nous complétons cette étude en comparant nos résultats analytiques et expérimentaux a plusieurs schémas de routage compact. En particulier, nous montrons que les besoins moyens en mémoire de notre schéma sont meilleurs que les schémas précédents d'au moins un ordre de grandeur pour des cartes CAIDA de 16K noeuds.

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; Pour permettre le routage dans un graphe, les nœuds doivent connaître des portions de route. La dynamique du graphe peut rendre les informations stockées erronées. Cet article s'intéresse à la caractérisation de la quantité d'informations erronées, ainsi qu'aux nombre de changements de distances dans le graphe suite à L suppressions d'arêtes et L' suppressions de nœuds. Nous considérons un graphe G de diamètre D possédant N nœuds et M arêtes. Nous montrons que l'espérance du nombre d'erreurs et de changement de distance est d'au plus D (LN/M + L').

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.

Graph Exploration is a problem motivated by several aspects of theoretical computer science, including logic and computational complexity. It has also numerous applications in robotics. In all these contexts, the amount of memory used by the mobile entity (robot, finite automaton, etc.) performing exploration is a key parameter. In this thesis, we study in depth the space complexity of graph exploration, in two different frameworks.In the first part of the thesis, we focus on exploration "without assistance", i.e., the case where the mobile entity does not possess any a priori information about the explored graph. In this context, we prove several lower and upper bounds on the amount of memory necessary and sufficient to the mobile entity for performing exploration of all graphs. In particular, we show that the depth-first search algorithm is optimal in space when the complexity is measured in term of degree and diameter.In the second part of the thesis, we focus on exploration "with assistance", by assuming that an oracle entirely aware of the input graph can help the mobile entity, by providing some information about it. This information is measured by its bit-space complexity, and we are interested in the minimal number of bits that the oracle must provide so that the mobile entity can perform exploration. The information can be either given directly to the entity, or encoded on the vertices of the graph., Le problème de l'exploration de graphes trouve ses motivations en informatique fondamentale, notamment en logique et en théorie de la complexité. Il possède également de nombreuses applications en robotique. Quel que soit le cadre, la quantité de mémoire utilisée par l'entité mobile (robot, automate fini, etc.) effectuant l'exploration est un des paramètres importants à considérer. Dans cette thèse, nous étudions en détail la complexité en espace de l'exploration de graphes, à travers différents modèles. Nous distinguons principalement deux cadres d'études.Dans la première partie de la thèse, nous nous attachons à l'étude de l'exploration ``sans assistance'', c'est-à-dire lorsque l'entité mobile ne possède aucune information sur le graphe à explorer. Dans ce contexte, nous prouvons plusieurs bornes inférieures et supérieures sur la quantité de mémoire nécessaire et suffisante à l'entité pour explorer tous les graphes. En particulier, nous montrons que l'algorithme très simple de parcours en profondeur d'abord est optimal en mémoire lorsque la complexité est exprimée en fonction du degré et du diamètre.Dans la seconde partie de la thèse, nous nous attachons à l'étude de l'exploration ``avec assistance''. Nous considérons un modèle supposant l'existence d'un oracle ayant une connaissance exhaustive du graphe exploré, et capable d'aider l'entité mobile en lui fournissant de l'information. Nous nous intéressons ainsi à la quantité minimale d'information (mesurée en nombre de bits) que l'oracle doit fournir à l'entité pour permettre l'exploration. Cette information peut être soit donnée directement à l'entité, soit codée sur les sommets du graphes.

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.

National audience; Une équipe d'entités mobiles (robots), identiques et sans mémoire, doit explorer un arbre anonyme en visitant tous ses noeuds. Les robots démarrent depuis des noeuds différents et arbitraires de l'arbre et opèrent suivant des cycles Regarder-Calculer-Aller (Look-Compute-Move). A la fin, chaque noeud doit avoir été visité par au moins un robot, et tous les robots doivent s'arrêter. Dans un cycle, un robot prend une photographie de la configuration courante (Regarder), prend la décision de rester immobile ou de se déplacer vers un des noeuds adjacents (Calculer), et dans ce dernier cas se déplace instantanément vers ce voisin (Aller). Les cycles sont exécutés de façon asynchrone par chaque robot. Nous présentons un algorithme d'exploration pour tous les arbres à n noeuds de degré maximum 3 utilisant O(log n/loglog n) robots, et nous prouvons que pour de tels arbres Omega(log n/loglog n) robots sont nécessaires pour les explorer. Nous montrons par ailleurs que l'exploration de certains arbres à n noeuds de degré maximum 4 nécessite Omega(n) robots.

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.

A computation scheme among n parties is fair if no party obtains the computation result unless all other \(n-1\) parties obtain the same result. A fair computation scheme is optimistic if n honest parties can obtain the computation result without resorting to a trusted third party. We prove, for the first time, a tight lower-bound on the message complexity of optimistic fair computation for n parties among which \(n-1\) can be malicious in an asynchronous network. We do so by relating the optimal message complexity of optimistic fair computation to the length of the shortest permutation sequence in combinatorics.

In order to respond to routing queries, the entities of the network, nammedrouters, require to have a knowledge concerning the topology of the network, thisknowledge is called routing table. The network is modeled by a graph in whichnodes represent routers and edges represent communication links between nodes.This thesis focuses on routing tables computation in a distributed model. In thismodel, computations are done by a set of process placed on nodes. Every processhas for objective to compute the routing table of the node on which he is placed.To perform this computation, processes have to communicate with each other. Inlarge scale network, in the case of a distributed computation, maintaining routingtables up to date can be costly in terms of communication. This thesis focuses mainlyon the problem of communication cost reduction. One of the solution we proposeis to reduce routing tables size which allow to reduce communication cost. In thecentralised model this strategy is well known under the name of compact routing.This thesis presents in particular a distributed compact routing algorithm that allowsto reduce significantly the communication costs in networks like Internet, i.e. theautonomous systems network and others networks that present scale-free properties.This thesis also contains an experimental study of several distributed compact routingalgorithms. Finally, some problems linked to network dynamicity are addressed.More precisely, the problem of network deconnexion during a shortest path treecomputation with auto-stabilisation guaranties, together with a study of the impactof several edges or nodes deletion on the state of the routing tables., Répondre à des requêtes de routage requiert que les entités du réseau, nommées routeurs, aient une connaissance à jour sur la topologie de celui-ci, cette connaissance est appelée table de routage. Le réseau est modélisé par un graphe dans lequel les noeuds représentent les routeurs, et les arêtes les liens de communication entre ceux ci.Cette thèse s’intéresse au calcul des tables de routage dans un modèle distribué.Dans ce modèle, les calculs sont effectués par un ensemble de processus placés sur les noeuds. Chaque processus a pour objectif de calculer la table de routage du noeud sur lequel il se trouve. Pour effectuer ce calcul les processus doivent communiquer entre eux. Dans des réseaux de grande taille, et dans le cadre d’un calcul distribué, le maintien à jour des tables de routage peut être coûteux en terme de communication. L’un des thèmes principaux abordés et celui de la réduction des coûts de communication lors de ce calcul. L’une des solutions apportées consisteà réduire la taille des tables de routage, permettant ainsi de réduire les coûts de communication. Cette stratégie classique dans le modèle centralisé est connue sous le nom de routage compact. Cette thèse présente notamment un algorithme de routage compact distribué permettant de réduire significativement les coûts de communication dans les réseaux tels que le réseau internet, i.e. le réseau des systèmes autonomes ainsi que dans des réseaux sans-échelle. Ce document contient également une étude expérimentale de différents algorithmes de routage compact distribués.Enfin, les problèmes liés à la dynamique du réseau sont également abordés. Plusprécisément le reste de l’étude porte sur un algorithme auto-stabilisant de calcul d’arbre de plus court chemin, ainsi que sur l’impact de la suppression de noeuds ou d’arêtes sur les tables de routage stockées aux routeurs.