Re: [Bitobi-arch] commentaires sur http://reziztanzia.free.fr/wiki/index.php?pagename=b2bScenarPostPropag

[Olivier Lourdais]

> pløp! à tous

plop

0)

> Déjà,je pense qu'il faut arrêtre de modifier les pages du wiki pour
> discuter.. [...] Des objections?

nope

1)

> Sur le boitakonnage, et la proposition de garder un historique des
> noeuds par lesquel un message est passé : est-ce nécessaire?


j'avais compris qu'il pouvais y'avoir plusieurs types de noeuds : des 
noeuds de confiance et d'autres. Et que seuls les noeuds de confiance 
pouvaient s'échanger la liste des utilisateurs/cookies. Si je me suis 
trompé, effectivement çà sert à rien de garder l'historique.

2)

> Pour la 'fin de la propagation'
> Nan, t'es pas clair ;)


bon je reprends avec un exemple alors :
j'envoie deux messages, "plop" à 42:42:42 et "pika" à 42:42:43 en 
passant par le noeud 127.0.0.1
scénario sur un autre noeud :
* réception de "plop" :
- j'ai pas reçu de message plus récent depuis 127.0.0.1
- last_message{127.0.0.1} := 42:42:42
- traitement/propagation du message
* réception de "pika"
- j'ai pas reçu de message plus récent depuis 127.0.0.1 (42:42:43 > 
last_message{127.0.0.1})
- last_message{127.0.0.1} := 42:42:43
- traitement/propagation du message
* réception de "plop" (depuis un autre noeud) :
- 42:42:42 < last_message{127.0.0.1} donc ignorationage du message
* réception de "pika"
- 42:42:43 == last_message{127.0.0.1} donc ignorationage du message

c'est mieux là non ? :)
et çà coûte pas trop cher en mémoire vu qu'on a un nombre limité de noeuds

en fait, je me base sur cette propriété :
"Lemme (j'ai jamais trop su ce que ça voulait dire exactement, mais çà 
fait classe de le classe, non ?) :
Si je reçoit un message daté d1 depuis le noeud h, je suis sûr d'avoir 
déjà reçu tous les messages datés d<d1 en provenance de h, que ce soit 
par le même chemin ou par un autre."
Ça doit pas être trop dur à démontrer, pour ma part je préfère m'en 
convaincre ;)

> Enfin je pense que t'es surtout trop compliqué pour ce dont on a besoin,
> là.. je dirais, perso, qu'on garde les ID des messages reçus genre ces
> 10 dernières minutes (et les plus vieux vont dans /dev/null de toutes
> façons, un message ne devrait jamais mettre 10mn à arriver). Et si on
> reçoit un message qu'on a déjà reçu (dont l'id est dans la liste) et ben
> on le propage pas (vu qu'on l'a déjà propagé). Vous voyez un problème
> avec ce système, ou qqch de plus simple?


Honêtement, je pense que ma solution est quand même plus légère : 
vérifier qu'un id est dans la liste, çà fait beaucoup de comparaisons 
(bon, en fait en prenant une structure de donnée kivabien (table de 
hash/hashset avec chaînage des éléments pour retrouver le plus vieil id 
pour le virer) pas tant que çà, mais quand même, çà me parait pas 
élégant ;-p )

3)

> Pour l'ordre
> chronologique, on s'en tape un peu, en fait. Le premier node à recevoir
> le post l'horodate, les nodes sont tous 'synchronisés' sur un même ntp,
> et c'est marre. Comme dit plus bas, l'id unique de chaque post est (est
> dérivé?) d'un hash quelconque, par exemple de l'horodatage + l'id du
> node d'origine, comme ça on retrouve quelque chose de presque
> chronologique, et le cas (rare) de 2 posts à la même miliseconde ne
> posera 'problème' que s'ils se produisent sur le même serveur (sinon le
> hash sera déjà différent). et là, ben on rajoute un suffixe genre 00,
> 01, ..


