Local stopping rules for gossip algorithms

The increasing importance of gossip algorithms is beyond dispute. Randomized gossip algorithms are attractive for collaborative in-network processing and aggregation because they are fully asynchronous, they require no overhead to establish and form routes, and they do not create any bottleneck or single point of failure. All nodes maintain independent asynchronous random clocks, and when a node's clock ticks it initiates a new round of gossip: it randomly selects a neighboring node, exchanges information with the neighbor, and the two nodes compute local updates. When these updates involve averaging the values of the two nodes that gossiped, the algorithm solves the widely-studied average consensus problem which is the focus in this thesis. To analyze the energy-accuracy tradeoff for randomized gossip, previous studies have focused on analyzing the worst-case number of transmissions required to reach a specified level of accuracy, over all initial conditions. In a practical implementation, though, rather than always running for the worst-case number of transmissions, one would like to fix a desired level of accuracy in advance and have the algorithm run for as many iterations as are necessary to achieve this accuracy with high probability. This thesis describes and analyzes an implicit local stopping rule with theoretical performance guarantees. After a node's estimate has not changed significantly for a number of consecutive iterations, it ceases to initiate new gossip rounds. To avoid stopping early and biasing the computation, stopped nodes still participate in gossip rounds when contacted by a neighbor. We provide theoretical guarantees on the final accuracy of the estimates across the network as a function of the algorithm parameters. Through simulation, we show that applying the local stopping rule leads to significant savings in the number of transmissions for many relevant initial conditions. In practical applications one often wishes to track a time-varying average, rather than compute a static quantity. In this scenario, we illustrate that our local stopping rule can be viewed as an event-triggered gossip algorithm. Simulations illustrate the benefits of the proposed approach.L'importance croissante des algorithmes décentralisées de passage de messages est incontestable. Ces algorithmes sont attrayants pour le traitement d'information dans les réseaux de collaboration et l'agrégation parce qu'ils sont totalement asynchrones, ils ne nécessitent pas de frais généraux pour établir et former les routes, il n'exige pas de coordination centralisée et conséquemment ils ne créent pas de goulot d'étranglement ou de point de défaillance unique dans le réseau. Tous les noeuds maintiennent indépendamment des horloges asynchrone, lorsque l'horloge d'un noeud tiques, le noeud initie un nouveau cycle de passage de messages: il sélectionne aléatoirement un noeud voisin, échange des informations avec le voisin, et les deux noeuds calculent et mettent a jour leur variables. Lorsque ces mises à jour incluent le calcul de la moyenne des valeurs des deux noeuds, l'algorithme permet de résoudre le problème du calcul du consensus moyen qui est le sujet de discussion du présent document. Afin d'analyser le compromis entre l'énergie de transmission et la précision de la valeur du consensus, de études antérieures ont porté sur l'analyse du nombre basé sur le pire des cas pour atteindre un niveau de précision. Dans une mise en oeuvre pratique, cependant, au lieu d'être toujours en cours d'exécution du nombre de pire des cas de transmissions, on voudrait fixer un niveau de précision désiré à l'avance et l'algorithme exécutera conséquemment un nombre d'itérations nécessaires pour obtenir cette précision avec haute probabilité. Ce document décrit et analyse une règle d'arrêt implicite locale avec garanties de performance théorique. Quand un noeud estime qu'il n'a pas changé de manière significative pour un certain nombre d'itérations consécutives, il cesse l'échange de donnée la prochaine fois que son horloge tique. Nous soulignons ici que pour éviter l'arrêt précoce de l'algorithme, le noeud participe au passage de message lorsqu'il est contacté par un voisin. Nous offrons des garanties théoriques sur la précision finale des estimations sur le réseau en fonction des paramètres de l'algorithme. En se basant sur les simulations, nous montrons que l'application de la règle d'arrêt local conduit à des économies importantes dans le nombre de transmissions pour de nombreuses conditions initiales. Dans les applications pratiques on souhaite souvent suivre une moyenne variante dans le temps, au lieu de calculer une quantité statique. Dans cette thèse nous développerons des algorithmes de passage de messages déclenchés par le événements pour suivre les signaux variables dans le temps. Des simulations illustrent les avantages de l'approche proposée