Chapitre 3 : Diffusion

Pierre Gançarski*

Octobre 2003

Département d'informatique

UFR de Mathématique et Informatique

Université Louis Pasteur – Strasbourg

Table des matières

1 - Introduction.. 2

2 - Protocole utilisant un serveur.. 2

3 - Protocole utilisant des estampilles. 3

4 - Protocole respectant l'ordre causal.. 6

* Pierre.Gancarski@dpt-info.u-strasbg.fr

1 - Introduction

Problématique Étant donnés N sites et un réseau de communication, comment assurer une diffusion stable où

- tous les destinataires, non en panne, reçoivent les mêmes messages ;

- si l'émetteur d'un message tombe en panne pendant une diffusion, alors aucun destinataire ne reçoit le message.

Hypothèses

- Il n'y a pas d'ordre supposé sur la réception des messages par les destinataires

- Il n'y a pas de relation entre l'ordre d'émission et l'ordre de réception.

Définition : Si l'ordre de réception est identique pour tous les récepteurs (propriété d'uniformité) ET si l'ordre de réception est identique à l'ordre global ou causal d'émission alors la diffusion est dite atomique.

2 - Protocole utilisant un serveur

Les émetteurs transmettent leurs messages au serveur qui les numérote et assure la diffusion. Ce protocole utilise très souvent des fenêtres d'anticipation.

Le serveur S dispose d'un tampon d'émission qui lui permet de stocker T messages, d'une variable A qui donne le numéro du dernier message reçu à diffuser et d'une variable d'acquittement V qui correspond au dernier message acquitté par TOUS les destinataires. A chaque case C du tampon est associé un tableau T_T de N entiers (ou bits).

Lorsque S reçoit un message à diffuser.

- soit le tampon n'est pas plein A - V < T : il numérote le message par A + 1 et incrémente A. Puis, il l'envoie a tous les destinataires.

- soit le tampon est plein : il prévient l'émetteur et stocke le message "ailleurs". Puis il renvoie chacun des messages du tampon aux destinataires qui ne l'ont pas acquitté.

Chaque destinataire dispose d'une variable R qui donne le numéro du dernier message reçu et acquitté. Lorsqu'un destinataire reçoit un message numéroté d noté M_d

- si d > R + 1, alors le destinataire stocke ce message et demande au serveur la ré-émission (vers lui) des messages M_Rk tel que d + 1 < R_k < R et M_Rk n'est pas stocké par le destinataire.

- si d = R + 1 alors le destinataire émet l'acquittement du message Md vers le serveur, incrémente R et "utilise" M_di

- si d < R + 1 alors le destinataire émet l'acquittement du message Md vers le serveur

Si après une incrémentation de R, le destinataire trouve M_R+1 dans son stock, il émet l'acquittement du message MR+1 vers le serveur, incrémente R et "utilise" M_R+1.

Lorsque S reçoit un acquittement du message M„ stocké dans la case c d'un destinataire Di , il met à 1 le bit T_T[i]. Si toutes les cases du tableau T_T valent 1, il considère le message M„ comme acquitté par tous les destinataires : dès que v = V + 1, il déstocke M„ et incrémente v.

Lorsqu'il reçoit un message de demande de ré-émission d'un message M, il le ré-émet vers le demandeur.

Cet algorithme qui assure l'ordre entre le serveur et les destinataires ainsi que l'uniformité, est utilisé par le réseau ethernet.

3 - Protocole utilisant des estampilles

Protocole ABCAST : Atomic Broadcast.

Un site Si émet un message Mk en diffusion en le numérotant par son horloge locale Hi par k = Hi. Puis il incrémente Hi.

Un site S_j qui reçoit un message M_k, le met dans une file d'attente locale AM_I au site et le marque "en attente". Il renvoie à l'émetteur un accusé de réception Rk estampillé par la date de réception (H„ j) du message puis incrémente H_j.