bon, je prends un exemple :
j'ai trois messages : "pika" envoyé à 42:42:42.000 depuis le noeud A, 
"plop" envoyé à 42:42:42.001 depuis le noeud B et "coin" envoyé à 
42:42:42.002 depuis le noeud A
j'ai mon coin coin ou mon browser sur le noeud C
scénario :
* le noeud C reçoit les messages du noeud A, mon coincoin affiche :
[1]
42:42:42 : pika
42:42:42(-2) : coin
* je réponds (via le noeud C) au second message : 42:43:00 : 42:42:42-2 pan
* après un laps de temps nécessaire, tous les coincoins affichent :
[3]
42:42:42 : pika
42:42:42(-2) : plop
42:42:42(-3) : coin
42:43:00 : 42:42:42-2 pan

çà risque de faire "désordre"
une solution pourrait être de demander au noeud qui reçoit un message en 
premier de parser les horloges et de rajouter les infos nécessaires pour 
être sûr de retrouver les liens de "causalité" entre les messages plus tard
par exemple, pour le message de 42:43:00, le noeud C ajoute [42:42:42-2 
--> 42/42/2042-42:42:42.002-0/A]
comme çà le coincoin peut se rendre compte que le post de 42:43:00 fait 
en fait référence au post de 42:42:42(-3) et activer la surbrillance, 
... correctement
éventuellement il peut même se permettre un s/42:42:42-2/42:42:42-3/ 
dans le corps du post de 42:43:00 (mais là il faut que le match des 
horloges soit plus strict qu'actuellement avec les c² (pour éviter de 
remplacer des horloges qui n'en seraient pas) et aussi que les 
utilisateurs en respectent la syntaxe)

il reste quand même une source d'incohérences : si l'état de mon noeud 
(C) est [1] quand je commence à écrire ma réponse ("pan") mais est passé 
dans l'état [2], composé des 3 premières lignes de [3] quand il reçoit 
et traite ma réponse, il ne va pas interpréter mon horloge correctement 
et associera à mon post le lien [42:42:42-2 --> 
42/42/2042-42:42:42.001-0/B] !
--> solution possible : pour les messages datés de la même seconde (en 
arrondissant), ils sont insérés dans le backend/html dans l'ordre dans 
lequel ils arrivent sur le noeud
quand je poste ma réponse, le noeud (enfin l'interface web/coincoin) est 
donc dans l'état
[2']
42:42:42 : pika
42:42:42(-2) : coin
42:42:42(-3) : plop
et donc l'horloge de mon post est bien interprétée

bon au final çà peut paraitre beaucoup de bordel pour pas grand chose, 
mais je pense que c'est un mal nécessaire

4)

> Pour les problème de grande connectivité :
> Bon, déjà gardons en tête que, à priori, on prévoit un nombre limité de
> nodes dans le bitobi, on refait pas gnutella non plus, hein..
> Sinon effectivement, trop de communications pourrait être embêtant. Je
> propose de garder une table des pairs connu, mais de ne causer qu'au 10
> premiers de la liste, par exemple. En revanche, il me semble qu'avec un
> système comme ça on pourrait se retrouver avec un 'bitobi-split', et le
> réseau se scinder en deux sous-réseaux imperméables.. Quelqu'un s'y
> connait en maillage pour nous sortir quelque chose de mieux?


10 pairs connus, ça me parait énorme, moi je limiterais à 2 ou 3 (en 
laissant la possibilité de monter jusqu'à 5-6 si d'autres pairs le 
demandent), au moins pour les noeuds sur une connexion adsl (mais on 
peut quand même envisager des noeuds plus gros)
bon malheureusement j'ai rien trouvé dans mes cours d'algo distribuée (à 
chaque fois on fait l'hypothèse que le nombre de noeuds est constant et 
connu dès le départ, ce qui n'est pas vraiment le cas ici) (par contre 
j'ai trouvé un algo intéressant dans mes cours d'algo des graphes, mais 
je vais y revenir)

bon, je propose que chaque noeud connaisse en permanence l'état 
(approximatif) du réseau, modélisé par un graphe
à chaque noeud pourrait être associé ces infos :
- infos d'authentification (clé gpg + autres infos ?) pour les noeuds 
"de confiance" (pour éventuellement pouvoir distinguer un sous-réseau de 
confiance)
- nombre de connexions max à d'autes noeuds (et à des noeuds passifs 
(définition plus bas : 6) ))
- nombre de requêtes/sec pour les n dernières minutes (+ éventuellement 
le nombres d'utilisateurs différents, reconnus par leur cookies (voire 
la liste des users)) (+ éventuellement le nombre max de req/sec (et 
d'utilsateurs ?) acceptées (limite "souple" vu que c'est difficile à 
bloquer sans faire chier le peuple))
et pour chaque arc :
- sa latence [question pour les experts en résal : y'a t'il un moyen 
d'avoir une estimation fiable (en tenant compte de la synchronisation 
d'heure entre tous les noeuds) de la latence entre les noeuds A et B ? 
on peut avoir facilement (latence(A, B) + latence(B, A)), mais est il 
possile de connaître latence(A, B) ET latence(B, A) par un moyen 
qualconque ? et sinon est-il acceptable d'approximer (latence(A, B) ~= 
latence(B, A) ~= ((latence(A, B) + latence(B, A)) / 2)) dans le cas 
général ? (grosso modo, j'entends par latence "temps de la propagation 
d'un message", ou toute valeure proportionnelle au temps de la 
propagation d'un message) ]

pour maintenir tout çà, il faut penser à diffuser des messages "de 
service" :
- ajout d'une connexion (A: le noeud B vient de se connecter à moi)
- suppression d'une connexion (A: je viens de perdre le contac avec le 
noeud B)
- mise à jour de la latence (plus éventuellement des messages pour 
estimer la latence, mais je pense qui çà se ferait plutôt à un plus bas 
niveau)
- mise à jour des infos associées à un noeud

