UP | HOME

Un modèle conceptuel pour les services

Table of Contents

1 La programmation répartie

1.1 Terminologie adoptée dans ce cours

Qualificatif pour des actions, des calculs, des programmes

  • Séquentiel : ordonné linéairement
  • Concurrent : pouvant arriver en même temps (anglicisme)
  • Parallèle : arrivant en même temps
  • Réparti (ou distribué, "distributed") : arrivant en plusieurs endroits

1.2 Du séquentiel au réparti

Les calculs informatiques sont concurrents et répartis depuis longtemps, à différentes échelles, celles :

  • du processeur,
  • du système d’exploitation, ou
  • du réseau.

Cependant, la programmation est séquentielle depuis toujours. Le parallélisme (et donc possiblement la répartition) est seulement ajouté, implicitement ou explicitement, au séquentiel, par des mécanismes dédiés, comme

Les deux premiers reposent sur une mémoire partagée, le dernier sur l'échange de messages.

1.3 Les deux modèles pour la répartition

  • Mémoire partagée
    • Multiples agents, chaque agent exécutant une ou plusieurs activités en parallèle
    • Communication et synchronisation par l’intermédiaire d’une mémoire partagée
    • Mémoire partagée contenant des valeurs en lecture et en écriture et protégée par des moniteurs

Exemples : mémoire cache d’un processeur multi-cœur, programmes multi-tâches

sharedMemory_cernSchoolComputing.png

Figure 1: Mémoire partagée (par des processeurs) (source : Cern - School of Computing)

  • Échange de messages
    • Multiples agents, chaque agent exécutant une ou plusieurs activités en parallèle
    • Communication en utilisant des canaux de communication
    • Synchronisation par envoi de messages

Exemples : services, les applications réseaux

messagePassing_cernSchoolComputing.png

Figure 2: Echange de messages dans une architecture à services (source : Cern - School of Computing)

1.3.1 Les modèles en pratique

  • Petite échelle : mémoire partagée
  • Grande échelle : échange de messages

1.3.2 Dualité entre les deux modèles

  • 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

1.4 La grande tendance : la répartition à toute échelle

  • Grande échelle : l’éther de communication
  • Petite échelle : les architectures multi-cœurs

Vers la programmation parallèle

  • Nouveau paradigme à concevoir
  • Vers du séquentiel implicite ou explicite dans du parallélisme

Exemples de cette évolution

2 Un modèle chimique pour la programmation répartie

Pour décrire et comprendre les services et leurs interactions par échange de messages, nous allons recourir à une métaphore chimique.

soc_pingPong.png

