[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Bitobi-dev] [propagation] Algo de fin de propagation des posts
From: |
Olivier Lourdais |
Subject: |
[Bitobi-dev] [propagation] Algo de fin de propagation des posts |
Date: |
Mon, 13 Jan 2003 03:09:48 +0100 |
User-agent: |
Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.1) Gecko/20020826 |
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/
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Bitobi-dev] [propagation] Algo de fin de propagation des posts,
Olivier Lourdais <=