4.2 Les bases

L’objet de cette section est de présenter le domaine des réseaux à préférences, dans ses grandes lignes, damé et balisé après trois années de tâtonnements : les notations et définitions, telles qu’elles se sont stabilisées au fil du temps (Section 4.2.1) ; le grand théorème des préférences acycliques, qui malgré sa simplicité est la colonne vertébrale du modèle (Section 4.2.2) ; et enfin, la zoologie des préférences acycliques, qui permet de voir comment relier le modèle à des situations réelles (Section 4.2.3).

4.2.1 Notations et définitions

Comme indiqué dans l’introduction, les réseaux à préférences sont issus de la théorie des -couplages [20, 24], et les notations s’en ressentent, même si un sous-vocabulaire spécifique a été introduit au fil des travaux [36, 37, 50, 55, 56]. En ce qui concerne la version française en particulier, le vocabulaire souvent imagé doit beaucoup à l’article de vulgarisation Mariages Stables de Dominique Dumont [28].

Ainsi, une instance de réseau à préférences est constituée d’un ensemble de pairs, d’un graphe d’acceptabilité, de préférences et de quotas. Une configuration est un ensemble d’interactions, dont la dynamique est décrite par des initiatives de pairs.

Réseau à préférences

Le réseau à préférences lui-même est donc constitué d’un ensemble de pairs (ou nœuds) et d’un graphe . Les préférences sont indiquées par une matrice de valeurs et les quotas par un vecteur .

Le graphe d’acceptabilité est un graphe non-orienté et non réflexif. Il décrit les compatibilités : deux pairs et peuvent interagir si, et seulement si, (ssi) . On dit alors que est acceptable pour , et réciproquement. Par exemple, peut représenter la connaissance des autres pairs (il est rare qu’un pair connaisse tous les autres pairs d’un réseau, sa vision est généralement limitée à un certain nombre de voisins), ou encore l’existence d’un intérêt commun (la recherche d’un même fichier, l’appartenance à un même groupe, …), ou tout simplement une structure overlay imposée. Le graphe peut a priori être quelconque, cependant nous userons souvent dans ce chapitre des graphes Erdős-Rényi , où chaque arête existe avec probabilité indépendamment des autres (le degré moyen est ainsi ). Ce choix est justifié par les facilités qu’offrent les graphes quant à l’analyse théorique des propriétés des réseaux à préférences.

La matrice de valeurs indique l’intérêt que les pairs ont les uns envers les autres. Elle détermine ainsi les préférences. Pour toute paire acceptable de pairs , est la valeur que donne à . Sauf indication contraire, on considère que les basses valeurs sont préférées¹. Ainsi, signifie que préfère à . Une hypothèse que l’on fait tout au long de ce chapitre est qu’il n’y a jamais d’égalité, c’est-à-dire que pour chaque ligne de , les valeurs acceptables sont deux à deux distinctes². La matrice peut posséder certaines propriétés particulières qui seront décrites en Section 4.2.3. Je précise également que s’il est toujours possible, et pratique, de supposer l’existence d’une matrice de valeurs , cela n’est pas indispensable d’un point de vue théorique, car seuls les ordres (les préférences) induits par importent [10, 36]. Il n’est pas nécessaire que les pairs connaissent . Dans le pire des cas, il est même possible qu’un pair ne connaisse pas les valeurs de sa propre ligne. Cependant, afin de garder un sens au concept de matrice de valeurs, on suppose qu’il est toujours possible pour un pair de comparer les valeurs de deux voisins en les contactant, par exemple au cours d’une initiative (voir plus loin).

Enfin, le vecteur des quotas, , limite le nombre de collaborations : un pair ne peut collaborer avec plus de voisins simultanément. On peut bien sûr toujours supposer que n’est pas plus grand que le degré de dans . Tout comme est souvent supposé Erdős-Rényi, est généralement supposé constant lorsque l’on veut analyser un réseau, même si toute distribution est autorisée a priori.

Configurations

La configuration d’un système décrit l’état des collaborations. Formellement, une configuration est un sous-ensemble de . Les voisins de dans sont les partenaires actuels de . Si désigne le nombre de partenaires de dans , les quotas impliquent . Si , on dit que est sous-couplé.

