Computation with partial information and network dynamics : distributed coordination, forbidden structures, and online routing

Calcul avec informations partielles et dynamique de réseau : coordination distribuée, structures interdites et routage en ligne Cette thèse étudie l'impact de la dynamique des réseaux (c'est-à-dire la présence ou l'absence de nœuds ou d'arêtes) sur la capacité à concevoir des algorithmes centralisés ou distribués efficaces. Dans le cadre centralisé, la thèse se concentre sur les graphes temporels, également connus sous le nom de graphes dynamiques ou variables dans le temps, dans lesquels les arêtes ne sont présentes que pendant des intervalles de temps spécifiques. Dans le cadre décentralisé, la thèse se concentre sur les réseaux synchrones de transmission de messages où les nœuds peuvent tomber en panne. Plus précisément, pour chaque k\geq 1, l'accord sur un ensemble de k est la tâche pour laquelle les nœuds d'un système distribué doivent se mettre d'accord sur au plus k valeurs différentes (c'est-à-dire qu'ils doivent parvenir à un consensus chaque fois que k=1). Ce problème fondamental a été largement étudié à travers un large éventail de modèles, y compris les systèmes synchrones de passage de messages dans lesquels les processus communiquent dans des tours synchronisés en échangeant des messages le long du bord d'un graphe. Cependant, la grande majorité de la littérature sur le sujet suppose des graphes entièrement connectés. Cette thèse étudie le cas où le réseau de communication peut ne pas être complet. Tout d'abord, nous établissons que l'algorithme oblivide connu pour le consensus dans un graphe (connecté) arbitraire~G soumis à des défaillances de collision est optimal parmi les algorithmes oblivides. Deuxièmement, nous concevons une nouvelle preuve de limite inférieure pour l'accord de k-set dans un réseau de communication arbitraire sans défaillance, qui peut être considérée comme plus simple que la preuve connue précédemment. Cette thèse contribue aux graphes temporels en étudiant les aspects structurels et algorithmiques de ces réseaux, qui sont essentiels dans les cadres où les contraintes temporelles sont connues à l'avance (par exemple, l'horaire des trains). Premièrement, nous étendons la notion standard de motifs interdits de la théorie des graphes (statique) aux motifs interdits \emph{temporels}, pour caractériser les classes de graphes temporels résultant d'un modèle de mobilité standard. Deuxièmement, nous étendons le problème du voyageur canadien - un problème de routage en ligne défini à l'origine sur des graphes statiques - au cadre temporel. L'objectif est de trouver un itinéraire d'une source à une cible alors que les arêtes peuvent être bloquées de manière inattendue au cours du voyage. Nous introduisons deux variantes du problème en fonction du moment où les arêtes bloquées sont révélées. Nous analysons la complexité de calcul de ces variantes, en montrant que l'une est résoluble en temps polynomial, tandis que l'autre est \mathsf{PSPACE}-complete. En outre, nous montrons que le problème du voyageur canadien standard (non temporel) est \mathsf{NP} difficile pour un nombre constant d'arêtes bloquées.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.