Protocole de production d'une proposition unique par agrégation de sous-réseaux

De Willforge
Aller à : navigation, rechercher

But de ce texte[modifier]

Supposons qu'il existe un très grand réseau d'ordinateurs personnels connectés en pair-à-pair (P2P) comportant des millions de noeuds. Supposons que parmi ces noeuds plusieurs milliers (les noeuds actifs) se portent volontaires pour produire une certaine proposition (loi ou article de loi par exemple) sur un thème bien défini. Des milliers de propositions équivalentes seront produites concurremment.

Un noeud donné ne pourra examiner qu'un nombre infime d'entre elles. Le protocole que nous proposons permet de faire en sorte que chaque proposition ait une chance égale d'être examinée par un noeud quelconque du réseau et obtienne une note permettant de sélectionner la meilleure.

Nous procéderons ainsi : à un instant donné, les noeuds actifs sont regroupés en sous-réseaux de 10 noeuds (produisant donc 10 versions semblables de la proposition) et les noeuds restants (non-actifs) sont répartis également dans chaque sous-réseau.

Dans chaque sous-réseau, un noeud n'a alors à examiner que de 10 propositions, qu'il note de 0 à 10. Les notes obtenues par chacune des propositions sont additionnées en une note globale. Ceci constitue l'étape zéro du protocole.

Dans chaque sous-réseau, la proposition qui obtient la meilleure note est la seule retenue pour l'étape suivante (il est possible d'en retenir plusieurs s'il y a des ex-æquo). L'étape zéro du protocole aura donc permis de réduire le nombre de propositions par un facteur 10.

A l'étape suivante, on agrège aléatoirement les sous-réseaux par dizaine. Ainsi, chaque noeud de chaque nouveau sous-réseau n'a toujours à noter que 10 propositions. En fin d'étape on a encore réduit le nombre de propositions par un facteur 10.

En itérant cette procédure 3 à 4 fois on épuisera le nombre de propositions, et à un instant donné, le réseau sélectionnera une seule proposition. Cette proposition est celle qui obtient la meilleure note sur l'ensemble du réseau.

On peut reproduire la même procédure à différents dates avec différents acteurs : la proposition retenue sera celle qui aura la meilleure note toute date confondue.

Au lieu d'utiliser une note on peut appliquer une Méthode de Condorcet.

Texte[modifier]

Exemple à l'instant T
Nc (Nb de noeud-citoyens) Na (Nb de noeud-actifs) Np (Nb de noeud-passifs)
900 000 300 000 600 000
Exemple à l'instant T étape 0
Ns0 (Nb de sous-réseaux) Nt0 (Nb total de noeuds par sous-réseau)
30 000 30
Exemple à l'instant T étape 1
Ns1 (Nb de sous-réseaux) Nt1 (Nb total de noeuds par sous-réseau)
3 000 300

Nous donnons ci-dessus un exemple chiffré.

  • Il existe un réseau de No (millions) ordinateurs personnels connectables en pair-à-pair (P2P) (les noeud-citoyens).
  • Nous allons considérer ce qui se passe à un instant bien défini T.
  • A l'instant T il y a Nc noeud-citoyens connectés (par exemple 900 000)
Reseaux agreges fr.png

