Un modèle conceptuel pour les services

• Petite échelle : mémoire partagée
  • Contrôle de la concurrence par mémoire transactionnelle (cf. les nouveaux processeurs d’Intel)
  • Mais présence aussi à grande échelle : cf. les bus de services
• Grande échelle : échange de messages
  • Services web à l'échelle d'Internet
  • Mais présence aussi à petite échelle : cf. le Single-chip Cloud Computer d’Intel

• Simulation d’une mémoire partagée par échanges de messages
  • Un agent représentant la mémoire partagée
  • Lectures et écritures représentées par des messages
• Simulation des échanges de message par une mémoire partagée
  • Un canal représenté par une file en mémoire, partagée en écriture par les émetteurs et en lecture par les destinataires
  • Une communication représentée par une écriture suivie d’une lecture exercée en attente active par le destinataire
• Exploitation de cette dualité pour permettre des implémentations d’un modèle avec l’autre

• L’agent émet un message et continue son activité. Le message transite pour finalement arriver à destination, à une date indéterminée.

• Exemple : le courrier postal

  Deux communications asynchrones. Pendant les communications décrites ci-dessous, les trois agents peuvent agir : d'autres transitions pourraient se produire.

     Emetteur[bp(lettre)], Poste[], Destinataire[] 
       // L'émetteur produit le message bp(lettre).
  -> Emetteur[], bp(lettre), Poste[], Destinataire[] 
       // La lettre s'achemine vers la poste.
  -> Emetteur[], Poste[bp(lettre)], Destinataire[]  
       // La poste reçoit le lettre postée.
  -> Emetteur[], Poste[bal(lettre)], Destinataire[] 
       // La poste réalise le tri postal et distribue les lettres.
  -> Emetteur[], Poste[], bal(lettre), Destinataire[] 
       // La lettre s'achemine vers la boîte aux lettres.
  -> Emetteur[], Poste[], Destinataire[bal(lettre)] 
       // Le destinataire reçoit la lettre.
  

L’agent produit un message que consomme immédiatement le destinataire : c'est le rendez-vous. Il est possible de modéliser la communication synschrone dans le modèle chimique, soit en ajoutant une transition particulière pour l'exécution, soit en utilisant une règle particulière pour exprimer la synchronisation. Prenons l'exemple du téléphone.

• Exemple de communication synchrone avec une transition particulière

  Les deux règles s'exécutent d'une manière synchronisée : le message produit est immédiatement consommé.

  Règles analogues au cas asynchrone

  Emetteur[
    Feu() -> appel18("Au feu", "4 rue Alfred") & Evacuation()
  ]
  Pompier[   
    appel18(message, adresse) -> Alerte(message, adresse)
  ]
  

  Exécution avec une transition assurant la synchronisation

     Emetteur[Feu()], Pompier[]
       // L'émetteur constate le début d'un incendie.
  -> Emetteur[Evacuation()], Pompier[Alerte("Au feu", "4 rue Alfred")]
       // L'émetteur et le récepteur se synchronisent via 
       //   le message échangé sur le canal synchrone appel18.
  

• Exemple de communication synchrone avec une règle particulière de synchronisation

  Règle impliquant les deux agents en communication synchrone (pouvant être interprétée comme une traduction des deux règles ci-dessus)

  Emetteur[ Feu() & X ] & Pompier [ Y ] 
  ->
  Emetteur[ Evacuation() & X ] & Pompier[ Alerte("Au feu", "4 rue Alfred") & Y]
  ]
  

  Exécution avec la même transition qu'au dessus

     Emetteur[Feu()], Pompier[]
       // L'émetteur constate le début d'un incendie.
  -> Emetteur[Evacuation()], Pompier[Alerte("Au feu", "4 rue Alfred")]
       // L'émetteur et le récepteur se synchronisent via 
       //   le message échangé sur le canal synchrone appel18.
  

La première modélisation traduit la communication synchrone en définissant une transition à partir de deux règles ; la seconde modélisation définit directement la règle généralisant la transition, cette règle correspondant à la communication sur un canal synchrone.

Une communication synchrone est plus contraignante qu'une communication asynchrone puisqu'elle induit des synchronisations avec les rendez-vous. Ainsi, une communication synchrone peut entraîner un blocage alors qu'une communication asynchrone n'en entraînerait pas, comme le montre l'exemple trivial suivant.

Client[
    -> requete()
]
Serveur[   
  // Ne fait rien, donc ne répond pas à la requête.
]

Avec une communication synchrone, aucune réaction ne se produit. Avec une communication asynchrone, le client envoie indéfiniment des requêtes.

(Rappel : le terme "diachrone" est inusité mais pratique. Cf. supra les variantes.)

• L’agent émet un message que reçoit le destinataire avec un délai qu'on peut majorer.

• Exemple : une requête Web (quand les connexions et les agents fonctionnent correctement)

  Deux communications diachrones. Pendant les communications décrites ci-dessous, le client et le serveur peuvent agir, mais d'une manière limitée : d'autres transitions pourraient se produire, mais en un nombre inférieur à un majorant fixé.

     Client[url(requête, ret)], Serveur[]
       // Le client produit la requête url(requête, ret).
  -> Client[], url(requête, ret), Serveur[]
       // La requête s'achemine vers le serveur.
  -> Client[], Serveur[url(requête, ret)]  
       // Le serveur reçoit le requête.
  -> Client[], Serveur[ret(reponse)]
       // Le serveur produit la réponse qu'il renvoie sur la canal ret.
  -> Client[], ret(reponse), Serveur[]
       // La réponse s'achemine vers le client.
  -> Client[ret(reponse)], Serveur[]
       // Le client reçoit la réponse.
  

Remarque : le modèle chimique n'est pas vraiment adapté pour modéliser ce mode de communication. Pour exprimer les contraintes temporelles, ou bien il faut encoder des chronomètres, ou bien il faut instrumenter l'exécution (la sémantique).

Avec une communication asynchrone, le temps d'une communication est indéfini. Pour le rendre nul, il suffit de bloquer l'émetteur dans l'attente d'un accusé de réception. Détaillons.

