4.3 Caractérisation de l’auto-stabilisation
Quelle est la vitesse de convergence ? Cette section va tenter de répondre à cette question, d’un point de vue théorique (Section 4.3.1 et Section 4.3.2) et pratique.
4.3.1 Bornes supérieures
Je propose d’abord de donner des bornes supérieures, au sens de la théorie de l’auto-stabilisation. L’initiative considérée dans toute cette section est meilleur partenaire. Pour , les bornes sont exactes, linéaires en rounds, et quasi-exactes, exponentielles en initiatives. Je donne ensuite des bornes plus faibles pour .
Convergence (rounds)
Pour , le temps maximal de convergence, exprimé en rounds, est donné par le théorème suivant.
Théorème 4.2 ([56]).
Partant de n’importe quelle configuration, une suite adversariale converge en au plus rounds. Cette borne est atteinte par une suite round-robin.
Démonstration.
Le Lemme 4.1 garantit la stabilisation d’au moins une arête bouillante par round. Comme il y a au plus arêtes à stabiliser, la borne vient tout de suite. Pour l’atteindre, on peut utiliser des préférences globales, un graphe d’acceptabilité complet, la configuration de départ , et une suite round-robin utilisant le motif du pire au meilleur.
□
Convergence (initiatives)
Si l’on veut maintenant mesurer la convergence en nombre d’initiatives actives, la borne dépend des contraintes de la suite : round-robin ou totalement adversariale.
Suite Round-Robin
La borne pour les suites round-robin est donnée par le théorème suivant.
Théorème 4.3 ([56]).
Partant de n’importe quelle configuration, une suite round-robin converge en au plus initiatives actives. Cette borne est exacte.
Démonstration.
Comme pour le Théorème 4.2, on utilise le fait qu’au moins une arête bouillante est stabilisée par round. De plus, un pair stable n’est par définition plus jamais actif ; le comptage précis des initiatives possibles donne alors . Le système utilisé pour le Théorème 4.2 atteint la borne, prouvant qu’elle est exacte.
□
Suite adversariale
La convergence pour une suite adversariale est décrite par le théorème suivant.
Théorème 4.4 ([56]).
Partant de n’importe quelle configuration, une suite adversariale converge en au plus initiatives actives. Réciproquement, il existe une suite qui converge en initiatives actives, avec , ce qui montre que la borne exacte des suites adversariales se situe entre ces deux valeurs.
Démonstration.
Comme beaucoup d’autres preuves, la borne est issue du Lemme 4.1. L’astuce est de considérer une arête bouillante et de regarder le moment où elle se stabilise. Avant cet instant, les pairs adjacents ne peuvent prendre l’initiative : on est par hypothèse en meilleur partenaire, donc ils se stabiliseraient. Après, ils sont inactifs. On en déduit une récursion sur le nombre de pairs autorisés à prendre une initiative, à partir de laquelle la borne est déduite.
La borne est quant à elle obtenue pour les préférences globales, en acceptabilité complète, à partir d’une suite le pire d’abord : à chaque instant, l’initiative est prise par le plus mauvais pair actif (celui avec la plus grande étiquette). Une étude complète du comportement de cette suite d’initiatives donne la borne inférieure.
□
Remarque 4.1.
Dans tous les résultats que je viens d’énoncer, les bornes sont atteintes à partir de préférences globales. De ce point de vue, on peut donc considérer que les préférences globales sont les « pires » possibles pour la convergence, comme la suite va le confirmer. D’une manière plus générale, les préférences globales ont souvent un comportement atypique au sein des préférences acycliques.
Généralisation au -couplage
Pour , une adaptation du Théorème 4.2 nous donne immédiatement une borne de rounds (au moins une arête est stabilisée par round). Mais il est facile de voir que c’est juste une borne supérieure. Par exemple, en prenant (c’est le cas limite de l’absence de quotas : tout le monde peut simultanément collaborer avec tout le monde), chaque pair est sûr d’être stabilisé après avoir pris initiatives, ce qui donne une borne de rounds beaucoup plus petite que .
L’explication derrière l’imprécision de la borne est que lorsque , une configuration non-stable possède des arêtes chaudes en plus des arêtes bouillantes. Ces arêtes simplement chaudes sont plus dures à dénombrer (toutes les configurations transitoires n’en ont pas), ce qui rend le calcul des bornes plus difficile. On peut quand même donner des bornes plus précises que pour les préférences globales (qui, rappelons-le, sont intuitivement les pires préférences possibles).
Théorème 4.5 ([55]).
Pour les préférences globales, le temps de convergence est borné par rounds si l’acceptabilité est complète, et par sinon.
Les simulations (cf Section 4.3.3) indiquent que la borne reflète assez bien le comportement réel des préférences globales : les premiers quotas sont ceux qui coûtent le plus cher en terme de convergence. L’acceptabilité complète semble de plus être le pire cas possible, ce qui fait que est clairement une estimation supérieure (sans parler de ).
Démonstration.
Si l’acceptabilité est complète, la configuration stable est faite de cliques de taille ([37]) ; rounds stabilisent une clique, d’où le résultat. Dans le cas général (acceptabilité inconnue), on peut juste affirmer que rounds stabilisent pairs, d’où la borne .
□
4.3.2 Temps moyens de convergence
Intéressons-nous maintenant à la convergence moyenne pour des suites round-robin et Poisson non adversariales. Les résultats présentés ici sont valables pour , en initiative meilleur partenaire. Il s’agit de bornes supérieures sur le temps moyen de convergence de certaines classes de systèmes à préférences, temps moyen mesuré en initiatives ().
Borne générique
Sous les hypothèses considérées ( et initiative meilleur partenaire), la borne suivante est valable pour tout système acyclique :
Théorème 4.6 ([55]).
Le temps moyen de convergence est borné par pour une suite Poisson, et par pour une suite round-robin.
Démonstration.
Comme souvent, le théorème repose sur le Lemme 4.1, à savoir l’existence d’au moins deux pairs bouillants dans toute configuration non-stable. On en déduit un temps moyen entre deux initiatives « bouillantes » de pour une suite Poissonnienne et pour une suite round-robin. En multipliant par (nombre maximal d’arêtes de la configuration stable), on obtient le résultat.
□
Remarque 4.2.
Pour des préférences globales avec acceptabilité complète, toute configuration instable admet exactement deux pairs bouillants (les deux meilleurs pairs non stabilisés). Ceci suggère que les bornes du Théorème 4.6 doivent être assez précises pour ces systèmes, ce qui est confirmé par les simulations [55]. On retrouve le fait que les préférences globales sont « les pires préférences acycliques possibles ».
Remarque 4.3.
La borne exacte pour les suites round-robin n’est pas contradictoire avec l’exactitude de la borne du Théorème 4.2 : l’une est une borne en moyenne sur l’ensemble des suites round-robin, l’autre une borne dans le pire cas.
Préférences globales
Pour les préférences globales, avec un graphe d’acceptabilité Erdős-Rényi , il existe des bornes plus fines :
Théorème 4.7 ([55]).
En préférences globales, si , le degré moyen étant , le temps moyen de convergence est en pour une suite Poissonnienne et en pour une suite round-robin.
Démonstration.
Le cœur de la preuve consiste à compter les pairs bouillants dans les configurations non-stables. Par des techniques combinatoires, on montre qu’il y en a de l’ordre de . On en déduit ensuite un temps moyen entre deux initiatives « bouillantes » de l’ordre de , ce qui donne le comportement commun en . Enfin, il faut porter une attention particulière à la finalisation du processus de convergence, lorsque la quasi-totalité des arêtes sont déjà stabilisées. Dans cette fin de partie, les nœuds non-stables sont quasiment tous bouillants. Une suite round-robin va alors achever la stabilisation en ( unité de temps stabilise tous les nœuds bouillants du moment), tandis qu’une suite Poissonnienne va avoir besoin de u.t. (problème de boules et d’urnes).
□
Préférences acycliques
Pour des préférences acycliques (aléatoires), on a un résultat similaire :
Théorème 4.8 ([55]).
Pour des préférences acycliques aléatoires, si , le degré moyen étant , le temps moyen de convergence est en pour une suite Poissonnienne et en pour une suite round-robin.
Démonstration.
Un calcul peut montrer que pour des préférences acycliques aléatoires, environ la moitié des pairs non stables sont bouillants. Cela permet de montrer que la fin de partie est atteinte au bout de unités de temps. Si la suite est Poisson, il faut alors rajouter u.t. supplémentaires.
□
Remarque 4.4.
Comme , certains voudront que je simplifie la borne en , et ils auront raison. Cependant, je reste sur ma notation, parce qu’en bon physicien du pays de Pagnol, j’estime que le grand O du compte plus que le grand O du (cf Section 4.3.3.1).
Autres préférences acycliques
Pour d’autres types de préférences acycliques, la clé pour estimer le temps de convergence moyen est d’arriver à estimer le nombre de pairs bouillants. Pour des préférences réelles comme celles issues de Meridian, c’est un exercice difficile. De même pour les préférences géométriques, où il existe de fortes corrélations entre les préférences de pairs proches. Notons que pour ce dernier cas, ne pas tenir compte de ces corrélations permet de se ramener au cas des préférences acycliques aléatoires, et cela marche assez bien en pratique (cette technique sera d’ailleurs abondamment utilisée dans la section suivante).
Dans self-stabilization in preference-based systems [55], je propose de regarder la distribution de la « valeur » des pairs pour déterminer si la convergence d’un système est plus proche de celle des préférences globales ou de celle des préférences acycliques. Si certains pairs sont bien classés par beaucoup de leurs voisins (ce sont donc des « bons » pairs), la convergence devrait ressembler à celle des préférences globales ( ou ). Par contre, si aucun bon pair ne se dégage (les pairs ont à peu près tous la même valeur), la convergence devrait être de type acyclique aléatoire ( ou ).
Je suggère d’utiliser cette règle empirique (tout réseau à préférences acycliques a un comportement entre celui des préférences acycliques aléatoires et celui des préférences globales, le curseur étant positionné par la distribution des valeurs) pour tous les types de préférences acycliques, par exemple pour des combinaisons linéaires de préférences. Et aussi pour des graphes d’acceptabilité et des quotas quelconques. Hélas, je n’ai pas de preuve théorique à apporter. Heureusement, pour tout ce que je ne peux pas prouver, il y a les simulations.
4.3.3 Simulations
Au-delà des résultats purement théoriques, je propose les simulations pour compléter la compréhension de la convergence des préférences acycliques. C’est une approche que j’affectionne tout particulièrement quand un système qui dépend de quelques paramètres ne peut pas être analysé entièrement : faire varier les paramètres un par un afin de se forger une intuition sur l’influence de chacun de ces paramètres. Tous les résultats présentés ici viennent de l’article self-stabilization in preference-based systems [55], dans lequel j’invite le lecteur soucieux des détails techniques à se plonger.
Initiative meilleur partenaire
Pour commencer, regardons la convergence sous l’initiative meilleur partenaire, qui a été abondamment étudiée au début de cette section. Des quotas supérieurs à seront utilisés pour voir comment les résultats vus pour s’appliquent pour .
Taille du voisinage acceptable
Afin de comprendre l’influence du nombre de voisins, on fixe et l’on fait varier ( est toujours supposé Erdős-Rényi). On observe deux principaux comportements :
- Pour les préférences globales, le temps de convergence croît de manière linéaire ; la suite round-robin est plus rapide que la suite Poissonnienne sauf lorsque est proche de ;
- pour les autres préférences étudiées, le temps de convergence croît d’une manière qui semble logarithmique ; la suite round-robin est toujours plus rapide que la suite Poissonnienne ; les deux préférences les plus rapides (acycliques aléatoires et géométriques) sont quasi-impossibles à différencier.
Taille du système
Considérons maintenant des systèmes où l’on fait varier , à constant. Les résultats sont les suivants :
- Le temps de convergence augmente avec pour les suites Poissonniennes. C’est l’effet fin de partie en ;
- pour les suites round-robin, le temps de convergence augmente sensiblement moins. Il y a même une légère décroissance au niveau des préférences globales pour proche de ;
- excepté pour le cas ci-dessus (préférences globales, proche de ), les séquences Poissonniennes sont plus longues que les séquences round-robin ;
- comme pour l’expérience précédente, les préférences acycliques et géométriques convergent le plus vite, suivies des préférences Meridian et enfin, relativement loin, des préférences globales.
La principale leçon à retenir de ces simulations reste que à fixé, a relativement peu d’effet sur le temps de convergence. « Le grand du est plus important que le grand du ».
Quotas de collaborations
Comme pour les autres paramètres, le rôle des quotas dans le temps de convergence dépend du type de préférences :
- Pour les préférences globales, le temps de convergence croît d’abord vite puis lentement (les premiers quotas coûtent le plus cher) ; les suites Poissonniennes sont légèrement plus rapides ;
- pour les autres préférences, on note une croissance linéaire ou quasi-linéaire, les suites round-robin étant légèrement plus rapides.
Récapitulatif
En résumé, les préférences globales se distinguent par un temps de convergence linéaire par rapport au degré moyen, ce qui fait de le principal paramètre à considérer pour la convergence. Les quotas ont une influence plus faible, surtout une fois les premières valeurs passées (plus il y a de connexions, moins une nouvelle connexion prend de temps).
Pour les autres préférences, où il n’y a pas vraiment de « bons » pairs, c’est quasiment l’inverse : la convergence est proportionnelle aux quotas (chaque connexion coûte le même prix en temps que la précédente), mais seulement logarithmique par rapport à la taille du voisinage.
Initiatives aléatoires et hybrides
La plupart des travaux que j’ai effectués jusqu’à présent portent sur l’initiative meilleur partenaire, car c’est une initiative déterministe, ce qui simplifie son étude. Pour conclure cette discussion sur la convergence, j’aimerais évoquer un peu l’initiative aléatoire, qui sera je pense un sujet très intéressant à étudier pour de futurs travaux.
Une initiative aléatoire est beaucoup moins coûteuse en messages de contrôle qu’une initiative meilleur partenaire, car il est inutile de connaître les rangs et partenaires de ses voisins pour la pratiquer. En contre-partie, elle augmente le temps de convergence : alors qu’un pair bouillant stabilise nécessairement une arête en prenant une initiative meilleur partenaire, ce n’est plus le cas en initiative aléatoire.
Cependant, il n’y a pas que le temps requis pour une convergence complète qui compte. Le temps nécessaire pour atteindre d’assez bonnes configurations (pour un certain sens) est au moins aussi important.
Par exemple, il est possible de mesurer une satisfaction des pairs dans une configuration donnée (cf [55] pour une description détaillée) et d’observer comment cette satisfaction évolue au cours du processus de convergence. Pour des préférences non-globales (géométriques, aléatoires ou Meridian) et des mêmes conditions initiales, l’initiative meilleur partenaire produit à chaque instant une satisfaction meilleure que l’initiative aléatoire. En revanche, la situation est beaucoup moins tranchée si les préférences sont globales : d’un côté, l’initiative aléatoire n’a besoin que de quelques u.t. pour créer une forte satisfaction, mais elle peine ensuite à atteindre la satisfaction stable ; de l’autre, l’initiative meilleur partenaire a une croissance initiale beaucoup plus faible et ne dépasse que tardivement la satisfaction de l’initiative aléatoire, mais elle converge ensuite rapidement.
L’intérêt de cet exemple est de montrer qu’en plus d’être moins coûteuse, il y a des cas (les préférences globales en l’occurrence) où l’initiative aléatoire peut s’avérer plus efficace : avoir une convergence initiale très forte, même si la convergence finale est lente, peut être très avantageux pour un système soumis à forte agitation (et où il est donc illusoire d’essayer d’atteindre une convergence complète). Je me permets au passage de remarquer que le protocole BitTorrent, qui peut de manière très grossière être assimilé à un système à préférences globales soumis à agitation, utilise l’initiative aléatoire, plus connue ici sous le nom d’optimistic unchoking.
Je propose l’interprétation suivante (toujours tirée de [55]) pour expliquer cette différence dans les convergences, pour les préférences globales : en initiative meilleur partenaire, tout le monde essaie les « bons » pairs. En particulier, les mauvais pairs vont continuellement essayer les meilleurs pairs non-stabilisés. Ces derniers se stabilisent très vite (ils sont chauds), ce qui casse leurs mauvaises connexions. Le résultat est une sorte de front de convergence (ou front de saturation) qui évolue temporellement des meilleurs aux pires pairs, les pairs étant stabilisés après le passage du front, mais n’ayant peu ou pas de connexions avant. En particulier, un mauvais pair n’arrive pas à conserver ses partenaires avant la convergence complète du système. À l’inverse, l’initiative aléatoire ne crée pas de front de saturation, mais une sorte de convergence uniforme de la satisfaction : les mauvais pairs peuvent choisir de mauvais partenaires, ce qui fait que leur connexions intermédiaires durent plus longtemps.
Les avantages des initiatives aléatoire et meilleur partenaire peuvent se combiner dans des initiatives hybrides. Je propose par exemple une initiative où chaque pair fonctionne en initiative aléatoire en dessous d’un certain nombre de partenaires, et bascule en meilleur partenaire au-delà. Les bons pairs convergent quasiment aussi vite qu’en meilleur partenaire, suivant un front de saturation, mais les pairs situés devant le front ont quand même une bonne satisfaction due à la composante aléatoire qui se déclenche dès qu’il n’y a pas assez de partenaires. Au final, l’initiative hybride se comporte bien quelles que soient les préférences acycliques (pas seulement pour les préférences globales donc), aussi bien en convergence initiale que complète, ce qui en fait un choix intéressant, en particulier pour des systèmes acycliques où la nature exacte des préférences est inconnue ou variable.