DEA Informatique - Systèmes et Communications
Algorithmique et techniques de base des systèmes répartis

Corrigé de l'examen du 13/12/99

Problème 1

Question 1

Il suffit d'examiner l'envoi d'un message entre deux sites. En effet, la datation des événements sur un même site et la transitivité n'introduisent pas de contraintes supplémentaires car on ne rajoute que des conditions sur l'ordre d'événements sur un même site, indépendantes de la dérive des horloges.
Soit alors t la date d'envoi d'un message et t' sa date de réception, lues sur les horloges. Alors on a (en considérant les conditions extrêmes pour la dérive et le temps de transmission) :
t + min - d < t' < t + max + d

La condition faible de validité s'écrit : t' > t. Pour qu'elle soit respectée, il faut et il suffit que d < min. Il n'y a pas de contrainte sur la valeur de max.

Question 2

Raisonnement informel : si l'horloge comporte n - 1 composants pour n sites, les événements d'un site (au moins) ne pourront être pris en compte. On pourra donc construire plusieurs chaînes causales différentes impliquant des événements différents sur ce site, avec des relations différentes aux autres, et il sera impossible de les distinguer entre elles.

Raisonnement plus rigoureux (par récurrence sur le nombre de sites).
Supposons la propriété vraie pour n sites : une horloge à n - 1 composants ne permet pas de caractériser la dépendance causale. Ajoutons un site, et un composant à l'horloge. Deux cas sont possibles :

  1. le nouveau composant concerne le nouveau site. La situation est inchangée pour les n sites initiaux.
  2. le nouveau composant  concerne l'un des n sites initiaux. Alors on peut caractériser la dépendance causale pour ces n sites, mais on peut définir sur le nouveau site deux événements ayant avec ceux des sites initiaux des relations causales différentes, et ces relations seront indistinguables.
Dans les deux cas, la propriété est vraie pour n + 1 sites si elle est vraie pour n. Comme elle est trivialement vraie pour n = 2 (les horloges scalaires ne caractérisent pas la dépendance causale sur 2 sites), elle est également vraie pour tout n>2.

Question 3

Un client n'a aucune dépendance causale directe vis-à-vis d'un autre client. Donc pour chacun des n clients il suffit d'une horloge à m+1 composants (1 pour lui et 1 pour chacun des serveurs).
Pour chacun des m serveurs, il suffit d'une horloge à m composants (1 pour chaque serveur).

Remarquons qu'il peut exister une dépendance causale indirecte entre deux clients, par l'intermédiaire d'un ou plusieurs serveurs. Les horloges ci-dessus permettent de détecter ces dépendances. Il suffit de remarquer que, pour un client donné, on n'a pas besoin des événements "envoi de la requête" et "réception de la réponse". Il suffit de raisonner sur les événements "arrivée de la requête au serveur" et "départ de la réponse du serveur", qui sont respectivement équivalents aux précédents en raison de la forme particulière de la relation client-serveur et de l'absence de relation directe entre clients.

Problème 2