Une configuration peut évoluer par la résolution d’arêtes adultères (le terme est un hommage à la théorie originale des mariages). Une arête acceptable est adultère pour une configuration si elle n’appartient pas à et si chaque pair de l’arête a intérêt à établir la collaboration , même si cela implique d’abandonner une collaboration de pour satisfaire les quotas. Formellement, une arête est adultère ssi :

• ( est sous-couplé), ou bien ( préfère à l’un de ses partenaires) ;
• ou bien (condition symétrique).

Un pair qui est adjacent à au moins une arête adultère est éligible (il est susceptible de modifier la configuration). Une configuration qui ne possède pas d’arête adultère (ou de manière équivalente pas de pair éligible) est stable.

Initiatives

Les arêtes adultères sont à la base de la dynamique des configurations. Plus précisément, l’évolution vient toujours d’un pair éligible qui essaie de résoudre une arête adultère à laquelle il appartient. Ce processus, supposé atomique, est appelé initiative. Une initiative est active si elle se traduit par la résolution d’une arête adultère.

Formellement, l’initiative est une « fonction » de sélection (qui peut dépendre du temps, de l’état du système, être aléatoire, …) qui associe à chaque pair de un voisin à « essayer », ou plus formellement une arête de incidente à . Si par défaut, l’ensemble de ces arêtes peuvent être considérées par cette fonction de sélection, dans le cas où les pairs ont la connaissance des arêtes adultères auxquelles ils appartiennent, il est possible de restreindre la sélection à ces seules arêtes.

Des exemples d’initiatives sont la sélection meilleur partenaire (parmi les arêtes adultères), décrémentale (choix en round-robin parmi la liste des voisins), ou simplement aléatoire. Remarquons que les différents types de sélection nécessitent, de manière implicite, plus ou moins de connaissances : ainsi, meilleur partenaire et décrémentale nécessitent d’être capable de trier ses voisins (et même de repérer les arêtes adultères pour la première), alors qu’une sélection purement aléatoire nécessite juste d’être capable d’évaluer un voisin à la volée. Enfin, il est toujours possible d’hybrider plusieurs sélections afin d’obtenir une sélection plus performante. Un exemple de sélection hybride sera décrit en Section 4.3.2 (d’après [55]).

Partant d’une configuration initiale donnée, l’évolution d’un système est donc décrite par la suite des initiatives réalisées par les pairs. Une suite classique est la suite Round-Robin, adaptée pour modéliser un comportement mono-périodique des pairs, ou la suite uniformément aléatoire, utilisée pour modéliser un processus Poissonien homogène (chaque pair suit un processus de Poisson i.i.d.). Enfin, il y a les suites adversariales, qui essaient de se comporter de la « pire » façon possible.

Par commodité, le temps est directement mesuré à l’aune de la suite des initiatives (il n’est ainsi pas nécessaire d’introduire explicitement des processus temporels d’initiatives). Il est malgré tout possible de considérer plusieurs mesures suivant le contexte que l’on considère. Par exemple, si l’on se place dans le contexte de l’auto-stabilisation au sens de Dijkstra [25], on comptera seulement les initiatives actives, et les suites seront découpées en rounds (un round est une sous-suite telle que chaque pair éligible au début du round prend une initiative ou devient non-éligible au cours de ce round). Pour les simulations, je préfère définir l’unité de temps (u.t.) par initiatives (actives ou non). Ainsi, chaque initiative atomique prend u.t., et au bout de u.t., le nombre d’initiatives par pair est en moyenne de . Lorsque la suite d’initiatives est round-robin, round et unité de temps peuvent être considérés comme synonymes, mais ce n’est pas vrai dans le cas général.

Stabilité locale

La notion d’initiative entraîne une définition alternative de la stabilité : une configuration est stable si la seule configuration atteignable par initiatives à partir de est elle-même. Il est facile de vérifier que pour des initiatives arbitraires, cette définition est équivalente à celle donnée en Section 4.2.1.2 (pas d’arête adultère). L’intérêt d’une approche au sens des initiatives de la stabilité est qu’elle permet une définition locale : une arête d’une configuration est stable ssi existe dans toutes les configurations atteignables à partir de . Écrit autrement, une arête stable est une collaboration que les initiatives ne peuvent rompre.

