Pairwise gossip in CAT (κ) metric spaces

Bellachehab Anass

September 23, 2018

Chapter 1

Introduction

Cette thèse s'est déroulée au sein du laboratoire SAMOVAR (Services répartis, Architectures, Modélisation, Validation, Administration des Réseaux) qui est une unité mixte de recherche Télécom SudParis-CNRS (UMR 5157), sous la direction de Pascal Bianchi et Jérémie Jakubowicz. L'objectif de cette thèse est de généraliser l'algorithme du "gossip" pair-à-pair ( [START_REF] Boyd | Randomized gossip algorithms[END_REF]). L'algorithme du "gossip" pair-à-pair consiste à calculer la moyenne arithmétique, de façon répétée, de vecteurs stockés dans deux noeuds adjacents d'un graphe, et d'affecter la moyenne ainsi calculée aux deux noeuds en question. Nous reviendrons en détail sur cet algorithme dans la suite de ce manuscrit. La généralisation proposée dans cette thèse s'intéresse au cas où les "vecteurs" sont de simples points dans un espace métrique et les calculs de moyennes deviennent des calculs de milieux de géodésiques. Dans les espaces métriques quelconques, il n'y a aucune raison pour que deux points admettent nécessairement un milieu, ni une géodésique, ni-même, si ce milieu existe, qu'il soit unique. Et quand bien même on ne considérerait que des espaces métriques pour lesquels le milieu de deux points existe toujours et est unique, il n'y a pas de raison pour que l'algorithme du "gossip" pair-à-pair décrit converge. Cette thèse développe un bon cadre pour étudier cette généralisation : celui des espaces métriques dit CAT (κ) [START_REF] Gromov | Metric structures for Riemannian and non-Riemannian spaces[END_REF], suivant Cartan, Alexandrov et Toponogov et où κ est un majorant scalaire de la "courbure" de l'espace. Là encore, nous reviendrons en détail sur les aspects techniques dans la suite de ce manuscrit.

Dans un premier chapitre, on passe en revue un certain nombre d'approches des algorithmes de gossip pour le consensus. En particulier, on présente les travaux précurseurs de DeGroot [START_REF] Morris | Reaching a consensus[END_REF] sur le consensus par moyennes itérées, puis l'approche de Tsitsiklis [START_REF] Tsitsiklis | Problems in Decentralized Decision Making and Computation[END_REF] sur les calculs distribués où le consensus est abordé sous l'angle de l'optimisation distribuée. Sont présentés également le gossip pair-à-pair aléatoire [START_REF] Xiao | Fast linear iterations for distributed averaging[END_REF] ainsi que les algorithmes de consensus en temps fini [START_REF] Shi | When do gossip algorithms converge in finite time[END_REF][START_REF] Julien | Finite-time consensus using stochastic matrices with positive diagonals[END_REF]. La dernière partie du chapitre 1 introduit l'angle sous lequel l'ouverture vers les espaces métriques sera la plus aisée : la minimisation d'une 8 CHAPTER 1. INTRODUCTION fonction uniquement basée sur la métrique de l'espace sous-jacent.

Le deuxième chapitre est la clé de voûte de cette thèse. Il développe le cadre CAT (κ) et montre les principaux résultats théoriques. Loin d'être évidente, la généralisation aux espaces métriques CAT (κ) fait jouer un rôle important à la courbure. Plus précisément, nous montrons que lorsque κ est négatif, tout se passe comme dans le cas euclidien: il y a convergence linéaire quelle que soit la configuration initiale des points. En revanche, lorsque κ est strictement positif, la configuration initiale joue, et on ne peut pas garantir la convergence dans toutes les configurations initiales.

Le troisième chapitre porte sur une application du cadre CAT (κ) aux systèmes métamorphes. Outre leur intérêt applicatif en robotique, ils sont aussi remarquables dans la mesure où ils ne s'inscrivent ni dans le cadre des espaces vectoriels, ni dans celui des variétés riemanniennes de courbure négative. Autrement dit, cette application est originale dans la mesure où elle rentre dans le cadre de l'algorithme de consensus étudié dans cette thèse, mais pas dans les cadres qui préexistaient.

Le quatrième chapitre de cette thèse généralise l'approche développée aux cas des graphes variant dans le temps et montre que, pourvu que la communication entre toutes les parties du graphe soit préservée, les résultats du cas "statique" restent valides. Un sens précis est donné à la "préservation de la communication entre toutes les parties du graphe".

Motivations

Un des plus anciens problèmes dans le domaine des algorithmes distribués, et probablement un des plus fondamentaux aussi, est le problème dit du consensus [START_REF] Michael | Impossibility of distributed consensus with one faulty process[END_REF]. Un résultat marquant concernant les algorithmes de consensus est le théorème d'impossibilité de Fischer, Lynch et Paterson (FLP) [START_REF] Michael | Impossibility of distributed consensus with one faulty process[END_REF]. Ce résultat concerne le modèle dit "panne-arrêt" ("fail-stop" en anglais) pour les agents déterministes asynchrones. Dans ce modèle, les agents font des calculs et s'envoient des messages mais peuvent également tomber en panne. Un agent qui tombe en panne cesse de calculer et n'envoie plus aucun message. Les pannes peuvent se produire de façon imprévisible, ou ne pas se produire du tout. Les pannes sont irréversibles, ce qui signifie qu'une fois qu'un agent est en panne, il le reste. Le théorème FLP traite des communications asynchrones : les messages prennent un temps non borné pour être transmis d'un agent à un autre, même si on est sûr qu'ils finiront par être délivrés. De sorte qu'un agent qui attend un message d'un autre agent, et ne l'a pas encore reçu, ne peut pas dire si cet autre agent est en panne, ou que le message prend simplement du temps à être délivré. En revanche, il est sûr que si un message lui a été envoyé, il finira par le recevoir, sauf 1.1. MOTIVATIONS à lui-même tomber en panne. Chaque agent part avec une valeur binaire d'entrée et devra, à terme, fournir une valeur binaire de sortie, à moins de tomber en panne entre temps. Une fois qu'un agent décide d'une valeur de sortie, il ne peut plus en changer mais peut continuer à communiquer avec les autres agents. Chercher le consensus signifie que toutes les valeurs de sortie doivent coïncider, sachant que les agents en panne n'affichent aucune valeur de sortie. De plus, pour éviter une situation inintéressante où les agents s'entendraient au préalable sur une valeur de consensus, indépendamment de leur valeur initiale, on demande que si tous les agents sont déjà dans une situation de consensus initial, disons "vrai" pour fixer les idées, le consensus atteint en sortie soit aussi "vrai". Le théorème FLP stipule qu'en présence de pannes, même s'il s'agit d'une seule panne, il n'y a pas moyen d'établir un protocole qui garantisse ce consensus.

Le cadre du théorème FLP est très éloigné du cadre dans lequel on va se placer, mais c'est une motivation essentielle dans la mesure où c'est probablement l'un des résultats phare du domaine des algorithmes de consensus. Le cadre étudié dans cette thèse est aussi appelé "asynchrone" mais dans un sens différent. C'est un cadre beaucoup moins "asynchrone" que celui du théorème FLP. En effet, dans le cadre qui va nous occuper, chaque agent possède une horloge distincte qui bat suivant un processus de Poisson d'intensité fixe. Ce processus de Poisson modélise une horloge régulière mais bruitée. Cette régularité sous-jacente est totalement absente du cadre FLP. Néanmoins, dans les deux cas, le mot "asynchrone" correspond à la terminologie standard. C'est le fait d'avoir des conditions de synchronisation beaucoup plus régulières qui fait que dans le cadre qui nous intéresse, on arrive non seulement à montrer qu'il existe un protocole menant au consensus, mais nous allons aussi en exhiber un et étudier sa vitesse de convergence.

Un autre travail remarquable, cette fois ci beaucoup plus proche du nôtre est la thèse de J. Tsitsiklis [START_REF] Tsitsiklis | Problems in Decentralized Decision Making and Computation[END_REF] qui date de 1984. Dans le travail de Tsitsiklis, les agents communiquent dans un temps borné et aucune panne ne peut se produire, tout au plus des retards bornés. Tsitsiklis montre que non seulement on peut atteindre un consensus, mais qu'on peut utiliser l'algorithme qui permet de l'atteindre comme une brique élémentaire pour des systèmes plus sophistiqués, tels que les algorithmes d'optimisation distribuée.

Citons également le travail de Boyd et al. [START_REF] Boyd | Randomized gossip algorithms[END_REF] qui est le premier à proposer le cadre suivant : chaque agent possède une valeur initiale vectorielle et les agents communiquent de façon pair-à-pair dans un ordre aléatoire, en calculant deux-à-deux la moyenne de leurs deux valeurs. Boyd et al. montrent que cet algorithme converge presque sûrement vers un consensus.

Dans la mesure où calculer la moyenne arithmétique de deux vecteurs consiste à calculer le milieu du segment formé par leurs extrémités, nous nous sommes posé la question suivante: est-il possible de proposer une variante géométrique CHAPTER 1. INTRODUCTION de l'algorithme de Boyd et al. ? Une variante où chaque agent part d'un point dans un espace géométrique et calcule le milieu du segment formé par son point à une extrémité, et celui d'un de ses voisins tiré au hasard parmi l'ensemble de ses voisins, à l'autre extrémité.

Algorithmes de consensus et espaces métriques CAT (κ)

Dans cette thèse, on étudie donc le problème du consensus dans un réseau de N agents, modélisé par un graphe non orienté G = (V, E), où l'ensemble des noeuds V = {1, . . . , N } désigne les agents et l'ensemble des arêtes E désigne les liens de communications entre ces agents. Chaque agent i stocke une donnée dont la valeur x i appartient à un espace métrique M.

Le cadre de communication du gossip pair-à-pair n'est pas synchrone. Chaque noeud du réseau possède une horloge interne qui suit un processus de Poisson de paramètre λ > 0, commun à tous les agents. A chaque coup d'horloge, un agent peut faire des calculs et communiquer avec d'autres agents voisins. Les horloges des agents sont supposées indépendantes. Ce modèle est équivalent à celui d'une horloge commune qui suit un processus de Poisson de paramètre λN , et qui à chaque coup, réveille de manière aléatoire et uniforme un agent du réseau. Cette horloge commune est une vue de l'esprit : il n'y a pas besoin de l'implémenter en pratique, il suffit que toutes les horloges des agents soient indépendantes et de même intensité.

À chaque réveil de l'horloge commune, un noeud v est choisi aléatoirement et uniformément dans le graphe. On note v(k) ∈ V le noeud choisi au k-ème réveil de l'horloge commune. Le noeud v réveille à son tour un noeud w voisin de lui dans le graphe G. On note w(k) le voisin choisi par v(k). À chaque instant k, on note X(k) = (x 1 (k), . . . , x N (k)) l'état global du système.

Par rapport au travail de Boyd et al. [START_REF] Boyd | Randomized gossip algorithms[END_REF], notre travail consiste a résoudre trois problèmes:

1. Problème 1: identifier un cadre de généralisation et une version adaptée de l'algorithme du gossip au cas des données non-vectorielles.

2. Problème 2: établir les conditions suivant lesquelles l'algorithme du gossip généralisé converge et estimer, le cas échéant, sa vitesse de convergence.

3. Problème 3: étudier sous quelles conditions l'algorithme du gossip généralisé peut être appliqué aux réseaux de topologie variable.

R ÉSULTATS OBTENUS

Dans le cas du gossip pair-à-pair classique, les calculs consistent à faire des moyennes arithmétiques. Pour généraliser l'algorithme à des espaces de données non-euclidiens (dans notre cas des espaces métriques), on a besoin de remplacer la notion de moyenne arithmétique par celle du point milieu. Cependant, les espaces métriques généraux sont trop irréguliers pour que la notion de point milieu y soit bien définie: il peut y avoir entre deux points donnés plusieurs points milieux ou aucun.

Les espaces métriques avec plusieurs points milieux sont nombreux. Un exemple est la sphère: chaque couple de points antipodaux a plusieurs points milieux qui forme "l'équateur". Un exemple d'espace métrique où on peut trouver des couples de points sans point milieu est le plan R 2 sans l'origine. Les points (-1, 0) et (1, 0) par exemple n'ont pas de point milieu dans R 2 -(0, 0).

Résultats obtenus

Notre approche pour généraliser l'algorithme du gossip aux espaces de données non-Euclidiens utilise la notion d'espace métrique CAT (κ). Les espaces CAT (κ) permettent d'étendre la notion de courbure, qui vient des variétés riemanniennes, aux espaces métriques. Ceci permet ensuite, via des inégalités, dites de comparaison, d'étudier les propriétés géométriques d'un espace métrique en le comparant à des espaces de référence de courbure constante. Les espaces de courbure constante ont des propriétés géométriques bien connues qui permettent d'établir des éléments de comparaison.

Dans les espaces CAT (κ), la notion de point milieu entre chaque couple de points est bien définie, pourvu que les points soient assez proches. On peut donc généraliser sans peine l'algorithme du gossip pair-à-pair "classique", pourvu que les points initiaux soient assez proches pour qu'on puisse considérer leur milieu. En terme algorithmique, on utilise le procédé décrit à la table RPM.

Ce qui n'est pas évident, et qui sera démontré dans cette thèse, est que si les points sont initialisés de façon à être suffisamment proches alors ils le resteront au fur et à mesure des itérations. On peut alors démontrer que l'algorithme converge vers un état de consensus avec une vitesse linéaire si l'espace de données est de type CAT (κ).

Pour énoncer rigoureusement le résultat obtenu, il nous faut un moyen de mesurer l'écart au consensus. Pour des raisons techniques qui apparaîtront plus tard dans le manuscrit, on utilise la fonction suivante, dite fonction de désaccord.

Définition 1. Étant donnée une configuration x = (x 1 , . . . , x N ) ∈ M N , la fonc-

Algorithm RPM [BJ16]

Input: un graphe G = (V, E) et une configuration de points initiaux X v (0), v ∈ V for all k > 0 do On choisit au hasard uniformément aléatoirement un noeud V k de V , puis un noeud W k uniformément aléatoirement parmi les voisins de V k Faire:

x V k (k) = Milieu (x V k (k -1), x W k (k -1)) x W k (k) = Milieu (x V k (k -1), x W k (k -1)) x v (k) = x v (k -1) for v ∈ {V k , W k } end for
tion de désaccord ∆(x) est donnée pour κ = 0 par:

∆(x) = v∼w {v,w}∈P 2 (V ) 1 N (deg(v) -1 + deg(w) -1 )d 2 (x v , x w )
Et pour κ > 0 par:

∆ κ (x) = v∼w {v,w}∈P 2 (V ) 1 N (deg(v) -1 + deg(w) -1 )χ κ (d(x v , x w )) Avec χ κ (x) = 1 -cos( √ κx).
Et où on note deg, la fonction degré d'un noeud.

A noter que lorsque le réseau est connexe, alors ∆ κ = 0 si et seulement si le réseau est dans un état de consensus.

On l'a évoqué plus haut, dans le cas où l'espace de données est de type CAT (κ) avec κ > 0, on doit ajouter une condition sur l'état initial du système: les points doivent être suffisamment proches. Précisément, on exige que le diamètre du nuage de points initial (définit comme étant la borne supérieure sur les distances entre les points) soit inférieur à la grandeur Dκ 2 où:

D κ = +∞ si κ ≤ 0 π √ κ si κ > 0
On obtient alors le résultat suivant, qui est le résultat central de cette thèse.

Théorème 1. Si le graphe G est connexe, et que

X(k) = (X 1 (k), . . . , X N (k))
désigne l'état des agents au temps k; que le diamètre de l'ensemble {X 1 (0), . . . , X N (0)} est inférieur à Dκ 2 , alors l'algorithme décrit à la table RPM converge et il existe L ∈ (-1, 0) tel que ∀k:

E∆ κ (X(k)) ≤ exp(Lk)
1.4. APPLICATIONS 13

Applications

Une première application de l'algorithme RPM concerne les matrices définies positives n × n noté Pos(n). L'ensemble des matrices définies positives équipé de la métrique: d(M, N ) = log(M N -1 ) 2 -où log(M ) désigne la seule matrice symmétrique positive telle que exp(log(M )) = M -est un espace métrique de type CAT (0), c'est-à-dire, à courbure négative. Le point milieu entre deux éléments de cet espace est donné par:

M + N 2 = M 1/2 (M -1/2 N M -1/2 ) 1/2 M 1/2 .
L'algorithme RPM fournit alors un outil pour obtenir un consensus dans l'espace des matrices définies positives. Lorsqu'on trace la courbe n → log ∆ κ (X n ) on peut bien vérifier dans la Figure 1.1 qu'on obtient une droite décroissante bruitée, ce qui confirme les résultats théoriques obtenus dans cette thèse. Le bruit est dû à la nature stochastique de l'algorithme qui choisit à chaque itération une paire d'agents aléatoire.

1.1 -Courbe n → log ∆ κ (X n ).
On voit ce qui s'apparente à une droite de pente négative -ce qui est en accord avec le théorème de convergence mentionné plus haut. Le bruit est dû à la nature stochastique de l'algorithme.

Une autre application est celle de la classification distribuée. Ici, chaque noeud v du réseau doit choisir une parmi p < ∞ possibilités. Ce choix est modélisé par une loi de probabilité notée (

x i v ) i∈[1,p] . Ainsi x i v ≥ 0 représente la croyance du noeud v à la possibilité i et p i=1 x i v = 1
. Le réseau doit s'entendre sur une loi de probabilité commune, c'est-à-dire un consensus. Notons qu'ici le consensus porte sur la CHAPTER 1. INTRODUCTION loi de probabilité et non sur les possibilités elles-mêmes. Formellement, l'espace M considéré est le simplexe de dimension p -1 qu'on munit de la métrique de Fisher, qui est la métrique la plus naturelle pour cet usage. En utilisant l'application T : (x 1 , . . . , x p ) → (2 √ x 1 , . . . , 2 √ x p ), on peut montrer que le simplOnexe peut être identifié à l'hypersphère de dimension p -1 et de rayon 2. Cette dernière est un espace métrique CAT ( 1 2 ). En initialisant les points suffisamment proches et en traçant la courbe n → log ∆(X n ) on obtient la Figure 1.2 Figure 1.2 -Courbe n → log ∆ κ (X n ). Il s'agit d'une droite de pente négative -ce qui est en accord avec le théorème de convergence mentionné plus haut. On décèle la présence de bruit, dû à la nature stochastique de l'algorithme.

Les deux exemples cités plus haut ont la particularité d'être analysables dans un cadre moins général que celui des espaces métriques. Les espaces de matrices définies positives et le simplexe sont tous les deux des exemples de variétés riemanniennes. Il existe cependant des cas où les espaces de données sont purement métriques auxquels aucune structure différentielle ne peut être appliquée. Un exemple de tels espaces est celui des systèmes métamorphes.

Beaucoup de problèmes en robotique, en informatique, ou en biologie impliquent des systèmes dits reconfigurables ou métamorphes. Ces systèmes changent leur état suivant un ensemble de règles locales, pour passer d'un état A vers un autre état B. Le système doit déterminer la séquence de mouvements locaux qu'il doit exécuter [KHJ + 03], les arbres phylogénétiques [START_REF] Louis | Geometry of the space of phylogenetic trees[END_REF] et les robots métamorphes [START_REF] Ardila | Moving robots efficiently using the combinatorics of CAT(0) cubical complexes[END_REF] en sont des exemples.

Dans cette thèse nous avons cherché à appliquer l'algorithme RPM au cas des robots métamorphes. Un robot métamorphe est une collection de modules 1.4. APPLICATIONS individuels qui sont capables de se connecter/déconnecter les uns aux autres et de former une structure rigide, qu'on appelle une configuration ou état. Les modules individuels peuvent changer leur position relativement à leurs voisins suivant une série de règles locales, pourvu que le système reste connexe. Ceci permet au système de changer sa position et sa configuration de manière dynamique.

Certains robots métamorphes sont basés sur des grilles, c'est à dire que les modules de base occupent un ensemble discret de positions sur une grille. La grille peut être hexagonale, carrée, etc. Ces systèmes peuvent être décrits mathématiquement comme une série de points dans un graphe (voir l'appendice A). Par exemple, le bras robotique qui consiste en des liens attachés à l'intérieur d'une grille et dont l'une des extrémités est attachée au point (0, 0) de la grille (cf figure 1.3) est un robot métamorphe. On suppose ici qu'on dispose de plusieurs robots métamorphes connectés grâce à un réseau de communication. On cherche à amener tous les robots vers un même état commun sans avoir recours à un agent central, c'est-à-dire, en ayant uniquement recours au réseau de communications utilisé par les robots eux-mêmes.

