title: Algorithme de Maekawa
text: # Algorithme de Maekawa
  
  L'algorithme de Maekawa est un algorithme d'exclusion mutuelle sur un système distribué.
  
  Dans l'algorithme de Maekawa, chaque composant appelé « site » ne peut donner de permission d'entrée dans une section critique qu'à un seul autre composant à la fois. Chaque site a la charge d'arbitrer les éventuels conflits qui apparaîtront entre différents autres sites. Cela impose au participant à qui cette permission a été donnée de rendre la main sur la section critique spontanément une fois qu'il a fini son travail, c'est-à-dire lorsqu'il sort de sa section critique.
  
  ## Terminologie
  
  * Un « site » est l'endroit où est exécuté l'algorithme de Maekawa
  * Pour toute demande d'entrée en section critique :
     * Le « site demandeur » est le site qui demande d'entrer en section critique.
     * Le « site de réception » est tout autre site qui reçoit la demande du site demandeur.
  * Tout site ayant donné sa permission en réponse à une demande est dit « verrouillé »
  
  ## Différents types de messages échangés
  
  Les types de messages échangés lors de l'exécution de l'algorithme sont :
  
  * DEMANDE : un message de demande d'entrée en section critique
  * ACCORD : un message d'acceptation d'entrée en section critique
  * ÉCHEC : un message de refus d'entrée en section critique
  * SONDAGE : un message envoyé pour résoudre les problèmes d’interblocage
  * RESTITUTION : une réponse à un message SONDAGE
  * LIBÉRATION : un message de sortie de section critique
  
  ## Algorithme
  
  ### Site demandeur
  
  * Un site $P_{i}$ demandant envoie un message de demande $(ts,i)$ à tous les sites dans son quorum Ri.
  
  ### Site receveur
  
  * Lors de la réception d'un message de demande $(ts,i)$, le site de réception $P_{j}$ :
     * Si le site $P_{j}$ n'a pas un accord en cours (c'est-à-dire un message d'accord qui n'a pas été relâché), alors le site $P_{j}$ envoie un message d'accord (j) sur le site $P_{i}$.
     * Si le site $P_{j}$ a un accord en cours pour un processus avec une priorité plus élevée que la demande, alors le site $P_{j}$ envoie un message d'échec (j) sur le site $P_{i}$ et $P_{j}$ ajoute à sa file d'attente la demande du site $P_{i}$.
     * Si le site $P_{j}$ a un accord en cours pour un processus avec une priorité inférieure à la demande, alors le site $P_{j}$ envoie un message de sondage (j) au processus qui est actuellement autorisé à accéder à la section critique par le site $P_{j}$ (c'est-à-dire le site avec le message d'accord en cours).
  * Lors de la réception d'un message de sondage (j), le site $P_{k}$ :
     * Envoie un message de restitution (k) sur le site $P_{j}$ si et seulement si le site $P_{k}$ a reçu un message d'échec d'un autre site, ou si $P_{k}$ a envoyé un message de restitution à un autre site, mais n'a pas reçu un nouvel accord.
  * Lors de la réception d'un message de restitution (k), le site $P_{j}$ :
     * Envoie un message d'accord à la première demande de sa file d'attente. Notez que les requêtes au sommet sont celles de plus haute priorité.
     * Place $P_{k}$ dans sa file d'attente.
  * Lors de la réception d'un message de libération (i), le site $P_{j}$ :
     * Supprime $P_{i}$ de sa file d'attente.
     * Envoie un message d'accord à la première demande de sa file d'attente.
  
  ### Section critique
  
  * Un site $P_{i}$ entre dans la section critique lorsqu'il reçoit un message d'accord de tous les sites du quorum Ri.
  * À la sortie de la section critique, $P_{i}$ envoie un message de libération (i) à tous les sites de Ri.
  
  ### Quorum
  
  Un quorum doit respecter les propriétés suivantes :
  
  * $\forall i\,\forall j\,[R_{i}\bigcap R_{j}\neq \emptyset ]$
  * $\forall i\,[P_{i}\in R_{i}]$
  * $\forall i\,[|R_{i}|=K]$
  * Le site $P_{i}$ est contenu dans exactement K ensembles de requêtes
  
      Ce qui implique:
     * $|R_{i}|\geq {\sqrt {N-1}}$
  
  ## Performance
  
  * En nombre de messages sur le réseau : $3{\sqrt {N}}$ à $6{\sqrt {N}}$
  * Délai de synchronisation : délai de 2 messages de propagation
  