Figure 3: Exemple d'un service ping

  • Les messages sont l'analogue de molécules ou d'atomes.
    • Structure : k(v)
      • k : canal
      • v : valeur transmise
  • Propriété fondamentale : la mobilité des canaux
    • La valeur v peut contenir un canal.
      • Exemple : message ping(pong, OK) transportant le canal de retour pong
  • Les agents consomment et produisent des messages. Leur comportement est décrit par des réactions chimiques.
    • Exemple : ping(k, x) -> k(x)
    • Structure : Messages & Etat -> Messages’ & Etat’
      • Possibilité de rajouter une condition : déclenchement de la réaction seulement si la condition est vérifiée.
      • Etat : représentation possible par un agrégat de messages internes, appelés atomes
      • Atome : R(v), où R est une relation (et non un canal)
        • Exemple : Val(x, 1) & Val(y, 2) ou X(1) & Y(2) pour représenter les valeurs 1 et 2 des variables x et y
  • Synchronisation : utilisation de l’opérateur de conjonction (le "join”, &) pour synchroniser des messages avec l'état
  • Convention : les relations commencent par des majuscules, les canaux par des minuscules.

2.1 L'exemple d'un compteur

Spécification

  • Service offrant un canal inc permettant d’incrémenter le compteur et un canal get permettant d’obtenir la valeur du compteur
  • Etat : la valeur du compteur

Règles

- inc(k) & Val(x) -> k() & Val(x+1)
- get(k) & Val(x) -> k(x) & Val(x)

Interprétation

  • Lorsque le compteur reçoit un message inc(k) et que son état est Val(x), il envoie un message vide sur le canal k pour accuser réception et modifie son état en Val(x+1).
  • Lorsque le compteur reçoit un message get(k) et que son état est Val(x), il envoie le message x sur le canal k et préserve son état.

3 Les canaux de communication : un concept central

On définit la communication à partir des canaux de communication. Dans la mesure du possible, on donne une interprétation dans le modèle chimique. On peut classer les canaux suivant les propriétés qu'ils garantissent. Voici trois classes fondamentales de propriétés.

  • Communication asynchrone ou synchrone
    • Quel rapport entre le temps de l’émetteur et celui du destinataire ?
  • Préservation de l'ordre
    • Un message émis avant arrive-t-il avant ?
  • La liaison entre les émetteurs et les destinataires
    • Quel nombre ?
    • Quelle durée de vie ? Quelle visibilité ?
    • Quelles garanties de sécurité ?

3.1 Préalable indispensable : définir le temps dans un système réparti

Quelle est la notion de temps dont il est question lorsqu'on parle de synchronisation ou de précédence par la suite ?

Dans un système réparti, il n'existe pas de temps absolu, mais seulement un temps relatif, obtenu par réunion des temps propres à chaque agent (comme en relativité restreinte, où le temps est relatif au repère considéré). Si le temps propre à chaque agent est ordonné totalement, ce n'est plus le cas du temps relatif. En effet, tous les évènements ne sont pas comparables deux à deux : deux événements sont dits indépendants, ou concurrents s'ils ne sont pas comparables. Nécessairement, de tels événements concurrents sont observés suivant des temps propres distincts. Il existe cependant des relations entre des temps propres, du fait de la communication : une émission est avant une réception. Il faut retenir que dans un système réparti, le temps relatif forme un ordre partiel et non total, comme l'illustre le schéma suivant.

soc_LamportLogicalTime.png

Figure 4: Le temps relatif dans un système réparti

A partir d'un diagramme spatio-temporel d'activités, dit de Lamport (du nom de son concepteur), représentant le temps (de gauche à droite) et les activités (de haut en bas) des agents, on peut déterminer cet ordre partiel : s'il est possible de relier un événement \(a\) à un événement \(b\) en suivant les flèches, alors \(a\) précède \(b\), sinon, ils sont concurrents. Par exemple, Les événements \(D\) et \(O\) sont concurrents alors que \(B\) précède \(P\).

Formellement le temps relatif se définit ainsi (Lamport, 1979). L'évènement \(a\) précède l'évènement \(b\) (noté \(a \leq b\)) si l’une des conditions suivantes est vérifiée :

  • \(a\) et \(b\) sont deux événements internes à une même activité séquentielle et \(a\) précède \(b\) dans cette activité,
  • \(a\) et \(b\) correspondent respectivement à l’émission et la réception d’un même message,
  • \(a\) et \(b\) sont égaux (réflexivité),
  • il existe un événement \(c\) tel que \(a\) précède \(c\) et \(c\) précède \(b\) (transitivité).

C'est donc la fermeture réflexive et transitive de la relation de précédence induite par l'exécution séquentielle des activités et la communication.

Le temps considéré peut être logique ou physique. Le temps logique est discret et se définit par la relation de précédence entre événements, autorisant ainsi la comparaison : le temps logique forme un ordre partiel, bien fondé, au sens où chaque activité a un début, et de degré fini, au sens où le nombre de prédécesseurs immédiats est fini. Le temps physique repose sur une mesure (continue ou presque) du temps. Cette mesure permet de transformer l'ordre partiel du temps logique en un ordre partiel de même structure, fondé sur le temps physique (précisément les temps physiques propres à chaque agent). De plus, cette structure peut se linéariser lorsqu'il est possible de synchroniser les temps propres des agents d'un système réparti : par exemple, on peut utiliser un protocole comme NTP (Network Time Protocol), qui permet d'obtenir un temps universel si le réseau inclut des horloges atomiques. On obtient ainsi une échelle commune de temps pour mesurer. Cette échelle permet de comparer des événements concurrents : cette comparaison n'est cependant pas significative puisqu'elle n'est pas déterminée logiquement, une autre exécution pouvant donner une comparaison différente.

Certaines applications imposent des contraintes concernant le temps réel d'exécution : ce sont des applications dites réactives, et non plus seulement interactives. Elles doivent réagir à temps aux messages reçus, en temps réel. A la limite, on trouve des systèmes synchrones, ceux dont les agents partagent le même temps, avec des temps négligeables de communication. Voir par exemple les circuits synchrones.

3.2 Modes de communication

Trois modes de communication

  • synchrone
  • asynchrone
  • diachrone (cf. remarque ci-dessous)

Remarque : "diachrone" est un terme inusité formé pour l’occasion, inspiré du qualificatif diachronique de la linguistique. On rencontre les termes

  • vibratoire, ou
  • faiblement synchrone, ou encore
  • asynchrone en précisant que le temps de communication est majoré au lieu d'être simplement fini.

Conformément à l'étymologie, on retient ici les interprétations suivantes qu'on raffinera progressivement. Une communication est dite

  • syn-chrone lorsque l'émission et la réception sont simultanées (en même temps),
  • asyn-chrone lorsque l'émission et la réception ne sont pas simultanées (pas en même temps),
  • dia-chrone lorsque l'émission et la réception sont deux temps séparés sur une échelle commune de temps, la durée entre l'émission et la réception postérieure étant majorée.

Tableau comparatif

  • À chaque mode de communication correspond une propriété qualifiant le temps de communication. Celle-ci vérifie une propriété de composition :

    temps ~ temps + temps (~ : équivalence modulo la propriété).

    Les propriétés s'expriment par trois qualificatifs : nul, majoré, arbitraire.

synchrone diachrone asynchrone
temps nul majoré arbitraire

Les trois modes de communication

3.2.1 Communication asynchrone

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

3.2.2 Communication synchrone (dite avec rendez-vous)

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 - Possibilité d'annoter la transition par le message échangé

       Emetteur[Feu()], Pompier[]
         // L'émetteur constate le début d'un incendie.
    -- (appel18("Au feu", "4 rue Alfred") : Emetteur -> Pompier) -->
       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) - Possibilité d'annoter la transition par le message échangé

    Emetteur[ Feu() & X ] & Pompier [ Y ] 
    -- (appel18("Au feu", "4 rue Alfred") : Emetteur -> Pompier) -->
    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.
    -- (appel18("Au feu", "4 rue Alfred") : Emetteur -> Pompier) -->
       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.