Le point milieu de deux points quelconques est calculé via modification d'un algorithme d'estimation du plus court chemin [START_REF] Bacak | Computing medians and means in hadamard spaces[END_REF] entre deux points du complexe d'états du système. Contrairement aux cas mentionnés plus haut, le point milieu est ici relativement plus complexe à calculer. Là encore, on pourrait montrer que les prédictions du théorème de convergence mentionné plus haut se retrouvent en pratique.

CHAPTER 1. INTRODUCTION

Graphe variable

Dans un dernier travail, nous avons cherché à mesurer quel pourrait être l'impact d'un graphe qui change dans le temps. En particulier, on cherche à savoir si cela affecte les propriétés de convergence de l'algorithme (RPM).

Le réseau de N agents est représenté par un graphe où les noeuds forment un ensemble fixe mais les arêtes sont susceptibles de varier: G(t) = (V, E(t)) où E(t) est l'ensemble des arêtes à l'instant t. Si t 1 et t 2 sont deux instants distincts, on peut définir l'union de deux graphes

G(t 1 ) = (V, E(t 1 )) et G(t 2 ) = (V, E(t 2 )) par G(t 1 ) ∪ G(t 2 ) = (V, E(t 1 ) ∪ E(t 2 )).
L'algorithme étudié est rigoureusement le même. À chaque instant k il n'y a que deux agents qui communiquent dans tout le réseau: V k et W k . On suppose que les (V k , W k ) sont indépendants même s'il ne peuvent bien évidemment plus être identiquement distribués.

Il faut également adapter la fonction de désaccord en prenant en compte le fait que les degrés dépendent maintenant du temps:

Définition 2. ∆(x, k) = {v,w}∈E(k) (deg v (k) -1 + deg w (k) -1 )χ κ (d(x v , x w ))
On obtient alors le résultat suivant:

Théorème 2. On suppose qu'il existe T > 0 tel que pour tout k ≥ k 0 , G(k) ∪ • • • ∪ G(k + T ) soit
un graphe connexe, où k 0 désigne un entier. On suppose aussi que le diamètre de l'ensemble {X 1 (0), . . . , X N (0)} est inférieur à Dκ 2 . Alors l'algorithme décrit à la table RPM converge et il existe L ∈ (-1, 0) tel que:

ED κ (k) ≤ exp(Lk) Avec: D κ (k) = k+T n=k ∆ κ (X(n))

Organisation du mémoire de thèse

Le manuscrit se divise en quatre chapitres dont les relations sont résumées par le schéma représenté à la figure 1.4.

Production scientifique

Les travaux de recherches présentés dans ce manuscrit ont fait l'objet des publications suivantes 1.7. PRODUCTION SCIENTIFIQUE Chapter 2

Gossip in distributed networks

Gossip algorithms are iterative algorithms. Each agent starts with its own data (temperature, polluting substance concentration, etc.) and progressively exchanges with its neighbors, such that, in the end, all agents end up sharing the same data.

The data space, defined as the space where data belong, plays an important role. For instance, if there is a pre-identified special point in this space, such as 0, agents can agree to set their data straight to that point. However, it can occur that such a special point does not exist, and more importantly, we require the consensus configuration to be dependent on the initial state.

There is another very important distinction related to the data space, that we will denote from now on by M. Namely, in the case where M is a vector space, the existence of a scalar multiplication and addition greatly simplifies the algorithms. It is therefore quite natural that the first gossip algorithms took place in a Euclidean setting.

On the other hand, there is an invariant in both Euclidean and non-Euclidean cases, which is the communication framework. This framework encompasses the communication network topology, the degree of synchronization between agents and the way agents can exchange information. Let us describe this communication first and make the distinction according to the data space afterwards.

Communication Framework

Notations

Assume V is some finite set. We denote by P 2 (V ) the set of pairs of elements in V : P 2 (V ) = {{v, w} : v = w}. Notice that, by definition, for v = w, {v, w} = {w, v} whereas (v, w) = (w, v). In what follows, random variables are assumed to be functions from a probability space Ω equipped with its σ-field F and probability 20 CHAPTER 2. GOSSIP IN DISTRIBUTED NETWORKS measure P; x = X(ω) denotes the realization associated to ω ∈ Ω for random variable X. For any set S and any subset A of S, δ{A} denotes the indicator function defined over S that takes value 1 on A and 0 otherwise. If x = (x 1 , . . . , x N ) ∈ R N is an N -dimensional real vector then define : x := 1 N N i=1 x i which is the average value of the components of x.

Graph model

The notion of gossip protocol is usually tied to that of a distributed network i.e. a network where there does not exist a central fusion node that can communicate with all the others or where all the information could be routed and processed. This network is represented using a graph, with the agents being represented by the vertices of the graph and communication links by its edges.

A distributed network in our working definition must satisfy the following constraints:

• The communications and computational capacity of each node is very limited and each agent can communicate only with neighboring nodes in the communication graph.

• The network has no central fusion node.

• The topology of the network is not necessarily known to the agents.

Mathematically, we model a distributed network of N agents as a graph G = (V, E) where V is the set of vertices representing the nodes, (|V | = N ) and E ⊂ P 2 (V ) is the set of edges representing communication links between agents. A link e ∈ E is given by a pair {v, w} ∈ P 2 (V ) where v and w are two distinct agents in the network that are able to communicate directly. We have implicitly assumed that the graph is undirected, meaning that if an agent v ∈ V is able to communicate with an agent w ∈ V then the reverse communication is also possible. This assumption makes sense when all nodes are supposed identical and communication is fast compared to agents movements. When a communication link e = {v, w} exists between two agents, both agents are said to be neighbors and the link is denoted v ∼ w.

How nodes communicate between each other and coordinate their actions with respect to time is the subject of the next subsection.

Time model

In this work we consider only discrete-time models, meaning that the time parameter will be a discrete variable. This implies that the different communications, computations and update events will be occurring at distinct separate points in time.

There are two types of discrete-time synchronization models: synchronous and asynchronous.

In the synchronous model, multiple agents can communicate at the same time. The nodes perform calculations simultaneously and update their results at the same time. Various methods to enforce clock synchronization have been proposed in [START_REF] Schenato | A distributed consensus protocol for clock synchronization in wireless sensor network[END_REF][START_REF] Li | Global clock synchronization in sensor networks[END_REF].

In the asynchronous model (see [START_REF] Boyd | Randomized gossip algorithms[END_REF]), it is assumed that each agent possesses its own internal clock that ticks according to a Poisson process of intensity λ (the clocks are identically made), each clock is assumed to be independent of the others. When an agent's clock ticks, the agent is able to perform some computations and communicate with neighboring agents. This model is equivalent to that of a single global Poisson clock that ticks at a rate of N λ at times Z k , where Z k is a Poisson process i.e. {Z k+1 -Z k } are iid exponentials of rate N λ. Time is discretized according to the global clock ticks, the interval [Z k , Z k+1 ) denoting the k-th time slot.

To this picture we add the capability for any given agent v ∈ V awakened to awake a neighboring agent w ∈ N v in order to communicate with it within the same slot. This is a strong requirement that implies some degree of synchronization between the nodes. This requirement is still less strong than the completely synchronous network where time would be slotted commonly between nodes.

Data space

Each node v ∈ V stores data represented as an element x v belonging to some data space M (more restrictive assumptions on M will follow). Initially, each node v has a value x v (0) and x(0) = (x 1 (0), . . . , x N (0)) is the N -tuple of initial values of the network. We focus on iterative algorithms that tend to drive the network to a consensus state; meaning a state of the form x ∞ = (x ∞ , . . . , x ∞ ) with: x ∞ ∈ M. We denote by x v (k) the value stored by the agent v ∈ V at the k-th ticking of the global clock and x(k) = (x 1 (k), . . . , x N (k)) the global state of the network at instant k.

Euclidean gossip

Let us thence assume that the data space M is a Euclidean vector space. This case has been extensively studied, and its solution will serve as a template for other cases of more general data spaces. The Euclidean space encompasses many data spaces of practical interest (temperature, concentration of a polluting agent, etc).

CHAPTER 2. GOSSIP IN DISTRIBUTED NETWORKS

In what follows, it is going to turn out that we can safely assume, i.e. without loss of generality, that M consists of scalars only: gossip algorithms are processed the same way when M = R or M = R p with p > 1.

Previous approaches

We now review some well known approaches to tackle the problem of consensus in the Euclidean setting. One of the first attempts is due to M.H. DeGroot in the early 70's, even though his main goal was more related to social behavior than consensus in general networks. The idea is quite simple: each agent in the network averages its own value with the values of its neighbors. M.H. DeGroot proved that the scheme indeed converges to consensus. Later, Chaterjee and Seneta [START_REF] Chatterjee | Towards consensus: some convergence theorems on repeated averaging[END_REF] refined DeGroot's model, allowing the averaging weights to change over time. They provided sufficient conditions under which consensus can still be guaranteed. Another landmark was the work of Krause [Kra00] that slightly modified the algorithm taking averages only among the agents that have close data values. Krause was able to show that consensus can no more be guaranteed with this modification. Instead the network has a tendency to form clusters.

One of the studies that investigated consensus in a more general context than social behavior was the work of Tsitsiklis [START_REF] Tsitsiklis | Problems in Decentralized Decision Making and Computation[END_REF]. The consensus problem is no longer restricted to the case of opinion dynamics, its scope has been extended now to include distributed computation between agents. Each agent of the network now stores a data value and can potentially -in the case of distributed optimizationhave a local cost function that it seeks to minimize. The communication between agents is no longer assumed to be instantaneous and synchronization is no longer perfect. The consensus protocol in this case must take into account the synchronization delays and the fact that not every two agents can directly communicate with one another. A modifed version of the gossip protocol has been proposed by the author and has been proven to converge to consensus under certain communications assumptions.

Another interesting question is whether it is possible to devise a modified version of the distributed gossip protocol so that consensus is achieved in a finite series of steps rather than being asymptotically approached. In [START_REF] Julien | Finite-time consensus using stochastic matrices with positive diagonals[END_REF] the authors have shown that in some specific network and communication situations, there exists a sequence of communication and averaging steps that lead to a consensus in a finite number of iterations. This sequence of steps can be characterized using matrix notation, where each iteration is seen as the application of a linear operator to the vector of all data points stored by the agents. If the underlying communications graph of the network is undirected and connected, then there exists a finite series of matrices that drive the system towards a consensus state. If the underlying communications graph is directed, further assumptions need to be made in order to guarantee finite time consensus.

Consensus in opinion dynamics

In [START_REF] Morris | Reaching a consensus[END_REF] the author studies consensus in the context of opinion dynamics. Consider a group of N agents that must estimate some parameter θ. Each agent i ∈ {1, . . . , N } has its own probability distribution F i that describes its opinion of what θ is. In what follows we can assume without loss of generality that the F i 's are scalars. Indeed, since all the following operations are pointwise operations, the mathematical treatment of the problem with scalars, instead of functions, will remain the same. Our goal will be getting all the agents to agree on a common scalar F c . The form of which is F C = N i=1 p i F i with: N i=1 p i = 1. The solution proposed by De Groot is a discrete time iterative process where at each step, one agent updates its value by averaging it with the values of the other agents. In mathematical terms, if at step k -1 the value of agent i is F i,k-1 , then the update at step k is:

F i,k = j p i,j F j,k-1 (2.1)
The numbers p i,j ≥ 0 are such that: N j=1 p i,j = 1, they represent the different weights an agent i gives to other agents opinions. These numbers form an N × N matrix: P = (p i,j ) 1≤i,j≤N . The global state of the system at iteration k is denoted by: F k = (F 1,k , . . . , F N,k ).

The update relation in equation 2.1 can be rewritten in matrix form as:

F k = P F k-1 = P k F 0
The components of the matrix P k are denoted: (p (k) ) ij . We say that the system converges towards a consensus state if and only if for any initial state F 0 , F k converges towards the same limit as k → ∞. The author shows that this condition is equivalent to saying that there exists a unique vector π = (π 1 , . . . , π N ) such that:

lim k→∞ p (k) ij = π j
for every i and j. The scalars π 1 , . . . , π N are such that:

1. π j ≥ 0 ∀j 2. N j=1 π j = 1 CHAPTER 2.

GOSSIP IN DISTRIBUTED NETWORKS

The consensus F C will be of the form: F C = N i=1 π i F i . De Groot proved, using Markov chain theory, that if there exists an integer k such that all of the elements of at least one column of P k has strictly positive elements, then a consensus will be reached. The asymptotic probability vector π will be the solution to the equation: πP = π.

Subsequent work by Chatterjee and Seneta [START_REF] Chatterjee | Towards consensus: some convergence theorems on repeated averaging[END_REF] extended the result to the case where the coefficients p ij vary with time. In this case the update rule becomes:

F k = P (k)F k-1 = P (k)P (k -1) . . . P (1)F 0
where (P (k)) k≥0 = ((p i,j (k)) 1≤i,j≤N ) k≥0 is a sequence of row stochastic matrices.

Denote by U r,k the sequence of matrices U r,k = P (r + k) . . . P (r + 2)P (r + 1). The sequence is said to be strongly ergodic if and only if for any r ≥ 0 there exists a probability vector d r such that:

lim k→∞ U r,k = 1d T r
Strong ergodicity indicates that opinions converge towards a same fixed value. The authors prove the following theorem that establishes sufficient conditions for consensus:

Theorem 1. [CS77] Let G 1 be the class of regular stochastic matrices (see ap- pendix A, definition 32). If ∀r ≥ 0, ∀k ≥ 1, U r,k ∈ G 1 and ∃δ > 0 such that: ∀k ≥ 1, min i,j {p i,j (k)|p i,j (k) = 0} ≥ δ > 0 ,
then strong ergodicity is obtained.

The opinion dynamics models seen up until now have common properties: They are linear, and they seek to establish how consensus is reached among all agents.

There are many observed situations in opinion dynamics where instead of reaching a single point of consensus, the agents tend to form clusters of opinions, causing a state of "polarization" instead of consensus. One of the first works to explain this phenomena using a nonlinear model was that of Krause in [START_REF] Krause | A discrete nonlinear and non-autonomous model of consensus formation[END_REF]. The author proposed a model where each agent only takes into account the opinions of agents whose opinions are close enough to its opinion. Let x 1 (k), . . . , x N (k) be the current state of the system at time k, for each i ∈ {1, . . . , N } and i > 0, define

I(i, k) = {1 ≤ j ≤ N | x i (k) -x j (k) < i },
the update rule is:

x i (k + 1) = I(i, k) -1 j∈I(i,k) x j (k) (2.2)
This update rule imposes that weights not only change with time but that they also depend on the current state of the system. Numerical experiments have shown that this update rule might drive the system towards a state where many clusters of nodes sharing the same opinion are formed. These clusters remain unchanged afterwards. A mathematical characterization of this phenomena has been given by Blondel et al. in [START_REF] Vincent D Blondel | On krause's multi-agent consensus model with state-dependent connectivity[END_REF], where the authors have established that when 1 = 2 = • • • = N = we have the following: Theorem 2. [BHT09] If the system evolves according to equation 2.2 then for any i ∈ {1, . . . , N }, x i (k) converges to a limit x * i in finite time. Moreover, for any i, j we have either

x * i = x * j or x * i -x * j >
The theorem states that over a finite amount of time, the opinions converge into clusters whose distance is at least . The number of clusters depends on the interaction constant . Clearly if is very small, there will be very few interactions between agents and thus, there will be more polarization of opinions, conversely if is large enough, the interaction would become sufficiently strong to pull the system towards a single consensus state.

The works of DeGroot, Chatterjee, Seneta, and Krause were among the pioneering works of distributed gossip algorithms and were aimed towards opinion dynamics. Furthermore, the agents were assumed to be perfectly synchronous, delays due to communications were neglected. A much more general framework has been presented in the work of Tsitsiklis in his Phd report [START_REF] Tsitsiklis | Problems in Decentralized Decision Making and Computation[END_REF], the next subsection will describe this work and its contributions.

Consensus in decentralized computational systems

In his PhD report [START_REF] Tsitsiklis | Problems in Decentralized Decision Making and Computation[END_REF], Tsitsiklis mentions the problem of distributed optimization in a network of agents that are referred to as processors. In addition to having data storage, each agent has a local cost function. The objective for these agents is to agree on a value that minimizes the sum of their local cost functions.

This situation is a generalization of the simple distributed averaging case, in that the local cost functions in the latter are quadratic functions.

Each agent is able to perform computations on its stored value or transmit it to another agent. Time is discretized according to a hypothetical global clock that ticks during each update event (computation performed by an agent). Such a global clock is needed only for analysis purposes, it will serve to describe the scheme used to achieve consensus. This time model differs only slightly from the one seen in section 2.1.3.

At the n-th tick of the global clock, each agent i ∈ {1, . . . , N } has a pending data point x i (n) ∈ M. When agent j sends a message to agent i that arrives at the n-th clock tick, the time the message takes to be transmitted is taken into account by introducing the variable t i,j (n), which is the time when the message was sent. The content of the received message is: x j (t i,j (n)). It is therefore assumed that t i,j ≤ n and t i,i = n, and denote by T i,j the set of all times agent i receives a message from agent j. Moreover, Tsitsiklis makes the assumption that T i,j is either empty or infinite. This assumption means that two agents either communicate an infinite amount of time or don't communicate at all, which greatly simplifies the framework.

time t i,j (n) Agent j sends message n Agent i receives message
The entire network of agents is modeled as a directed graph G = (V, E) whose vertices V = {1, . . . , N } correspond to the set of agents. An edge (j, i) belongs to E if and only if T i,j is infinite, i.e. if agent j sends messages to agent i an infinite amount of time. Since we assumed that agents either communicate an infinite number of time or don't communicate at all, this condition is equivalent to having at least one message sent from agent j to agent i.

Since we are interested in this work in the case of distributed consensus, we will restrict ourselves to the following scheme:

1. At iteration n, each agents i updates its current value once it has received all messages to x i (n + 1) through the formula:

x i (n + 1) = N j=1 a ij (n)x j (t ij (n))
Where the scalars a ij (n) verify:

• For every i, j, n: a ij (n) ≥ 0 • For every i, n: N j=1 a ij (n) = 1
• For every i, j, n such that: i = j, and n / ∈ T ij we have a ij (n) = 0. This is essentially a scheme similar to that of DeGroot with the addition of communication delays. The coefficients (a i,j (n)) i,j,n are averaging weights that change over time. In order to have convergence of the procedure towards a consensus state, further assumptions must be made on the weights:

Assumption 1. [Tsi84]
• G is strongly connected • There exists an α > 0 such that:

-If agent i receives a message from agent j at time n (i.e. if n ∈ T ij ), then a ij ≥ α.

-For every computing agent i, a ii (n) ≥ α

These conditions make it so that no message received by an agent receives a weight less than a fixed value α in its value update, it also ensures the past states of that agent have a lasting effect on its future ones.

Assumption 1 ensures that all links of the network of agents are active a sufficient number of times and that data is exchanged with enough regularity so that information is effectively propagated throughout the network.

Finally, the issue of communication delays is dealt with by introducing a uniform bound on all communication delays in the following assumption: Assumption 2. [START_REF] Tsitsiklis | Problems in Decentralized Decision Making and Computation[END_REF] Communication delays are bounded by some B 0 ≥ 0, i.e. for all i, j and n ∈ T ij we have n -

t ij (n) ≤ B 0 .
Given assumptions 1 and 2, Tsitsiklis proves the following consensus result: Theorem 3. Under all the previous assumptions, the distributed averaging protocol with communication delays converges towards a consensus state.

The process of attaining consensus does not have to be asymptotic. When the objective is simply to force the agents to agree on a common value, there are protocols that can drive a distributed network of agents to a consensus state in a finite number of iterations. An example of one of these protocols will be the focus of the next subsection.

A word on finite time consensus

The gossip methods seen so far lead to consensus in an asymptotic way, the convergence speed of the algorithm gives an estimate of the number of iterations necessary to get to a state as close as desired to a consensus state. However, if we want to achieve consensus in a finite number of iterations, we need a different approach than the ones seen so far.

In [START_REF] Julien | Finite-time consensus using stochastic matrices with positive diagonals[END_REF] the authors show that it is possible to achieve consensus in a finite number of iterations for any undirected connected graph, and for directed graphs under certain conditions.

The authors begin by restating the consensus problem in matrix terms. Given a graph G = (V, E) and a stochastic matrix A, we say that A is compatible with G if A i,j > 0 for i = j only if (j, i) ∈ E. We say that A has positive diagonal if A i,i > 0 for every i.

CHAPTER 2. GOSSIP IN DISTRIBUTED NETWORKS

Definition 1. [START_REF] Julien | Finite-time consensus using stochastic matrices with positive diagonals[END_REF] The sequence of matrices (A 1 , A 2 , . . . , A T ) with positive diagonal achieves finite-time consensus on a graph G if A t is compatible with G for t = 1, . .

. , T and A