quand un noeud veut rejoindre le réseau (je zappe des étapes qui ont 
déjà été énumérées) :
1. il demande à un noeud (noeud fixe, de référence ?) l'état du réseau 
(le graphe)
1bis. éventuellement il ne conserve que le sous-graphe composé des 
noeuds de confiance
2. il applique sur ce graphe un algo basé sur Roy-Warshall (voir plus 
bas : 5) ) pour déterminer le diamètre du réseau (le nombre max d'arcs 
entre deux noeuds, mais ici plutôt la latence max entre deux noeuds)
3. il se connecte aux deux noeuds qu'il a établi être les extrémités du 
diamètre du réseau
remarques :
- un comportement de ce type a imho tendance à améliorer l'état du 
réseau (vu que çà ajoute un lien potentiellement plus rapide entre les 
deux noeuds les plus éloignés du réseau)
- l'algo peut prendre d'autres éléments en compte (info sur les noeuds) 
pour choisir les noeuds
- l'algo est donné à titre indicatif, pas normatif (çà fait pas partie 
du protocole et çà n'est pas gênant que tous les noeuds n'utilisent pas 
le même algo)
- le noeud peut se choisir plus de 2 voisins
- on peut aussi envisager qu'un noeud déjà relié au réseau lance 
régulièrement un algo de ce genre pour voir s'il est possible 
d'améliorer le réseau
- quand est noeud se déconnecte, ses anciens voisins vont éventuellement 
établir de nouvelles liaisons (selon leur nb de liaison min) pour 
améliorer le réseau et leur place dans le réseau

5)
Algo de Roy-Warshall

c'est à la base un algo de calcul de fermeture transitive d'un graphe
il est assez efficace (O(n3) en cpu quand même, mais c'est mieux que ses 
concurrents et c'est supportable pour le nombre de noeuds qu'on aura, et 
il utilise un espace mémoire de 1 graphe seulement (y'a un autre algo, 
en O(n4) et avec un espace mém de 3 graphes !)) et il offre la 
possibilité d'insérer d'autres calculs qui peuvent nous intéresser
l'algo de base (en pseudo langage, je le balance tel quel) :
-----
GRAPHE roy-warshall(GRAPHE G) c'est
  local SOMMET x, y, z; ENS[SOMMET] X;
début
  Result := G; X := G.lst_som;
  pour tout x de X
      pour tout y de Y
          si Result.validarc(y, x) alors
              pour tout z de X
                  si Result.validarc(x, z) alors
                      Result.ajoutarc(y, z)
                  fsi
              fpourtout
          fsi
      fpourtout
  fpourtout