Lorsqu’un pair est incident à une arête stable, son degré de liberté s’en trouve diminué. Le quota libre d’un pair , noté , est le quota auquel l’on retranche le nombre d’arêtes stables incidentes à . Les quotas libres forment un vecteur qui est fonction de la configuration et qui ne fait que décroître avec le temps. Il est ainsi possible d’étendre la définition de stabilité au niveau des pairs : un pair est stable (ou inactivé) si ou si partage une arête stable avec tous ses voisins non-stables.

Enfin, une dernière notion fondamentale à propos de la stabilité est celle de chaleur. Dans une configuration donnée , une arête acceptable mais hors de () est chaude ssi :

• appartient aux meilleurs voisins non-stables de ,
• appartient aux meilleurs voisins non-stables de .

Il existe de même une définition plus stricte de la chaleur : une arête acceptable entre deux pairs non-stables qui ne collaborent pas est dite bouillante pour ssi est le meilleur voisin non-stable de et vice versa.

Par extension, un pair sera dit chaud (resp. bouillant) s’il est adjacent à une arête chaude (resp. bouillante).

Intuitivement, les arêtes chaudes, et plus encore bouillantes, sont des arêtes super-adultères, qui n’attendent qu’une initiative bien placée pour devenir des arêtes stables. Elles jouent un rôle central dans les réseaux à préférences acycliques, à cause du Lemme 4.1, qui est utilisé dans beaucoup de démonstrations :

Bien évidemment, ce lemme n’a de sens qu’une fois définie la notion d’acyclicité. C’est d’ailleurs l’objet du reste de cette section sur les bases des réseaux à préférences.

4.2.2 Grand théorème des préférences acycliques

Un cycle de préférences, ou cycle de Kieschnick, est un cycle de pairs tel que chaque pair préfère son successeur à son prédécesseur : préfère à , préfère à , …, préfère à (ou encore, exprimé en terme de valeurs, , , …, ).

L’objet principal de ce chapitre est les réseaux à préférences acycliques, c’est-à-dire qui ne contiennent pas de cycle de Kieschnick. Remarquons que l’acyclicité est entièrement définie par , et qu’elle ne dépend ni des quotas, ni des initiatives. De même, si produit des préférences acycliques pour une acceptabilité complète, alors le réseau sera acyclique pour tout graphe d’acceptabilité . Par convention, une telle matrice de valeurs est également appelée acyclique. Une classification des matrices acycliques, et le lien avec les systèmes P2P, sont proposés en Section 4.2.3.

Les réseaux à préférences acycliques sont caractérisés par une propriété qui les rend uniques au sein des réseaux à préférences :

J’insiste encore une fois sur le caractère fondamental de ce théorème d’existence/unicité/auto-stabilisation, car il permet de s’affranchir de l’étude de stabilité faite pour les autres types de préférences, et de se concentrer plus finement sur les configurations proprement dites.

La première application de ce théorème est apparue dans l’article Stratification³ in P2P Networks: Application to BitTorrent [37]. Dans cet article, qui cherchait à modéliser un réseau BitTorrent comme un réseau à préférences acycliques (j’en parlerai plus en détail dans la suite du chapitre), nous avons mesuré la convergence effective entre configuration réelle et stable. Afin d’estimer l’importance pratique de l’auto-stabilisation, nous avions considéré trois types de scénarios (cf Figure 4.1) :

Statique (Figure 4.1a)

Partant de la configuration vide (souvent notée ), nous avons observé la convergence vers la configuration stable. Nous avons pu observer une bonne convergence dans tous les cas, tout en remarquant que les paramètres du système, et le degré moyen du graphe d’acceptabilité en particulier, jouaient un rôle majeur ;

Altération atomique (Figure 4.1b)

Un deuxième scénario élémentaire consiste à enlever un pair à partir d’une configuration stable (ce qui modifie la configuration stable), et refaire converger le système. On observe que la configuration réelle ne s’éloigne guère de la configuration stable, et finit par re-converger, même si à cause d’un éventuel effet domino, il se peut que le temps de convergence soit comparable au cas statique.

