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.

• Exemple : le téléphone

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

  Emetteur[
    Feu() -> appel18("Au feu", "4 rue Alfred") & Evacuation()
  ]
  Pompier[   
    appel18(message, adresse) -> Alerte(message, adresse)
  ]
  
     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.
  

• Une communication synchrone est plus contraignante qu'une communication asynchrone puisqu'elle induit des synchronisations avec les rendez-vous. Ainsi, une communication synchrone peut entrainer un blocage alors qu'une communication asynchrone n'en entrainerait 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. Il serait nécessaire d'instrumenter l'exécution (la sémantique) pour exprimer des contraintes temporelles permettant de rendre compte de la possibilité d'une majoration des temps.

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 (sauf si la communication est synchrone agent-à-agent)

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 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 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.

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

Exemple : validation d'une transaction répartie

• L'ensemble des agents doivent être d'accord sur la validation de la transaction.

Dans le cas d'une communication asynchrone, lorsque les agents peuvent tomber en panne, il est impossible de définir un algorithme de consensus : cf. Impossibility of distributed consensus with one faulty process de Fischer, Lynch et Paterson (1985).

C'est ce que nous montrons maintenant. 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\))
• Pour tout agent \(i\), possible production d'un atome \(B(i, v)\), appelé registre
  • Une fois produit, le registre est persistant et ne peut être dupliqué (avec la même valeur \(v\) ou une autre).
  • \(v\) appartient à un domaine d'au moins deux valeurs.