T A T -1 . . . A 2 A 1 = 1
n 11 T The authors prove the following theorem for undirected graphs: Theorem 4. [START_REF] Julien | Finite-time consensus using stochastic matrices with positive diagonals[END_REF] If G contains a bidirectional spanning tree, then there exists a sequence of at most n(n-1) 2 stochastic matrices with positive diagonal that achieves average consensus on G. In particular, finite-time average consensus can be achieved on every undirected graph For directed graphs, the authors add another condition to strong connectedness which is that the graphs contain a simple directed cycle with even length.

All the historical approaches seen so far deal with data belonging to a linear vector space. We will see later that this treatment is not sufficient in covering many cases where agents store data that do not belong to a linear space. Subsequent historical approaches have addressed these non linear cases using descriptions and tools from Riemannian geometry. Most of the generalizations to Riemannian manifolds have been built on top of a specific gossip framework which we will present in the next section.

A generalizable Euclidean gossip framework

In this section we describe a framework for Euclidean gossip in both synchronous and asynchronous cases. We will use this framework to extend gossip to Riemannian data spaces and later in chapter 3 to a special class of general metric spaces, which is our main contribution. We will also explore how the model can be made to accommodate changes in network topology.

Synchronous Gossip

We now go back to the network model defined in the beginning of the chapter. In this section, we study how the gossip protocol relates to the concept of gradient descent, and how we can use that to achieve consensus in both the synchronous case and the asynchronous case.

Consider a network of N identical sensors, and assume that each agent v measures a scalar quantity x v ∈ R, set x(0) = (x 1 (0), . . . , x N (0)) and define the cost function:

φ(x(k)) = 1 2 N i∼j x i (k) -x j (k) 2 .
(2.3)

A GENERALIZABLE EUCLIDEAN GOSSIP FRAMEWORK

29

The index notation i ∼ j means that we are summing over pairs {i, j} ∈ E, where E is the set of edges of the communications graph, that is only assumed to be connected. Function φ measures how much disagreement is left in the network.

One approach for achieving consensus consists of using the gradient descent on the function φ.

x i (k + 1) = x i (k) -grad x i φ(x(k)),
(2.4) with 0 < < 1 deg(G) being the step-size. This is equivalent to:

x i (k + 1) = x i (k) - j∈N (i) (x i (k) -x j (k)) (2.5)
Function φ is convex, and its global minimum is 0. If the graph is connected, then the minimum is only attained at a consensus state i.e. when:

x 1 = x 2 = • • • = x N .
The update stated above requires that all nodes be synchronized, and that they need to wake up and update simultaneously. At each time step k, each agent i ∈ V broadcasts its current values to his graph neighbors and receives their values. It then performs the update rule shown in equation (2.5).

The following theorem establishes the convergence of synchronous gossip to a consensus state: Theorem 5. [OSFM07] If the process x(k) is generated according to equation 2.5 then:

lim n x(n) = x(0)1

Asynchronous pairwise gossip

In order to relax the strict synchronization requirement, we introduce a stochastic version of gradient descent optimization: The pairwise gossip protocol, which was proposed in [START_REF] Boyd | Randomized gossip algorithms[END_REF]. It is sometimes also referred to as the epidemic algorithm since it propagates information in a way similar to how a virus propagates in a biological community [DGH + 87, GKG06].

The difference with the previous approach lies in the time and communication models. This setting uses the asynchronous model based on independent, identical, Poisson clocks described in section 2.1.3. At a given time slot k, we denote by V k the agent whose clock ticks. This agent will randomly and uniformly activate a neighbor node W k to communicate and share data with. Therefore, at time k, the only communicating agents in the whole network are V k and W k . A single link is then active at each time, and the other links are not used. The above described time model implies that (V k , W k )'s are independent and identically distributed.

CHAPTER 2. GOSSIP IN DISTRIBUTED NETWORKS

We assume that the distribution of V k is uniform over the network while the distribution of W k is uniform in the neighborhood of V k . More precisely, the probability distribution of (V k , W k ) is given by:

P[V k = v, W k = w] = 1 N 1 deg(v) if v ∼ w 0 otherwise (2.6)
Notice that this probability is not symmetric in (v, w). It will turn out to be convenient to also consider directly the link {V k , W k }, forgetting which node was the first to wake up and which node was second. In this case P[{V k , W k } = {v, w}] is of course symmetric in (v, w). One has:

P[{V k , W k } = {v, w}] = 1 N 1 deg(v) + 1 deg(w) if v ∼ w 0 otherwise (2.7)
Thus, at each count of the virtual global clock one node v is selected uniformly randomly from the set of agents V ; node v then randomly selects a node w from N (v). Both nodes v and w then compute and update their value to xv+xw 2 . Denote, e i = [0, . . . , 0, 1, 0, . . . , 0] T ∈ R N , with 1 being at the i-th position. We can rewrite the update rule in a more concise form:

x(k) = M (k)x(k -1)
For each time slot k, M (k) is a sequence of iid random matrices such that:

M (k) = I N - (e i -e j )(e i -e j ) T 2
The following theorem establishes the convergence of asynchronous gossip to a consensus state at a linear rate:

Theorem 6. [BGPS06] If x(k) = (x v 1 (k), ..., x v N (k))
is the sequence generated by the gossip algorithm. Then we have:

• Almost sure convergence lim n x(n) = x(0)1 a.s.
(2.8)

• ∃L < 0 such that: Let (M i,j ) be a doubly stochastic time-varying matrix, i.e a matrix with nonnegative coefficients each of whose rows and columns sum to 1. We consider a gossip protocol where the update rule can be written as:

∀n : 1 n log E[ x(n) -x(0)1 2 ] ≤ L (2.9)

Case of directed time-varying graphs

x i (t + 1) = M i,i (t)x i (t) + j∈N i (t) M i,j (t)x j (t)
the update can also be written more concisely as:

x(t + 1) = M (t)x(t).
Assumption 3. [BT + 07] Assume that the coefficients M i,j (t) are required to satisfy:

• M i,i (t) ≥ 0, ∀i, t • M i,j = 0, if i ∈ N j (t)
where N j (t) is the set of neighbors of j ∈ V at time t.

• There exists some α > 0 such that if {i, j} ∈ E(t) then: M i,j (t) ≥ α • There exists some B such that for every t: E(t+1)∪• • •∪E(t+B) is strongly connected

The following theorem from [BT + 07] ensures convergence towards a consensus state.

Theorem 7. [BT + 07] There are nonnegative coefficients φ 1 , . . . , φ N such that:

lim t→∞ x i (t) = N j=1 φ j x j (0), ∀i
This theorem is important since it establishes the robustness of the protocol to changing graph topology and to non bidirectional communications, which are essential constraints of real world distributed systems.

CHAPTER 2. GOSSIP IN DISTRIBUTED NETWORKS

Limits of the Euclidean framework

The gossip algorithm in Euclidean setting is interesting when data can be seen as elements of a vector space, for example temperature or coordinate estimates. It is however inadequate in treating cases where data is non-linear. Take for example a network of cameras, each one having its own orientation. We would like the cameras to agree on a same direction. The data in this case belongs to a space of non Euclidean structure, for example, the 3-dimensional rotations group SO(3). Indeed the elements of SO(3) are rotation matrices, and if we consider two rotations R 1 and R 2 from SO(3) with two different axis, their average R 1 +R 2 2 is not a rotation, hence does not belong to SO(3). And since different rotations have different rotation axis trying to do a consensus on the rotation angles wont work either. Thus, the arithmetic averaging technique cannot be applied in this setting. The same problem arises if data belongs to a projective space P n , since two projective lines cannot be added.

In general, when treating non linear data spaces, we need to find a substitute for the notions of addition and averaging. In the next section, we shall deal with a special class of data spaces that were thoroughly studied, and on which we have a series of results: Riemannian manifolds.

Gossip in Riemannian manifolds

The study of gossip in the context of Riemannian manifolds (see appendix, section B.1 for a definition) has recently received attention. The work of Sarlette and Sepulchre [START_REF] Sarlette | Consensus optimization on manifolds[END_REF] use an embedding framework to extend regular gossip first into the unit circle and then into Riemannian spaces. This embedding approach alternates between adding data values in the Euclidean embedding space and re-projecting them in the data space M again. The notion of centroid of points is also derived from re-projecting the Euclidean centroid onto the Riemannian data space. The authors prove that asymptotic convergence towards a consensus state is achieved provided we have a certain set of conditions on the embedding space. The work of Tron et al [START_REF] Tron | Average consensus on Riemannian manifolds with bounded curvature[END_REF] proposes an intrinsic approach to consensus optimization in the synchronous case. Their approach relies on the notion of Riemannian gradient and the exponential function (see appendix B.1), that make it possible to define a Riemannian version of the gradient descent protocol. Finally, we shall look at an intrinsic asynchronous case that was first studied by Bonnabel in [START_REF] Bonnabel | Stochastic gradient descent on Riemannian manifolds[END_REF] which uses similar notions as Tron et al but with stochastic gradient descent, in order to accommodate for agents asynchronism.

Consensus in circular data

One of the first extensions of gossip to non-Euclidean data spaces is that of circular data by Sarlette et al. [START_REF] Sarlette | Global synchronization on the circle[END_REF].