Agitation continue (Continuous churn) (Figure 4.1c)

Enfin, un troisième scénario consiste à faire partir et arriver des pairs dans le système selon une certaine intensité. Ce scénario permet de constater que la configuration réelle n’arrive pas toujours à rattraper l’évolution de la configuration stable, surtout quand l’agitation est extrême. Cependant, l’auto-stabilisation fait en sorte que la configuration réelle reste malgré tout assez proche de la configuration stable, la distance entre les deux étant grossièrement proportionnelle à l’agitation.

À la suite de cette étude, j’ai commencé à travailler en partant du principe qu’à la condition que la convergence du système soit suffisamment grande devant l’évolution de celui-ci, la configuration stable devait être une bonne approximation des configurations réelles. C’est l’image du ressort (cf Figure 4.2). Cette image nous suggère de décomposer l’étude des systèmes à préférences acycliques en deux problèmes distincts :

Quelle est la vitesse de convergence ?

En effet, le Théorème 4.1 ne nous donne que le nombre de configurations possibles comme borne. Ce nombre croît de manière factorielle [21] et offre donc un intérêt pratique assez limité. Une première zone d’étude consiste donc à caractériser plus finement la raideur effective du ressort.

Quelles sont les propriétés des configurations stables ?

La question précédente doit permettre de déterminer dans quelle mesure une configuration stable est une bonne approximation d’une configuration réelle. Quand c’est le cas, les propriétés génériques des solutions stables peuvent permettre d’estimer les performances du système.

Ces deux questions vont faire l’objet des deux prochaines sections de ce chapitre. Mais avant d’y répondre, je propose de regarder d’un peu plus près ces préférences acycliques dont je n’ai jusqu’à présent donné qu’une définition sommaire et peu pratique.

4.2.3 Zoologie des préférences acycliques

Parmi toutes les matrices réelles possibles, peu sont acycliques. En fait, si l’on prend une matrice dont les coefficients sont choisis au hasard, il est très probable que les préférences qui en résultent contiennent au moins un cycle de longueur ⁴. D’un autre côté, beaucoup de propriétés matricielles sont synonymes d’acyclicité. Par exemple ([36]) :

Matrices globales

Une matrice de valeurs est globale si toutes ses lignes sont identiques si l’on se restreint aux entrées acceptables. Intuitivement, c’est un cas particulier de matrice de rang , et formellement, on a pour tous les qui acceptent . Les préférences correspondantes, également appelées globales, reflètent un ordre total sur les pairs. On peut d’ailleurs remarquer qu’à cause de cet ordre total, on peut dire qu’à acceptabilité et permutation des pairs près, il n’y a qu’une seule préférence globale.

Matrices symétriques

Si est symétrique sur ses entrées acceptables ( pour toute paire acceptable) est acyclique. Une propriété intéressante des matrices symétriques est qu’elles décrivent l’ensemble des préférences acycliques (cf [10, 36]). Le lien entre matrices acycliques, symétriques, globales, et les préférences correspondantes est illustré Figure 4.3⁵.

Combinaison linéaire de matrices globales et symétriques

Les matrices obtenues sont acycliques tant qu’elles ne génèrent pas d’égalité (mais comme indiqué en Section 4.2.1.1, il est toujours possible de s’affranchir des cas d’égalité). En revanche, une combinaison linéaire de matrices acycliques n’est pas forcément acyclique : si les matrices d’entrée ne sont pas déjà elles-mêmes combinaison linéaire de matrices symétriques et globales, il faut les symétriser, ce qui se fait assez facilement car la preuve de surjection des matrices symétriques dans les préférences acycliques est constructive (cf [10, 36]).

Préférences adaptées au P2P

Après avoir esquissé ce qui fait que des préférences sont acycliques, je propose maintenant de nous recentrer dans le contexte du pair-à-pair, et de considérer les préférences pair-à-pair acycliques.

Capacités

Un pair dans un réseau P2P possède de nombreuses caractéristiques scalaires intrinsèques qui peuvent créer des préférences : bande passante d’accès, capacité de stockage ou de calcul, uptime moyen, … Si l’on prend l’exemple du protocole de partage de fichiers BitTorrent [23], un algorithme donnant-donnant fait qu’un pair tend à collaborer de préférence avec ses voisins qui lui fournissent la plus grande vitesse de téléchargement. Cela peut être vu en première approximation comme un réseau à préférences où la valeur est la bande passante d’émission divisée par le quota (le nombre d’émissions simultanées).