L'émetteur Si maintient un tableau Ai(l..n) lui permettant de mémoriser les acquittements reçus. Quand il reçoit un accusé de réception Rk de S_j il incrémente A_i[j]. Quand l'émetteur a reçu tous les accusés de réception Rk (c'est à-dire : b'j = l..n, Ai[j] > k ), il valide le message Mk en envoyant aux destinataires un message Vk d'estampille E_k = E_m,,,_x égale au maximum des estampilles reçues.

Lorsqu'un site Sv reçoit un message de validation V_k d'estampille E_k correspondant à un message M_k, il date le message Mk par l'estampille Ek, effectue H,. = max(Ek, H,.) + 1, et met Mk dans la liste des messages utilisables UMi

Voyons quand il peut les utiliser.

Prenons l'exemple suivant : S2 envoie un message M_I. Sl envoie deux messages M2et Mien diffusion de suite. Tout ce que S2 sait, c'est qu'il n'a pas reçu de message en diffusion avant d'émettre Ml. Voyons à quel moment, il pourra décider de traiter ces trois messages, en fonction des dates d'arrivée de ces messages sur les différents sites.

• Premier cas

S2 peut traiter Ml lorsqu'il reçoit tous les accusés de réception (donc lorsqu'il s'envoie V_i) car il sait que toute nouvelle demande sera estampillée par lui-même, d'une date supérieure à la date d(V₁) = H2 de réception de Vl car H2 = max(estampille(Vi), d(V₁)) + 1 .

• Deuxième cas

Il ne peut pas traiter Ml car on peut avoir la situation suivante

où Ml est acquitté en 3 par S3, alors que M2 est acquitté en 1 par SI, en 1 par S3 et en 2 par S2 donc est daté par 2.

Il est donc obligé d'attendre.

• Troisième cas

Pour S2 il n'y a aucune différence entre ce cas et le cas 2. Il attend(alors que nous voyons bien qu'il pourrait le traiter)

En conclusion, un site ne peut donc traiter un message Mk que si les diffusions commençant entre la date de réception de Mk et la date de réception de la validation de Mk sont résolues.

Donc

Pour chaque message M_ut utilisable, il attend la date de validation pour tous les messages M,_a qu'il a acquitté avant réception de la validation de M_k. Puis il traite dans l'ordre de leur date de validation, les messages utilisables.

Remarque

On peut représenter en un seul état l'émission en diffusion d'un message Mk par Si , sa réception, son acquittement et la réception de cet acquittement par Si avec Hi = Hi+2, Ai(i) = Ai(i)+1, Ami = AMi U{Mk}

Exemple d'application du protocole

Nous donne, avec Hi estampille du site Si, Mk message envoyé, Ai acquittements reçus, AMi message en attente de datage, UMi message utilisables, Rk envoi d'un acquittement de Mk , Vk envoi d'une validation de Mk )

Évén.

E1

E2

E3

E4

E5

E6

E7

E8

E9

E10

E11

E12

E13

H1

2

3

3

4

A1

1,0,0

1,1,0

AMI

M2

M2,M1

M2,M1,M3

UM1

Action

M2=M(0,1)

Rl(2,1)

R3(3,1)

H2

2

3

3

5

6

A2

0,1,0

0,1,1

0,2,1

1,2,1

1,2,2

AM2

M1

M1,M2

M1,M2,M3

M2,M3

UM2

M1(2,1)

Action

M1=M(0,2)

R2(2,2)

M3=M(3,2)

Vl(2,1)

H3

1

2

3

A3

M1,M3,M2

AM3

M1

Ml,M3

UM3

Action

R1(0,3)

R3(1,3)

R2(2,3)

Évén.	E14	E15	E16	E17
H1		5	5
A1			1,1,1
AMI		M2,M3	M3
UM1		M1(2,1)	M1(2,1),M2(2,3)
Action			V2(2,3)
H2				6
A2				2,2,2
AM2				M3
UM2				M1(2,1),M3(3,2)
Action				V3(3,2)
H3	4
A3
AM3	M3,M2
UM3	M1(2,1)
Action

