Délivrance causale

Dans un système réparti, la communication entre les noeuds du système est en général assurée par une couche de communication spécifique utilisée par des entités de la couche supérieure pour expédier ou recevoir des messages. Cette couche de communication peut être amenée à ne pas rendre accessible les informations reçues depuis d'autres sites aux applications de la couche supérieure. C'est le cas de la couche TCP qui ne rend accessible un caractère que lorsque tous les caractèress envoyés précédemment sur la connexion ont été effectivement reçus.

La délivrance d'un message est l'opération consistant à le rendre accessible aux applications clientes : nous noterons del(m) cette opération.
La délivrance d'un message recu pourra le cas échéant être retardée par rapport à sa réception afin de satisfaire des contraintes spécifiques de l'ordre de délivrance souhaité si la couche de transport ne garantit pas elle-même la réception des messages dans cet ordre.

Nous mentionnons maintenant les deux propriétés de l'ordre de délivrance des messages qui peuvent s'avérer souhaitables pour certains types d'application.

• Ordre de délivrance FIFO : cette propriété assure que si deux messages sont envoyés successsivement depuis un même site S_i vers un même destinataire S_j, le premier sera délivré sur le site S_j avant le second, c'est-à-dire qu'on a :
  
  
  
  Dans la figure suivante, le canal de communication ne garantit pas une réception FIFO des messages envoyés
  
  
  
  Le message m₂ double le m₁ (il est envoyé après lui mais arrive néanmoins avant lui) : pour respecter un ordre de délivrance fifo sa délivrance doit être retardée et n'avoir lieu qu'une fois que le message m₁ est arrivé et est délivrable. D'un point de vue pratique, cela suppose que la couche de communication dispose d'un tampon (buffer) ordonné dans lequel les messages sont placés dans l'ordre où les applications les liront et d'un autre tampon dans lequel les messages reçus mais non délivrables immédiatement sont conservés jusqu'à ce que les conditions autorisant leur délivrance soient satisfaites.
  Il est assez facile de développer une couche garantissant cette propriété de la délivrance en numérotant sur chaque canal les messages expédiés.
  
  
• Ordre de délivrance causale : cette propriété étend la précédente à des communications à destination d'un même site en provenance de plusieurs autres.
  Elle assure que si l'envoi du message m₁ par le site S_i à destination du site S_k précède (causalement) l'envoi du message m₂ par le site S_j à destination du site S_k, le message m₁ sera délivré avant le message m₂ sur le site S_k.
  Autrement dit, on a :
  
  
  
  Une situation dans laquelle la propriété de délivrance causale est violée si les messages sont délivrés dans l'ordre où ils sont reçus est décrite dans la figure ci-dessous :
  
  
  
  On a en effet dans ce cas :
  
  
  
  Afin de garantir une délivrance respectant la causalité, il est nécessaire de différer la délivrance du message m₃ jusqu'à arrivée du message m₁ et son passage au statut de message délivrable.
  Ainsi que nous le verrons dans la section suivante, garantir le respect de la causalité dans l'ordre de la délivrance des messages n'est pas aussi simple que garantir le respect de l'ordre fifo.

Horloges et estampilles logiques

Afin de dater les événements, des horloges logiques de différents types peuvent être définies afin de rendre compte de la relation de causalité entre les événements.
Les valeurs des horloges associées à des événements (leurs estampilles logiques) comparables doivent être elles-mêmes comparables et refléter l'ordre des événements, c'est-à-dire que