Algorithm Distributed
1) Algorithm Structure :
var
1: arrayofworddatain={Datatobesent},dataout=⇐1,...,...,⇐1
Label1: {Condition}
2: beginsend<tag,datain>toqend
3: code;
Label2: {Condition}
4: beginreceive<pack,w,i>;
5: code;
6: end
Label3: {receive<stop,i>}
7: begincode;
8: print(”Goodbye”);
9: end
Information échangée entre deux nœuds connectés
Exemple avec deux processus p et q
Les processus p et q ont le même nombre de messages à échanger.
Le réseau est fiable mais asynchrone (il n'y a donc aucune hypothèse sur l'ordre
des messages).
Exercice :
1. Écrire un algorithme simple permettant l’échange d’informations entre les deux
processus.
var
1: array of word datain={Data to be sent}, dataout = ⇐1,...,...,⇐1
2: count rcv=0, i=0
Send: { i < n }
3: begin
4: send <msg,datain[i],i > to q
5: i = i +1;
6: end
receiveMsg: { receive <msg,data,j> }
7: begin
8: dataout[j]=data;
9: count rcv = count rcv +1;
10: end
Stop: { i==n AND count rcv==n }
11: begin
12 : print(”Goodbye”);
13: STOP.
14: end
Information échangée entre deux nœuds connectés
Exemple avec deux processus p et q
p et q ont le même nombre de messages à échanger.
Le réseau est fiable.
Exercices :
1. Écrire un algorithme simple permettant l’échange d’informations entre les deux
processus.
2. Que se passe-t-il si le réseau est peu fiable ? Écrire un algorithme simple qui
prend en compte la perte de messages.
Corrigé :
1) Algorithme pour un réseau fiable
Dans ce cas, les messages arrivent toujours à destination, donc on garde
une structure simple sans retransmission.
var
1: array of word datain = {Données à envoyer}, dataout = ⇐1,...,...,⇐1
2: count_rcv = 0, i = 0
Send: { i < n }
3: begin
4: send <msg, datain[i], i> to q
5: i = i + 1;
6: end
receiveMsg: { receive <msg, data, j> }
7: begin
8: dataout[j] = data;
9: count_rcv = count_rcv + 1;
10: end
Stop: { i == n AND count_rcv == n }
11: begin
12: print("Goodbye");
13: STOP.
14: end
Explication :
Chaque message est envoyé une seule fois sans vérification.
Le programme s'arrête quand tous les messages ont été envoyés et reçus.
2) Algorithme pour un réseau peu fiable (avec retransmission)
Ici, on ajoute un accusé de réception (ACK) pour confirmer la bonne
réception des messages. Si un message est perdu, il est retransmis.
var
1: array of word datain = {Données à envoyer}, dataout =
⇐1,...,...,⇐1
2: array of boolean ack = {⇐0, ..., ⇐0} // Tableau de confirmation
3: count_rcv = 0, i = 0
Send: { i < n }
4: begin
5: send <msg, datain[i], i> to q
6: start_timer(i) // Démarrer un timer pour vérifier la réception
7: i = i + 1;
8: end
receiveMsg: { receive <msg, data, j> }
9: begin
10: dataout[j] = data;
11: count_rcv = count_rcv + 1;
12: send <ACK, j> to p // Envoyer un accusé de réception
13: end
receiveACK: { receive <ACK, j> }
14: begin
15: ack[j] = true; // Marquer le message comme reçu
16: stop_timer(j) // Arrêter le timer associé
17: end
Resend: { timeout(i) AND ack[i] == false }
18: begin
19: send <msg, datain[i], i> to q // Retransmettre le message perdu
20: start_timer(i) // Redémarrer le timer
21: end
Stop: { i == n AND count_rcv == n }
22: begin
23: print("Goodbye");
24: STOP.
25: end
Explication :
Chaque message envoyé est accompagné d'un timer.
Si l'ACK n'est pas reçu avant expiration du timer, le message est retransmis.
Dès qu'un ACK est reçu, la retransmission est annulée.
L'algorithme garantit que tous les messages finissent par être livrés.