Consider N agents whose stored data belong to the circle S 1 . The unit circle is 2π periodic which makes it fundamentally different from vector spaces. Each element of the circle can be uniquely represented by an angle θ ∈ [0, 2π[. A candidate for consensus protocol can be obtain by replacing the Euclidean update rule:

x i (k + 1) = x i (k) + j∈N i a ij (x i (k) -x j (k))
With the following update rule:

θ i (k + 1) = θ i (k) + j∈N i a ij sin(θ i (k) -θ j (k))
Defining z u (k) = exp(iθ u (k)) the update rule is equivalent to:

z u (k + 1) = z u (k) + Proj zu(k) v∈Nu a uv (z u (k) -z v (k))
where Proj zu(k) (x) is the projection of x ∈ C onto the tangent to the unit circle at

z u (k): Proj zu(k) (x) = iz u (k) z u (k), x . Proposition 1. [STBS08]
Consider a set of N agents evolving on S 1 according to the above update rule. If the underlying communications graph is connected and all agents are initially located within an open semicircle, then they converge towards a consensus state.

While local consensus is achievable using this protocol, for global consensus, a modified version of the pairwise gossip approach is more adapted.

This algorithm achieves global consensus on the unit circle when the underlying communications network between agents is a connected undirected graph.

In [START_REF] Sarlette | Consensus optimization on manifolds[END_REF] the authors show that the consensus results on circular data can be extended to the case of data belonging to a compact, connected homogeneous manifold.

The approach taken by the authors is to reformulate the consensus problem as a minimization problem of an appropriate cost function. The authors embed the data space M in a Euclidean space R m of sufficiently large dimension m. Then they define a cost function φ on R m that they link the notion of centroid of points. Consensus is no longer described as merely a state where all agents have the same value, instead it is redefined using the notion of Induced arithmetic mean. We shall see in the next section how these ideas are implemented.

CHAPTER 2. GOSSIP IN DISTRIBUTED NETWORKS

Algorithm Gossip on the circle

Input: a graph G = (V, E) and the initial nodes configuration θ v (0), v ∈ V for all k > 0 do At instant k, uniformly randomly choose a node V k from V and a node W k uniformly randomly from N (V k ). Update:

θ V k (k) = arg exp(iθ V k (k-1))+exp(iθ W k (k-1)) 2 θ W k (k) = arg exp(iθ V k (k-1))+exp(iθ W k (k-1)) 2 θ v (k) = θ v (k -1) for v ∈ {V k , W k } end for

Extension to Riemannian manifolds

Assume now that the data space is a Riemannian manifold (M, , ) (see appendix B.1 definitions 35 and 43)and that we place ourselves in the synchronous communications regime. Each agent v ∈ V has an initial measurement x v (0) ∈ M. We want a procedure that drives the agents towards a consensus state (x ∞ , . . . , x ∞ ) ∈ M N .

One way to achieve this, is to use methods of optimization. Recall that in the Euclidean setting, one could consider the function:

φ(x 1 , . . . , x N ) = N i=1 d 2 (x i , x) with x = 1 N N i=1
x i (0) and try to minimize it on R N using tools of distributed optimization. Gradient descent writes:

dx k dt (t) = -grad x k (φ)(x 1 , . . . , x N )
where α > 0 is the step size of the gradient descent. In discrete time, the algorithm becomes:

x k (t + 1) = x k (t) -grad x k (t) (φ)(x 1 (t), . . . , x N (t)) .
In a Riemannian setting, while the notion of a Riemannian gradient exists, the addition operation is not always well defined. In [START_REF] Sarlette | Consensus optimization on manifolds[END_REF], the authors circumvent this problem by embedding the data space in a Euclidean vector space of sufficiently large dimension, making the usual gradient descent update using Euclidean gradient and then re-projecting the result on the original data space. This is possible via the embedding theorem: Theorem 8. [START_REF] Han | Isometric embedding of Riemannian manifolds in Euclidean spaces[END_REF] Let M be a Riemannian manifold of dimension n, then there exists an integer m and a C ∞ isometry f : M → R m compatible with the metric , and the standard dot product on R m i.e. ∀p ∈ M u, v p = df p (u).df p (v) This theorem essentially states that any n-dimensional manifold can be isometrically embedded in a Euclidean space R m for m sufficiently large. This embedding will allow us to use Euclidean distance to find a suitable cost function on which we could apply distributed gradient descent. We assume also that M is a homogeneous manifold i.e. a manifold with a transitive action by some Lie group G (see appendix section B.1.1), the idea of homogeneity allows to focus on the relative positions between agents rather than their absolute positions on the manifold.

w k d 2 R n (x k , c)
This new definition of centroid, while analogous to that used in Euclidean geometry, does not necessarily reduce to a single point. Indeed in the context of Riemannian manifold the induced arithmetic can be a subset of M with ;ore than one element. Definition 3. The Euclidean centroid C e ∈ R m of N weighted agents located on M is:

C e = 1 W N k=1 w k x k ∈ R m where W = N k=1 w k
The sum here is the usual sum in R m .

CHAPTER 2. GOSSIP IN DISTRIBUTED NETWORKS

The centroid is linked to the IAM by the relationship:

IAM = arg max c∈M (c T C e )
Thus, computing the IAM involves searching for a global maximum of a linear function. If all local maxima of the function were global maxima, then we could use local optimization methods to compute the IAM. Thus, we make the following assumption:

Remark 1. Calculating x reduces to calculating the global minima of a linear function. To make the computation even easier; we can assume that the manifold M is such that the local minima of any linear function are also global minima. Since the notion of barycenter is no longer unique, [START_REF] Sarlette | Consensus optimization on manifolds[END_REF] updates the notion of consensus. Definition 4. A consensus configuration (x 1 , . . . , x N ) on a graph G = (V, E) and a manifold M is such that:

x k ∈ arg max c T N j=1 1 N x j ∀1 ≤ k ≤ N A synchronized configuration (x 1 , . . . , x N ) verifies x 1 = x 2 = • • • = x N
In order to transport the tools of distributed optimization to Riemannian manifold, we need a new cost function. By analogy with previous studies on circular data [START_REF] Sarlette | Discrete-time synchronization on the n-torus[END_REF], the cost function φ is defined as:

φ(x 1 . . . , x N ) = 1 2N 2 N k=1 N j=1 x T j x k
In the case of undirected graphs, a gradient flow for φ with step size α > 0 is:

dx k dt (t) = -2N 2 α grad k,M (φ)(x 1 , . . . , x N )
Where grad k,M (φ) is the k-th component of the riemannian gradient of φ. We can obtain this gradient from the Euclidean gradient grad

k,R m (φ)(x 1 , . . . , x N ) = 1 N 2 j x j . dx k dt = -2αN Proj T M,x k (C e (t) -x k )
where Proj T M,x k is the projection operator on the tangent space T x k M at x k . The discrete time algorithm has the form:

x k (t + 1) = x k (t) -2αN Proj T M,x k (C e (t) -x k (t))
In order to characterize the convergence properties of the algorithm, we need the following definitions.

Definition 5 (Lyapunov stability). [HSD12] X ∞ is a stable equilibrium if for every neighborhood U of X ∞ there is a neighborhood O ⊂ U of X ∞ such that every X(t) starting in O remains in U for all t ≥ 0 Definition 6 (Asymptotic stability). [HSD12] An equilibrium X ∞ ∈ M N is
asymptotically stable if it is Lyapunov stable and additionally O can be chosen so that: d(X(t), X ∞ ) → 0 as t → ∞ for any initial X(0).

The following proposition, whose proof can be found in [START_REF] Sarlette | Consensus optimization on manifolds[END_REF], establishes asymptotic convergence of the gradient descent algorithm.

Proposition 2. [SS09]

If the manifold M satisfies assumptions 4 and 5 and if α > 0, then all stable equilibrium are consensus configurations.

If the graph G = (V, E) is an undirected, connected graph, then stable equilibrium are synchronized states.

While this approach leads to consensus in a computationally efficient way, it remains highly dependent on the embedding of the manifold, on which additional conditions are imposed. It guarantees only asymptotic stability which is different from convergence.

An intrinsic approach, using only the properties of the manifold M, addresses these issues. This is object of the following section.

The intrinsic approach

The synchronous case Let M be a connected, geodesically complete Riemannian manifold (see definition 44). This implies via Hopf-Rinow theorem [START_REF] Chavel | Riemannian Geometry[END_REF]p.26] that between any two points there exists a minimal geodesic. The unique geodesic γ such that: γ(0) = p and γ(0) = X, can be written in the form: γ(t) = exp p (tX).

We would like to find the minima of a smooth function φ : M → R. Given an initial point x 0 ∈ M, it is possible to define an iterative algorithm that is purely intrinsic using the notions of geodesic and the exponential function. The algorithm would generate a sequence x(k) such that:

CHAPTER 2. GOSSIP IN DISTRIBUTED NETWORKS x(0) = x 0 x(k + 1) = exp x(k) (-k D k )
with D k the direction of descent and (k) the (possibly time-varying) step size of the descent.

The method used in determining the direction D k and stepsize k will determine the convergence proprieties of the sequences x(k) and f (x(k)).

Following the Euclidean gradient descent approach, [TAV11] chooses a direction verifying:

grad f (x(k)), D k < 0
We then determine (k) such that:

f (exp x(k) ( (k)D k )) < f (x(k + 1)) and set x(k + 1) = exp x(k) ( k D k ).
This iterative process continues until we have satisfied at least one stopping criteria, which are of the form:

grad(x(k)) ≤ η; |f (x(k + 1)) -f (x(k))| ≤ η .
In the steepest descent method, we choose D k = -grad f (x(k)):

x(k + 1) = exp x(k) (-k grad f (x(k)))
where k is chosen so that f (x(k + 1)) < f (x(k)). If grad f (x(k)) = 0 then we stop the algorithm.

In order to apply the gradient descent algorithm to solve the consensus problem, we use the following cost function:

φ : M N → R (x 1 . . . , x N ) → i∼j d 2 (x i , x j )
The gradient of φ with respect to the i-th component is [START_REF] Tron | Average consensus on Riemannian manifolds with bounded curvature[END_REF]:

grad x i φ = 1 2 grad x i j∈N (i) d 2 (x i , x j ) = - j∈N (i) exp -1 x i (x j ).
The idea is to use a distributed version of the Riemannian gradient descent with a constant step-size > 0, by iterating the following updates for each node i ∈ {1 . . . N } in parallel:

x i (k + 1) = exp x i (k) ( grad x i φ(x i (k)))
When M = R and the metric is the standard metric, we obtain the distributed Euclidean gradient descent.

We also want a constant step size > 0, it has to ensure that: φ(x(k + 1)) < φ(x(k)) for all k ≥ 0.

Definition 7. We say that a function φ is of uniformly bounded Hessian if and only if there exists a constant M such that for any x 0 ∈ M, v ∈ T x 0 M, and γ x 0 (t) = exp x 0 (tv) we have:

d 2 φ dt 2 ≤ M v 2
In order to see if such a step size exists, we will use the following lemma: Lemma 1. [START_REF] Bonnabel | Stochastic gradient descent on Riemannian manifolds[END_REF] For any function f : M → R twice continuously differentiable, p ∈ M and v ∈ T p M we have:

f (exp p (tv)) -f (p) ≤ t v, grad f (p) p + t 2 2 v 2 M f
where M f is a bound on the hessian of the function f .

The following proposition characterizes the admissible values of :

Proposition 3. [TAV11] Assume f : M → R is a twice differentiable function with bounded Hessian. Let x 0 ∈ M and γ x 0 (t) = exp(-t grad f (x 0 )). If t ∈ 0, 2 M f
(with M f being the uniform bound on the Hessian of f ), then we have f (γ x 0 (t)) -f (x 0 ) ≤ 0 Proof. Applying the previous lemma with v = -grad f (x 0 ) we get:

f (exp(-t grad f (x 0 ))) -f (x 0 ) ≤ -t grad f (x 0 ), grad f (x 0 ) x 0 + t 2 2 v 2 M f Thus: f (x 0 ) -f (exp(-t grad f (x 0 ))) ≥ t grad f (x 0 ) 2 1 - M f t 2
The right hand side of the inequality is positive when t ≤ 2 M f which implies that:

f (x 0 ) ≥ f (exp(-t grad f (x 0 ))).
In order to have a uniform bound on the cost function φ(x 1 , . . . , x N ) = i∼j d 2 (x i , x j ), we make the additional assumption that M is a manifold of bounded curvature, this gives us the following uniform bound (see: Tron et al [START_REF] Tron | Average consensus on Riemannian manifolds with bounded curvature[END_REF]): Proposition 4. [START_REF] Tron | Average consensus on Riemannian manifolds with bounded curvature[END_REF] Assume that M is a manifold of bounded curvature, with curvature bounds δ and ∆. Then a universal bound on the Hessian of the function φ on the domain:

D = {(x 1 , . . . , x N ) ∈ M N : d(x i , x j ) < r M } is: M φ = deg(G) max 2, r M C δ (r M ) S δ (r M ) + 1 S ∆ (r M ) Function S κ is defined such that: S κ (t) = 1 √ κ sin( √ κt) when κ > 0, S κ (t) = t
when κ = 0, and S κ (t) = 1 √ κ sinh( κ t) when κ < 0.

Function C κ is defined such that: C κ = cos( √ κt) when κ > 0, C κ = 1 when κ = 0, and C κ = cosh( √ κt) when κ < 0.

The following theorem establishes the local convergence of the gradient descent algorithm.

Theorem 9. [START_REF] Tron | Average consensus on Riemannian manifolds with bounded curvature[END_REF] Assume that M is a Riemannian manifold with bounded curvature. Let S conv be the set defined as

S conv = {X = (x 1 , . . . , x N ) ∈ M|φ(X) ≤ (r M ) 2 2 diam(G) }.
If the initial set of points X(0) = (x 1 (0), . . . , x N (0)) is initialized in S conv , then the gradient descent sequence (X(k)) k∈N converges towards a consensus state.

For a complete proof, see [START_REF] Tron | Average consensus on Riemannian manifolds with bounded curvature[END_REF]. This gradient algorithm is a synchronous one since updates need be performed simultaneously. We now follow the work of [START_REF] Bonnabel | Stochastic gradient descent on Riemannian manifolds[END_REF] for the asynchronous case.

The asynchronous case

The objective of stochastic optimization consists of minimizing a cost function C(x) = E z H(z, x) = H(z, x)dP (z) which we assume here to be three times continuously differentiable with respect to x, where x is a minimization parameter belonging to a Riemannian manifold M. H(z, x) is such that E z H(z, x) = H(z, x)dP (z) = ∇C(x) and dP is is assumed to be unknown. The gradient descent update rule here has the form:

x k+1 = exp x k (-k H(z k , x k ))
where t is the time dependent stepsize which assumed to verify: 2 k < ∞ and k = +∞ We have the following convergence theorem: Theorem 10. [START_REF] Bonnabel | Stochastic gradient descent on Riemannian manifolds[END_REF] Suppose the stochastic gradient descent is applied on a connected Riemannian manifold M such that inj(M ) > 0, and the stepsize verify the relations described above. Assume that there exists a compact K such that w k ∈ K for all k ≥ 0. Assume also that H(x, w) is bounded on K, meaning that ∃A > 0 such that ∀z, and ∀x ∈ K: H(x, w) ≤ A.

Then C(x k ) converges almost surely and lim k→∞ grad C(x k ) = 0.

In the stochastic version of the algorithm we use the Poisson clock model previously used for the asynchronous Euclidean gossip. At each count of the virtual global clock one node v is selected uniformly randomly from the set of agents V . The node v then randomly selects a node w from N (v) and both nodes make the update:

x v (k + 1) = exp xv(k) ( k exp -1 xv(k) (x w (k))) x w (k + 1) = exp xw(k) ( k exp -1 xw(k) (x v (k)))
Meaning that the two agents advance towards each other along the geodesic [x v (k), x w (k)] with a small stepsize k . This is equivalent to applying the stochastic descent algorithm on the cost function:

C(x 1 . . . , x N ) = v∼w P[v, w]d 2 (x v , x w )
And:

H(x(k), V k , W k ) = v∼w 1 {V k =v,W k =w} d 2 (x v , x w )

Conclusion

In this chapter, we presented distributed gossip in the case of Euclidean and Riemannian data spaces in both synchronous and asynchronous cases. While Euclidean gossip provides satisfactory convergence results in synchronous as well as asynchronous cases, it is limited in its scope of application. This was the reason for introducing the Riemannian framework. However, convergence results for the Riemannian framework were not entirely satisfactory. Indeed, for the embedding approach, only an asymptotic stability result has been established with strong constraints on the embedding space. The intrinsic approach works well for the synchronous case, but in the asynchronous case we have only convergence in the case of non positive sectional curvature which limits the applicability of the result. A clear statement concerning convergence speed is also lacking.

Chapter 3

Our extension of gossip to CAT (κ) metric spaces

Motivation

In this chapter, we present our approach in generalizing the gossip algorithm to nonlinear spaces. We advocate that the CAT(κ) metric space framework generalizes and simplifies previous work on the consensus problem in non Euclidean spaces by avoiding usage of differential geometry tools. We mainly address the gossip problem in the asynchronous case by proposing a distributed gossip protocol: the Random Pairwise Midpoint (RPM) algorithm. We establish convergence to consensus state for data spaces with positive as well as negative sectional curvature bounds. Convergence speed at a linear rate is also established and tested via numerical simulations.

Generalities on metric spaces

First definitions

Let M be some set. A function d : M 2 → R is called a distance function if and only if the following conditions hold:

• d(x, y) ≥ 0 for all x, y ∈ M • ∀ x, y ∈ M: d(x, y) = 0 if and only if x = y • ∀ x, y ∈ M d(x, y) = d(y, x) • ∀ x, y, z ∈ M d(x, z) ≤ d(x, y) + d(y, z) 44CHAPTER 3.

OUR EXTENSION OF GOSSIP TO CAT (κ) METRIC SPACES

The set M equipped with a distance function is called a metric space and is denoted by (M, d).

Definition 8 (Geodesic, Segments). A path c : [0, l] → M, l ≥ 0 is said to be a geodesic if d(c(t), c(t )) = |t -t |, for all (t, t ) ∈ [0, l] 2 ; x = c(0) and y = c(1) are the endpoints of the geodesic and l = d(x, y) is the length of the geodesic. The image of c is called a geodesic segment with endpoints x and y. If there is a single segment with endpoints x and y, it is denoted [x, y].

Definition 9 (Midpoint). The midpoint of a segment [x, y] is denoted x+y 2 , it is defined as the unique point m such that d(x, m) = d(y, m) = d(x, y)/2.

Next, we shall construct the metric spaces M n κ which will serve as standard models against which one can compare more general metric spaces. They will play a central role in defining the notion of CAT (κ) metric spaces.

Model space M n κ

In order to properly define the model space, we need three prototype spaces: the Euclidean space, the sphere and the hyperbolic space. General model spaces are then simply derived by dilation.

Let us denote E n the vector space R n equipped with its standard Euclidean norm x 2 = n-1 i=0 x 2 i with x = (x 0 , . . . , x n-1 ) ∈ E n . Denote

S n = {(x 0 , . . . , x n ) ∈ E n+1 : n i=0
x 2 i = 1} , the n-dimensional unit Euclidean sphere and

H n = {(x 0 , . . . , x n ) ∈ E n+1 : (-x 2 0 + n i=1 x 2 i ) = -1, x 0 > 0} ,
one sheet of a two-sheets n-dimensional hyperboloid. As a metric space

E n is equipped with distance d E (x, y) = x -y 2 , S n κ is equipped with distance 0 ≤ d S (x, y) ≤ π such that cos (d S (x, y)) = n i=0 x i y i ,
and H n is equipped with distance d H (x, y) ≥ 0 such that:

cosh (d H (x, y)) = x 0 y 0 - n i=1
x i y i .

GENERALITIES ON METRIC SPACES

Remark 2. Function d S is well defined since for (x, y) ∈ (S n ) 2 , -1 ≤

x i y i ≤ 1. Note that if (x 0 , . . . , x n ) ∈ H n then necessarily x 0 ≥ 1. For all (x, y) ∈ H n , n i=1

x i y i ≤ n i=1 x 2 i 1/2 n i=1 y 2 i 1/2 ≤ (x 2 0 -1) 1/2 (y 2 0 -1) 1/2 ≤ x 0 y 0 .
Thus, function d H is well defined. We refer the reader to [BH99, chap I.2] for the proof that d S and d H satisfy the requirements of distance functions (triangle inequality is not obvious).

In what follows we also use notation r κ = Dκ 2 .

Definition 10 (Comparison Triangles in M n κ ). Assume p, q and r are three points in M. A comparison triangle in M n κ refers to any three points, provided there exist, p, q and r in M n κ such that d(p, q) = d(p, q), d(q, r) = d(q, r), and d(r, p) = d(r, p).

Concerning the existence and uniqueness of such comparison triangles, we provide without proof the following proposition (see for instance [START_REF] Bridson | Metric Spaces of Non-Positive Curvature[END_REF] for a proof) .

Proposition 5. [BH99, chap I.2] Assume p, q and r are three points in M such that d(p, q) + d(q, r) + d(r, p) < 2D κ and max(d(p, q), d(q, r), d(r, p)) ≤ D κ . Then there exists a comparison triangle in M n κ . Moreover, this comparison triangle is unique up to an isometry. Remark 3. Note that the proposition is straightforward for κ = 0, where triangle inequality is a necessary and sufficient condition for the There is also a notion of angle in this "metric" context, as illustrated by the next definition.

Definition 11 (Alexandrov Angle). Assume c : [0, l] → M and c : [0, l ] → M are two geodesics such that x = c(0) = c (0), y = c(l) and z = c (l ). For each 0 ≤ t ≤ l and 0 ≤ t ≤ l , consider a comparison triangle (x, ȳt , zt ) in M 2 0 for the triplet (x, c(t), c (t )). The angle between c and c at x, denoted by ∠(c, c ), is defined by:

∠(c, c ) = lim →0 sup 0≤t,t ≤ ∠x ([x, ȳt ], [x, zt ])
where ∠x ([x, ȳt ], [x, zt ]) denotes the angle at x of the comparison triangle (x, ȳt , zt ). 46CHAPTER 3. OUR EXTENSION OF GOSSIP TO CAT (κ) METRIC SPACES

CAT (κ) metric spaces

The concepts from metric triangle geometry presented in the previous subsections yield the following definition of CAT (κ) spaces.

Definition 12 (CAT (κ) inequality). Assume (M, d) is a metric space and ∆ = (c 0 , c 1 , c 2 ) is a geodesic triangle with vertices p = c 0 (0), q = c 1 (0) and r = c 2 (0) and with perimeter strictly less than 2D κ . Let ∆ = (p, q, r) denote a comparison triangle in M 2 κ . ∆ is said to satisfy the CAT (κ) inequality if for any x = c 0 (t) and y = c 2 (t ), one has:

d(x, y) ≤ d(x, ȳ)
where x is the unique point of [p, q] such that d(p, x) = d(p, x) and ȳ on [p, r] such that d(p, y) = d(p, ȳ).

Remark 4. Applying this inequality to the case where κ ≤ 0 and d(q, r) = 0, the uniqueness of geodesics is recovered when κ ≤ 0.

Definition 13 (CAT (κ) metric space). A metric space (M, d) is said to be CAT (κ) if every geodesic triangle with perimeter less than 2D κ satisfies the CAT (κ) inequality.

Proposition 6. If x and y are two points in a CAT (0) space, there is a unique geodesic [x, y] and the midpoint x+y 2 is always well defined and unique.

One has the so-called Bruhat-Tits inequality [START_REF] Bridson | Metric Spaces of Non-Positive Curvature[END_REF], which is a straightforward application of the CAT (0) inequality: Proposition 7. [BH99] Assume (M, d) is CAT (0), and ∆ is a geodesic triangle with vertices (p, q, r) such that m is the midpoint of q and r along the side of the triangle. Then, 2d(p, m) 2 ≤ d(p, q) 2 + d(p, r) 2 -d(q, r) 2 /2 (3.1)

Remark 5. Note that CAT (0) inequality does apply to all geodesic triangles since the diameter restriction is void when κ ≤ 0.

An important notion for studying consensus algorithm is that of convexity. We define the notion of convex sets of metric spaces and study how convexity interacts with curvature.

Convex Sets

Convexity can have several meanings in the context of metric spaces (cf., e.g. [Cha06, p.403]).

Definition 14 (Convexity). A subset S of M is said to be convex when for every couple of points (x, y) ∈ S 2 , every geodesic segment γ joining x and y in (M, d) is such that γ ⊂ S.

The notion of convex hull is going to be useful in the sequel.

Definition 15 (Convex Hull). Assume S is a subset of M. Then the convex hull of S, denoted conv(S), is the intersection of all closed convex sets containing S.

One can easily check that conv(S) is indeed convex (and closed).

Proposition 8. If (M, d) is CAT (0), then for each x 0 ∈ M and r ≥ 0, every ball B x 0 ,r = {x ∈ M : d(x, x 0 ) ≤ r} is convex.

Proof. Consider x, y ∈ B x 0 ,r and a comparison triangle ∆(x 0 , x, y). Then for each z ∈ [x, y], CAT (0) inequality implies d(x 0 , z) ≤ max(d(x 0 , x), d(x 0 , y)) ≤ r. Hence z ∈ B x 0 ,r , which finishes the proof.

Proposition 9 ([BH99][prop. II.1.4). ] Let M denote a CAT (κ) metric space.

1. If x and y in M are such that d(x, y) < D κ , there exists a unique geodesic [x, y] joining them.

2. For any x ∈ M, the ball B x,r with r < r κ is convex.

Remark 6. CAT (κ) metric spaces appear in many situations:

• An example of a data space where CAT (0) geometries involved is the space of phylogenetic tree (see [START_REF] Louis | Geometry of the space of phylogenetic trees[END_REF]). CAT (0) geometry also appears in the context of reconfigurable systems where the space of all possible configurations of the system can be modeled by a CAT (0) cubical complex [START_REF] Ardila | Moving robots efficiently using the combinatorics of CAT(0) cubical complexes[END_REF].

• Examples of CAT (κ) spaces with κ > 0 are: The projective space, the Grassmanians, and the group of N -dimensional rotations. These spaces appear frequently in computer vision [SBS10, Lui12, TVT08].

For notational convenience, define the functions:

C κ (t) = cos( √ κt), S κ (t) = sin( √ κt) √ κ , χ κ (t) = 1 -C κ (t).
Lemma 2 (Law of Cosines). Given a complete manifold M n κ with constant sectional curvature κ and a geodesic triangle ∆(pqr) in M n κ , assume max{d(p, r), d(q, r), d(p, q)} < r and let α := prq. We have:

C κ (d(p, q)) = C κ (d(p, r))C κ (d(q, r)) + S κ (d(p, r))S κ (d(q, r)) cos(α) 48CHAPTER 3.

OUR EXTENSION OF GOSSIP TO CAT (κ) METRIC SPACES

We deduce the following result. Lemma 3. For for any triangle ∆(pqr) in M where m is the midpoint of [p, q] we have:

C κ (d(p, r)) + C κ (d(q, r)) ≤ 2C κ (d(m, r))C κ d(p, q) 2
Proof. Let us consider the triangle ∆(pqr) in M. We denote the geodesic midpoint of p and q by m = p+q 2 . Let ∆(p q r ) be a comparison triangle to ∆(pqr) in M n κ and m a comparison point to m. A fundamental characterization of CAT (κ) spaces is that d(r, m) < d(r , m ). We apply lemma 3 to comparison triangles ∆(p m r ) and ∆(r m q ).

• r p q m r p m × || γ r q m π -γ × || r' p' m' × || γ r' q' m' π -γ × || C κ (d (p , r )) = C κ (d (m , r ))C κ d (p , q ) 2 + S κ (d (m , r ))S κ d (p , q ) 2 cos(γ )
and

C κ (d (q , r )) = C κ (d (m , r; ))C κ d (p , q ) 2 +S κ (d (m , r ))S κ d (p , q ) 2 cos(π-γ )
summing the two equations we get:

C κ (d (p , r )) + C κ (d (q , r )) = 2C κ (d (m , r ))C κ d (p , q )
Since ∆(pqr) and ∆(p q r ) are comparison triangles:

C κ (d(p, r))+C κ (d(q, r)) = 2C κ (d (m , r ))C κ d(p,q) 2
. Since C κ is decreasing in [0, π √ K ] and d(r, m) < d(r , m ), we get:

C κ (d(p, r)) + C κ (d(q, r)) ≤ 2C κ (d(m, r))C κ d(p, q) 2 ;
which is the desired result.

Proposition 10 ([prop. II.1.4). ] [BH99] Let M denote a CAT (κ) metric space.

1. If x and y in M are such that d(x, y) < D κ , there exists a unique geodesic [x, y] joining them.

2. For any x ∈ M, the ball B x,r with r < r κ is convex.

Distributed consensus protocol proposal

The Random Pairwise Midpoint (RPM) algorithm

At each count of the virtual global clock one node v is selected uniformly randomly from the set of agents V ; the node v then randomly selects a node w from N (v). Both nodes v and w then compute and update their value to xv+xw 2 .

Algorithm RPM Input: a graph G = (V, E) and the initial nodes configuration X v (0), v ∈ V for all k > 0 do At instant k, uniformly randomly choose a node V k from V and a node W k uniformly randomly from N (V k ). Update:

x V k (k) = x V k (k-1)+x W k (k-1) 2 x W k (k) = x V k (k-1)+x W k (k-1) 2 x v (k) = x v (k -1) for v ∈ {V k , W k } end for
Remark 7. Please note that the previous algorithm is well defined in the case where data belongs to some CAT (0) space thanks to proposition 6. Otherwise, midpoints are not necessarily well-defined, and the algorithm should read: compute any midpoint between x V k (k -1) and x W k (k -1), if there exists any. However, it will be seen in the next sections that, in this case, the algorithm might fail to converge to a consensus. 50CHAPTER 3. OUR EXTENSION OF GOSSIP TO CAT (κ) METRIC SPACES Remark 8. The complexity to compute midpoints depends a lot on the considered space. For some data spaces (SO(3), the sphere, etc), the formula for the midpoint is available in closed form. In other instances (cubical complexes, pylogenetic spaces, etc . . . ) a closed form cannot be found but there exists an algorithm for computing the midpoints [START_REF] Bellachehab | Distributed consensus for metamorphic systems using a gossipalgorithm for cat (0) metric spaces[END_REF].

Convergence in the case of CAT (0) spaces

In order to study convergence, we recall the following assumptions. Assumption 6.

1. G = (V, E) is connected 2. (V k , W k ) k≥0 are i.i.d random variables, such that: (a) (V k , W k ) is independent from x 0 , . . . , x k-1 , (V 0 , W 0 ), . . . , (V k-1 , W k-1 ), (b) P[{V 0 , W 0 } = {v, w}] = 1 N (deg -1 (v) + deg -1 (w))δ{v ∼ w} Assumption 7. (M, d) is a complete CAT (0) metric space.
We now define the disagreement function.

Definition 16. Given a configuration x = (x 1 , . . . , x N ) ∈ M N , the disagreement function ∆(x) is given by:

∆(x) = v∼w {v,w}∈P 2 (V ) 1 N (deg(v) -1 + deg(w) -1 )d 2 (x v , x w )
Function ∆ measures how much disagreement is left in the network. Indeed, since the network is connected, ∆ is 0 if and only if the network is at consensus. It would be a graph Laplacian in the Euclidean setting. The normalizing term involving degrees gives less weight to more connected vertices, since they are more likely to be solicited by neighbors, in order to give equal weight to each edge in the graph. This normalization will turn out to be convenient in the analysis. Notice also that ∆(x) at each link vw is proportional to the variance of distance between x v and x w .

Another important function is the variance function.

Definition 17. Given a configuration x = (x 1 , . . . , x N ) ∈ M N , the variance function is defined as:

σ 2 (x) = 1 N {v,w}∈P 2 (V ) d 2 (x v , x w )

DISTRIBUTED CONSENSUS PROTOCOL PROPOSAL

51

Remark 9. The 1 N normalizing constant accounts for the fact that when d is the Euclidean distance then σ 2 (x) equals v∈V x v -x 2 , with x = 1 N v∈V x v . The next proposition measures the average decrease of variance at each iteration.

Proposition 11. [START_REF] Bellachehab | Random pairwise gossip on cat(κ) metric spaces[END_REF] Under Assumptions 6 and 7, for X k given by (RPM) algorithm, the following inequality holds, for every k ≥ 1.

E[σ 2 (x(k)) -σ 2 (x(k -1))] ≤ - 1 2 E[∆(x(k -1))]
Proof. Taking into account that at round k, two nodes with indices V k and W k woke up, it follows that:

N (σ 2 (x(k)) -σ 2 (x(k -1))) = -d 2 (x V k (k -1), x W k (k -1)) + u∈V u =V k ,u =W k T (V k , W k , u) where T (V k , W k , u) = 2d 2 (x u (k), M k )-d 2 (x u (k), x V k (k -1))-d 2 (x u (k), x W k (k -1)) and M k denotes the midpoint x V k (k-1)+x W k (k-1) 2 . Notice that x W k (k) = x V k (k) = M k
. Now, using the CAT(0) inequality, one has:

N (σ 2 (x(k)) -σ 2 (x(k -1))) ≤ - N 2 d 2 (x V k (k -1), x W k (k -1)) .
taking expectations on both sides and dividing by N gives:

E[σ 2 (x(k)) -σ 2 (x(k -1))] ≤ - 1 2 E[d 2 (x V k (k -1), x W k (k -1))] recalling that P[{V k , W k } = {u, v}] = 1 N ( 1 deg u + 1 deg v
) when u ∼ v and 0 otherwise, and that (V k , W k ) are independent from X k-1 , one can deduce: E) is an undirected connected graph, there exists a constant C G ≥ 1 depending on the graph only such that:

E[d 2 (x V k (k -1), x W k (k -1))] = E[∆(x(k -1))] Proposition 12. [BJ16] Assume G = (V,
∀x ∈ M N , 1 2 ∆(x) ≤ σ 2 (x) ≤ C G ∆(x) 52CHAPTER 3. OUR EXTENSION OF GOSSIP TO CAT (κ) METRIC SPACES Proof. First: ∆(x) = v∼w 1 N (deg(v) -1 + deg(w) -1 )d 2 (x v , x w ) ≤ 2 N v∼w d 2 (x v , x w ) ≤ 2 N {v,w}∈P 2 (V ) d 2 (x v , x w ) = 2σ 2 (x)
For the second inequality, consider v = w two vertices in V , not necessarily adjacent. Since G is connected, there exists a path u 0 = v, . . . , u l = w such that u i ∼ u i+1 . Then, using Cauchy-Schwartz inequality: Remark 10. Both functions ∆ and σ 2 measure disagreement in the network, ∆ takes into account the graph connectivity while σ 2 does not. The previous result shows that ∆ and σ 2 are nonetheless equivalent up to multiplicative constants.

d(x v , x w ) 2 ≤ l l-1 i=0 d 2 (x u i , x u i+1 ) ≤ C l-1 i=0 (deg(u i ) -1 + deg(u i+1 ) -1 )d 2 (x u i , x u i+1 ) with: C = deg(G) diam(G)
We now state a first convergence result.

Theorem 11 (Almost-sure convergence to consensus). [BJ16] Under Assumptions 6 and 7, there exists a random variable x ∞ = (x ∞,v ) v∈V , such that: (i) x k converges almost surely to x ∞ and, (ii

) almost surely, ∀(v, w) ∈ V 2 , x ∞,v = x ∞,w , i.e. x ∞ takes consensus values.
Proof. Let us first show that ∆(x k ) converges almost surely to 0. From proposition 11, E[σ 2 (x k )] is non-increasing; which implies again from proposition 11:

k E[∆(x k )] < 2σ 2 (x 0 ) < ∞ hence, k ∆(x k
) has a finite expectation and ∆(x k ) converges almost surely to 0. Therefore, using the first inequality in proposition 12, σ 2 (x k ) converges to 0. As

DISTRIBUTED CONSENSUS PROTOCOL PROPOSAL

53

a direct consequence, the diameter max{d(x v (k), x w (k)) : (v, w) ∈ V 2 } also tends to 0 when k goes to ∞. Now denote by S k the set {x v (k) : v ∈ V } and by conv(S k ) its convex hull. One has diam(conv(S k )) ≤ 2 diam(S k ): every ball centered at x v (k) with radius diam(S k ) is a convex set containing S k and hence conv(S k ). Moreover, using the definition of convexity, one has S k+1 ⊂ conv(S k ). Therefore conv(S k ) forms a family of nested closed sets with diameter converging to 0. It is an easy result that in a complete metric space, the intersection of a family of nested closed subsets with diameter converging to 0 reduces to a singleton.

Remark 11. A precise relationship between the distribution of x ∞ and x 0 seems out of the scope of this work. However, notice that the previous proof straightforwardly implies that x ∞ lies in the convex hull of the initial points {x 0 (v); v ∈ V }.

Actually the previous proof can be adapted to give information on the convergence speed of the algorithm. Let us first prove an elementary lemma.

Lemma 4. Assume a n is a sequence of nonnegative numbers such that a n+1 -a n ≤ -βa n with β ∈ (0, 1). Then,

∀n ≥ 0, a n ≤ a 0 exp(-βn) Proof. Indeed if l n = log a n , then l n+1 -l n ≤ log(1 -β) ≤ -β. Hence l n ≤ l 0 -βn.
Taking exponential on both side gives the expected result.

We are now in a position to prove the following result:

Theorem 12 (Convergence speed). [BJ16] Let x k = (x 1 (k), ..., x N (k)) denote the sequence of random variables generated by (RPM) algorithm. Under Assumptions 6 and 7, there exists L ∈ (-1, 0) such that ∀ k ∈ N:

Eσ 2 (x(k)) ≤ exp(Lk)
Proof. Denote by a n = Eσ 2 (x(k)). Using the same argument as in the proof of theorem 11 and proposition 12, we know that the constant L = -1 2C G verifies a n+1 -a n ≤ La n and L ∈ (-1, 0) since C G ≥ 1. We conclude using lemma 4.

Remark 12.

• Using Proposition 12, it is straightforward to see that an analogous inequality holds for E∆(x k ).

• The convergence rate places a linear bound of negative slope on log Eσ 2 (x k ).

This means that on average, the ∆ function converges to 0 at a linear rate. Remark 13. What we have shown so far is that for CAT (0) spaces, both convergence and convergence speed are similar to the Euclidean case; yet the proof techniques only rely on metric comparisons, whereas spectral techniques are mainly used in the Euclidean case (e.g. [START_REF] Boyd | Randomized gossip algorithms[END_REF]). 54CHAPTER 3. OUR EXTENSION OF GOSSIP TO CAT (κ) METRIC SPACES Remark 14. The convergence and speed results are still true in the case where instead of explicitly giving the probability of the gossiping on each link, we now only assume that it is strictly positive for neighboring nodes.

• This means that: P[{V 0 , W 0 } = {v, w}] = P v,w with P v,w > 0 if v ∼ w and P v,w = 0 otherwise.

• Proposition 11 remains true by changing the expression of the disagreement function to:

∆(X) = v,w∈P 2 (V ) P v,w d 2 (x v , x w )
Proposition 12 also remains correct by taking:

C G = N (N -1) diam(G) 2 min v∼w (P v,w )
.

Thus theorems 11 and 12 remain valid.

Remark 15. We can obtain the real time convergence speed. If K t is the Poisson process if the global clock of parameter N λ then we define the real time measurements vector as:

X(t) = (x 1 (K t ), . . . , x N (K t )), the variance function becomes σ(X(t)) = u,v d 2 (x u (K t ), x v (K t )).
We know that for any positive integer k we have:

E[σ(X(k))] ≤ exp(-Lk)
And that:

P (K t = k) = (N λt) k k! exp(-N λt)
Thus:

E[σ 2 (X(K t ))] = ∞ k=0 E[σ 2 (X(K t ))|K t = k]P (K t = k) = ∞ k=0 E[σ 2 (X(k))]P (K t = k) ≤ ∞ k=0 exp(-Lk) (N λt) k k! exp(-N λt) = exp(-N λt) ∞ k=0 (exp(-L)N λt) k k! 3.3. DISTRIBUTED CONSENSUS PROTOCOL PROPOSAL 55 = exp(-(1 -I)N λt) with I = exp(-L) < 1. And thus: E[σ 2 (X(K t ))] ≤ exp(-(1 -I)N λt)
3.3.3 Convergence in the case of CAT (κ) spaces with κ > 0

In this section, we replace Assumption 7 by the following:

Assumption 8.

1. κ > 0 2. (M, d) is a complete CAT (κ) metric space. 3. diam({x v (0) : v ∈ V }) < r κ
By proposition 10 we are ensured that Random Pairwise Midpoint algorithm is well-defined. Indeed, by convexity of balls with radius smaller than r κ , points will remain within distance less than r κ of each other. Moreover midpoints are well-defined and unique since r κ < D κ .

The trick used to study CAT (κ) configurations is to replace distance d(x, y) by: χ κ (d(x, y)) with χ κ = 1 -C κ being pointwise non negative. We adapt the definitions used in the CAT (0) setting as follows: Definition 18. For x ∈ M n define:

∆ κ (x) = 1 2N v∼w {v,w}∈E ( χ κ (d(x v , x w )) deg(v) + χ κ (d(x v , x w )) deg(w) ) σ 2 κ (x) = 2 N {v,w}∈P 2 (V ) χ κ (d(x v , x w ))
One can observe that for all k ≥ 0, (v, w) ∈ V 2 : σ 2 κ (X k ) ≥ 0 and ∆ κ (X k ) ≥ 0. Notice that σ 2 κ (x) = 0 implies that for all {v, w} ∈ P 2 (V ):

χ κ (d(v, w)) = 0; and, since 0 ≤ d(v, w) ≤ π 2 √
κ , it implies that d(v, w) = 0, hence the system is in a consensus state. Moreover, when κ → 0, ∆ κ → ∆ and σ 2 κ → σ 2 . The following proposition is a direct consequence of lemma 3. Proposition 13. [BJ16] Under Assumption 8, for any triangle ∆(pqr) in C where m is the midpoint of [p, q] we have:

χ κ (d(m, r)) ≤ χ κ (d(p, r)) + χ κ (d(q, r)) 2 56CHAPTER 3. OUR EXTENSION OF GOSSIP TO CAT (κ) METRIC SPACES Proof.
From lemma 3 we get:

C κ (d(p, r)) + C κ (d(q, r)) -2C κ (d(m, r)) ≤ 2C κ (d(m, r))C κ (d(p, q)) -2C κ (d(m, r))
since max{d(m, r), d(p, q)} < π 2 √ κ we have:

0 ≤ C κ (d(p, q)) ≤ 1 0 ≤ C κ (d(m, r)) ≤ 1
which means that:

2C κ (d(m, r))C κ (d(p, q)) -2C κ (d(m, r)) ≤ 0 and thus: 2χ κ (d(m, r)) ≤ χ κ (d(p, r)) + χ κ (d(q, r))
With this result, it is now possible to obtain an analogous result to that of proposition 11. The techniques are the same but the details differ slightly. For the sake of completeness, we give the details below.

Proposition 14. [BJ16] E[σ 2 κ (x k+1 ) -σ 2 κ (x k )] ≤ - 1 N E∆ κ (x k )
Proof. At round k, two nodes with indices V k and W k wake up, it follows that:

N (σ 2 κ (x k ) -σ 2 κ (x k-1 )) = -χ κ (d(x V k (k -1), x W k (k -1))) + u∈V u =V k ,u =W k T κ (V k , W k , u)
where T κ is defined as:

T κ (V k , W k , u) = 2χ κ (d(x u (k), M k )) -χ κ (d(x u (k), x V k (k -1))) -χ κ (d(x u (k), x W k (k -1))) .
Now, using the inequality of proposition 13, one gets that T κ (V k , W k , u) ≤ 0 and:

N (σ 2 κ (x k ) -σ 2 κ (x k-1 )) ≤ χ κ (d(x V k (k -1), x W k (k -1))) .
taking expectations on both sides and dividing by N gives:

N E[σ 2 κ (x k ) -σ 2 κ (x k-1 )] ≤ -E[χ κ (d(x V k (k -1), x W k (k -1)))]
using similar reasoning as in the proof of proposition 11 we have:

E[χ κ (d(x V k (k -1), x W k (k -1)))] = E[∆ κ (x k-1 )]
which yields:

E[σ 2 κ (x k+1 ) -σ 2 κ (x k )] ≤ - 1 N E∆ κ (x k )
Remark 16. Notice the constant 1/N is in the right hand side which differs from the case of non positive curvature (compare with Proposition 11).

In order to derive a convergence result, we need an analogous result to Proposition 12 for CAT (κ) spaces.

Proposition 15. [START_REF] Bellachehab | Random pairwise gossip on cat(κ) metric spaces[END_REF] Assume G = (V, E) is an undirected connected graph, there exists a constant C κ depending on the graph only such that:

∀x ∈ M N , κ π 2 ∆ κ (x) ≤ σ 2 κ (x) ≤ C κ ∆ κ (x)
Proof. One has:

2κ π 2 x 2 ≤ χ κ (x) ≤ κ 2 x 2 when 0 ≤ x < π 2 √ κ .
Hence, under Assumption 8, χ κ and d are equivalent. The result then follows from Proposition 15.

All the tools needed to show almost-sure convergence and speed are in place. The proofs of the following two results are exactly the same than in the CAT (0) case, with ∆ and σ replaced by ∆ κ and σ κ .

Theorem 13. [BJ16] Let x(k) = (x 1 (k), ..., x N (k)) denote the sequence generated by RPM algorithm, then under Assumptions 6 and 8, there exists a random variable x ∞ taking values in the consensus subspace, such that x k tends to x ∞ almost surely. Theorem 14. Let x(k) = (x 1 (k), ..., x N (k)) denote the sequence of random variables generated by algorithm RPM; under Assumptions 6 and 8, there exists L ∈ (-1, 0) such that,

E∆ κ (x k ) ≤ exp(Lk)
These results show that -provided all the initial points are close enough from each other, as detailed by Assumption 8.3 -the situation is the same as in non positive curvature, specifically, almost sure convergence taking place at least exponentially fast. Notice that, by contrast, there are no constraints on the initialization, for the result to hold true in CAT (0). Notice also that the radius involved in Assumption 8.3 depends on the curvature upper bound κ and ensures convexity of corresponding balls. It gives a hint that convexity plays an important role in the behavior of the algorithm, which is not surprising, since the algorithm basically amounts to taking random midpoints. 58CHAPTER 3. OUR EXTENSION OF GOSSIP TO CAT (κ) METRIC SPACES

Numerical applications

In this section we simulate the (RPM) algorithm for four examples. The first example is the space of covariance matrices; it is a Hadamard manifold (i.e., a complete, simply connected manifold with nonpositive sectional curvature, see, e.g. [Lan99, Chap XI.3]). The second is the metric graph, (a complex of (0, 1] segments), which is a CAT (0) metric space with no differential structure. The other two examples are of CAT (κ) spaces with κ > 0. They are the three dimensional unit sphere S 2 and three dimensional rotation matrices SO(3).

When one of the above mentioned spaces happens to be stable by addition and multiplication by a scalar (this is the case for positive definite matrices), we compare the performance of the RPM algorithm with that of the Arithmetic Gossip. In order to distinguish between the two algorithms, we use the term RPM for the Random Pairwie Midpoint algorithm and the term Arithmetic Gossip for the classical random pairwise algorithm

x n+1,v = x n+1,w = 1 2 (x n,v +x n,w ) [BGPS06]
which is equivalent to Midpoint Gossip when the distance is the Euclidean one.

The results of these comparisons, as we shall see, might depend on the distance function used to define the disagreement function, or equivalently, the variance function.

Positive definite matrices

The scenario in this experiment is as follows. Each sensor in the network estimates a covariance matrix for some observed multivariate process. Then the network seeks a consensus on these covariance matrices. We implemented the proposed algorithm on the of positive definite matrices Pos(n), [Lan99, chap. 12]. Pos(n) is equipped with distance

d(M, N ) 2 = tr{log(N -1/2 M N -1/2 ) log(N -1/2 M N -1/2 ) T } = log(M N -1 ) 2 and: M + N 2 = M 1/2 (M -1/2 N M -1/2 ) 1/2 M 1/2 .
using this distance, which comes from a Riemannian metric, Pos(n) is a Hadamard manifold [Lan99, p.326], see also [START_REF] Barbaresco | Information geometry of covariance matrix: Cartan-Siegel homogeneous bounded domains, Mostow/Berger fibration and Frechet median[END_REF] for an in-depth presentation, and as such, it is a CAT (0) space [Lan99, prop 3.4, p.311]. Using the previous relationships, it is straightforward to implement the RPM algorithm and compute log σ 2 M (n) at each iteration n; where x(n) = (x 1 (n), . . . , x N (n)) denotes the tuple of positive definite matrix held by the agents 1 ≤ v ≤ N at time n.

Regarding the initialization step, we generate N iid matrices x v (0), following a Wishart distribution on q × q positive definite matrices with parameters (q, 1), i.e.,

NUMERICAL APPLICATIONS

as

q k=1 M k,v M T k,v
where M k,v ∼ N (0, I q ) are independent standard multivariate Gaussian vectors of dimension q (in this numerical experiment q = 3 and N = 30).

Regarding the network, the experiments are carried out using randomly generated graphs. Such graphs have N nodes and a probability p ∈ (0, 1) that each two nodes are connected. For a given p, we generate a graph and check if it is connected; if it is, we run the RPM algorithm.

We plot in the same figure the curve σ 2 n : n → log Eσ 2 (x(n)) for graphs of N = 30 nodes with parameters p = 0.5, 0.7, and 0.9, and see how the speed of convergence is affected by the connectivity parameter p.

It is also interesting in this case to make a comparison for positive definite matrices between the RPM algorithm and the Euclidean arithmetic gossip. In figure 3.2, we plot n → σ 2 n where n is the number of iterations and σ 2 the sum of "non Euclidean" distances squared. The result suggests that the Euclidean gossip algorithm has a slight advantage over RPM gossip in terms of convergence speed. However, if we plot n → σ 2 n,E where

σ 2 n,E = 1 N {i,j}∈P 2 (V ) ||x i (n) -x j (n)|| 2
F and ||.|| F is the Frobenius Euclidean norm, the opposite seems to be true. As shown in figure 3.3 RPM algorithm performs slightly better. The midpoint gossip algorithm converges faster than Euclidean gossip when the variance is expressed in Euclidean distances.

Distributed classification

The situation is the following: Each node of the network must make a decision on a finite number p < ∞ of hypothesis shared between the elements of the network, which then must reach a consensus. Typical examples include intrusion detection, classification of planes by thermal sensor, etc.

Each node v ∈ V has a discrete probability distribution x v = (x 1,v , . . . , x p,v ), with x i,v being the probability assigned to the i-th hypothesis. Naturally we have the relation: p i=1 x v,i = 1. The data space considered here is the p -1 dimensional simplex S p with the fisher information metric [START_REF] Amari | Methods of Information Geometry[END_REF]. Using the map T : (x 1 , . . . , x p ) → (2 √ x 1 , . . . , 2 √ x p ), we can show that the simplex can be isometrically identified to the p -1 dimensional sphere with radius 2, which is a metric space of positive curvature κ = 1 2 . In this example, we shall consider the 3-dimensional simplex, which can be mapped to the quarter of the 3 dimensional sphere

S 2 = {(x, y, z) ∈ R 3 |x 2 + y 2 + z 2 = 4|x ≥ 0, y ≥ 0, z ≥ 0} equipped with the distance d(a, b) = cos -1 ( a, b ) such that 0 ≤ d(a, b) ≤ π for all a, b ∈ S 2 , which is of diameter r 1 = π
2 thus convex and thus CAT ( 1 2 ) (as a convex subset of the model space M 3 2 -with an abuse of language since M n κ is only defined up to an isometry). Note that the sphere does not possess a vector space structure and thus one cannot use Euclidean gossip without a re-projection step. n for the positive definite matrices space; the underlying network is the randomly generated graph for parameter p = 0.5, 0.7, 0.9. Because of the stochastic nature of the RPM algorithm, 50 simulations are done and we plot log σ 2 n . The variance function behaves like an exponential, in accordance with the prediction of theorem 12. We can also observe that the slope of log σ 2 n decreases with p which highlights the importance of graph connectivity in information mixing.

We sample a set of N = 30 points uniformly from Q as initial step. The expression of a geodesic γ(t) on Q such that γ(0) = p and γ(1) = q and p = q is given by: γ(t) = sin cos -1 ( p, q )t q -p, q p 1 -p, q 2 + cos cos -1 ( p, q )t p .

The total number of iterations is 500. We use a randomly generated graph. By plotting the variance function

σ 2 1 (X n ) = 1 N {i,j}∈P 2 (V ) χ 1 (d(x i (n), x j (n))
with respect to the number of iterations we get from figure 3.5 that n → log σ 2 1 (X n ) (or equivalently n → log ∆ 1 ) is a linear function with negative slope which is in accordance with theorem 14. Convergence slows as p decreases, this again highlights the influence of graph connectivity on the speed of convergence. n,E (using euclidean norm) for the positive definite matrices manifold, the full curve represents the RPM Algorithm, while the dashed curve represents Euclidean gossip. The midpoint gossip seems to have faster convergence.

Group of rotations

We shall be interested in what follows in the rotations group SO 3 of the Euclidean space R 3 . A rotation R a,θ acting on R 3 is characterized by its axis of rotation a ∈ R 3 and its rotation angle θ ∈ [-π, π). One of the possible applications of n for the positive definite matrices manifold. The full curve represents RPM gossip while the dashed curve represents the stochastic gradient descent method applied to the function σ 2 . Convergence is exponential in the first case while it is not for the second.

RPM algorithm with data in SO 3 is a network of 3D cameras [START_REF] Tron | Distributed pose averaging in camera networks via consensus on SE(3)[END_REF] that seeks to achieve a consensus in order to estimate the pose of an object.

The convexity radius for the 3-D rotations group is:

r κ = π 2 [TAV11]
. Toponogov comparison theorem [START_REF] Chavel | Riemannian Geometry[END_REF]p.400] shows that the geodesic ball B with center

I 3 and diameter r κ is a CAT ( 1 4 ) space. Let, (R a 1 ,θ 1 , R a 2 ,θ 2 ) ∈ B 2 . If -1 is not an eigenvalue of R T a 1 ,θ 1 R a 2 ,θ 2
, then the distance between the two elements is:

d(R a 1 ,θ 1 , R a 2 ,θ 2 ) 2 = 1 2 || log(R T a 1 ,θ 1 R a 2 ,θ 2 )|| 2 = [α] 2 where {e i[α] , e -i[α] , 1} are the eigenvalues of (R T a 1 ,θ 1 R a 2 ,θ 2 ), such that [α] ∈ (-π, π). If -1 is an eigenvalue of R T a 1 ,θ 1 R a 2 ,θ 2 then d(R a 1 ,θ 1 , R a 2 ,θ 2 ) = π, and (R a 1 ,θ 1 , R a 2 ,θ 2
) are said to be antipodal points.

For R a,θ ∈ B we have

d(I 3 , R a,θ ) = |θ| < π 4 , and for (R a 1 ,θ 1 , R a 2 ,θ 2 ) ∈ B 2 we have |[α]| = d(R a 1 ,θ 1 , R a 2 ,θ 2 ) ≤ d(I 3 , R a 1 ,θ 1 ) + d(I 3 , R a 2 ,θ 2 ) < π 2 which implies that -1 cannot be an eigenvalue of R T a 1 ,θ 1 R a 2 ,θ 2 . Thus B does not contain antipodal points.
For all (R a 1 ,θ 1 , R a 2 ,θ 2 ) ∈ B 2 there exists a unique minimizing geodesic γ(t) such that γ(0) = R a 1 ,θ 1 and γ(1) = R a 2 ,θ 2 , and it has the following expression: 1 (X n ) where n is the iteration index and M = S 2 . The underlying network is the randomly generated graph for parameters p = 0.5, 0.7, 0.9. Again, because of the stochastic nature of the RPM algorithm, 50 simulations are done and we plot log σ 2 n . The variance function behaves like an exponential, in accordance with the prediction of theorem 12; we can also observe that the slope of log σ 2 n decreases with p which highlights the importance of graph connectivity in information mixing.

γ(t) = R a 1 ,θ 1 exp t log(R T a 1 ,θ 1 R a 2 ,θ 2 ) since B is strongly convex [Cha06, p.404], γ(t) ∈ B for all t ∈ [0, 1]. The expression of the midpoint is thus: R a 1 ,θ 1 +R a 2 ,θ 2 2 = R a 1 ,θ 1 R a 2 ,θ 2 .

NUMERICAL APPLICATIONS

In the numerical simulation presented in this chapter, we sample N = 30 rotation matrices (R i ) 1≤i≤N ∈ B. The underlying graph is randomly generated. The results of the experiment are displayed in figure 3.6 where we plot the logarithm of: σ 2 1 4 (X n ) as a function of n. We observe that n → log σ 2 1 4 (X n ) decreases linearly, which is in accordance with theorem 14.

Conclusion

We presented in this chapter a new proposal: RPM algorithm, which achieves consensus at a linear rate in the asynchronous case for both positive and negative sectional curvature bounds. Our numerical results for RPM algorithm match with the predictions of the convergence and speed theorems established in section 3.3.1. The above seen examples can also be treated efficiently using Riemannian framework. The added value of the RPM algorithm is the simplification of proofs and an explicit result on the convergence rate in the asynchronous case.

In the next chapter, we will investigate a purely metric application that cannot be treated within Euclidean or Riemannian frameworks: Metamorphic/Reconfigurable 64CHAPTER 3. OUR EXTENSION OF GOSSIP TO CAT (κ) METRIC SPACES (n) where n is the iteration index, and M = SO 3 . The underlying network is the randomly generated graph for parameter p = 0.5, 0.7, 0.9. Because of the stochastic nature of the algorithm, 50 simulations are done and we plot log σ 2 n . The variance function behaves like an exponential, in accordance with the prediction of theorem 12; we can also observe that the slope of log σ 2 n decreases with p which highlights the importance of graph connectivity in information mixing.

systems. They constitute one example of a novel extension of gossip to cases where only a metric setting can be applied.

Chapter 4

Application of RPM algorithm to metamorphic systems

Introduction

So far, the examples of CAT (κ) data spaces where our RPM algorithm was applied could also be treated within the Riemannian framework. In this chapter, we apply the RPM algorithm to a purely metric data space where no differentiable structure can be applied.

Definitions and examples

There are many examples of metamorphic/reconfigurable systems, such as reconfigurable manufacturing systems [KHJ + 03], and phylogenetic trees [START_REF] Louis | Geometry of the space of phylogenetic trees[END_REF]. Another example, one in which we will be more interested in this chapter, is that of metamorphic robots. They were described by E.H. Ostergaard in [START_REF] Hallundbaek Østergaard | Design of the atron lattice-based selfreconfigurable robot[END_REF] as robotic systems that:

1. Consist of several identical and physically independent unit modules, 2. Their modules can be connected to each other in many possible ways in order to form rigid structures, 3. Their modules can disconnect and reconnect while the system is active, 4. They can change the way their modules are connected, i.e. they are fully automatic.

Some of these robots are lattice-based, meaning that the robotic modules that occupy a discrete set of possible positions, this set of possible positions forms a 66CHAPTER 4. APPLICATION OF RPM ALGORITHM TO METAMORPHIC SYSTEMS lattice. The nature of the lattice depends on the geometry of the modules, it can be hexagonal, squared, dodecahedral, etc. These metamorphic systems can be mathematically described as a collection of states on a graph (see section 4.3).

Representing the various states of a metamorphic system by their lattice configuration will prove to be insufficient for finding a simple consensus protocol. Indeed, the lattice representation does not provide an ordering of states. Following [START_REF] Abrams | State complexes for metamorphic robots[END_REF], we represent a system configuration as a point in a cubical complex S called the state complex (see also section 4.4 for a definition). The 0-dimensional skeleton of this complex is the set of states, and two vertices are linked by an edge if their corresponding states differ by a single action of a generator (see section 4.3). A k-cube of the complex represents k commutative movements -i.e. movements that are non-overlapping whatever their order.

An example of a metamorphic system is the robotic arm which consists of attached links, inside a grid with one of its extremities attached to the basepoint (0, 0) of the grid (see figure 4.1).

Figure 4.1 -Example of a lattice based reconfigurable system: the robotic arm. The edges in bold indicate the presence of a unit module, a black edge indicates its absence. The arm is attached at its basepoint (0, 0). Here, an elementary movement has been performed by the module at the end of the arm, which changes the overall form of the system.

We assume here that metamorphic systems form a network; two systems are connected whenever they are able to communicate with each other. Our aim is to synchronize all the systems that compose the network, i.e. all the systems should have the same configuration, as shown in the example of figure 4.2.

Modeling metamorphic systems

For a rigorous definition of metamorphic systems, we follow the approach of [START_REF] Abrams | State complexes for metamorphic robots[END_REF]. We represent the lattice by its dual graph G = (V(G), E(G)) whose vertices represent the individual cells of the lattice; two vertices are joined by an edge if and only if their corresponding cells are adjacent in the lattice. We associate to this graph a set of labels A on the set of vertices to indicate whether the corresponding cell is occupied or not and in the former case, whether it is occupied by an obstacle or by a module and of which type. A state of the system is any map U : G → A. The metamorphic system dynamically changes its state through a set of elementary movements which satisfy the following rules: (i) units cannot overlap during reconfiguration and (ii) overall connectivity should always be maintained. This is done via generators which are defined below: Definition 19. [START_REF] Ghrist | The geometry and topology of reconfiguration[END_REF] Let G = (V(G), E(G)) be a graph and A a set of labels. A generator φ is a collection of three objects:

• A support SUP(φ) ⊂ G which is a subgraph of G • A trace TR(φ) ⊂ SUP(φ) which is a subgraph of SUP(φ)
• An non-ordered pair of states u 0 , u 1 : V(SUP(φ)) → A verifying :

u 0 | V(SUP(φ))-V(TR(φ)) = u 1 | V(SUP(φ))-V(TR(φ))
where V(SUP(φ)) are the vertices of SUP(φ) 68CHAPTER

APPLICATION OF RPM ALGORITHM TO METAMORPHIC SYSTEMS

The support of the generator corresponds to the region of the graph that contains the necessary information to verify whether the movement is feasible (i.e. absence of obstacles, no modules overlapping, and connectivity of the system is maintained). The trace of the generator is the region of the graph where the movement actually takes place.

Definition 20. [GP07]

A generator is said to be admissible at a state U if: U | V(SUP(φ)) = û0 . The action of φ denoted by Φ maps a state u : V(G) → A to a new one Φ[u] : V(G) → A given by:

Φ[U ] := U : on V(G) -V(TR(φ)) û1 : on V(TR(φ))
Thus, a generator φ acts on a state U by modifying its restriction on the vertices of TR(φ) from u 0 to u 1 . This corresponds to an elementary movement of unit modules. However a metamorphic system should be able to perform many such elementary movements simultaneously. In order for this to be feasible, the movements have to be compatible, i.e., their simultaneous execution does not lead to module overlap or loss of system connectivity. For this, we introduce the following definition: Definition 21. [GP07] In a metamorphic system, a collection of generators {φ i } is said to be commutative if:

i = j ⇒ TR(φ i ) ∩ SUP(φ j ) = ∅,
Next we shall see an important tool for visually representing the space of available states of a metamorphic system which is the state complex.

The state complex

Definition

A cubical complex can be seen as a collection of cubes glued together using isometries.

Definition 22. [BH99, p.112] Let Γ ⊂ N and (C i ) i∈Γ be a collection of Euclidean unit cubes of various dimensions and X = i∈Γ C i a disjoint union of these cubes. A cubical complex S is the quotient of X by an equivalence relation ∼ such that if p : X → S is the natural projection then:

• For every i ∈ Γ the restriction p i of p to the cube C i is injective.

• If p i (C i ) ∩ p j (C j ) = ∅ then there is an isometry h i,j from a face T i ⊂ C i onto a face T j ⊂ C j such that p i (x) = p j (x ) if and only if x = h i,j (x).

Definition 23. [START_REF] Ghrist | The geometry and topology of reconfiguration[END_REF] The state complex S of a metamorphic system is a cubical complex. Each k-cube e (k) of S is an equivalence class [u, (φ i ) k i=1 ] where:

• (φ i ) k
i=1 is a k-tuple of commuting generators.

• u is a state for which the generators (φ i ) k i=1 are admissible.

• [u 0 , (φ i ) k i=1 ] = [u 1 ; (φ i ) k i=1 ]
if and only if ∃σ ∈ k such that: ∀i ∈ {1, . . . , k} we have: φ i = φ σ(i) and u 0 = u 1 on the subgraph: G -TR(φ α i )

The boundary of each k-cube is a collection of 2k faces:

∂[u; (φ α i ) k i=1 ] = k i=1 ([u; (φ α j ) j =i ] ∪ [φ α i [u]; (φ α j ) j =i ])
One advantage of using the cubical complex representation over that of the transition graph is that it shows which elementary movements can be performed simultaneously, and thus contains more information than the transition graph. It is not generally computationally feasible to construct the cubical complex associated to a given reconfigurable system but there are some interesting cases where it is possible to do so like the case of the robotic arm [START_REF] Ardila | Moving robots efficiently using the combinatorics of CAT(0) cubical complexes[END_REF].

Encoding as a partially ordered set

Given a cubical complex S and a vertex v (called the root vertex) of S, one can introduce a partial order relation in the set of vertices of S by stating that u ≺ w if and only if there is an edge path geodesic (i.e, a geodesic on the metric graph associated to S) from the root v to w that passes through u. The complex S can thus be seen as a partially ordered set. In [START_REF] Ardila | Geodesics in cat (0) cubical complexes[END_REF] it is shown that if one can choose the special node v such that the set of vertices of S equipped with the partial order relation ≺ is a poset with inconsistent pairs then S is a globally CAT (0) cubical complex. This last property guarantees the existence and uniqueness of the midpoint of any given two points, and allows us to apply the RPM algorithm on a network of agents whose data are encoded in a cubical complex. We assume in this chapter that all the studied complexes are CAT (0).

Reciprocally, if given a poset with inconsistent pairs (P, ≺) one can build a lattice whose summits are the order ideals of (P, ≺) that do not contain any inconsistent pairs (such order ideals are said to be consistent). An edge is drawn between two summits if their corresponding ideals differ by exactly one element. The vertices are ordered according to their corresponding ideals, u < w if and only

The standard embedding

One way to embed the cubical complex associated to a poset with inconsistent pairs of cardinal N is the so called standard embedding [START_REF] Ardila | Geodesics in cat (0) cubical complexes[END_REF]. An element u ∈ S is represented by a N -tuple u = (u 1 , . . . , u N ) where ∀i u i ∈ [0, 1], and if for 4.5. THE STANDARD EMBEDDING 71 some (i, j) ∈ {1, . . . , N } 2 we have: u j = 0 and u j > u i , then we must have: u i = 1. Also, if x i and x j are inconsistent then: u i u j = 0. Figure 4.5 shows an example of a cubical complex where the standard embedding coordinates of the points x and y are: x = (1; 0.25; 0.25; 0) and y = (1; 0.75; 1; 0.75).

Computing the midpoint

In [START_REF] Bacak | Computing medians and means in hadamard spaces[END_REF], an algorithm is given for computing means and medians in general CAT (0) metric spaces. We are here interested in finding the midpoint x+y 2 of any two given points x and y of a CAT (0) cubical complex S. We first determine the geodesic [x, y] between x and y.

Let x = (x 1 . . . x N ) and y = (y 1 . . . y N ) be the coordinates of x and y in the current standard embedding of S in Z N .

Then, we define v = (v 1 , . . . , v N ) and w = (w 1 , . . . , w N ) such that for i ∈ {1, . . . , N }:

v i = 0 if x i ≤ 0.5 v i = 1 if x i > 0.5
and:

w i = 0 if y i ≤ 0.5 w i = 1 if y i > 0.5
v and w are respectively the closest vertices of S to x and y (see figure 4.5).

Next, we re-root the cubical complex at v and change the labeling of its vertices consequently as well as the coordinates of x and y . To obtain the new coordinates of any point a = (a 1 , . . . , a N ) in the new standard embedding, we update: a i,new = 1 -a i,old if v i = 1 and a i,new = a i,old if v i = 0 (see figures 4.5 and 4.6).

We denote by I w = {i ∈ {1, . . . N }|w i = 1} the order ideal associated with the vertex w. Now that the complex is rerooted, we need to find the cubical sequence that contains the geodesic between x and y. According to [START_REF] Ardila | Geodesics in cat (0) cubical complexes[END_REF], a valid sequence (C k ) 1≤k≤n = (I k , M k ) 1≤k≤n of cubes containing the geodesic, consists of a sequence of order ideals

I 1 ⊂ I 2 ⊂ • • • ⊂ I n = I w and maximal antichains M k ⊂ I k , 1 ≤ k ≤ n (see section 4.4

for the representation of individual cubes of a complex).

To find this sequence, we take the subset of minimal elements of I w and call it I 1 , then set M 1 = I 1 . Then, in order to form

C k = (I k , M k ) from C k-1 = (I k-1 , M k-1 ),
we take the subset of minimal elements m k of Q -I k-1 and put I k = I k-1 ∪ m k and let M k be the maximal antichain of I k . Using this procedure until I k = P , we obtain a valid cube sequence which contains the geodesic. In the example of the figures 4.5 and 4.6, we have: After the cube sequence has been determined, we then have to find the 'breakpoints' from which the geodesic passes. The points {p 1 , . . . , p n-1 } are such that:

I 1 = {2, 3}, M 1 = {2, 3} and I 2 = {2, 3, 4} , M 2 = {2}.
x -p 1 + p 1 -p 2 + • • • + p n-1 -p n + p n -
y is minimal and that for each k ∈ {1, . . . , n -1} p k ∈ F k with F k being the common frontier of (I k , M k ) and (I k+1 , M k+1 ) which is the cubical cell (I k , M k ∩ M k+1 ). This problem can be cast as a touring problem with n polyhedral regions and 2n facets [START_REF] Ardila | Geodesics in cat (0) cubical complexes[END_REF].

min t 0 + t 1 + • • • + t n ∀k ∈ {0 . . . n} : t k ≥ p k -p k+1 p k ∈ F k , k = 1 . . . n p 0 = x, p n+1 = y
the touring problem is a second order cone optimization problem, for which numerical solvers exist. We solve the touring problem and obtain a series of points p 1 . . . p n and the distances t 1 . . . Knowing the sequence of points (p i ) 1≤i≤n and distances (t i ) 0≤i≤n , we want to determine the midpoint of x and y. We have two cases:

Case 1: n > 0 First we determine the cubical cell of (C k ) 1≤k≤n+1 that contains the midpoint. x

Let i 0 = min 1 ≤ i ≤ n|d(x, p i ) ≥ d(x,y)
+ y 2 = p i 0 + D t i 0 (p i 0 +1 -p i 0 )
with:

• D = 1 2 i 0 -1 k=0 t k -n+1 k=i 0 +1 t k -t i 0 : If 2 ≤ i 0 ≤ n -1. • D = 1 2 t i 0 : If i 0 = 1. • D = 1 2 t i 0 -i 0 -1 k=0 t k : If i 0 = n.
Case 2: n = 0. In this case, x and y belong to the same cubical cell and we have: x+y 2 = x+y 2 . In the rest of this section, we apply the RPM algorithm to two examples of lattice-based metamorphic systems: the robotic arm and the hexagonal lattice robot.

Application to the robotic arm

To understand why the robotic arm is CAT (0), one must construct a poset with inconsistent pairs associated with the state complex of the arm (see section 4.4.2). 74CHAPTER 4. APPLICATION OF RPM ALGORITHM TO METAMORPHIC SYSTEMS Definition 24. Define for any robotic arm with n articulations R n the set: P n = {(x, y)|y ≥ 0, y ≤ x, x ≤ n -1} and define the partial order relation ≤ such that: (x 1 , y 1 ) ≤ (x 2 , y 2 ) if and only if: x 1 ≤ x 2 , and y 1 ≤ y 2 .

Using the partially ordered set P n , we can show that the state complex of R n is CAT (0) through the following proposition: Proposition 16. [ABY12] Let S n be the cubical complex of R n rooted at the state where the arm is completely horizontal. Then there is a bijection between the possible states of R n and the order ideals of P n .

We plot the log-variance log σ 2 as a function of the number of iterations k, for N = 10 robotic arms of n = 7 joints (see figure 4.8), first on a complete graph and then for a path graph. In both cases we observe a linear curve of negative slope in accordance with the results of [START_REF] Bellachehab | Random pairwise gossip on CAT (κ) metric spaces[END_REF]. In the case of the path graph however the slope is smaller than for the complete graph.

Application to the planar hexagonal lattice

The same analysis is applied to the hexagonal lattice system [START_REF] Abrams | State complexes for metamorphic robots[END_REF] which is a connected aggregate of hexagonal shaped modules that occupy a planar lattice. Its graph representation and associated cubical complex can be seen in figure 4.9.

We observe similar patterns as for the robotic arms experiment; the function log σ 2 decreases at a linear rate for both the complete graph and the path graph cases.

Communication

At each time k, there are only two communicating agents in the whole network: V k and W k . We assume that (V k , W k ) are independent but not identically distributed anymore, the probability distribution of (V k , W k ) is given by:

P[V k = v, W k = w] = P v,w (k) = 1 deg v (k) + 1 deg w (k) if {v, w} ∈ E(k) 0 otherwise
We have P u,v (k) > 1 N , for any k > 0 and {u, v} ∈ E(k). We define the constant α > 0 as α = 1 N .

Data

Each node v ∈ V stores data represented as an element x v belonging to a CAT (0) space M. Initially each node v has a value x v (0) and X(0) = (x 1 (0), . . . , x N (0)) is the tuple of initial values of the network. The new scheme is similar to the one for static graphs: when the global clock of the system ticks for k-th time the measurements vector of the network is X(k -1), and the communication links are described by G(k) the underlying graph of the network at instant k. Agents V k and W k wake up, communicate and perform some computation, and then change the measurements vector to X(k).

Convergence results

Assumption 9. The following assumptions are adapted from [NO09]:

1. (M, d) is a CAT (0) metric space 2. (V k , W k ) k≥0 are independent random variables, such that:

• (V k , W k ) is independent from X(0), . . . , X(k-1), (V 0 , W 0 ), . . . , (V k-1 , W k-1 ), • P[{V k , W k } = {v, w}] = P v,w (k)δ {{v,w}∈E(k)} 3. ∃ T > 0 such that for any k > 0 we have: G(k) ∪ G(k + 1) ∪ • • • ∪ G(k + T )
is a connected graph.

We now define time variant versions of the disagreement and variance functions.

CONVERGENCE RESULTS

79

Definition 25. Given a configuration x = (x 1 , . . . , x N ) ∈ M N , the disagreement function at instant k is:

∆(x, k) = {v,w}∈E(k) P v,w (k)d 2 (x v , x w )
The variance function is defined for any configuration x as:

σ 2 (x) = 1 N {v,w}∈P 2 (V ) d 2 (x v , x w )
The next proposition measures the average decrease of variance at each iteration.

Proposition 17. Under Assumptions 9, for X k given by Algorithm RPM, the following inequality holds, for every k ≥ 1.

E[σ 2 (X(k)) -σ 2 (X(k -1))] ≤ - 1 2 E[∆(X(k -1), k)]
Next we shall need the following definitions:

Definition 26. For a given integer k ≥ 1 we define the stochastic processes:

L(k) = k+T n=k σ 2 (X(n)) D(k) = k+T n=k ∆(X(n), n + 1)
We shall see later that L reaches 0 if and only if the system reaches a consensus state.

Proposition 18. We have the following relationship between L and D for every integer k:

E[L(k + 1) -L(k)] ≤ - 1 2 E[D(k)]
Proof. We know that:

L(k) = k+T n=k σ 2 (X(n)). L(k + 1) -L(k) = k+T +1 n=k+1 σ 2 (X(n)) - k+T n=k σ 2 (X(n)) 80CHAPTER 5. RPM FOR TIME VARYING GRAPHS AND FOR DIRECTED GRAPHS = k+T n=k σ 2 (X(n + 1)) -σ 2 (X(n))
Taking the expected value and using proposition 17 we have:

E [L(k + 1) -L(k)] = k+T n=k E σ 2 (X(n + 1)) -σ 2 (X(n)) ≤ - 1 2 k+T n=k E[∆(X(n), n + 1)] = - 1 2 E [D(k)]
Which is the desired result.

Next we prove the following proposition:

Proposition 19. Given assumptions 9, there exists a constant C N,α,T depending on N, α and T only such that:

∀k > 0, L(k) ≤ C N,α,T D(k)
Proof. For a given k > 0, we have:

L(k) = k+T n=k {v,w}∈P 2 (V ) d 2 (x v (n), x w (n))
And:

D(k) = k+T n=k {v,w}∈E(n) P u,v (n)d 2 (x v (n -1), x w (n -1))
Given x v (n) and x w (n) with: {v, w} ∈ P 2 (V ) and k ≤ n ≤ k + T , we want to find a bound for d 2 (x v (n), x w (n)) of the form:

d 2 (x v (n), x w (n)) ≤ CD(k)
where the constant C is independent of v, w and n.

We know from assumptions 9 that k+T +1 n=k+1 G(n) is connected; and thus, there exists l > 0, u 1 , . . . , u l+1 ∈ V and k 1 . . . k l ∈ {k + 1, . . . , k + T + 1} such that:

• u 1 = v and u l+1 = w • ∀ i ∈ {0, . . . , l}: {u i , u i+1 } ∈ E(k i )

CONVERGENCE RESULTS

81

Next, define the sequence t 0 , . . . , t l such that: t 0 = t l+1 = n and for any i ∈ {1, . . . , l} :

t i = k i -1.
The idea is that while in general it may not be possible to find in G(n) a path between v and w, one can construct a path involving displacements along edges that are available at different times. From this path between v and w, we can create a path between x v (n) and x w (n) that involves only two types of displacements: displacements along an edge at a fixed time, and time increments (or decrements) along a fixed node.

This will allow us via the triangular inequality to write:

d(x v (n), x w (n)) ≤ l i=1 d(x u i (t i ), x u i+1 (t i )) + l i=0 d(x u i+1 (t i ), x u i+1 (t i+1 ))
The right hand side of this inequality is the sum of two terms that we will call T 1 and T 2 with:

T 1 = l i=1 d(x u i (t i ), x u i+1 (t i ))
and:

T 2 = l i=0 d(x u i+1 (t i ), x u i+1 (t i+1 ))
T 1 sums over displacements between nodes u i and u i+1 at time k i , while T 2 sums over displacements between time events k i and k i+1 at node u i .

Using Cauchy-Schwartz inequality, we have:

T 2 1 = ( l i=1 d(x u i (k i -1), x u i+1 (k i -1))) 2 ≤ l l i=1 d 2 (x u i (k i -1), x u i+1 (k i -1)) ≤ T (N -1) l i=1 {a,b}∈E(k i ) d 2 (x a (k i -1), x b (k i -1)) ≤ T (N -1) k+T i=k {a,b}∈E(k i ) d 2 (x a (i -1), x b (i -1)) ≤ T (N -1) α k+T +1 i=k+1 {a,b}∈E(i) P a,b (i)d 2 (x a (i -1), x b (i -1)) = T (N -1) α D(k) 82CHAPTER

RPM FOR TIME VARYING GRAPHS AND FOR DIRECTED GRAPHS

Thus, by taking the expected value on both sides we get:

E[T 2 1 ] ≤ T (N -1) α E[D(k)] (5.1)
For the second term we have: Taking C N,α,T = 2T 2 (N -1) 2 N (α+1) α gives us the desired result.

T 2 2 = (
We are now in a position to prove the following result:

Theorem 15 (Convergence speed). Let X k = (x 1 (k), ..., x N (k)) denote the sequence of random variables generated by Algorithm RPM, under Assumptions 9 , there exists L < 0 such that, Eσ 2 (L(k)) ≤ exp(Lk)

Proof. We know from propositions 18 and 19 that:

Eσ 2 (L(k + 1)) -Eσ 2 (L(k)) ≤ - 1 2C N,α,T Eσ 2 (L(k))
Denote by a n = Eσ 2 (L(k)) and β = 1 C N,α,T < 1, by applying lemma 4 we get the desired result with L = -β = -1 C N,α,T .

Theorem 16 (Almost-sure convergence to consensus). There exists a random variable X ∞ = (X ∞,v ) v∈V , such that: (i) X k converges almost surely to X ∞ and, (ii) almost surely, ∀(v, w) ∈ V 2 , X ∞,v = X ∞,w , i.e. X ∞ takes consensus values.

Proof. From Theorem 15, E[L(k)] is bounded by a decreasing exponential, which implies that L(k) converges almost surely to 0. As a direct consequence, the diameter max{d(x v (k), x w (k)) : (v, w) ∈ V 2 } also tends to 0 when k goes to ∞. And as seen previously in the static case, this implies the convergence towards a consensus state 5.3.1 The case of CAT (κ) spaces with k > 0

It is possible to extend the results above to any CAT (κ) metric space with κ > 0 provided some additional assumptions on the initial set of data points.

Assumption 10. The following assumptions are adapted from [NO09]:

1. (M, d) is a CAT (k) metric space with κ > 0 2. The initial data set is of diameter < D κ 3. (V k , W k ) k≥0 are i.i.d random variables, such that:

• (V k , W k ) is independent from X(0), . . . , X(k-1), (V 0 , W 0 ), . . . , (V k-1 , W k-1 ),

• P[{V k , W k } = {v, w}] = P u,v (k)δ {{v,w}∈E(k)} 4. ∃ T > 0 such that for any k > 0 we have:

G(k) ∪ G(k + 1) ∪ • • • ∪ G(k + T ) is a connected graph.
To prove that assumptions 10 lead to a consensus state we need to define the CAT (κ) version of the disagreement and variance functions. The CAT (κ)-variance function is defined for any configuration x as:

σ 2 κ (x) = 1 N {v,w}∈P 2 (V )
d 2 (x v , x w )

Definition 28. For a given integer k ≥ 1 we define the stochastic processes:

L κ (k) = k+T n=k σ 2 κ (X(n)) D κ (k) = k+T n=k ∆ κ (X(n), n + 1)
The following proposition is analogous to proposition 14 and can be derived using a similar proof Proposition 20.

E[σ 2 κ (x(k)) -σ 2 κ (x(k -1))] ≤ - 1 N E∆ κ (x(k -1), k)
Summing the relationship over a period we get:

Proposition 21. We have the following relationship between L κ and D kappa for every integer k and real number κ > 0:

E[L κ (k + 1) -L κ (k)] ≤ - 1 N E[D κ (k)]
We also have the proposition:

Proposition 22. Given assumptions 9, there exists a constant C N,α,κ,T depending on N, α, κ and T only such that:

∀k > 0, L(k) ≤ C N,α,κ,T D(k)
Proof. We have that 2κ π 2 x 2 ≤ χ κ (x) ≤ κ 2 x 2 when 0 ≤ x < π 2 √ κ . Hence, under Assumption 10, χ κ and d are equivalent and using proposition 19 we have the result propositions 21 and 22 coupled with lemma 4 lead to a convergence result with exponential speed for the CAT (κ) case similar to theorems 15 and 16 under assumptions 10.

Directed graphs

Motivation for directed graphs

In the case where two way communications become impossible, we want to adapt the framework and the (RPM) algorithm so as to be able to perform some form of gossip in the network.

Framework

The network topology is now modeled by a time-invariant directed graph G = (V, E), with E ⊂ V × V being the set of directed edges which represents the communication links between agents. We denote by e = (v, w) the communication link from v ∈ V towards w ∈ V , the set of neighbors of a given agent v is denoted by N (v). This time the 'neighbor' relationship is not symmetric, meaning that if w is a neighbor of v, that does not necessarily mean that w is a neighbor of v. For this reason we will drop the term 'neighbors' in what follows. Instead, we will cal N (v) the set of reachable agents of v.

The synchronization model of the agents is still the same, the system is modeled by a global Poisson clock of intensity N λ. At each tick of the clock one agent is awakened, this agent can perform some computation and communicate with his reachable agents. Like in the original (RPM) framework, the agent can awaken another agent from its set of reachable agents.

The adapted (RPM) algorithm is as follows, at each step k, one V k agent is awakened, this agent wakes up another agent W k form its reachable agents set (assuming it is not empty, else the agent does nothing), V k communicates its value x V k (K -1) to W k which then updates its value to x V k (k-1)+x W k (k-1) 2

, the algorithm becomes:

Algorithm Directed (RPM)

Input: a graph G = (V, E) and the initial nodes configuration X v (0), v ∈ V for all k > 0 do At instant k, uniformly randomly choose a node V k from V and a node W k uniformly randomly from N (V k ) (If N (V k ) is not empty). Update:

x W k (k) =
x V k (k-1)+x W k (k-1) 2

x v (k) = x v (k -1) for v = W k . end for 86CHAPTER 5. RPM FOR TIME VARYING GRAPHS AND FOR DIRECTED GRAPHS

Convergence study

We say that a directed graph G = (V, E) is strongly connected if and only if for every v, w ∈ V there exists a series of directed edges in E linking v to w and a series of edges (not necessarily the same), linking w to v. We make the following assumptions on the graph and data space: Assumption 11. G = (V, E) is a directed, strongly connected graph, and it does not change over time M is a CAT (0) metric space Using the directed (RPM) algorithm under the above assumptions we should be able to reach a consensus state with a linear rate of convergence. This expressed via the thorem: Proposition 23. Under Assumptions 11 and for X k given by the new (RPM) algorithm, the following inequality holds, for every k ≥ 1.

E[σ 2 (x k ) -σ 2 (x k-1 )] ≤ - 1 4 E[∆(x k-1 )]
Where ∆ and σ 2 are respectively the disagreement and variance function as defined in the static graphs case.

Proof. Taking into account that at round k, two nodes with indices V k and W k woke up, it follows using the Bruhat-Tits inequality:

N (σ 2 (x k ) -σ 2 (x k-1 )) ≤ - 1 4 d 2 (x V k (k -1), x W k (k -1)) + 1 2 u∈V u =V k ,u =W k T (V k , W k , u)
where

T (V k , W k , u) = d 2 (x u (k -1), x W k (k -1)) -d 2 (x u (k -1), x V k (k -1))
And Since V K is chosen randomly in the graph while

W k ∈ N (V K ) 1 2 E[d 2 (x V k (k -1), x u (k -1))] ≥ 1 2 E[d 2 (x u (k -1), x W k (k -1))]
Which gives the proposition.

Proposition 19 remains true under assumptions 11

Proposition 24. Given assumptions 11, there exists a constant C N depending on N and the graph only such that:

∀k > 0, σ 2 (k) ≤ C N ∆(k)
The two propositions plus lemma 4 gives the convergence and speed theorem.

Conclusion

The context of this thesis was on gossip protocol and how it can be used to solve the consensus problem in distributed sensor networks. We first reviewed how gossip is implemented for both Euclidean and Riemannian data spaces, in synchronous and asynchronous time models. We reviewed current techniques that allow distributed gradient descent and distributed averaging to be extended to Riemannian manifolds: either by embedding the manifold into a larger Euclidean space, or by using intrinsic geometry. We discussed the conditions under which one can obtain convergence of these algorithms. Next, we presented our proposal which extends the gossip protocol to the case of CAT (κ) metric spaces in the asynchronous pairwise case: the RPM algorithm. We identified a set of conditions on the curvature (κ ≤ 0) that guarantee a global convergence of RPM. For κ > 0, a local convergence result has been proven. The algorithm converges in each case towards an arbitrary consensus state at exponential speed. Our experiments with positive definite matrices, the sphere and the three dimensional special orthogonal group agree with theoretical results and validate our approach. We also saw how the CAT (κ) framework can lead to new applications that were not covered by Euclidean and Riemannian frameworks, such as metamorphic systems.

The CAT (κ) metric framework allows to generalize the pairwise gossip protocol in many cases of non Euclidean data while preserving the exponential rate of convergence to a consensus state. Our approach is however limited by its ability to find either a closed-form expression for the midpoint of any two points, or a least to find a way to compute it. Another limitation in the case of positive sectional curvature, is that we need extra conditions on the initial configuration of the system, to ensure that data points are close enough in their initial state.

An interesting question to examine would be whether or not one can drop the conditions on the initial configuration of the network in the case of CAT (κ) metric spaces with κ > 0. Dropping the condition on the initial state will likely cause Define also the Laplacian of the graph G as the N × N matrix (L) 1≤i,j≤N such that:

L i,j =      deg(i) if i = j -1 if i ∼ j 0 otherwise
The Laplacian can be written as: L = D-A with D = diag(deg(v 1 ), . . . , deg(v N )) and A the adjacency matrix of G. It is a symmetric matrix, its eigenvalues satisfy: This means that if i and j belong to the same connected component then x i = x j . If the graph G is connected then the only eigenspace associated with the eigenvalue 0 is Vect{(1, . . . , 1)}, this observation will be useful in a future section. is an n-dimensional manifold with two charts (U 1 , φ 1 ) and (U 2 , φ 2 ) with:

0 = λ L 1 ≤ λ L 2 ≤ • • • ≤ λ L N (
U 1 = {x ∈ S n |x n+1 > -1}, φ 1 (x) =
x 1 1 + x n+1 , . . . , x n 1 + x n+1 and:

U 2 = {x ∈ S n |x n+1 < 1}, φ 2 (x) =
x 1 1 -x n+1 , . . . , x n 1 -x n+1 (See figure B.3).

• The projective space RP n is the set of lines of R n+1 that pass through the origin. Another way to define it is: RP n = (R n+1 -{0})/ ∼ with ∼ being the equivalence relationship (x 1 , . . . , x n+1 ) ∼ (y 1 , . . . , y n+1 ) if and only if ∃λ ∈ R -{0} such that: (x 1 , . . . , x n+1 ) = (λy 1 , . . . , λy n+1 ).

For i = 1 . . . n + 1 denote the set:

U i = {[x 1 , . . . , x n+1 ] : x i = 0}
and the map

φ i : U i → R n [x 1 , . . . , x n+1 ] → x 1 x i , . . . , x n+1 x i
Equipped with the charts, (U i , φ i ) 1≤i≤n+1 is an n-dimensional smooth manifold.

(x 1 ,x 2 ,x 3 ) (y 1 , y 2 ) N S (0,0,1) (0,0,-1)

Figure B.
3 -Example of a chart for the 3-dimensional sphere. The point (x 1 , x 2 , x 3 ) with x 3 > 0 is mapped to the point (y 1 , y 2 ) = x 1 1-x 3 , x 2 1-x 3

Figure

  Figure1.1 -Courbe n → log ∆ κ (X n ). On voit ce qui s'apparente à une droite de pente négative -ce qui est en accord avec le théorème de convergence mentionné plus haut. Le bruit est dû à la nature stochastique de l'algorithme.

Figure 1

 1 Figure 1.3 -Un exemple de robot métamorphe: le bras robotique. Les arêtes en couleur représentent la présence d'un module, les arêtes en noir indiquent l'absence de module. Le bras est attaché à sa base au point (0, 0). Ici un mouvement élémentaire a été executé par le module au bout du bras, ce qui change la configuration du système.

Figure

  Figure 1.4

  Assumption 4. [SS09] M is a connected compact homogeneous manifold smoothly embedded in R m with the Euclidean norm y = r M constant over y ∈ M. The Lie group G acts as a subgroup of the orthogonal group on R m First, we define an equivalent for the notion of arithmetic average x of a sequence of points x 1 . . . x N : Definition 2. [SS09] The induced arithmetic mean (IAM ) ⊂ M of N agents of weights w k > 0 and positions x k ∈ M, k = 1 . . . N , is the set of points that globally minimize the weighted sum of squared Euclidean distances in R m x = arg min c∈M N k=1

Assumption 5 .

 5 [START_REF] Sarlette | Consensus optimization on manifolds[END_REF] The local minima of any linear function f (c) = c T b over c ∈ M with b fixed in R n are all global minima.

2,

  where deg(G) denotes the maximum degree max{deg(v) : v ∈ V } and diam(G) the diameter of G. Hence taking C G = (N -1) deg(G) 2 diam(G) ≥ 1, one recovers the desired inequality.

60CHAPTER 3 .Figure 3

 33 Figure 3.1 -Plot of n → log σ 2n for the positive definite matrices space; the underlying network is the randomly generated graph for parameter p = 0.5, 0.7, 0.9. Because of the stochastic nature of the RPM algorithm, 50 simulations are done and we plot log σ 2 n . The variance function behaves like an exponential, in accordance with the prediction of theorem 12. We can also observe that the slope of log σ 2 n decreases with p which highlights the importance of graph connectivity in information mixing.

Figure 3 Figure 3

 33 Figure 3.2 -Plot of n → log σ 2n (non euclidean distances) for the positive definite matrices manifold, the full curve represents the RPM algorithm, while the dashed curve represents the Euclidean gossip based on arithmetic averaging. Euclidean gossip seems to converge faster.

62CHAPTER 3 .Figure 3

 33 Figure 3.4 -Plot of n → log σ 2n for the positive definite matrices manifold. The full curve represents RPM gossip while the dashed curve represents the stochastic gradient descent method applied to the function σ 2 . Convergence is exponential in the first case while it is not for the second.

Figure 3

 3 Figure3.5 -Plot of n → log σ 2 1 (X n ) where n is the iteration index and M = S 2 . The underlying network is the randomly generated graph for parameters p = 0.5, 0.7, 0.9. Again, because of the stochastic nature of the RPM algorithm, 50 simulations are done and we plot log σ 2 n . The variance function behaves like an exponential, in accordance with the prediction of theorem 12; we can also observe that the slope of log σ 2 n decreases with p which highlights the importance of graph connectivity in information mixing.

Figure 3

 3 Figure 3.6 -Plot of n → log σ 2 1 4

Figure 4

 4 Figure 4.2 -In this example we are given five robotic arms. In the leftmost figure -describing the initial state -each arm has its own configuration. The rightmost figure represents a consensus state, in which all the arms share a common configuration.

70CHAPTER 4 .Figure 4 . 3 -Figure 4

 4434 Figure 4.3 -The cubical complex associated with the poset (P = {1, 2, 3, 4, 5, 6}, ≺) such that: 1 ≺ 4, 1 ≺ 5 and 4 ≺ 6. Each vertex is labeled by a consistent order ideal of P .

Figure 4 . 5 -Figure 4 . 6 -

 4546 Figure4.5 -Example of a cubical complex with an initial root vertex r. We want to compute the geodesic between the points x = (1, 0.25, 0, 0, 0) and y = (0, 0.75, 0, 1, 0.75)

Figure 4 . 7 -

 47 Figure4.7 -In this example, the cube complex and the points x and y are such that we have non co-linear sequence of points {p 1 , p 2 } that the geodesic between x and y passes through. The cube sequence {C 1 , C 2 , C 3 } contains this geodesic.

2, then we have: x+y 2 ∈ C i 0 and x+y 2 ∈

 22 [p i 0 , p i 0 +1 ]. Using the convention p 0 = x and p n+1 = y, the analytical expression of x+y 2 is:

Figure 4

 4 Figure 4.8 -In the leftmost figure, a robotic arm with n = 7 articulations; and in the rightmost figure, its associated state graph

Figure 4

 4 Figure 4.9 -In the left, a hexagonal lattice system, and in the right, its associated state graph

Figure 4 .

 4 Figure 4.11 -Plot of n → log σ 2 for a network of k = 10 robotic arm with n = 7 articulations. In the left figure, the underlying communication graph is the complete graph, while on the right it is the path graph. Because of the stochastic nature of the algorithm, the procedure is averaged over 30 runs. The resulting curve is a line of negative slope of larger magnitude for the complete graph than for the path graph.

  u i+1 (t i ), x u i+1 (t i+1 ))) 2 ≤ l l i=0 d 2 (x u i+1 (t i ), x u i+1 (t i+1 )) ≤ T (N -1) l i=0 a∈V d 2 (x a (t i ), x a (t i+1 )) ≤ T (N -1) k+T i=k+1 a∈V d 2 (x a (i), x a (i + 1))Taking the expected value on both sides we get:E[T 2 2 ] ≤ T (N -1) k+T i=k+1 a∈V E[E[d 2 (x a (i), x a (i + 1))|F i ]] ≤ T (N -1) ,b}∈E(i+1) P a,b (i + 1)d 2 (x a (i), x b (i))]Thus:E[T 2 2 ] ≤ T (N -1)E[D(k)] (5.2)By adding equations 5.1 and 5.2 we get:E[d 2 (x v (n), x w (n))] ≤ E[(T 1 + T 2 ) 2 ] ≤ 2E[(T 2 1 + T 2 2 )] ≤ 2T (N -1)(α + 1) α E[D(k)]And since:E[L(k)] = k+T n=k {v,w}∈P 2 (V ) E[d 2 (x v (n), x w (n))] we get:E[L(k)] ≤ 2T 2 (N -1) 2 N (α + 1) α E[D(k)]