3.2.3 Communication diachrone

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

Exemple : La poste pneumatique

3.3 Traduction entre modes de communication

3.3.1 Communication synchrone au-dessus d'une communication asynchrone

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.

../medias/rendezVous_deadlock.svg

Inter-blocage avec deux 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.

3.3.2 Variante pour un protocole requête-réponse synchrone

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.

3.3.3 Communication asynchrone au-dessus d'une communication synchrone

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.

3.4 Préservation de l'ordre des messages

  • Communication préservant l’ordre des messages entre l'émission et la réception
    • Toujours pour tout canal synchrone, possible pour les autres

      Exemple : la ligne téléphonique, comme tout canal synchrone, mais aussi les tubes pneumatiques

  • Communication ne préservant pas l’ordre des messages
    • Impossible pour un canal synchrone, possible pour les autres

      Exemple : le courrier postal

3.5 Différents types de liaison

Destinataire
1 N
Emetteur 1 Point-à-point Diffusion
N Port d'entrée Bus

Types de canaux suivant le nombre de destinataires et d’émetteurs

  • Les canaux point-à-point sont utilisés pour des topologies avec des canaux fixes.
  • La diffusion peut être implémentée simplement par un service.
  • Les canaux mobiles correspondent à des ports d’entrée : ce sont leurs adresses qui sont transmises pour établir des communications.
  • Les bus pour les services ("Enterprise Service Bus") permettent de fournir des services de publication, d’abonnement et de diffusion.