fin
-----
bon il est pas trop dur à comprendre, je vous passe le bordel 
mathématique qu'il y a tout autour :)
et une adaptation (Warshall-Floyd) qui devrait nous être plus utile :
-----
TABLE[SOMMET, SOMMET] SOMMET::R;
GRAPHE warshall_floyd(GRAPHE G) c'est
  local SOMMET x, y, z; ENS[SOMMET] X;
  REEL vy, vz, w;
début
  Result := G; X := G.lst_som;
  initroutage;
  pour tout x de X
      pour tout y de Y
          vy := Result.v(y, x);
          si vy != nil alors
              pour tout z de X
                  vz := Result.v(x, z);
                  si vz != nil alors
                      w := Result.v(y, z);
                      si w != nil alors
                          si vy + vz < w alors
                              w := vy + vz;
                              majroutage(y, z, x)
                          fsi
                      sinon
                          w := vy + vy; // !!!!! bug ?
                          majroutage(y, z, x)
                      fsi;
                      Result.modif_val(y, z, w)
                  fsi
              fpourtout
          fsi
      fpourtout
  fpourtout
fin

avec
initroutage : quelquesoit z appartenantà X, quelquesoit y appartenantà X 
: y.R[z] := (y, z)  appartientà arcs(G) ? z : nil
majroutage(y, z, x) : y.R[z] := y.R[x]
-----
bon celui là est un peu plus dur à lire, je vais essayer de le potasser 
et de pondre une version plus mieux dans la semaine
mais en gros çà calcule la distance (ici la latence) entre deux noeuds 
quelconques du graphe en se basant sur la distance entre les noeuds 
voisins (valeurs initialement dans le graphe) et en se servant d'une 
table de routage (euh en fait nan, çà a l'air de juste produire une 
table de routage mais de pas s'en servir, donc on peut zapper ces lignes)

6)
Proposition d'architecture

- les noeuds ne savent communiquer qu'avec les noeuds
- une catégorie particulière de noeuds : les noeuds passifs : ils savent 
parler aux noeuds mais ils ne propagent pas les posts
- chaque site a un noeud et (a priori) une interface web/coincoin qui 
est un noeud passif
- on peut imaginer des coincoins de seconde génération (cc2g) qui serait 
des noeuds passifs et qui ne passeraient plus par une interface --> plus 
besoin d'ouvrir une connexion toutes les 30 secondes, et les posts 
arrivent en direct

et après on peut ajouter des antigones (noeuds passifs "muets") et plein 
de jouets dans ce genre
penser aussi à une interface d'admin (noeud passif "sourd") pour les 
plonks, passages en mode bunker, ...

7)
Signature des posts

Je pense qu'il pourrait être intéressant de rajouter une signature GPG 
sur les posts :
- vérification par les noeuds de confiance que la signature est bonne 
(si elle est présente) pour les utilisateurs enregistrés (non anonymes)
- en mode bunker, seuls les posts signés sont autorisés

la signature est effectuée :
- par le coincoin avec la clé de l'utilisateur
- par l'interface html (noeud de confiance) avec sa propre clé pour les 
utilisateurs enregistrés qu'elle connait

même remarque que pour le 1)
mais après tout, il vaut peut-être mieux penser à blinder le système dès 
le début ?

8)
vrac

tous les possesseurs de noeuds signés peuvent plonker/passer en mode 
bunker/... qui ils veulent ou il vaut mieux imaginer un système de vote ?


bon, je crois que c'est tout ce que j'avais en tête
merci d'avoir lu ce mail jusqu'à la fin :)
désolé si j'ai écrit quelques énormités, mais j'ai commencé à écrire ce 
mail il y a une quinzaine d'heures et j'en ai repris la rédaction après 
une nuit blanche et quelques boissons alcoolisées, donc j'ai ptet pas 
les idées très fraiches ;)

je serais aussi probablement offline toute la semaine ou presque, donc 
d'avance joyeux réveillon, tout çà, tout çà (pas "bonne année" : çà se 
fête en début d'année si je ne m'abuse)

@+
olo