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

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

Sorry, your browser does not support SVG.

Figure 1: Mémoire partagée (par des processeurs) (source : Wikipedia)

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

Sorry, your browser does not support SVG.

Figure 2: Echange de messages dans une architecture à services (source : svgopen)

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 à chaque agent (comme en relativité restreinte, où le temps est relatif au repère considéré). Le temps considéré peut être logique ou physique.

Le temps logique s'intéresse à la relation de précédence entre événements : il autorise la comparaison. Cependant du fait de la relativité du temps, 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 suivant l’ordre de précédence. Autrement dit, le temps forme un ordre partiel et non total.

soc_LamportLogicalTime.png

Figure 4: Le temps logique 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 logique 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é).

Autrement dit, c'est 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 physique permet non seulement la comparaison mais aussi la mesure. Il est possible de synchroniser les agents d'un système réparti sur un réseau comme Internet, en utilisant un protocole comme NTP (Network Time Protocol) : on obtient ainsi une échelle commune de temps pour mesurer. Pour que cette mesure donne un temps universel, il est nécessaire d'introduire parmi ces agents une horloge donnant ce temps universel, par exemple une horloge atomique.

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 fixés de communication. La communication y est diachrone ou synchrone : les temps relatifs des agents sont identiques et en relation avec les temps de communication qui sont majorés ou (supposés) nuls.

3.2 Modes de communication

Trois modes de communication

  • synchrone
  • asynchrone
  • diachrone (ou vibratoire, faiblement synchrone ou asynchrone avec temps majoré)

diachrone : 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 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 un qualificatif pour le temps de communication. Celui-ci vérifie une propriété de composition :

    temps ~ temps + temps (~ : du même ordre).

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

       Emetteur[Feu()], Pompier[]
         // L'émetteur constate le début d'un incendie.
    -> Emetteur[Evacuation()], Pompier[Alerte("Au feu", "4 rue Alfred")]
         // L'émetteur et le récepteur se synchronisent via 
         //   le message échangé sur le canal synchrone appel18.
    
  • Exemple de communication synchrone avec une règle particulière de synchronisation

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

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

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

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

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

3.3 Traduction entre modes de comunication

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 seul 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 ; côté serveur, il est égal au temps de calcul de la réponse. 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, 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

Problème (sauf si la communication est synchrone agent-à-agent)

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

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.

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

../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 intersection (cf. Defining Liveness) :

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

Exemple pour un serveur

  • Sûreté : le serveur n'est jamais dans un état d'erreur.
  • Vivacité : le serveur peut toujours répondre aux requêtes.
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

  • 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)\), où \(p\) et \(q\) sont des parties de \(A\) 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 aboutissant à 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.
  • 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).

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étectée d'un agent.

  • Il termine toujours.
  • 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 détectées, Faux sinon.

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

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

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 d'introspection 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.

Du lemme de commutativité, on déduit que l'inactivité se préserve.

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

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. Par le lemme de génération, cet état engendre une valeur. Par le lemme de stabilité de l'inactivité, tous les états subséquents sont inactifs. On en déduit que cet état produit une valeur et est donc monovalent. CQFD

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

Lemme [Monovalence consensuelle] : 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 la règle de panne de l'agent \(i\) 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 correspondant à une action ou à une communication pour un agent \(i\) et menant à un état total et monovalent, engendrant \(u\).
      • S'il existe une réduction correspondant à une action ou à une communication pour un autre agent \(j\) et menant à un état total et monovalent, engendrant \(v\), alors par commutativité des réductions qui sont composables, on obtient \(u = v\).
      • Supposons qu'il existe une autre réduction correspondant à une action ou à une communication pour l'agent \(i\) et menant à un état total et monovalent, engendrant \(v\).
        • Supposons l'existence d'une réduction correspondant à une action ou à une communication pour un autre agent \(j\) et menant à un état total et monovalent. 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 de la monovalence consensuelle, 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 de la monovalence consensuelle 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.

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 (théorème dit CAP ("Consistency, Availability, Partition")). Soit les réplicas évoluent d'une manière incohérente, soit ils sont indisponibles lorsqu'une partition du réseau apparaît. Bref, soit la sûreté est sacrifiée, soit la vivacité l'est.

Bibliographie :

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 panne

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

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. Evidemment, 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].
Comments or questions: Send a mail.
The webpage content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.