Particularités diverses

  • Durée de vie - Visibilité

    Certains canaux sont gérés par les protocoles de communication, par exemple les canaux de retour. Ils n’existent ou ne sont visibles que le temps d’une session, par exemple le temps de terminer l’interaction requête-réponse.

    Exemple : canal de réponse http

  • Sécurité

    Certains canaux garantissent l’authentification (de l’émetteur), la confidentialité des données et leur intégrité. Ils utilisent alors des techniques de chiffrement.

    Exemple : canal https

3.6 Relation entre la communication, la production et la consommation de messages

Il est important de distinguer la communication de l'action. Précisément, voici les différentes phases lors d'un échange de messages.

  • Production d’un message

    Client[url(requête, ret)], Serveur[]
      // Le client produit le message url(requête, ret).
    
  • Émission du message

    Client[], url(requête, ret), Serveur[]
      // La client émet le message url(requête, ret).
    
  • Réception du message

    Client[], Serveur[url(requête, ret)]  
      // Le serveur reçoit le message url(requête, ret).
    
  • Consommation du message

    Client[], Serveur[ret(reponse)]
      // Le serveur consomme le message url(requête, ret).
    

Cette distinction donne naissance à deux qualificatifs, point-à-point ("point-to-point") et agent-à-agent ("end-to-end"). Voici un exemple.

La communication est dite

  • synchrone point-à-point lorsque l’émission et la réception sont simultanées,
  • synchrone agent-à-agent ("end-to-end") lorsque la production et la consommation sont simultanées.

    Emetteur[
      Feu() -> appel18("Au feu", "4 rue Alfred") & Evacuation()
    ]
    Pompier[   
      appel18(message, adresse) -> Alerte(message, adresse)
    ]
    // Communication synchrone point-à-point
       Emetteur[Feu()], Pompier[]
         // L'émetteur constate le début d'un incendie.
    -> Emetteur[appel18("Au feu", "4 rue Alfred"), Evacuation()], Pompier[]
         // L'émetteur produit un message appel18. 
    -> Emetteur[Evacuation()], Pompier[appel18("Au feu", "4 rue Alfred")]
         // La communication se fait en un temps nul.
    -> Emetteur[Evacuation()], Pompier[Alerte("Au feu", "4 rue Alfred")]
         // Le récepteur consomme le message appel18.
    
    // Communication synchrone agent-à-agent      
       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.
    

Bien sûr, la seconde implique la première. La réciproque est fausse : il peut y avoir un délai entre la production et l'émission, comme entre la réception et la consommation. Dans l'exemple ci-dessus, d'autres transitions pourraient survenir avant l'émission ou après la réception, produisant un délai. Autrement dit, une communication synchrone point-à-point peut être asynchrone agent-à-agent.

Lorsqu'on s'intéresse à la programmation des agents, seules les propriétés agent-à-agent importent. On suppose implicitement cette qualification par la suite ; en revanche, pour une propriété point-à-point, on le précise. Ainsi, quand on dit "communication synchrone", on entend "communication synchrone agent-à-agent". Bien noter que cette convention n'est pas toujours celle suivie dans la pratique : il est donc nécessaire de lever toute ambiguïté dans la qualification de la communication, puisque la différence est importante.

Cette qualification concerne non seulement la synchronisation des communications, mais aussi l'ordre des messages ou encore la sécurité.

4 Concurrence et distribution - Problèmes classiques

On s'intéresse à une liste de problèmes classiques liés à la concurrence et à la répartition.

  • Concurrence
    • Sérialisabilité garantissant la cohérence des accès concurrents à des données partagées
    • Détection et prévention de l'interblocage
  • Répartition
    • Communication préservant l'ordre des messages (induit par le temps logique)
    • Tolérance aux pannes : consensus, cohérence et disponibilité
    • Sécurité : authentification, confidentialité, intégrité

