Synchronization problems in dynamic multi-agent networks
Problèmes de synchronisation dans les réseaux dynamiques multi-agents
Résumé
We study a network of agents connected by a dynamic communication graph and we consider a computing model consisting of a sequence of synchronous rounds.We study several synchronization and coordination problems in the context of arbitrary starts and initializations.First, we study the Firing Squad synchronization problem in which the agents must "fire" simultaneously, i.e., in the same round, in spite of asynchronous starts.Solving this problem requires strong assumptions. We introduce a weakening of this problem in which the agents must fire, not in the same round, but rather in rounds that are congruent modulo some integer P. We present an algorithm solving this problem under weaker communication assumptions: while the exact synchronization for the Firing Squad requires a strong connectivity property, which is not granted in many contexts, the synchronization modulo P is achievable as long as there exists an agent which is connected to all other agents in any bounded time period of consecutive rounds.Proving the correctness of this algorithm is hard due to a combinatorial explosion of the number of executions. That's why we give a formal proof of the correctness properties of our algorithm using the Isabelle proof assistant.Then we consider the model of "self-stabilizing" algorithms that must reach a "correct" state regardless of the arbitrary initial states of the agents. We study the synchronization modulo P: each agent holds a clock. All those local clocks must be congruent to P from a certain round. This problem has previously been studied in static strongly connected networks. Moreover, agents were assumed to know some global information (e.g., the total number of agents).In the second part of this thesis, our aim is finding a relaxation of those hypothesis. We first show that no algorithm can reconcile an absence of global knowledge and a finite set of states. Then we propose a self-stabilizing variant of the MinMax consensus algorithm for the synchronization modulo P. This algorithm tolerates a very high degree of dynamicity of the communication network but requires an infinite memory.Then we introduce an algorithm that we named SAP (for Self Adaptive Period). Its state space is infinite. However, only a finite number of states is reached in each of its executions. This kind of algorithm is referred to as finite but unbounded memory. We prove the correctness of SAP in networks with an unknown but finite dynamic diameter. This result is then extended to a wider class of centered dynamic networks.Finally, we study the behaviour of SAP in probabilistic communication models. Instead of proving a property on each executions of SAP, we prove a probabilistic hyperproperty -- the synchronization modulo P with high probability --, that is, a property on the set of its executions. Proving an hyperproperty, instead of a simple property, is generally more tedious and requires different techniques. In our case, we define a hierarchy of probabilistic diameters. Using the first two probabilistic diameters, we show that SAP solves the synchronization modulo P with high probability. This proof covers a large number of probabilistic communication models, including the rumor spreading models such as PUSH, PULL and PULLPUSH.
Nous considérons un réseau d'agents reliés par un graphe de communication dynamique et nous nous plaçons dans un modèle de calcul consistant en une succession de rounds synchrones. Nous étudions différents problèmes de synchronisation et coordination dans le contexte de départs et initialisations arbitraires.Tout d'abord, nous étudions le problème de synchronisation du Firing Squad consistant à ce que les agents « fassent feu » simultanément, i.e., au même round, malgré des départs asynchrones. Ce problème nécessitant des hypothèses fortes pour être résoluble, nous introduisons le problème plus faible où les agents doivent faire feu, non pas au même round, mais à des rounds congrus modulo un certain entier P. Nous présentons un algorithme qui résout ce problème sous des hypothèses de connectivité du graphe de communication bien plus faibles : alors que la synchronisation parfaite pour le Firing Squad exige une connexité forte entre les agents, non garantie dans de nombreux contextes, la synchronisation modulo P est réalisable lorsqu'il existe un agent connecté à tous les autres agents dans toute période de temps (rounds consécutifs) bornée.La correction de l'algorithme que nous présentons est difficile à prouver du fait d'une explosion combinatoire du nombre de ses exécutions. C'est pourquoi, nous donnons ensuite la preuve formelle des propriétés de correction de notre algorithme avec l'assistant de preuve Isabelle.Nous considérons ensuite le modèle des algorithmes « auto-stabilisants » qui doivent atteindre un état « correct », quels que soient les états initiaux arbitraires des agents. Nous étudions le problème de la synchronisation modulo P : chaque agent détient une horloge et toutes ces horloges locales doivent être congrues modulo P à partir d'un certain round. Ce problème a été étudié par le passé dans le cadre des réseaux statiques fortement connexes. De plus, les agents sont supposés disposer d'informations globales sur le réseau (e.g., le nombre d'agents).Notre objectif, dans la seconde partie de cette thèse, est d'étudier s'il est possible de relaxer ces hypothèses. Nous commençons par établir l'impossibilité de concilier l'absence de connaissance globale avec l'utilisation d'algorithmes à états finis. Nous proposons alors une variante auto-stabilisante de l'algorithme de consensus MinMax pour la synchronisation modulo P. Cet algorithme tolère une très grande dynamicité des liens de communication mais requiert une mémoire infinie.Nous introduisons ensuite un algorithme que nous appelons SAP (pour Self Adaptive Period). Son espace des états est infini mais seul un nombre fini d'états est atteint dans chacune des exécutions. On parle alors d'algorithme à mémoire finie mais non bornée. Nous démontrons la correction de SAP dans les réseaux dynamiques avec un diamètre dynamique fini mais inconnu. Nous étendons ensuite ce résultat à la classe plus générale des réseaux dynamiques centrés.Pour finir, nous étudions le comportement de l'algorithme SAP dans les modèles de communications probabilistes. Il ne s'agit plus de prouver une propriété de chaque exécution de l'algorithme, mais une hyperpropriété probabiliste -- ici la synchronisation modulo P avec haute probabilité --, c'est à dire une propriété de l'ensemble de ses exécutions. De façon générale, les preuves d'hyperpropriétés sont plus délicates que les preuves de simples propriétés, et nécessitent des techniques différentes. En l'occurrence, nous définissons une hiérarchie de diamètres probabilistes. À partir des deux premiers diamètres de cette hiérarchie, nous prouvons que SAP résout la synchronisation modulo P avec haute probabilité. Cette preuve s'applique à un grand nombre de modèles de communications probabilistes, notamment les modèles de propagation de rumeur comme les modèles PULL, PUSH et PULLPUSH.
Origine : Version validée par le jury (STAR)