Question 1 (c'était une question de cours)

Après avoir enregistré son état (à te), chaque processus pi enregistre les messages qu'il reçoit et qui portent une estampille inférieure à te. Les messages reçus de pj constituent l'état du canal pj -> pi au moment de la coupure. La durée de la période d'enregistrement est au plus égale à D.

Question 2

Chaque processus enregistre son état initial, puis p1 enregistre son état après chaque envoi de message, et p2 après chaque réception. Soit e1(i) le i-ème enregistrement de p1 et e2(j) le j-ème enregistrement de p2. Alors, pour que l'état défini par la coupure e1(i)-e2(j) soit cohérent, il faut et il suffit que i > j (l'état e1(i)-e2(i) est cohérent, sans message en transit ; si on augmente de 1 l'indice de e1, on rajoute un message en transit).
Le raisonnement ci-dessus suppose que la communication est FIFO. Si ce n'est pas le cas, la propriété reste vraie à condition de noter e2(j) l'événement "arrivée du j-ème message émis", et non "j-ème enregistrement de p2".
Cette propriété se généralise à n processus, tels que pour 2 processus quelconques la communication soit dans un seul sens. Les coupures cohérentes sont celles pour lesquelles l'indice de l'enregistrement de tout émetteur est au moins égal à celui de l'enregistrement du ou des récepteur(s) correspondant(s).
 

Problème 3

Question 1

La description des deux techniques de tolérance aux fautes a été traitée dans le cours et n'est pas reprise ici.
Pour un serveur de calcul, la redondance active permet de réduire le temps d'indisponibilité en cas de panne et évite le retour en arrière (donc la perte de temps), au prix d'une mobilisation complète des ressources. Pour un serveur de données (en supposant comme  indiqué que la panne ne touche pas les données permanentes), la technique du serveur primaire et du serveur de secours mobilise moins de ressources en permanence et répond correctement aux besoins (l'essentiel de l'état du système est constitué par les données permanentes). Si les données ne sont pas modifiées, le serveur primaire peut en outre renvoyer la réponse au client sans attendre l'acquittement de l'autre serveur.
N.B. Pour chaque application, est possible de trouver des arguments en faveur des deux solutions ; il n'y a pas de réponse unique, et les réponses ont été évaluées en fonction de leur analyse des différents critères de choix.

Question 2 (c'était une question de cours)

Si l'exécution des requêtes modifie l'état du serveur, et dans ce cas seulement, alors les requêtes doivent être exécutées dans le même ordre sur les deux serveurs.
Lors de la remise en route après panne, le serveur défaillant doit consulter l'autre pour reconstituer son état et ne peut servir de requêtes avant la restauration effective de cet état. Les requêtes reçues entre la consultation de l'autre serveur et la réception de sa réponse doivent être mémorisées pour être exécutées après restauration.

Question 3

L'intérêt de la technique indiquée est de réaliser le séquencement uniforme des requêtes sans recourir à la diffusion atomique. En contrepartie, on perd la symétrie initiale, et le traitement des pannes peut demander une plus grande implication des clients car on réduit la redondance des serveurs.

Panne du serveur 1. Le client détecte une panne du serveur 1 par un délai de garde. Il connaît le numéro de la dernière requête satisfaite, et renvoie la première requête non satisfaite au serveur 2. Le serveur 2 détecte aussi la panne par délai de garde. À la réception d'une requête de numéro i, il vérifie qu'il possède l'état correspondant au traitement jusqu'à i - 1 (sinon, il peut redemander les requêtes manquantes aux clients). Lors de la reprise, le serveur 1 restaure son état et les rôles des serveurs sont permutés (1 prend le rôle de 2 et vice-versa).

Panne du serveur 2. La panne est invisible aux clients. Elle est détectée par le serveur 1 au moyen d'un délai de garde. Pas d'action immédiate, mais le serveur 2 doit reconstituer son état après reprise (comme dans le schéma classique).

Problème 4

Question 1

Programme client :

Valeur Consulter (Clé c) {

val = ConsulterLocalement (c) ;
if (val != null) return val ;
m.fonction = consulter ;
m.clé = c ;
m.port = portclient ;
EnvoyerMsg (portserveur, m) ;
m = RecevoirMsg (portclient) ;
ModifierLocalement (c, m.valeur) ;
return m.valeur ; }

void Modifier (Clé c, Valeur v) {

ModifierLocalement (c, v) ;
m.fonction = modifier ;
m.clé = c ;
m.valeur = v ;
EnvoyerMsg (portserveur, m) ; }

void cohérence () {

while (1) { m = RecevoirMsg (portcohérence) ;
ModifierLocalement (m.clé, null) ; } }

Programme serveur :

 while (1) { m = RecevoirMsg (portserveur) ;
switch (m.fonction) { case consulter : m1.valeur = ConsulterLocalement (m.clé) ;
EnvoyerMsg (m.port, m1) ;
Add (listeclient[m.clé], m.port) ;
break ; case modifier : ModifierLocalement (m.clé, m.valeur) ;
foreach port in listeclient
EnvoyerMsg (port, m) ;
listeclient[m.clé] = null ;
break ; } }

Question 2

void main() {
if (Global.state == 0) { Global.state = 1 ;
move (portserveur) ;
} if (Global.state == 1) { Global.state = 2 ;
foreach op in Global.liste { switch op.fonction { case consulter : Op.valeur = ConsulterLocalement (op.clé) ;
break ; case modifier : ModifierLocalement (op.clé, op.valeur) ;
break ; } Add (liste2, op) ;
} move(Global.portclient) ;
} if (Global.state == 3) { // afficher résultat
} }