Pour chaque problème, on décrit :

  • la nature du problème,
  • des contextes typiques où il se rencontre,
  • une ou plusieurs solutions en utilisant le modèle conceptuel.

4.1 Concurrence - Cohérence lors d'accès concurrents

Un agent serveur contrôle une ressource et propose deux services pour lire cette ressource (get) et modifier cette ressource (set). Deux agents clients veulent modifier cette ressource suivant son état courant. Que se passe-t-il ? C'est un problème typique d'accès concurrents à une donnée (de "data race").

Il est possible qu'il y ait des pertes en écriture ("lost updates"). Ce phénomène peut se produire dès qu'une ressource est partagée et qu'elle peut être modifiée. Il peut aussi se produire de mauvaises lectures ("dirty read") lorsqu'une valeur intermédiaire est lue, alors que seule la valeur finale est correcte.

Exemple

  • ressource : simple registre (à valeur entière)
  • action des clients : incrémenter d'une unité la valeur du registre
  • perte en écriture : deux clients incrémentant d'un produisant une incrémentation d'un au lieu de deux

soc_consistency_executionDiagram.png

Figure 5: Exécutions concurrentes avec possibles pertes en écriture

On considère que les ressources restent dans un état cohérent si toute exécution est équivalente à une exécution qui serait séquentielle. C'est la propriété de sérialisabilité.

Formalisation de l'exemple

Un serveur gérant un registre :

  • get : canal pour lire le registre
  • set : canal pour modifier

et possédant un état :

  • Val : valeur du registre

Deux clients incrémentant le registre

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

4.1.1 Solution naïve

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

Le problème n'apparaît pas si la communication est synchrone et si pour chaque agent, les deux couples de requêtes-réponses s'effectuent lors du même rendez-vous. Dans tous les autres cas, un problème peut survenir : certaines exécutions ne sont pas équivalentes à une exécution en série des clients.

Solution : on utilise des transactions.

4.1.2 Mécanisme transactionnel - Approche pessimiste

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)

4.1.3 Mécanisme transactionnel - Approche optimiste

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

4.1.4 Comparaison entre les approches

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

4.1.5 Généralisation à n ressources

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.

4.1.6 Verrouillage en deux phases

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, une lecture puis une incrémentation comme précédemment.

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.

medias/soc_twoPhaseLocking_precedenceGraph.svg

Verrouillage en deux phases - Circuit impossible dans le graphe de précédence

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.

4.2 Concurrence - Interblocage

Un agent serveur contrôle deux ressources X et Y. Un agent client cherche à verrouiller la ressource X puis la ressource Y. Un second agent client cherche à verrouiller la ressource Y puis la ressource X. Que se passe-t-il ?

Les clients peuvent être bloqués : c'est l'interblocage ("deadlock"). Ce phénomène peut se produire avec une approche pessimiste du contrôle de la concurrence, en présence de plusieurs ressources.

soc_deadlock.png

Figure 6: Interblocage

Deux solutions sont possibles :

  • la détection de l'interblocage,
  • la prévention de l'interblocage.

4.2.1 Détection de l'interblocage

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.

soc_useGraph.png

Figure 7: Circuit dans le graphe d'usage des ressources

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.

4.2.2 Prévention de l'interblocage

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.

4.3 Répartition - préservation de l'ordre des messages

Il est possible de garantir que la communication préserve l'ordre des messages, en annotant les messages ou en complexifiant le protocole de communication. On parle parfois de communication causale, au sens où elle préserve l'ordre causal induit par la relation de précédence temporelle. La propriété de préservation s'énonce précisément ainsi :

pour tout couple de messages m1 et m2 de même destinataire, si l'émission de m1 précède celle de m2 (possiblement par deux émetteurs distincts), alors la réception de m1 précède la réception de m2.

