Search

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.