84CHAPTER 5 .

 5 RPM FOR TIME VARYING GRAPHS AND FOR DIRECTED GRAPHSDefinition 27. Given a configuration x = (x 1 , . . . , x N ) ∈ M N , the CAT (κ)disagreement function at instant k is:∆ κ (x, k) = {v,w}∈E(k) P v,w (k)χ κ (d(x v , x w ))

Theorem 17 (

 17 Convergence speed). Let x k = (x 1 (k), ..., x N (k)) denote the sequence of random variables generated by the undirected (RPM) algorithm. Under Assumptions 11, there exists L ∈ (-1, 0) such that ∀ k ∈ N: Eσ 2 (x k ) ≤ exp(Lk) 88CHAPTER 5. RPM FOR TIME VARYING GRAPHS AND FOR DIRECTED GRAPHS Chapter 6

  see [HJ12, Th. 7.2.1]). The number of eigenvectors associated with this eigenvalue is equal to the number of connected components of the graph G [Chu97, Lemma 1.7].

  Before moving to the generalization of gossip to Riemannian manifolds, it is of practical importance to address the issue of what happens when the underlying graph topology changes with time. Taking time variability into account is important to study dynamics of mobile autonomous agents [OSM02, JL + 03, BT + 07], where new links can form and existing ones disappear.Given a network with a time changing graph G(t) = (V (t), E(t)), what conditions on G can still guarantee convergence? and at which rate?