Proximités

Toutes les valeurs qui peuvent être assimilées à une sorte de distance (physique ou virtuelle) ou de similarité sont symétriques par nature. Ainsi, beaucoup de systèmes P2P essaient de minimiser les latences⁶, comme par exemple la DHT Pastry [68] ou les applications de jeu en ligne en temps réel [51]. De même, les jeux massivement multi-joueurs en ligne (MMOG) doivent connecter ensemble les joueurs proches dans un certain espace virtuel [33, 47, 48]. Certains auteurs proposent également de connecter les participants d’un système de partage de fichiers en fonction de leurs intérêts communs [29, 71], ce qui reste une mesure symétrique. Le co-uptime, c’est-à-dire le temps (moyen) d’activité commune, est un dernier exemple de mesure symétrique ayant un intérêt pour des applications collaboratives.

Complémentarités

La mesure des différences entre les ressources des participants peut également s’avérer intéressante. Par exemple, dans une application de stockage distribué de fichiers, il est utile de trouver des machines qui sont allumées quand ma propre machine est éteinte, afin de garder mes données disponibles à tout moment. La mesure correspondante est l’uptime complémentaire. De même, dans un système comme BitTorrent, tous les participants cherchent à avoir le même fichier, qui est divisé en blocs⁷. Trouver les voisins qui ont le plus de blocs que je n’ai pas encore obtenus a un intérêt. Toutes ces préférences dites complémentaires sont un cas particulier de combinaison linéaire d’une matrice globale et d’une matrice symétrique, et sont donc acycliques [36].

Classes de préférences étudiées

Comme nous venons de le voir, il existe de nombreuses préférences acycliques présentant un intérêt du point de vue du P2P. Au cours de mes travaux, je me suis concentré sur quatre classes de préférences acycliques, ce qui évite de se disperser dans un labyrinthe de cas particuliers tout en donnant une idée précise des liens entre préférences et propriétés des systèmes.

Globales

Bien que représentant un sous-ensemble négligeable (en terme de cardinalité) des préférences acycliques, les préférences globales sont parmi les plus importantes des préférences acycliques (elles modélisent les capacités), et doivent recevoir une attention particulière. Comme il n’existe en fait qu’un unique système de préférences globales, induit par un ordre total sur les pairs, j’utiliserai cet ordre au lieu d’expliciter la matrice des valeurs . Les pairs seront ainsi étiquetés de à , étant le meilleur (il est préféré par tous ses voisins acceptables), et ainsi de suite…

Géométriques

Pour des préférences issues de distances, les propriétés des préférences dépendent grandement de la manière dont les points sont positionnés dans l’espace sous-jacent. On peut d’ailleurs facilement montrer que toutes les préférences acycliques peuvent être générées en plaçant les pairs aux sommets d’un simplexe et en le perturbant (en bougeant légèrement les sommets) de manière adéquate. Malgré tout, l’expérience semble montrer que certaines caractéristiques se retrouvent fréquemment. Pour se donner des préférences de proximité typiques et analysables, je propose de considérer les préférences obtenues en considérant les distances prises entre points au hasard sur un -tore unitaire de dimension ().

Latences réelles

Avoir des mesures réelles pour valider les résultats est bien évidemment nécessaire, même si l’analyse théorique devient alors difficile. Pour , j’utilise, pour contrôler la validité de certains résultats géométriques, des sous-ensembles de taille extraits du jeu de données du projet Meridian [6]. Les valeurs sont les latences (symétriques) entre les nœuds sélectionnés.

Acycliques aléatoires

Une dernière classe de préférences est obtenue en attribuant à chaque arête acceptable une valeur aléatoire uniforme comprise entre et . J’appelle les préférences qui en résultent acycliques aléatoires (ou simplement acycliques quand il n’y a pas d’ambiguïté), car on peut montrer que cette approche produit un échantillonnage uniforme sur l’ensemble des préférences acycliques possibles [10, 36].