• Hypothèse : une communication asynchrone
• Objectif : communication synchrone
• Solution : protocole avec accusé de réception

  • L’agent émetteur envoie un message et bloque l’activité ayant causé l’émission. A réception du message, l’agent destinataire envoie immédiatement un accusé de réception.

    Exemple : la phase initiale de synchronisation du protocole TCP ("Transmission Control Protocol"), avec un double accusé de réception

    Formalisation

    Client[
    - ... -> canal(rep) & Blocage
    - Blocage & rep() -> ...
    - ... & (Blocage inactif) -> ... // Blocage : inhibiteur pour les autres réactions
    ], 
    Serveur[
    - canal(k) & ... -> k() & ... // Accusé de réception 
    ]
    

    Pour garantir le blocage, on impose que les autres règles du client ne peuvent se déclencher si l'atome Blocage est présent : il s'agit donc d'un inhibiteur.

  • Synchronisation logique mais pas physique (ce n'est pas du temps réel mais logique)

Cette solution présente l'inconvénient de produire des blocages dans des situations où logiquement une véritable communication synchrone n'en aurait pas produit. Considérons deux agents aux comportements parfaitement symétriques réalisant chacun une communication synchrone avec l'autre.

Agent 1

• Canal fourni : requete1
• Canal requis : requete2
• Etat initial : Init()

- Init() -> requete2()
- requete1() ->

Agent 2

• Canal fourni : requete2
• Canal requis : requete1
• Etat initial : Init()

- Init() -> requete1()
- requete2() ->

Cette définition peut se traduire ainsi, suivant la définition de la communication synchrone que nous avons retenue.

Agents A1 et A2

- A1[ Init() & X ] & A2[ Y ] -> A1[ X ] & A2[ Y ]
- A1[ X ] & A2[ Init() & Y ] -> A1[ X ] & A2[ Y ]

Les deux communications peuvent se produire, l'une après l'autre, pour aboutir à l'état final A1[], A2[], à partir de A1[ Init() ], A2[ Init() ].

Peut-on réaliser ces communications synchrones au-dessus d'une communication asynchrone, en utilisant la traduction donnée reposant sur le blocage en attente d'un accusé de réception ? La réponse est négative, comme le montre le contre-exemple suivant.

Agent 1

• Canal fourni : requete1, ar1
• Canal requis : requete2
• Etat initial : Init()

- Init() -> requete2(ar1) & Blocage() 
- requete1(k) & (Blocage() inactif) -> k() 
- ar1() & Blocage() ->

Agent 2

• Canal fourni : requete2, ar2
• Canal requis : requete1
• Etat initial : Init()

- Init() -> requete1(ar2) & Blocage() 
- requete2(k) & (Blocage() inactif) -> k()
- ar2() & Blocage() ->

Après l'émission de requete2(ar1) et de requete1(ar2), les deux agents sont bloqués et donc incapables d'accuser réception. Or seule la réception d'un accusé permet le déblocage. C'est un exemple d'inter-blocage ("deadlock"), problème étudié ci-dessous. Il se manifeste par un circuit dans le graphe représentant les demandes et les blocages de rendez-vous.

Une meilleure traduction est d'utiliser une file pour l'émission. Elle affaiblit la synchronisation mais préserve cependant l'ordre causal, comme on le verra ci-dessous.

Cette solution par blocage est très souvent utilisée pour un protocole requête-réponse : le client bloque dans l'attente de la réponse du serveur, ce qui fait que le temps de communication peut être considéré comme nul du point de vue du client ; du point de vue du serveur, il est égal au temps de calcul de la réponse augmenté du temps de communication. Autrement dit, la communication est synchrone du point de vue client, quelle que soit le mode de communication entre le client et le serveur : le protocole requête-réponse est dit synchrone.

Règles (en supposant la communication asynchrone)

• req(k, x) : canal fourni par le serveur et dédié aux requêtes
• rep(x) : canal fourni par le client pour obtenir la réponse
• u : valeur
• Blocage : état marquant le blocage côté client
• DebutTraitement(k, x), FinTraitement(k, x, y) : états marquant le début et la fin du traitement côté serveur

Client[
- ... -> req(rep, u) & Blocage & ... // Envoi de la requête et début du blocage
- rep(y) & Blocage & ... -> ... // Réception de la réponse et fin du blocage
- ... & (Blocage inactif) -> ... // Blocage : inhibiteur pour les autres réactions
],
Serveur[
- req(k, x) & ... -> DebutTraitement(k, x) & ... // Réception de la requête et début du traitement
- ... // Traitement
- FinTraitement(k, x, y) -> k(y) & ... // Fin du traitement et  envoi de la réponse
]

Le blocage a l'avantage de préserver la cohérence logique, en évitant toute concurrence côté client, mais le défaut de réduire l'efficacité, en empêchant tout parallélisme. La solution est de transformer le blocage en attente : l'attente de la réponse future du serveur, ce qu'on appelle une promesse, ce qui permet de gérer précisément le parallélisme, en bloquant certaines réactions, celles dépendant de la réponse et pour lesquelles la promesse est un inhibiteur, et en autorisant les autres.

Client[
- ... -> req(rep, u) & Attente(u) & ... // Envoi de la requête et début de l'attente
- rep(x, y) & Attente(x) & ... -> ... // Réception de la réponse et fin de l'attente
- ... -> ... // Pas d'inhibition
],
Serveur[
- req(k, x) & ... -> DebutTraitement(k, x) & ... // Réception de la requête et début du traitement
- ... // Traitement
- FinTraitement(k, x, y) -> k(x, y) & ... // Fin du traitement et  envoi de la réponse
]

Ce modèle de communication asynchrone reposant sur une promesse de réponse et une réponse future est devenu courant dans les langages à objets et leurs frameworks dédiés aux services web, dans la mesure où il remplace les invocations de méthodes distantes, qui sont synchrones. Il tend aussi à remplacer l'approche avec des threads et des objets partagés : on associe à la promesse la réaction qui doit être déclenchée lorsque la réponse arrive. Par exemple, en Java, il existe une interface générique appelée Future utilisable pour les réponses des services Web.

On pourrait considérer qu'une communication asynchrone est un cas particulier de communication synchrone, un temps indéfini pouvant être nul : cependant, ce n'est pas exact, dans la mesure où une communication synchrone implique un rendez-vous, qui peut donc bloquer l'émetteur. Pour éviter des rendez-vous bloquants, on dissocie la production de l'émission et la réception de la consommation. On transforme ainsi une communication synchrone agent-à-agent en point-à-point, par des mises en attente : la communication devient asynchrone agent-à-agent. Détaillons.

Hypothèse : communication synchrone (agent-à-agent)

Exemple d'une requête

• req(x) : canal fourni par le serveur et dédié aux requêtes
• A, B : états du client
• C, D_x : états du serveur (dont un paramétré)

Règles

Client[
- A -> req(v) & B // Production de la requête
]
Serveur[
- req(x) & C -> D_x // Consommation de la requête
]

Lors d'un rendez-vous, la transition suivante se produit.

Exécution

   Client[A], Serveur[C]
-> Client[B], Serveur[D_v]

Si le serveur n'est pas initialement dans l'état C, le client est bloqué.

Exécution

Client[A], Serveur[]

Pour éviter ce blocage, il est possible d'ajouter des attentes.

• Req(x) : état correspondant à une mise en attente (pour émission côté client, pour consommation côté serveur)

Règles

Client[
- A -> Req(v) & B // Production de la requête
- Req(x) -> req(x) // Emission de la reqûete si rendez-vous
]
Serveur[
- req(x) -> Req(x) // Réception de la reqûete si rendez-vous
- Req(x) & C -> D_x // Consommation de la requête
]

Le rendez-vous n'est plus bloquant.

Exécution

   Client[A], Serveur[]
-> Client[Req(v), B], Serveur[]
-> Client[B], Serveur[Req(v)] // Communication synchrone de req(v)

Grâce à ces mises en attente, il est donc possible de simuler une communication asynchrone au-dessus d'une communication synchrone.

Serveur :

- get(k) & Val(x) -> k(x) & Val(x)
- set(x, k) & Val(y) -> k(x) & Val(x)

Client i :

- 1 -> 2 & get(rep_i)
- 2 & rep_i(x) -> 3 & set(x + 1, rep_i)
- 3 & rep_i(x) -> 4

Problème (même si la communication est synchrone agent-à-agent pour chacun des quatre échanges (deux couples de requêtes et de réponses)) !

Solution : on utilise des transactions.

Le serveur contrôle l'utilisation du registre par un verrou.

Serveur :

• état : Val(x) ou Val(x, k) après verrouillage par le client utilisant le canal k
• deux canaux get et set (/ registre)
• deux canaux begin et end (/ transaction)

- begin(k) & Val(x) -> k() & Val(x, k) // Verrouillage
- get(k) & Val(x, k) -> k(x) & Val(x, k)
- set(x, k) & Val(y, k) -> k(x) & Val(x, k)
- end(k) & Val(x, k) -> k() & Val(x) // Déverrouillage

Client i :

• cinq états : 0, 1, 2, 3, 4
• un canal rep_i pour les réponses (i = 1, 2)

-  0 -> 1 & begin(rep_i)
-  1 & rep_i() -> 2 & get(rep_i)
-  2 & rep_i(x) -> 3 & set(x + 1, rep_i)
-  3 & rep_i(x) -> 4 & end(rep_i)

Le serveur utilise un registre possédant une version pour sa valeur.

Serveur :

• deux canaux get et set (/ registre)
• état : Val(x, n) (valeur x, version n)

- get(k) & Val(x, n) -> k(x, n) & Val(x, n)
// Ecriture acceptée
- set(x, n, ok, ko) & Val(y, n) -> ok(x, n + 1) & Val(x, n + 1) 
// Ecriture refusée 
- set(x, n, ok, ko) & Val(y, p) & (p != n) -> ko(y, p) & Val(y, p)

Client i :

• trois états : 1, 2, 3
• un canal lu_i pour les réponses en lecture (i = 1, 2)
• un canal ecrit_i pour les réponses (positives) en écriture (i = 1, 2)

- 1 -> 2 & get(lu_i)
- 2 & lu_i(x, n) -> 2 & set(x + 1, n, ecrit_i, lu_i)
- 2 & ecrit_i(x, n) -> 3

Approche pessimiste

• Ressource possiblement indisponible si verrouillée par un client en panne
  • Pas de tolérance aux pannes survenant chez les clients
• Transactions plus longues (à cause de l'ouverture et la fermeture)
• Aucun parallélisme entre transactions
  • Possibilité cependant de paralléliser des transactions ne réalisant qu'une lecture
• Progression garantie de chaque client (puisqu'il suffit de gérer une file d'attentes pour les demandes d'ouverture de transaction)
• Risque d'interblocage (deadlock) dans le cas de plusieurs ressources, cf. infra

Approche optimiste

• Ressource disponible quel que soit l'activité des clients
  • Tolérance aux pannes survenant chez les clients
• Transactions plus courtes mais possibilités de reprises
• Parallélisme possible entre transactions
  • Meilleur des cas : accélération de l'exécution
  • Pire des cas : ralentissement dû à un grand nombre de reprises
• Pas de garantie de progression pour les clients
  • Possible blocage perpétuel d'un client par répétition des reprises (risque de livelock) dans le cas où de nouveaux clients arrivent en permanence (risque accru lorsque le client est lent et les arrivées fréquentes)

En pratique : pour les services Web, on utilise plutôt l'approche optimiste, qui garantit la tolérance aux pannes des clients, à condition d'éviter un excès de reprises et des blocages perpétuels (ce qui est le cas si les écritures sont rares).

C'est possible dans les deux cas.

• Approche optimiste : attribuer une version à l'ensemble des n ressources
  • Risque accru de reprises ou de blocages perpétuels (livelocks)
• Approche pessimiste : utiliser le verrouillage en deux phases ("two-phase locking")
  • Risque d'interblocage (deadlock)

Remarque. Cet algorithme de verrouillage ne doit pas être confondu avec l'algorithme de consensus utilisé pour valider une transaction répartie, appelé "two-phase commit protocol" : cf. wikipedia.

Chaque client doit vérifier pour le verrouillage et le déverrouillage un protocole particulier, en deux phases consécutives :

• phase ascendante : verrouillage possible, déverrouillage impossible,
• phase descendante : verrouillage impossible, déverrouillage possible.

Si ce protocole n'est pas vérifié, il peut exister une exécution qui n'est pas sérialisable, comme le montre un exemple très simple : deux agents, une ressource, chaque agent réalisant deux transactions (verrouillage, actions, déverrouillage) consécutivement.

Proposition : Si tous les clients suivent ce protocole, alors toute exécution est sérialisable.

Démonstration dans le cas de deux clients et de n ressources

On considère deux actions pour chaque ressource : lecture (get) et écriture (set).

Observons une exécution T du point de vue du serveur gérant les n ressources. Cette exécution entrelace des traitements de requêtes get et set provenant des deux clients.

Considérons maintenant toutes les exécutions équivalentes à T. L'équivalence entre les exécutions exprime non seulement que les projections pour chaque client sont identiques mais aussi que les écritures et les lectures des ressources partagées sont cohérentes. Précisément, on construit la relation d'équivalence à partir d'un ordre partiel défini à partir de T et prenant en compte la causalité (ou la précédence) entre évènements :

• pour chaque client, les traitements associés sont ordonnés linéairement suivant l'ordre dans T,
• étant donné une ressource, pour chaque lecture d'un client telle que la dernière écriture a été réalisée par l'autre client dans T, l'écriture par l'autre client précède la lecture.

Cet ordre partiel est appelé le graphe de précédence, noté GP par la suite. Les exécutions équivalentes se déduisent alors par linéarisation de cet ordre partiel.

Par définition, l'exécution T est sérialisable si une linéarisation de GP est telle que tout traitement d'un client est avant tout traitement de l'autre client. Une telle linéarisation est possible si et seulement s'il n'existe pas dans GP un circuit du genre suivant.

Or, un tel circuit est effectivement impossible dans l'hypothèse où les clients vérifient le protocole de verrouillage en deux phases. En effet, entre les moments a et c, le client 1 a dû libérer la ressource écrite en a et lue en c, ce qui implique que plus jamais ensuite, il ne peut acquérir de verrou pour une ressource. Or, entre les moments d et b, le client 1 a dû acquérir la ressource écrite en d par le client 2 et lue en b par le client 1. Ce serait une contradiction avec la définition des deux phases de verrouillage.

A partir des requêtes et des verrouillages des ressources, le serveur peut maintenir un graphe d'usage des ressources. Les nœuds du graphe sont les clients et les ressources. Une flèche relie un client à une ressource lorsqu'il la verrouille ; une flèche relie une ressource à un client lorsqu'il la réclame. On a alors l'équivalence suivante : il y a interblocage si et seulement s'il existe un circuit dans ce graphe.

Une fois qu'un interblocage est détecté, le remède est simple : libération arbitraire d'une ressource verrouillée et verrouillage par un autre client la réclamant.

Pour éviter un interblocage fatal, on peut adapter le protocole de verrouillage en deux phases : chaque client doit initialement demander le verrouillage de toutes les ressources qu'il utilisera. La première phase (de verrouillage) se réalise donc immédiatement, tandis que la seconde phase (de déverrouillage) s'étale jusqu'à la fin de la transaction.

Généralisons à un nombre quelconque de ressources l'exemple précédent verrouillant une ressource initialement. Cette solution garantit non seulement la cohérence mais aussi l'absence d'interblocage.

Serveur

• Etat
  • Libre(R) : ensemble R de ressources non verrouillées
  • Verrou(k, R) : ensemble R de ressources verrouillées par le client utilisant le canal k
  • Val(x, v) : ressource x de valeur v
• Canaux :
  • deux canaux get(x, k) et set(x, u, k) pour chaque ressource x
  • deux canaux begin(k, R) et end(k) pour débuter et terminer la transaction, qui utilise le canal k du client et les ressources de l'ensemble R

// Verrouillage initial
- begin(k, S) & Libre(R) & (S inclus dans R) & (Verrou(k, ...) inactive)
    -> k() & Libre(R - S) & Verrou(k, S) 
// Lecture autorisée
- get(x, k) & Val(x, v) & Verrou(k, S) & (x élément de S) 
    -> k(x, v) & Val(x, v) & Verrou(k, S)
// Lecture refusée
  get(x, k) & Verrou(k, S) & (x non élément de S) 
    -> k(x, KOL) & Verrou(k, S) // KOL : erreur en lecture
// Ecriture autorisée
- set(x, u, k) & Val(x, v) & Verrou(k, S) & (x élément de S) 
    -> k(x, u) & Val(x, u) & Verrou(k, S)
// Ecriture refusée
- set(x, u, k) & Verrou(k, S) & (x non élément de S) 
    -> k(x, KOE) & Verrou(k, S) // KOE : erreur en écriture
// Déverrouillage
  end(k) & Libre(R) & Verrou(k, S) -> k() & Libre(R union S)

On aurait pu permettre un déverrouillage progressif, plutôt qu'un déverrouillage complet à la fin de la transaction.

C'est le cas le plus simple. On considère n clients et un serveur recevant les requêtes des clients.

Exemple : le protocole TCP qui utilise un compteur pour chaque segment de données transmis

Première solution utilisant un horodatage

• Client utilisant un compteur (initialement nul)
• Serveur utilisant un compteur (initialement nul) par client
• Annotation des messages par l'émetteur et le numéro du compteur

• Client i

  // Horodate du message envoyé dans la requête
  - ... & Compteur(j) -> ... & requete(i, j, m) & Compteur(j+1)
  

• Serveur

  // Traitement du message ayant le bon numéro
  - ... & Compteur(i, j) & requete(i, j, m) 
    -> ... & Compteur(i, j+1)
  

Seconde solution utilisant un protocole avec accusé de réception

• Client utilisant une file d'attente (initialement vide) pour les émissions
• Serveur accusant réception des messages

• Client i

  // Mise en file d'attente du message pour émission (en queue de file)
  - ... & File(f) -> ... & File(m :: f)
  // Envoi de la requête pour le message en tête de file et attente d'un accusé de réception
  - File(f :: m) & (Attente() inactif) -> requete(m, ar) & File(f :: m) & Attente()
  // Fin de l'attente et retrait du message en tête de file à réception de l'accusé
  - ar() & Attente() & File (f :: m) -> File(f)
  

• Serveur

  - ... & requete(m, k) -> ... & k()
  

Lorsque deux clients peuvent communiquer entre eux, la préservation de l'ordre causal entre chaque client et le serveur ne suffit plus. Dans l'exemple décrit ci-dessous, le premier client envoie un message au serveur puis un message au second client. Lorsque le second client reçoit ce message, il envoie un message au serveur. Dans l'hypothèse où côté serveur, la réception du message du premier client est postérieure à celle du message du second client, l'ordre causal n'est pas préservé. En effet, l'émission du premier client (1) vers le serveur est avant celle du second client (4), alors que les réceptions par le serveur sont en ordre inverse ((6) après (5)).

De plus, le serveur ne dispose d'aucun moyen pour deviner la violation de la préservation, à partir des solutions ci-dessus. Celles-ci doivent être étendues.

Pour la solution par horodatage scalaire (par une simple valeur), il est nécessaire de représenter l'idéal principal d'ordre de manière plus complète dans l'horodatage (par un vecteur dans le cas de la diffusion, par une matrice dans le cas général, qui contiennent les émissions connues).

Pour la solution utilisant des files, il est nécessaire d'utiliser la file d'émission pour tous les messages émis, quelque soit le destinataire, et d'accuser réception de tout message reçu.

Bibliographie

• About logical clocks for distributed systems, de M. Raynal (1991), pour les solutions par horodatage
• A Non-Blocking Lightweight Implementation of Causal Order Message Delivery, de F. Mattern and S. Fünfrocken (1995), pour la solution utilisant des files

La tolérance aux pannes ("fault tolerance") est la capacité à fonctionner en présence de pannes. Ces pannes ont pour origine le réseau de communication ou les agents communiquant.

• Faute : erreur statique déclenchant une erreur dynamique lorsqu'elle est activée
• Résultat possible : panne pouvant aboutir à la non-vérification de la spécification
• Tolérance : vérification de la spécification malgré la panne

// Erreur si f est appelée
int f(){
  x:=1; 
  y:=0; 
  return x + (x/y); // Faute
}
// Tolérance
try {
  f();
} catch(Exception e) {
  // Comportement en cas d'erreur (division par zéro)
  ...
}

La tolérance aux pannes est relative à une classe de fautes. Voici quelques classes remarquables.

• Fautes byzantines (fautes arbitraires)
• Perte de messages
• Arrêt complet d'un agent

Les mécanismes pour la tolérance se caractérisent par la classe des propriétés qu'ils permettent de garantir. De manière générale, on considère des propriétés de deux sortes : les propriétés de sûreté et les propriétés de vivacité. Ces propriétés sont importantes car elles permettent de décrire toute propriété, grâce à une décomposition canonique.

Décomposition (unique) de toute spécification (propriété) en une intersection (cf. Defining Liveness) :

• d'une propriété de sûreté (l'interdit est impossible, typiquement un invariant est toujours respecté) et
• d'une propriété de vivacité (l'attendu est toujours possible, typiquement la disponibilité est garantie).

Exemple pour un serveur

• Sûreté : le serveur n'est jamais dans un état d'erreur.
• Vivacité : le serveur peut toujours répondre aux requêtes.

Les mécanismes pour la tolérance aux pannes sont fondés sur la redondance :

• réplication,
• ajouts superflus (logs, contrôles, etc.).

Ils permettent la détection des erreurs, idéalement dès qu'elles surviennent pour un meilleur diagnostic et traitement (mode dit "fail-fast"), et la correction des erreurs, par un retour en arrière dans un état correct ou par une compensation de l'erreur.

Exemple : une transaction

• Maintien d'un log des modifications réalisées (modifications supposées réversibles)
• Détection des erreurs
• Réaction en cas d'erreur : réalisation des modifications inverses à partir du log

Un compromis peut être nécessaire. En présence de certaines fautes, il est parfois impossible de garantir la sûreté et la vivacité simultanément : une des deux composantes doit être sacrifiée. Voici quelques exemples classiques. Bien noter que l'impossibilité vient de l'hypothèse retenue pour la communication : celle-ci est supposée asynchrone, ce qui empêche de détecter une panne, un agent très lent dans ses communications ne pouvant être distingué d'un agent en panne.

Les problèmes de consensus interviennent lorsque plusieurs agents répartis doivent prendre une décision commune.

Exemple : validation d'une transaction répartie

• Les agents doivent s'accorder sur la validation de la transaction.

Une solution classique est le protocole en deux phases ("two-phase commit protocol"), l'une de proposition d'une valeur consensuelle et l'autre de validation, deux phases organisées par un coordinateur. Elle convient parfaitement, sauf en présence de pannes.

En effet, dans le cas d'une communication asynchrone, lorsque les agents peuvent tomber en panne, il est impossible de définir un algorithme de consensus : c'est un résultat fameux, démontré par Fischer, Lynch et Paterson dans l'article Impossibility of distributed consensus with one faulty process, paru en 1985.

C'est ce que nous montrons maintenant dans le cadre du modèle chimique. Cette démonstration, plutôt technique, est intéressante parce qu'elle révèle des méthodes et des modes de raisonnements typiques de l'algorithmique répartie :

• l'importance de la modélisation et de la formalisation,
• des aspects combinatoires, avec un lemme de commutativité,
• le principe de récurrence appliqué à des exécutions, vues comme des suites d'états.

Hypothèses

• \(n\) agents formant l'ensemble \(A\) (\(n \geq 2\))
• Possibilité d'une panne ou plus
  • Modélisation des pannes par un prédicat noté \(Panne\) et indexé par une partie de l'ensemble des agents
  • Simulation de la possibilité d'une panne par des réductions valables pour un ensemble \(R\) de couples \((p, q)\), où \(p\) et \(q\) sont des parties de \(A\) vérifiant \(p = q + \{i\}\) (union disjointe), \(R\) contenant au moins les couples \((A, A - \{i\})\) pour tout agent \(i\) (tout agent pouvant ainsi tomber en panne si aucun ne l'est)

  • Règles de panne

    - Panne_p -> Panne_q // Elimination de la possibilité de panne pour i 
    - Panne_p, Agent_i[E] -> Panne_q // Déclenchement de la panne de l'agent i
    

  • Dans tout état initial, tout agent peut tomber en panne.

    - Panne_A // Etat initial du réseau d'agents
    