étape initiale 0[modifier]

  • Parmi ces Nc noeuds Na (par exemple 300 000) noeud-actifs se portent volontaires pour produire une certaine proposition (article de loi, texte ...).
  • Il y a Np = Nc - Na noeud-passifs (par exemple 600 000).
  • On regroupe les Na noeud-actifs par groupes de Nw (par exemple Nw=10).
  • On crée Ns0 = Na / Nw sous-réseaux contenant chacun Nw noeud-actifs (par exemple 30 000 groupes de 10 noeud-actifs).
  • On distribue aléatoirement les Np noeud-passifs dans ces Ns0 sous-réseaux.
  • Chaque sous-réseau possède Nw noeud-actifs
  • Chaque sous-réseau possède au plus Np0 = Np/Ns0 (par exemple 600 000/30 000 = 20) noeud-passifs .
  • Chaque noeud-actif produit une proposition distribuée à tous les Nt0 = Np0 + Nw noeuds du sous-réseau (par exemple 30)
  • Chaque noeud du sous-réseau n'a prendre connaissance que de Nw propositions différentes.
  • Chaque noeud d'un sous-réseau note les propositions de 0 à 5.
  • le proposition qui a le meilleur score est seule retenue pour cette étape.
  • Le noeud-actif auteur de cette proposition est dit noeud-élu.
  • Les (Nw-1) noeud-actifs non élus sont ajoutés aux noeud-passifs.
  • En fin d'étape 0 il y a Nt0-1 noeud-passifs et un seul noeud-actif dans chacun des Ns0 sous-réseaux.
  • En fin d'étape 0, sur tout le réseau, Ns0 informations ont été extraites parmi les Na (leur nombre a été réduit par un facteur nw).

étape 1[modifier]

  • On agrège les Ns0 sous-réseaux par groupe de Nw en Ns1 = Ns0 / Nw sous-réseau-agrégés de niveau 1.
  • Dans chaque sous-réseau-agrégé il y a Nt1 = Nt0 * Nw noeuds dont Np1 = (Nt0 -1) * Nw noeud-passifs et Nw noeud-actifs.
  • Dans chaque sous-réseau-agrégé on peut demander à chacun des Nw noeud-actif d'améliorer la formulation de leur information.
  • Dans chaque sous-réseau-agrégé on sélectionne la meilleure information par notation de 0 à 5.
  • Dans chaque sous-réseau-agrégé on ajoute les Nw-1 actifs non élus aux passifs, on a Nt1-1 noeud-passifs.
  • On obtient alors une information pour Nt1 noeuds.

itération étape k[modifier]

  • On itère : à chaque étape, le nombre de noeuds d'un sur-sous-réseau est multiplié par Nw.
  • A l'étape k le nombre de noeuds agrégés est Nk = (Nn + Nw)*Nwk
  • On arrête les itérations quand le sur-réseau contient plus de noeuds que le réseau : (Nn + Nw)*Nwk > Nc
  • soit k < Log (Nc / Nn + Nw)/Log Nw ( k < 4.5 )
  • par exemple si k = 4 (5ème étape) on a ( 30 * 104 = 300 000 < 900 000) mais la suivante sera de 3 000 000.

Remarque[modifier]

  • L'exemple ci-dessus montre que le processus converge vite, il est réaliste de supposer que l'on puisse extraire une information en une à deux heures de connexion.
  • Le nombre de noeud-citoyens peut varier au cours du temps, il suffit de mettre à jour la liste des noeuds entrant et sortant.
  • On peut jouer sur Nw en le faisant varier à chaque étape.
  • La randomisation permet d'éviter que des propositions soient connues de plus de noeuds que d'autres.
  • On peut faire participer des noeuds-citoyens à plusieurs dates pour augmenter le nombre de vues des propositions.
  • On peut introduire des contraintes sur le contenu de l'information lors du passage d'une étape à l'autre.
  • Les divisions introduites ne sont pas entière il sera donc nécessaire de répartir les restes.
  • On pourrait garder non pas une mais plusieurs informations à chaque étape.

Exemples[modifier]

Pour produire un texte :

Les sous-pages[modifier]

Protocole_de_production_d'une_proposition_unique_par_agrégation_de_sous-réseaux n’a pas de sous-pages à énumérer.

le canevas de cette page a été crée par {{subst:page de texte}}


Les passages à souligner
Les remarques
Les passages à commenter
Les passages à questionner
Les passages à prouver
Les passages à réfuter
Les promesses à vérifier
Les passages à référencer
Les notes et références