• 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

  • Réductions valables pour un ensemble \(R\) de couples \((p, q)\) vérifiant \(p = q + \{i\}\) (union disjointe), \(R\) contenant les couples \((A, A - \{i\})\) pour tout agent \(i\) (tout agent pouvant ainsi tomber en panne si aucun ne l'est)

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

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

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

• Règles pour la communication asynchrone

  - A_i[S & msg] -> A_i[S] & msg // Emission par l'agent i d'un message
  - A_i[S] & msg -> A_i[S & msg] // Réception par l'agent i d'un message
  

• 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 d'introspection (et de non-extraspection). 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.

Définitions

• Une exécution est une suite d'états obtenus par des réductions successives.
• Un état 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 agent \(i\) produit la valeur \(v\) dans un état si son registre est initialisé à \(B(i, v)\) dans cet état.
• 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 (d'exécution) est final si aucune réduction n'est possible à partir de cet état.
• Un état est vide si tout agent en est absent.
• 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 commençant avec cet état et se terminant dans un état 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.
• 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 est accessible à partir 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.

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

• Terminaison : l'algorithme termine toujours (sans être nécessairement déterministe).
• Consensus final : un état final soit est vide, soit produit une valeur \(v\).
• Consensus non trivial : il existe un état initial plurivalent.

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 résultats de validation des agents, avec le résultat faux en cas de panne d'un agent.

• Il termine toujours (et est déterministe).
• Un état final soit est vide, soit produit Vrai, soit produit Faux.
• L'état initial dans lequel tous les résultats en entrée sont à Vrai engendre Vrai en l'absence de pannes, Faux sinon.

Démonstration par l'absurde de l'impossibilité d'un algorithme de consensus : supposons l'existence d'un algorithme de consensus. On montre qu'on obtient une contradiction.

Commençons par quelques lemmes utiles.

Ce premier lemme permet de réduire les combinaisons à explorer.

Lemme [Commutativité] : A partir d'un état, considérons une réduction 1 suivie d'une réduction 2. Alors à partir du même état de départ, la réduction 2 suivie de la réduction 1 aboutit au même état d'arrivée dans les cas suivants.

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

Ce lemme s'étend par récurrence à une réduction commutant avec \(m\) réductions. Du lemme de commutativité, on déduit que l'inactivité se préserve.

Lemme [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

L'algorithme de consensus calcule une valeur de consensus si les agents ne sont pas tous en panne.

Lemme [Génération] : Tout état accessible qui n'est pas vide engendre une valeur.

Démonstration. A partir de l'état accessible non vide, éliminons progressivement les possibilités de panne. A partir de l'état ainsi atteint, les états accessibles ne sont pas vides (puisque des agents y sont présents) : comme l'algorithme termine, il existe un état final parmi ces états accessibles. Par la propriété du consensus final, n'étant pas vide, celui-ci produit une valeur. CQFD

De ce lemme 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.

Lorsque l'algorithme parvient à un état inactif non vide, c'est qu'il a atteint le consensus.

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. Supposons que l'état accessible inactif ne soit pas vide. A partir de cet état, éliminons progressivement les possibilités de panne. L'état ainsi atteint est final, puisqu'inactif et sans aucune règle de panne applicable. Comme il n'est pas vide, par la propriété du consensus final, il produit une valeur, la valeur de consensus. Comme aucune règle d'action n'a été appliquée et que tous les agents présents dans l'état de départ le sont aussi dans l'état final, on déduit que l'état de départ produit la valeur de consensus et est donc monovalent. CQFD

Lorsque l'algorithme devient déterministe (parvient à un état monovalent), il ne peut s'engager que sur la valeur de consensus.

Lemme [Consensus] : Si dans un état accessible monovalent de valeur de consensus \(v\), un agent produit une valeur \(u\), alors cette valeur \(u\) est égale à la valeur de consensus \(v\).

Démonstration. Soit \(i\) l'agent produisant la valeur \(u\). Considérons à partir de l'état accessible monovalent le programme obtenu à partir des règles d'action et de communication, ainsi que des règles de panne, excepté la règle de panne de l'agent \(i\). Par la propriété de terminaison, ce programme termine toujours. Un état final pour ce programme est aussi un état final pour l'algorithme de consensus : en effet, si une règle de panne est applicable, alors la règle correspondante d'élimination de la possibilité de panne l'est aussi. Dans un tel état final, l'agent \(i\) est présent, et produit la valeur de consensus \(v\), qui est donc égale à \(u\). 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. La plurivalence exprime l'absence de consensus ; la totalité, en permettant à tout agent de tomber en panne à tout moment, fournit l'argument décisif pour empêcher le consensus.

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

On construit par récurrence une exécution formée d'états totaux et plurivalents.

Rang 0 : parmi les états initiaux, totaux par hypothèse sur les pannes, 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. On montre qu'on obtient une contradiction.
  • Si tous les états accessibles sont partiels, alors l'état \(E_n\) est inactif. Par le lemme de l'inactivité consensuelle, il est monovalent, contradiction.
  • Il existe donc une réduction impliquant un agent \(i\) et menant à un état total et monovalent, engendrant \(u\).
    • S'il existe une réduction impliquant un autre agent \(j\) et menant à un état total et monovalent, engendrant \(v\), alors par commutativité des réductions, on obtient \(u = v\).
    • Supposons qu'il existe une autre réduction impliquant l'agent \(i\) et menant à un état total et monovalent, engendrant \(v\).
      • S'il existe une réduction impliquant un autre agent \(j\) et menant à un état total et monovalent, alors on déduit \(u = v\) de la proposition précédente.
      • Sinon, considérons une panne de l'agent \(i\) à partir de \(E_n\). Comme l'état atteint est inactif et non vide, par le lemme de l'inactivité consensuelle, il est monovalent, et tout agent \(j\) présent dans cet état produit la valeur de consensus, \(w\). En \(E_n\), ces agents produisent déjà la valeur \(w\). Par le lemme du consensus, on déduit que \(u = w\) et \(v = w\), donc \(u = v\).
  • On a ainsi montré que toute réduction menant à un état total et monovalent engendre la même valeur \(u\). On montre finalement que l'état \(E_n\) est monovalent, engendrant \(u\), ce qui constitue une contradiction. Considérons une réduction à partir de \(E_n\) menant à un état partiel et correspondant donc à l'application d'une règle de panne. Considérons une exécution à partir de cet état engendrant \(v\). Deux cas sont possibles.
    • Soit cette exécution contient une application d'une règle d'action ou de communication. Considérons alors la première rencontrée. Par le lemme de commutativité, on peut commencer par appliquer la règle de communication ou d'action puis appliquer les règles de panne. Il s'ensuit \(u = v\).
    • Soit cette exécution ne contient pas d'applications de règle d'action ou de communication. L'état \(E_n\) produit alors la valeur \(v\), comme l'état final. Comme \(E_n\) se réduit en un état monovalent engendrant \(u\), on déduit par le lemme du consensus que \(u = v\).
  • Conclusion : \(E_n\) est monovalent, engendrant \(u\), ce qui est une contradiction.
• Donc il existe un état \(E'\) accessible en une réduction à partir de \(E_n\), et qui est total et plurivalent. Il suffit de définir \(E_{n+1}\) par \(E'\).

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.

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.

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 : AES

• 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'attaquant doit être incapable de déterminer la clé privée connaissant la clé publique.

  Exemple : RSA

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é.

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.