• Communication asynchrone via des canaux
  • Message : k(v)
    • k : canal comme port d'entrée dans un unique agent
    • v : contenu du message

  • Règles pour la communication asynchrone

    - A_i[S & k(v)] -> A_i[S] & k(v) // Emission par l'agent i d'un message sur 
                                     //   le canal k port d'entrée dans un agent 
                                     //   autre que i
    - A_i[S] & k(v) -> A_i[S & k(v)] // Réception par l'agent i d'un message sur
                                     //   le canal k port d'entrée dans l'agent i
    

Définitions générales

• Un état (d'exécution) décrit
  • l'état des pannes (\(Panne_p\)),
  • l'état du réseau (messages en transit),
  • l'état de chaque agent (état interne, messages reçus et à émettre).
• Un algorithme est défini par un ensemble d'états initiaux, et par un ensemble de règles de réduction. Ces règles incluent les règles de communication et de panne. Toute autre règle est associée à un seul agent et est dite règle d'action : elle consomme des messages reçus par l'agent, modifie l'état de l'agent et produit des messages à émettre par l'agent. Elle peut réaliser une introspection de l'état de l'agent, et seulement de l'état : c'est l'hypothèse de localité des calculs. En particulier, il est impossible de
  • détecter une panne,
  • d'observer l'état d'un autre agent,
  • d'observer les messages en transit sur le réseau.
• Un état (d'exécution) est final si aucune réduction n'est possible à partir de cet état.
• Une exécution est une suite d'états obtenus par des réductions successives à partir d'un premier état. Elle est complète si elle est soit infinie, soit finie et se terminant par un état final.
• Un agent est présent dans un état s'il n'y est pas en panne, absent s'il y est.
• Un agent est précaire dans un état s'il peut tomber en panne dans cet état.
• Un état est vide si tout agent en est absent.
• Un état est dit total si tous les agents y sont présents et précaires ; autrement dit, si le prédicat \(Panne\) est indexé par \(A\).
• Un état est dit partiel s'il n'est pas total.
• Un état est accessible s'il appartient à une exécution partant d'un état initial.
• Un état est inactif si toute réduction à partir de cet état correspond à l'application d'une règle de panne.

Ce premier lemme permet de commuter des réductions et ainsi de restreindre les combinaisons à traiter. On ne décrit que les commutations utiles à la démonstration.

Lemme [Commutativité] :

1. Considérons à partir d'un état une réduction correspondant à une panne suivie d'une réduction correspondant à une action ou à une communication. Alors ces réductions commutent.
2. Considérons un état pour lequel sont possibles deux réductions correspondant à une action ou une communication pour deux agents distincts. Alors ces réductions se composent et commutent.

Démonstration. La commutativité découle des définitions des règles de panne et de communication et de l'hypothèse de localité pour les règles d'action. CQFD

La première proposition du lemme s'étend par récurrence à une réduction suivant \(m\) réductions liées à des pannes. Voici une première utilisation de la commutativité.

Lemme [Stabilité de l'inactivité] : Considérons un état inactif. Alors tout état accessible à partir de cet état est aussi inactif.

Démonstration. Supposons un état accessible qui n'est pas inactif. Considérons le premier tel état rencontré pendant l'exécution y menant. Alors par commutativité, on déduit qu'une réduction correspondant à une règle de communication ou d'action est possible dans l'état inactif de départ, contradiction. CQFD

Formalisons maintenant la notion d'algorithmes de consensus.

Décisions pour le consensus : tout agent \(i\) peut produire un atome \(B(i, v)\), appelé registre.

• Persistance : une fois produit, le registre est persistant et ne peut être dupliqué (avec la même valeur \(v\) ou une autre).
• Décision : La valeur \(v\) du registre appartient à un domaine d'au moins deux valeurs.

Définitions spécifiques au consensus

• Un agent \(i\) produit la valeur \(v\) dans un état si son registre est initialisé à \(B(i, v)\) dans cet état.
• Un état produit une valeur \(v\) (dite valeur de consensus) s'il n'est pas vide et si tout agent présent y produit la valeur \(v\).
• Un état engendre une valeur \(v\) (dite valeur de consensus) s'il existe une exécution partant de cet état et aboutissant à un état final produisant la valeur \(v\).
• Un état est dit plurivalent s'il engendre au moins deux valeurs distinctes.
• Un état est dit monovalent s'il engendre une unique valeur.

Algorithme de consensus : algorithme vérifiant les propriétés suivantes

• Terminaison : l'algorithme termine toujours.
• Consensus final : un état final soit est vide, soit produit une valeur \(v\).
• Non trivialité : il existe un état initial plurivalent.

Ces propriétés visent à affirmer que l'algorithme se termine toujours par un consensus, ou une inactivité complète, où tous les agents sont en panne. La non trivialité vise à écarter la solution évidente d'une fonction constante, qui donnerait toujours le même résultat. Ainsi, suivant notre définition, un algorithme de consensus n'est pas déterministe, même si les règles d'action le sont, à cause du non-déterminisme des règles de panne (qu'on inclut donc dans l'algorithme) et du non-déterminisme entre les règles d'action et celles de communication.

Exemple d'un algorithme de consensus qui serait utile pour la validation de transactions réparties : algorithme terminant toujours et calculant une fonction booléenne, la conjonction des décisions de validation des agents, avec le résultat faux en cas de panne d'un agent.

• Il termine toujours.
• Un état final soit est vide, soit produit Vrai, soit produit Faux.
• L'état initial dans lequel toutes les décisions en entrée sont à Vrai engendre Vrai en l'absence de pannes, Faux sinon.

On démontre par l'absurde l'impossibilité d'un algorithme de consensus. Commençons par quelques lemmes utiles.

Lemme [Génération] : Tout état accessible qui n'est pas vide engendre une valeur. De plus, pour tout agent présent initialement, il existe une exécution dans laquelle cet agent produit finalement la valeur de consensus.

Démonstration. Soit \(i\) un des agents présents dans l'état. Considérons à partir de cet état une exécution complète du programme obtenu à partir des règles d'action et de communication, ainsi que des règles de panne, excepté la règle déclenchant la panne de l'agent \(i\). Par la propriété de terminaison, l'exécution se termine. Son état final est aussi un état final pour l'algorithme de consensus : en effet, si la règle déclenchant la panne de l'agent \(i\) était applicable, alors la règle correspondante d'élimination de la possibilité de panne le serait aussi. Dans l'état final, l'agent \(i\) est présent. Par consensus final, l'état final produit une valeur, donc l'agent \(i\) la produit. CQFD

Du lemme de génération appliqué à un état total, donc non vide, on déduit qu'il existe pour une réduction à partir d'un état accessible total trois cas possibles qui s'excluent mutuellement : l'état atteint après cette réduction est

• soit un état partiel, après l'application d'une règle de panne,
• soit un état total, après l'application d'une règle de communication ou d'action, état
  • soit monovalent,
  • soit plurivalent.

Lemme [Production Monovalente] : Dans un état accessible, il existe au plus une valeur produite.

Démonstration. Supposons que dans un état accessible, deux agents \(i\) et \(j\) produisent respectivement les valeurs \(u\) et \(v\). Considérons à partir de cet état une exécution complète du programme obtenu à partir des règles d'action et de communication, ainsi que des règles de panne, excepté les règles déclenchant les pannes des agents \(i\) et \(j\). Par la propriété de terminaison, l'exécution se termine. Son état final est aussi un état final pour l'algorithme de consensus : en effet, si la règle déclenchant la panne de l'agent \(i\) ou \(j\) était applicable, alors la règle correspondante d'élimination de la possibilité de panne le serait aussi. Dans l'état final, les agents \(i\) et \(j\) sont présents. Par consensus final, l'état final produit donc une valeur. Par persistance, cette valeur est égale à \(u\) et \(v\), qui sont donc égaux. CQFD

Lemme [Inactivité consensuelle] : Un état accessible inactif qui n'est pas vide est monovalent. De plus, cet état produit la valeur de consensus.

Démonstration. Par le lemme de génération, cet état engendre une valeur. Supposons qu'il engendre deux valeurs, \(u\) et \(v\). Par le lemme de stabilité de l'inactivité, tous les états subséquents sont inactifs. On en déduit que des agents de cet état produisent les valeurs \(u\) et \(v\). Par le lemme de production monovalente, on déduit \(u = v\). L'état est bien monovalent. CQFD

Lemme [Production générative] : Si un état accessible produit une valeur \(v\), alors il engendre \(v\).

Démonstration. Considérons un agent présent initialement. Il produit dans l'état de départ la valeur \(v\). Par le lemme de génération, il existe une exécution dans laquelle cet agent produit finalement la valeur de consensus, qui par persistance est nécessairement \(v\). Par conséquent, l'état engendre \(v\). CQFD

La plurivalence exprime l'absence de consensus ; à l'inverse la monovalence exprime le consensus. Le prochain lemme, fondamental, montre que si un état mène à des états consensuels, alors cet état est lui-même consensuel, c'est-à-dire monovalent. C'est qu'en effet on peut montrer que différentes voies consensuelles mènent toutes à la même valeur de consensus. L'argumentation repose soit sur la commutativité des voies consensuelles, soit en son absence, sur la possibilité de comparer ces voies à celle d'une panne rendant impossible l'engagement sur ces voies consensuelles. Le lemme suivant montre effectivement que la transition de la plurivalence à la monovalence est impossible.

Lemme [Stabilité inverse de la monovalence] : Considérons un état accessible total. Supposons que toute réduction à partir de cet état aboutisse :

• soit à un état partiel, après l'application d'une règle de panne,
• soit à un état total monovalent, après l'application d'une règle de communication ou d'action.

Alors l'état est monovalent.

Démonstration.

Primo, montrons que l'état engendre une valeur.

• Si l'on n'aboutit par réduction qu'à des états partiels, alors l'état est inactif par définition. Comme l'état n'est pas vide, étant total, par le lemme de l'inactivité consensuelle, l'état est monovalent.
• Sinon, on aboutit par réduction à au moins un état monovalent, ce qui garantit que l'état engendre une valeur.

Secundo, montrons que si l'état engendre \(u\) et \(v\), alors \(u = v\), ce qui permettra de conclure à la monovalence. Considérons donc deux exécutions complètes se terminant par la production de \(u\) et \(v\) respectivement. Considérons quatre cas, suivant que les exécutions soient exclusivement formées de réductions de panne ou non.

• Premier cas. Supposons que les deux exécutions soient exclusivement formées de pannes. Dans l'état initial, au moins un agent produit la valeur \(u\), et au moins un agent produit la valeur \(v\). Par le lemme de production monovalente, \(u = v\).
• Second et troisième cas (symétriques). Supposons qu'une seule des deux exécutions soit exclusivement formée de pannes, par exemple celle produisant \(u\). Dans l'état initial, au moins un agent produit la valeur \(u\). La seconde exécution produisant \(v\) commence par une série, éventuellement vide, de réductions de panne, suivie d'une réduction de communication ou d'action. Par commutativité, il est possible de commencer par la réduction de communication ou d'action, suivie des réductions de panne, pour parvenir au même état. La première réduction, par hypothèse, conduit à un état monovalent, engendrant \(v\). Comme dans cet état, l'agent produit aussi par persistance la valeur \(u\), par le lemme de production générative et par monovalence, \(u = v\).
• Quatrième cas. Chaque exécution commence par une série, éventuellement vide, de réductions de panne, suivie d'une réduction de communication ou d'action. Par commutativité, on peut supposer que chaque exécution commence par la réduction de communication ou d'action. Par hypothèse, ces réductions conduisent à des états monovalents, engendrant \(u\) et \(v\) respectivement.
  • Supposons que ces deux réductions impliquent deux agents distincts, \(i\) et \(j\) respectivement. Il est possible de les composer, pour arriver par commutativité dans le même état. Comme cet état n'est pas vide, par le lemme de génération, il engendre une valeur \(w\). Par monovalence, \(u = w\) et \(v = w\), donc \(u = v\).
  • Sinon, ces deux réductions impliquent un même agent \(i\). Considérons alors à partir de l'état initial la réduction déclenchant la panne de \(i\). L'état atteint est soit inactif, soit permet une réduction d'action ou de communication d'un agent \(j\) distinct de \(i\).
    • Supposons que l'état atteint soit inactif. Par le lemme d'inactivité consensuelle, il produit une valeur \(w\). Cette valeur est déjà produite dans l'état initial, mais aussi dans les deux états obtenus après les deux réductions de l'agent \(i\). Par le lemme de la production générative et par monovalence, on déduit \(u = w\) et \(v = w\), donc \(u = v\).
    • Sinon, supposons que l'état atteint permette une réduction d'action ou de communication d'un agent \(j\) distinct de \(i\). Par commutativité, cette réduction de l'agent \(j\) est déjà possible dans l'état initial. Par hypothèse, elle aboutit à un état monovalent, engendrant \(w\). Il est possible de la composer avec chacune des deux réductions de l'agent \(i\), respectivement. Dans les deux cas, on parvient à un état non vide, qui par le lemme de génération engendre une valeur. Par commutativité et monovalence, cette valeur est égale d'une part à \(w\), et d'autre part à \(u\) ou \(v\) suivant le cas. On déduit par transitivité \(w = u\) et \(w = v\), puis \(u = v\).
• Conclusion : l'état de départ est monovalent. CQFD

Pour démontrer l'impossibilité d'un algorithme de consensus, on va construire une exécution infinie formée d'états totaux et plurivalents, ce qui contredira la propriété de terminaison. Le lemme précédent est décisif.

Démonstration par l'absurde de l'impossibilité d'un algorithme de consensus.

Supposons l'existence d'un algorithme de consensus. On construit par récurrence une exécution infinie formée d'états totaux et plurivalents.

Rang 0 : parmi les états initiaux, totaux par hypothèse, on choisit un état plurivalent, puisqu'il en existe par la propriété de non-trivialité du consensus. Soit \(E_0\) cet état.

Hypothèse de récurrence : supposons au rang \(n\) une exécution \((E_k)_{0 \leq k \leq n}\) formée d'états totaux et plurivalents.

On construit l'état suivant, \(E_{n+1}\).

• Supposons que tout état accessible en une réduction à partir de \(E_n\) soit partiel ou total et monovalent. Par le lemme de stabilité inverse de la monovalence, on déduit que \(E_n\) est monovalent, contradiction.
• Il existe donc un état accessible en une réduction à partir de \(E_n\) qui est total et plurivalent. Soit \(E_{n+1}\) cet état.

Conclusion. Il existe une exécution infinie, ce qui est impossible par l'hypothèse de terminaison. Il n'existe pas d'algorithmes de consensus. CQFD.

Intéressons-nous au cas de données répliquées, appelées réplicas. Avec une communication asynchrone non fiable (pouvant aboutir à une partition du réseau où tous les messages entre des parties disjointes du réseau sont perdus), il est impossible de préserver la cohérence de réplicas (sûreté) et la disponibilité des réplicas (théorème dit CAP ("Consistency, Availability, Partition")). Soit les réplicas évoluent d'une manière incohérente, soit ils sont indisponibles lorsqu'une partition du réseau apparaît. Bref, soit la sûreté est sacrifiée, soit la vivacité l'est.

Bibliographie :

• Perspectives on the CAP Theorem, par Seth Gilbert et Nancy Ann Lynch
• A Critique of the CAP Theorem, par Kleppmann

A l'aide de détecteurs de pannes, il est possible de résoudre des problèmes insolubles avec une communication asynchrone, comme celui du consensus.

Dans la pratique, on utilise deux techniques pour détecter des pannes.

• Approche active
  • Envoi périodique d'un message (ping) vers l'agent suspect
  • Attente d'un accusé de réception avec un délai maximal (timeout)
• Approche passive (plus fréquente)
  • Diffusion périodique d'un message de l'agent (possible suspect, heartbeat)
  • Attente de la diffusion avec un délai maximal

La durée du délai maximal est sensible : trop longue ou trop courte, elle peut ralentir ou compromettre l'exécution d'une application répartie.

La propriété d'intégrité est la suivante : un message reçu doit avoir le même contenu que lors de son émission. Si ce n'est pas le cas, le destinataire doit le refuser.

Pour garantir l'intégrité, on ajoute au contenu C du message une valeur, h(C), résultat de l'application d'une fonction h au contenu C. L'attaquant doit être incapable de trouver un couple (x, h(x)), avec x différent de C, tout en connaissant le couple (C, h(C)) : c'est la propriété que doit vérifier la fonction h. A la réception du message (C, H), le destinataire vérifie que H = h(C).

Il existe de telles fonctions, dites de hachage. Elles sont paramétrées par une clé qui doit être connue de l'émetteur et du destinataire et inconnue de l'attaquant : on parle de hachage chiffré. Appliquées à un message, elles produisent ce qu'on appelle un code d'authentification du message (MAC, pour "Message Authentication Code").

Exemple : cf. wikipedia.

Une fonction de hachage chiffrée prend une clé et un contenu et produit une valeur de hachage. Elle est dite à sens unique ("one way") : connaissant un contenu et la valeur produite, il est pratiquement impossible de retrouver la clé.

La propriété d'authentification est la suivante : le destinataire d'un message doit être capable de déterminer si un message reçu est bien de l'émetteur annoncé.

La méthode précédente peut s'appliquer. Cependant, si l'attaquant rejoue l'envoi d'un message, il peut tromper le destinataire. Pour parer cette éventualité, on doit rendre spécifique chaque message, par exemple en les numérotant, ou en ajoutant un nombre tiré aléatoirement. Ainsi, le destinataire pourra déterminer si le message a déjà été reçu précédemment.

La propriété de confidentialité est la suivante : un attaquant ne peut déterminer le contenu d'un message.

Au lieu de transmettre le contenu C, on transmet le contenu f(C), où f est la fonction de chiffrement. A réception, le destinataire utilise la fonction de déchiffrement, qui est l'inverse de f pour retrouver C. L'attaquant doit être incapable de retrouver C connaissant f(C).

Il existe deux grandes familles de fonctions de chiffrement, paramétrées par des clés.

• La première famille est paramétrée par une clé, dite privée, parce que connue de l'émetteur et du destinataire et inconnue de l'attaquant. La fonction de chiffrement et celle de déchiffrement sont paramétrées par la clé privée : on parle de chiffrement symétrique.

  Exemple : DES (1977), AES (1997)

• La second famille est paramétrée par un couple de clés, l'une publique, connue de tout le monde, l'autre privée, connue du destinataire seulement. La fonction de chiffrement est paramétrée par la clé publique alors que la fonction de déchiffrement est paramétrée par la clé privée : le chiffrement est dit asymétrique. L'émetteur peut donc utiliser la fonction de chiffrement, publique, seul le destinataire ayant accès à la fonction de déchiffrement. L'attaquant doit être incapable de déterminer la clé privée connaissant la clé publique. Évidemment, il est plus difficile de concevoir de telles fonctions de chiffrement, du fait de la connaissance de la clé publique.

  Exemple : RSA (1977)

Le chiffrement asymétrique résout un problème important du chiffrement symétrique comme du hachage chiffré : le partage d'une clé privée. Comme il est coûteux, nécessitant de plus grandes clés, on l'utilise souvent pour échanger initialement une ou plusieurs clés privées, qui deviennent partagées et permettent ensuite d'utiliser du chiffrement symétrique ou du hachage chiffré.

Le chiffrement asymétrique permet aussi d'authentifier un message. En effet, la fonction de chiffrement peut aussi être paramétrée par la clé privée, la fonction de déchiffrement étant alors paramétrée par la clé publique. C'est l'émetteur qui possède un couple de clés, l'une publique, l'autre privée. Il suffit alors à l'émetteur de chiffrer une valeur de hachage calculée à partir du message en utilisant sa clé privée. Le destinataire déchiffre la valeur de hachage en utilisant la clé publique de l'émetteur et vérifie qu'elle est bien associée au message reçu.

Bibliographie

• New directions in cryptography, de Diffie et Hellman (1976) - "We stand today on the brink of a revolution in cryptography." : introduction des principes de la cryptographie asymétrique

Il s'agit d'une attaque par interception de tous les messages échangés entre deux agents. L'attaquant se fait passer pour le destinataire attendu ou l'émetteur attendu. Elle permet d'attaquer un protocole d'échange de clés privées utilisant du chiffrement asymétrique.

• Agents : A et B
• Clés de B : K publique, L privée
• Fonctions de chiffrement et déchiffrement asymétrique : C et D
• Clé secrète (privée) : S (connue initialement de A seulement)
• Objectif : partager la clé secrète S

A -> B : requête demandant à *B* sa clé publique
B -> A : K
A -> B : C_K(S)
B : D_L(C_K(S)) => S

Après cet échange, A et B partagent une clé secrète, S, qui peut servir à leurs échanges ultérieurs utilisant du chiffrement symétrique.

Attaque

• Intercepteur : I
• Clés de I : KI publique, LI privée, SI secrète (privée)
• Objectif (pour I) : se faire passer pour B auprès de A, pour A auprès de B

A -> I : requête demandant à *B* sa clé publique et interceptée par I
I -> A : KI 
A -> I : C_KI(S)
I : D_LI(C_KI(S)) => S
I -> B : requête demandant  à *B* sa clé publique
B -> I : K
I -> B : C_K(SI)
B : D_L(C_K(SI)) => SI

Après ce double échange, A et I partagent la clé secrète de A, soit S, alors que I et B partagent la clé secrète de I, soit SI. Ces clés sont ensuite utilisées lors des échanges, l'intercepteur faisant les transitions d'une clé à l'autre.

Cette attaque par interception est dure à contrer. Voici deux défenses classiques.

• Première défense : obtenir la clé publique par un canal sûr, auprès d'un tiers sûr, rendant l'interception impossible (cf. les infrastructures à clés publiques).
• Seconde défense : surveiller les temps de communication, qui sont augmentés par les traitements réalisés par l'intercepteur, de manière à détecter l'attaque.