Remerciements

Je voudrais tout d'abord remercier mon encadrant Jérémie Jakubowicz et mon directeur de thèse Pascal Bianchi qui m'ont accompagné durant toute ma thèse. Leur exigence et leur rigueur m'ont permis de m'améliorer et leur soutien m'a été d'une grande importance. Je tiens aussi à remercier Tijani Chahed pour ses remarques précieuses sur mon manuscrit.

Je tiens particulièrement à remercier Cédric Richard et Silvère Bonnabel pour avoir accepté de lire et de rapporter ma thèse. Je remercie également Anne Bouillard, Olivier Rioul, et Romain Couillet, examinateurs lors de ma soutenance.

Finalement, je tiens à remercier ma famille pour m'avoir poussé et supporté durant ce projet.

Chapter 5 RPM for time varying graphs and for directed graphs

Motivation for time varying graphs

While previous approaches in gossip generalization assumed a fixed network topology. We would like to see how changes in the underlying graph topology affects the convergence properties of the (RPM) algorithm,. Here, the graph is no longer assumed to be fixed with time; such restriction is important to study dynamics of mobile autonomous agents [OSM02, JL + 03, BT + 07], where new links can form and existing one disappear.

Framework

Network

Here, our network of N agents will be represented by a time varying graph G(t) = (V, E(t)), where E(t) is a time-varying set reflecting the time-dependent nature of the communication links. When at a given instant t, a communication link e = {v, w} ∈ E(t) exists between two agents, both agents are said to be neighbors. We denote by N (v, t) the set of all neighbors of the agent v ∈ V at instant t.