• en Ell : les acquittement reçus sont : (2,1) ; (1,2) et (0,3) è validation par (2,1). S2 ne peut pas traiter Ml car il y a une autre diffusion en cours
• en E14, S3 ne peut pas traiter Ml car il y a une autre diffusion en cours, idem en E15 pour S_l
• en E16 : les acquittements reçus sont : (1,1) ; (2,2) et (2,3) è validation par (2,3). S₁ ne peut pas traiter M2 car il y a une autre diffusion en cours[1]
• en E17 : les acquittement reçus sont : (3,1) ; (3,2) et (1,3) è validation par (3,2). S2 ne peut pas traiter M3 car il y a une autre diffusion en cours¹

Évén.	E18	E19	E20	E21
H1
A1
AMI
UM1		M1(2,1), M2(2,3), M3(3,2)
Action		TRAITER M1, M2, M3
H2
A2
AM2
UM2			M1(2,1), M3(3,2), M2(2,3)
Action			TRAITER M1, M2, M3
H3	5
A3
AM3	M2
UM3	M1(2,1), M3(3,2)			M1(2,1), M3(3,2), M2(2,3)
Action				TRAITER M1, M2, M3

L'uniformité est assurée, pas l'atomicité : si tous les sites reçoivent _Mi+i avant Mi, alors l'estampille de Vi₊l sera inférieure à l'estampille de Vi et donc _Mi+i sera "utilisé" avant Mi.

De plus, ce protocole nécessite 3 x N messages.

Néanmoins, la reprise sur panne est simplifiée : Un site Si peut reprendre le protocole en cas de panne en examinant sa liste de messages en attente

Pour chaque message M_k de cette liste S_i interroge tous les autres destinataires

- Si un site Sj possède le message Mk à l'état "utilisable", il transmet à Si l'estampille Ek associée à M_k. Si transmet alors, le message de validation V_k estampillé Ek à tous les autres sites.

- Sinon, S émet Mk comme s'il n'avait jamais été émis.

4 - Protocole respectant l'ordre causal

Protocole CBCAST : Causal Broadcast

Chaque site Si entretient une horloge vectorielle Vi[N]. Chaque événement d'envoi ou de réception de message sera daté par celle-ci : la relation de précédence causale entre les événements pourra donc être retrouvée (propriété des horloges vectorielles).

- avant de diffuser un message M, S_i exécute V_i[i] + + et estampille M par VM = V_i.

- à la réception d'un message M envoyé par Si et estampillé par VM, S_j le met en attente jusqu'à ce que VM[i] = V_j[i] + 1 et "k ¹ i, VM[k] £ V_j[k] (horloge vectorielle)

- après traitement de M, Sj exécute : V_j[k] = max(Vj[k], VM [k]) pour tout k = 1, ..., N

Exemple

nous donne :

Evénement	État et action initiaux	État et actions correspondants
EO	V1=[0,0,0]	V1=[1,0,0], émission M1([1,0,0],1)
El	V2=[0,0,0], réception de Ml par S2	S2 traite Ml, V2=[1,0,0]
E2	V3=[0,0,0]	V3=[0,0,1], émission M2([0,0,1],3)
E3	V2=[1,0,0], réception de M2 par S2	S2 traite M2, V2=[1,0,1]
E4	V3=[0,0,1], réception de Ml par S3	S3 traite Ml, V3=[1,0,1]
E5	V3=[1,0,1]	V3=[1,0,2], émission de M3 :([1,0,2],3)
E6	V2=[1,0,1], réception de M3 par S2	S2 traite M3, V2=[1,0,2]
E7	V2=[1,0,2]	V2=[1,1,2], émission de M4 :([1,1,2],2)
E8	V3=[1,0,2], réception de M4 par S3	S3 traite M4, V3=[1,1,2]
E9	V1=[1,0,0], réception de M4 par S1	V1[3] < Vm[3], S1 stocke le message
E10	V1=[1,0,0], réception de M2 par S1	S1 traite M2, V1=[1,0,1]
E11	V1=[1,0,1], réception de M3 par S1	Si traite M3, V1=[1,0,2] à
E11(suite)		S1 peut alors traiter M4, et Vl=[1,1,2]

A noter que les trois horloges vectorielles V1, V2 et V3 ont la même valeur.

---

[1] Il faudrait voir s’il peut traiter M₁