Il est intéressant de la vérifier dès lors que les actions déclenchées par la réception des messages ne commutent pas. Prenons l'exemple d'une édition collaborative et décentralisée, où chaque agent possède une copie du document édité et doit donc diffuser aux autres agents ses propres actions. L'action d'effacer le dernier caractère écrit ne commute pas avec l'action d'ajouter un caractère par exemple.

Il n'y a pas de solution simple à ce problème : par exemple, ajouter aux messages la date d'émission ne suffit pas, même dans le cadre d'un temps universel à disposition, puisqu'il est nécessaire de déterminer à réception d'un message si un autre message a pu être émis antérieurement à cette date. C'est l'historique des émissions qui importe.

En théorie, il est possible de garantir que chaque agent connaisse non seulement sa trace d'exécution mais aussi des préfixes de celles des autres agents: précisément, il peut connaître l'idéal principal formé de tous les évènements survenus avant l'évènement courant de sa propre trace. En effet, il suffit que l'émetteur ajoute à chaque message émis l'idéal principal qu'il connaît ; à réception, le destinataire met alors à jour ses propres connaissances. Il peut ainsi découvrir un message indirectement, alors que l'original ne lui est pas encore parvenu.

Il devient possible de préserver l'ordre causal : un message reçu n'est traité que si tous les messages précédents vers le même destinataire ont été reçus et traités.

En pratique, la solution précédente n'est pas raisonnable, du fait de la taille croissante des idéaux principaux à transmettre. Il est préférable d'en faire des approximations, typiquement en numérotant les messages (par un horodatage, ou "timestamp"). La communication devient alors possible, par exemple :

  • entre deux agents, en ajoutant un simple numéro aux messages,
  • entre plusieurs agents dans le cas d'une diffusion causale, en transmettant des vecteurs de numéros (de taille le nombre d'agents),
  • entre plusieurs agents dans le cas d'une communication causale, en transmettant des matrices carrées de numéros (de taille le nombre d'agents).

D'une manière duale, plutôt que d'enrichir les messages, il est possible d'enrichir le protocole pour garantir l'ordre. Par exemple, dans le cas d'une communication causale entre deux agents, il suffit d'utiliser une file d’attente pour l’émission et un protocole avec accusé de réception.

L'inconvénient d'une solution fondée sur l'horodatage tient d'une part à la taille des informations nécessaires, d'autre part à la difficulté à prendre en compte le départ et l'arrivée d'agents dans le réseau. Une piste actuellement explorée pour pallier cet inconvénient consiste à réaliser un compromis, la préservation n'étant garantie qu'avec une forte probabilité, ce qui autorise à diminuer drastiquement la taille des informations nécessaires.

4.3.1 Exemple de la communication causale entre deux agents

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

../medias/causalCommunication_triangle.svg

Echange ne vérifiant pas l'inégalité triangulaire (marquage du temps des émissions et des réceptions)

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

4.4 Répartition - Tolérance aux pannes