Also, if t 1 and t 2 are two distinct times, we can define the union of the graphs G(t 1 ) = (V, E(t 1 )) and G(t 2 ) = (V, E(t 2 )) as: G(t 1 ) ∪ G(t 2 ) = (V, E(t 1 ) ∪ E(t 2 )).

Synchronization

We assume the same Poisson clock model as in the asynchronous gossip case. We use the notation G(k) = (V, E(k)) to mean the set of communication links at 90 CHAPTER 6. CONCLUSION the loss of the uniqueness of midpoints of a given segment. However, the RPM algorithm could be modified so as to choose one of the midpoints at random. It could be the case that such a random choice eventually lead to a close enough configuation of points so that convergence can take place.

Appendix A A.1 Graph theory reminder

In the framework of pairwise gossip in a network, we usually represent the communication links of the network by a graph. Since future definitions will rely on graph theory concepts, this section contains reminders of notions like graph connectivity and the Laplacian matrix of a graph.

A.1.1 Fundamental notions

Definition 29. A graph G = (V, E) is composed of a finite set V of vertices and a finite set E whose elements are called edges. We can distinguish two main types of graphs:

• The directed graph: Where E is a subset of V × V , the edges are ordered pairs (v, w) with v and w ∈ V .

• The undirected graph: Where E is a subset of P 2 (V ), the edges are unordered pairs {v, w} = {w, v} with v and w in V .

In both types of graph we exclude single vertex edges or loops, which are of the form: (v, v) or {v, v}. In an undirected graph, if an edge exists between two nodes, they are said to be neighbors. Definition 30. Neighborhood and Degree We denote by N (v) the set of all graph neighbors of the agent v ∈ V . The number of elements in N (v) is referred to as the degree of v and denoted deg(v). The degree of a graph deg(G) is the maximum of its node degrees.

Definition 31. Connectivity An undirected graph G is said to be connected if and only if for every two agents u, v, there exists a finite sequence of vertices w 0 = u, . . . , w d = v such that:

This means that each two agents are at least indirectly related.

The distance between u and v is the cardinal of the smallest of such sequences minus one.

The diameter of the graph: diam(G) is the maximum distance between any two of its vertices.

For directed graphs we have the notion of strong connectivity which defines a graph G as being strongly connected if and only if for every two agents v and w in V there exists a finite sequence of vertices w 0 = u, . . . , w d = v such that:

Stochastic matrices

Definition 32. A N ×N matrix is called stochastic if all its entries are nonnegative and the sum of each column vector is 1. It is said ti be bi-stochastic if all its entries are nonnegative and the sum of each row and column vectors is 1.

A stochastic matrix is said to be regular if and only if all the entries of some power of the matrix are positive.

Proposition 25. [START_REF] Roger | Matrix analysis[END_REF] For any integer p, if A is a stochastic matrix, then A p is also a stochastic matrix.

Proposition 26 (Eigenvalues of stochastic matrices). [START_REF] Rk | Spectral graph theory[END_REF] If A is a stochastic matrix then:

• all the other eigenvalues of A have absolute value smaller or equal to 1.

A.1.3 Laplacian matrix

One important notion in the theory of graphs is that of the adjacency matrix, which provides a simple way to encode relationships between the nodes of a graph. The Laplacian of a graph will be very important for studying the convergence of synchronous gossip algorithms in this chapter.

Definition 33 (Adjacency matrix and Laplacian). If G = (V, E) is a graph with N vertices, then define the adjacency matrix as the N × N matrix (A) 1≤i,j≤N such that:

Manifolds and tangent space

If the structure we wish to study does not behave like a Euclidean space, we could see if locally we can still study it like a Euclidean space. This can be achieved via charts:

The dimension d may depend on the chart (U, φ).

The point of a chart is to reduce the study of U ∈ M to that of a subset of R n , the set M can thus be assigned a local coordinate system. If a point x ∈ M belongs to two charts (U 1 , φ 1 ) and (U 2 , φ 2 ) then the two charts must be compatible with one another. For example if a function f is defined on

U ϕ(U)

1 and f •φ -1 2 must have the same differentiability proprieties. This will allow us to transpose some notions of differentiable calculus to our set.

For this, the notion of Atlas is introduced, and as we shall see later, it will allow us to define the notions of differentiable function in a consistent manner.

95

Definition 35 (Atlas). Let M be a set; a C ∞ -atlas of M is a collection of charts (U α , φ α ) of the set M such that:

Equipped with an atlas, M is called a smooth real manifold. And if M is connected, then d is independent of the chosen chart (U, φ), and we say that M is a d-dimensional manifold.

In this manuscript, we will consider only connected manifolds. Examples of real manifolds are:

• The sphere:

Definition 36. Given a map F between a manifold M 1 to another manifold M 2 . We say that F is smooth at a point x ∈ M 1 if we can find charts φ 1 and φ 2 around x and F (x) such that the function:

Definition 37. A manifold L is said to be a submanifold of M if and only if:

Given a real valued function f : M → R, we would like to find a way to define directional derivatives of f on M. Directional derivatives are useful in optimization, like for example in gradient descent; if one wishes to choose a descent direction it would generally be the one minimizing the directional derivative.

Since M is not necessarily a vector space, the formula

is no longer valid. We instead use the notion of curves of M, and the tangent vectors to these curves. A curve is a map c : R → M, if the function t → f (c(t)) can be shown to be differentiable then the quantity df •c dt (0) can be defined as the directional derivative of f . Definition 38 (Equivalent curves). [AMS09] Given a smooth manifold M of dimension d, and two curves c 1 , c 2 : [-, ] → M such that: c 1 (0) = c 2 (0) = p. c 1 and c 2 are said to be equivalent if and only if there exists some chart (U, φ) at p such that:

Definition 39 (Tangent vector). [START_REF] Absil | Optimization algorithms on matrix manifolds[END_REF] Let M be a manifold, p ∈ M. Let F p (M) be the set of real valued functions on M that are locally smooth at p. A tangent vector ∂ p to M at a point p is a mapping from F p (M) to R such that there exists a curve c on M with c(0) = p satisfying:

This definition does not depend on a specific choice of c since any equivalent curve would satisfy the definition.

Proposition 27 (Tangent space, tangent bundle). [START_REF] Absil | Optimization algorithms on matrix manifolds[END_REF] The set of all tangent vectors to a manifold M at a given point p ∈ M forms a vector space and is denoted T p M.

For p ∈ M, it is possible to define a basis for the tangent space T p M, (∂ 1 , ∂ 2 , . . . , ∂ d ), this means that T p M is of dimension d for all p.

The set T M = ∪ p∈M T p M is called, the tangent bundle

Definition 40 (Vector fields). [AMS09]

A smooth vector field is a C ∞ map X : M → T M.

The set of vector fields on M is denoted by Γ(T M).

Let γ : [0, 1] → M. We want to differentiate a vector field X = dγ dt (t). The formula dX dt (t 0 ) = lim t→0 X(γ(t))-X(γ(0)) t cannot work since X(γ(t)) and X(γ(0)) belong to two different vector spaces (respectively T γ(t) M and T γ(0) M). There is no general correspondence between tangent vector spaces that can allow us to define a differential of a vector space. We need to introduce such a correspondence using affine connections, which are the equivalent of directional derivatives for vector fields.

Definition 41 (Connections

And for all Y 1 , Y 2 ∈ Γ(T M)), u ∈ T M, and f a smooth function on M:

Let M be a manifold with a connection ∇. A vector field X along a curve c is said to be parallel along c if ∇ ċX = 0. Theorem 18. [START_REF] John | Riemannian manifolds: an introduction to curvature[END_REF] Given a curve c : [0, 1] → M and a vector ξ 0 ∈ T ċM, there exists a unique parallel vector field X along c such that: X(0) = X 0 If t 0 , t 1 ∈ I, Parallel translation defines an operator:

such that: P t 0 ,t 1 (ξ 0 ) = X(t 1 ), where X is a parallel vector field along c with respect to ∇ such that:

Riemannian metrics

A metric , on a smooth Riemannian manifolds is a collection of Euclidean scalar products ( , p ) p∈M on each of the tangent spaces T p M of M. We also require that , p varies smoothly with respect to p.

Definition 43 (Riemannian metric). Given a smooth manifold M, define a Riemannian metric , on M to be a mapping that associates each p ∈ M to a scalar dot product , p : T p M × M → R such that: If X and Y are smooth vector fields of M then the function: p → X p , Y p is smooth. A Riemannian manifold is a smooth manifold equipped with a Riemannian metric.

B.1. GENERALITIES ON RIEMANNIAN MANIFOLDS

101

A special kind of connection we will be interested in is the Levi-Civita connection, whose existence and uniqueness is given by the following lemma: Lemma 5. [START_REF] Chavel | Riemannian Geometry[END_REF] If M is a Riemannian manifold, then there exists a unique connection ∇ such that for all smooth vector fields X, Y and Z we have:

Definition 44. Let v ∈ T p M be a tangent vector to the manifold M at p. Then there is a unique geodesic γ v satisfying γ v (0) = p with initial tangent vector γ v (0) = v. The exponential map at p is defined by exp p (v) = γ v (1) for any v ∈ T p M.

The injectivity radius at a point p ∈ M is the quantity: inj(p, M) = sup r>0 {r| exp p : B(0, r) → B(p, r) is a diffeomorphism }. The injectivity radius of the whole manifold M is defined as: inj(M) = inf p∈M inj(p, M)

A manifold is said to be geodesically complete if the exponential map is defined on all of T M

Sectional curvature and convexity

If c is a curve on M, we define the length of the curve as the quantity:

We denote as ∇ the Levi-Civita connection on M. If X, Y and Z are three vector fields, the Riemannian curvature tensor R is defined as:

In what follows, we shall make use of the following notation: R(X, Y, Z, W ) = R(X, Y )Z, W . Given a point p ∈ M and two linearly independent vectors v, w ∈ T p M spanning a two dimensional space σ = span{v, w}, the sectional curvature at p for the subspace σ is defined as:

Using this definition, the notion of distance between two points x and y ∈ M is defined by: d(x, y) := inf {c|c(0)=x;c(1)=y}

L(c)

A curve γ(t) between x and y verifying: L(γ) = d(x, y) is called a geodesic. If such a curve exists and is unique, we denote it by [x, y]. This notation suggests that geodesics are the Riemannian analog to the Euclidean line segment. The manifold M is said to be complete if for every couple (x, y) ∈ M 2 a geodesic between x and y exists.

We also define the midpoint of x and y (assuming existence and uniqueness of the geodesic):

x + y 2 := [x, y] 1 2 It is important to notice that notation x+y 2 denotes the midpoint of [x, y] in the manifold and involves actually no addition nor dilation. Obviously in the Euclidean case the two notions ("midpoint" and "arithmetic mean") coincide.

For p ∈ M and σ a 2-dimensional subspace of T p M, we denote by K p (σ) the sectional curvature of σ [START_REF] Do | Riemannian Geometry[END_REF]. A manifold is said to be of bounded curvature if and only if: ∃ δ, ∆ ∈ R such that: δ ≤ K σ (p) ≤ ∆ for any point p ∈ M.

We define the convexity radius r M as:

where inj(M) is the injectivity radius. With these notions defined, we can start describing the first optimization tools: the gradient and the Hessian.

Differential operators

Definition 45 (gradient). Let f M → R be a smooth function. The vector field grad f is defined so that the relationship:

is valid for any vector field X on M.

Remark 17. It can be shown that the gradient field verifies the following relationships:

Definition 46. Let M → R be a smooth function. The Hessian of f is defined as: Hess(f ) = ∇(df ).

B.1. GENERALITIES ON RIEMANNIAN MANIFOLDS

103

Remark 18. The Hessian also verifies the relationship:

for any vector fields X and Y .

A word on Lie Groups and Homogeneous manifolds

A Lie group is a group that is also a finite-dimensional smooth manifold, such that the multiplication and inversion mappings are smooth. These two conditions can be summed up by stating that the map (x, y) → x.y -1 is a smooth map from the product manifolds G × G to G.

Examples of Lie groups are: The unit circle S 1 , the n-dimensional torus

A manifold M is said to be homogeneous with respect to a Lie group G if there exists a transitive action of G on M.

B.1.2 Examples Grassmannian manifolds

The first example of interest are Grassmann manifolds, which arise naturally in several vision applications such as image matching and learning theory [START_REF] Turaga | Statistical analysis on stiefel and grassmann manifolds with applications in computer vision[END_REF][START_REF] Chikuse | Statistics on special manifolds[END_REF].

A Grassmanian manifold G(r, n) with r, n ∈ N is the quotient of R n×r by the equivalence relationship:

It can be shown [START_REF] Absil | Optimization algorithms on matrix manifolds[END_REF]p.48] that Grassmannians admit a manifold structure. The tangent space at an r-dimensional subspace W ⊂ R n , T W G(r, n) can be identified to the space of linear maps from W to R n /W : Lin(W, R n /W ) [START_REF] Piccione | On the geometry of Grassmannians and the symplectic group: the Maslov index and its applications[END_REF].

This tangent space can be endowed with the Riemannian metric [AMS09, p.83]:

such that Y(0) = span(Y 0 ) and dY dt (0) = U ΣV T where U ΣV T is the singular value decomposition of the tangent vector.

The curvature bounds are ∆ = 2 and δ = 0 [TAV11], the injectivity radius is inj(G(r, n)) = π 2 .

Positive definite matrices

The space of positive definite matrices is defined as:

The tangent space at a given point M ∈ Pos(n) can be identified with the space of symmetric matrices. Equipped with the metric:

X 1 , X 2 P = tr X 1 P -1 X 2 P -1

Pos(n) is a Riemannian manifold.

Equipped with this metric and the Levy-Civita connection, Pos(n) is a Riemannian manifold of constant negative curvature [Lan99, chap. 12], and the injectivity radius is infinite inj(Pos(n)) = ∞. The geodesic P (t) such that P (0) = P and Ṗ (0) = X is [Lan99, p.326]:

The rotation group

Another data space of interest is the 3-dimensional rotations group SO(3) = {R ∈ R 3×3 : R T R = I, det(R) = I}. The tangent of SO(3) at a point R is given by T R SO(3) = {RV : V T = -V }.

The Riemannian metric at identity is v 1 , v 2 = -1 2 tr(V 1 v 2 ). In this metric, the sectional curvature is constant and positive ∆ = δ = 1 4 , and the injectivity radius is inj(SO(3)) = π.

For all (R a 1 ,θ 1 , R a 2 ,θ 2 ) ∈ B 2 there exists a unique minimizing geodesic γ(t) such that γ(0) = R a 1 ,θ 1 and γ(1) = R a 2 ,θ 2 , and it has the following expression:

In the next section, we shall see how we can extend the gradient descent method to Riemannian manifolds. This first approach involves embedding the manifold into a Euclidean space of sufficiently large dimension.