[Bitobi-dev] [propagation] Algo de fin de propagation des posts

[Olivier Lourdais]

Pour rappel, et au cas où il y aurait des questions en suspens, je 
reprends l'algo de fin de propagation des posts.

chaque message a une estampille : (noeud qui a daté le message, date)
chaque noeud maintient pour chaque "noeud dateur" qu'il connait l'heure 
du dernier post qu'il a reçu et qui a été daté par ce noeud dateur
quand un noeud reçoit un post d'un autre noeud, il vérifie que l'heure 
du post est postérieure à l'heure du dernier post reçu pour le noeud qui 
a daté le post (sinon post ignoré) (puis il met à jour cette date)


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

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 :
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."

Démonstration du lemme :
Concentrons nous sur les messages émis par le noeud A.
Domontration par récurrence :
- étape 0 : le lemme est vérifié sur le noeud A (trivialement, il traite 
ses propres messages dans le bon ordre)
- supposons que le lemme est vérifié à l'étape n-1 : les voisins du site 
B qui le précèdent dans la diffusion des messages de A les reçoivent 
dans l'ordre et chacun les propage dans l'ordre => B reçoit plusieurs 
séquences entrelacées contenant chacune les messages de A dans le bon 
ordre => pour chaque message de A, B est sûr d'avoir reçu les précédents 
depuis le même voisin (chacun d'entre eux ayant pû être ignoré si et 
seulement si il a été précédemment délivré par un autre voisin), càd 
lemme vérifié à l'étape n
- donc lemme vérifié \o/