4.4.1 Différentes tolérances aux pannes

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 conjonction (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.
Propriété préservée
Type de tolérance
Sûreté Vivacité
Masquage des pannes
Mode dégradé (fail-safe) X
Mode robuste
X
Aucune
X X

Quatre types de tolérance

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.

4.4.2 Impossible consensus en communication asynchrone

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 (\((p, q) \in R\))

      - 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.
Réduction 1
Réduction 2
Panne Action
Panne
Communication
Action i
Action j
Communication i
Communication j
Action i
Communication j
Communication i
Action j
image/svg+xml Layer 1 1 1 2 2

(agent i différent d'agent j)
Commutation de deux réductions

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, à partir de cet état accessible, pour tout agent présent, il existe une exécution dans laquelle cet agent produit dans l'état final la valeur de consensus obtenue.

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 dans cet état accessible. Il y produit 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.

4.4.3 Nécessaire compromis entre cohérence et disponibilité

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 (vivacité) : c'est le théorème dit CAP ("Consistency, Availability, Partition"). Lorsqu'une partition du réseau apparaît, soit les réplicas évoluent d'une manière incohérente, soit ils sont indisponibles. Bref, soit la sûreté est sacrifiée, soit la vivacité l'est. Les solutions visent donc un compromis, par exemple la disponibilité avec une incohérence momentanée mais l'assurance de la convergence des réplicas. Avec une telle solution, la sérialisabilité, qui garantit la cohérence et est une propriété de sûreté, est abandonnée : une exécution de plusieurs clients n'est plus équivalente à une exécution en série des clients. La convergence est assurée en deux phases :

  • la diffusion entre réplicas des versions courantes des réplicas ou des opérations ayant mené aux nouvelles versions,
  • la réconciliation permettant de déterminer une valeur commune finale pour les réplicas.

Des structures de données adaptées permettent de faciliter la réconciliation : libres de tout conflit, elles peuvent être fusionnées simplement. Voir les Conflict-free replicated data types.

Bibliographie :

4.4.4 Détection de pannes

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.

4.4.4.1 Exemple de consensus avec la détection de pannes

La communication synchrone peut s'exprimer, comme on l'a vu, par une règle impliquant les deux agents en communication. Une garde exprimant l'inactivité d'une telle règle permet de détecter les pannes.

Communication synchrone - Schéma de la règle

Agent1[ A ] & Agent2[ B ] 
  -- (message : Agent1 -> Agent2) -> 
Agent1[ C ] & Agent2[ D ]

Détection de pannes par une garde particulière

Agent1[ ... ] & ((Agent2[_]) inactif) -> ...

Avec une telle garde, il devient possible de réaliser un consensus. Reprenons l'exemple ci-dessus devant réaliser pour consensus la conjonction de décisions booléennes. L'algorithme procède par rondes : la convergence vers le consensus est garantie au bout d'un certain nombre de rondes. Pour simplifier, la communication est supposée synchrone. Avec une communication asynchrone sans perte de messages, il suffirait d'attendre suffisamment avant de passer à la ronde suivante.

Agent A[i] (sur n agents au total)

  • Etat
    • Recensement(v) : vecteur de booléens de taille n, utilisé pour recenser les décisions des agents
    • AEnvoyer(r, j) : indicateur d'envoi de message à j lors de la ronde r
    • ARecevoir(r, j) : indicateur de réception de message provenant de j lors de la ronde r
  • Etat initial
    • AEnvoyer(r, j), ARecevoir(r, j) (r parcourant les numéros de rondes, j parcourant les agents j différents de i)
    • Recensement((i := Vrai)) ou Recensement((i := Faux)) : valeur décidée par l'agent A[i]

Notation vectorielle - v ou u vecteurs, i ou j indices, b booléen

  • v[i] : valeur en i
  • (i := b) : vecteur valant b en i, Vrai ailleurs
  • v.(i := b) : vecteur valant b en i et v[j] en j différent de i
  • v ∧ u : vecteur valant v[i] ∧ u[i] en i

Agent A[i] communiquant avec agent A[j] - Ronde 1

-   A[i] [ AEnvoyer(1, j) & Recensement(x) & X ]
  & A[j] [ ARecevoir(1, i) & Recensement(y) & Y ]
  -> A[i] [ Recensement(x) & X]
   & A[j] [ Recensement(y.(i := x[i])) & Y ]

// Détection de la panne de A[j]
-   A[i] [ AEnvoyer(1, j) & X ] & ( (A[j] [_]) inactif)
  -> A[i] [ X ]

// Détection de la panne de A[i] - Décision associée : Faux
-   A[j] [ ARecevoir(1, i) & Recensement(y) & Y ] & ( (A[i] [_]) inactif)
  -> A[j] [ Recensement(y.(i := Faux)) & Y ]

Agent A[i] communiquant avec agent A[j] - Rondes suivantes

-   A[i] [ AEnvoyer(r, j) & Recensement(x) & X ]
  & A[j] [ ARecevoir(r, i) & Recensement(y) & Y ]
  -> A[i] [ Recensement(x) & X]
   & A[j] [ Recensement(y ∧ x) & Y ]

// Détection de la panne de A[j]
-   A[i] [ AEnvoyer(r, j) & X ] & ( (A[j] [_]) inactif)
  -> A[i] [ X ]

// Détection de la panne de A[i]
-   A[j] [ ARecevoir(r, i) & Y ] & ( (A[i] [_]) inactif)
  -> A[j] [ Y ]

Lorsqu'à la fin d'une ronde, un agent est toujours actif, deux propriétés sont vérifiées, compte tenu de la première règle :

  • il a transmis à tout autre agent actif son message,
  • il a reçu et consommé les messages envoyés par les autres agents actifs.

Cependant, un agent peut tomber en panne au cours d'une ronde. Pendant cette ronde, un tel agent a pu recevoir et transmettre certains messages. Ainsi, il est possible qu'après la ronde 1 des agents actifs à l'issue de la ronde aient obtenu des valeurs différentes pour un agent A[i] tombé en panne : c'est le cas si la valeur décidée par cet agent était Vrai et a été transmise au moins une fois, et si sa panne a été détectée par au moins un agent.

Si aucun tel cas n'a été rencontré, tous les agents actifs ont le même vecteur : il suffit de calculer la conjonction des composantes du vecteur pour obtenir la valeur de consensus.

Supposons qu'on soit dans le cas problématique pour un agent A[i] tombé en panne. A l'issue de la première ronde, réalisons une bipartition des agents actifs, suivant la valeur de leur vecteur en i. A l'issue de la ronde suivante, considérons la bipartition obtenue en conservant les agents actifs dans chacune des deux parties initiales. Si un agent qui avait détecté la panne et avait donc associé à l'agent A[i] la valeur Faux est encore actif, c'est qu'il a transmis cette valeur à tous les autres processus actifs, ce qui fait que le consensus est obtenu pour la valeur associé à l'agent A[i]. Sinon, il ne reste que les agents associant initialement à l'agent A[i] la valeur Vrai. Comme certains de ces agents ont pu mettre à jour leur valeur à Faux, à la réception d'un message d'un agent de l'autre partie, on obtient une nouvelle bipartition de ce groupe. Si une des deux parties est vide, un consensus est atteint pour la valeur associée à l'agent i. Sinon, la partie contenant les agents associant la valeur Vrai à l'issue de cette ronde est strictement incluse dans celle initiale. Comme elle ne peut décroître indéfiniment, le consensus est certain, au bout d'au plus n rondes, en remarquant qu'un consensus se préserve lors d'une ronde.

4.5 Répartition - Sécurité

Lorsqu'on envisage la sécurité, on doit s'astreindre à une certaine rigueur :

  • bien définir la propriété de sécurité souhaitée (notée P),
  • bien définir la classe d'attaquants (notée A).

On peut alors montrer des propriétés du genre suivant : si on prend des mesures M, alors quel que soit le comportement d'un attaquant de la classe A, la propriété P sera vérifiée.

On s'intéresse ici à la sécurité lors de l'échange de messages. On envisage des attaques sur le réseau : un attaquant peut intercepter un message, le lire, modifier son contenu, le détruire ou encore le transmettre plusieurs fois. Pour contrer ces attaques, on s'intéresse à des mesures utilisant le chiffrement des données.

4.5.1 Intégrité

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

Sorry, your browser does not support SVG.

Figure 8: Code d'authentification d'un message (source : Wikipedia)

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

4.5.2 Authentification

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.

4.5.3 Confidentialité

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

4.5.4 Attaque dite de l'homme du milieu ("Man in the Middle Attack")

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.

Author: Hervé Grall
Version history: v1: 2016-10-19; v2: 2016-10-21[*text]; v3: 2017-02-06[*text]; v4: 2017-10-30[+causality]; v5: 2018-01-30[*text]; v6: 2018-02-07[*text, +consensus, +causality]; v7: 2019-01-28[update]; v8: 2019-02-01[*consensus]; v9: 2019-10-07[*time, *CAP, update].
Comments or questions: Send a mail.
The webpage content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.