Algorithme de Maekawa

• Un site ${\displaystyle P_{i}}$ demandant envoie un message de demande ${\displaystyle (ts,i)}$ à tous les sites dans son quorum Ri.

• Lors de la réception d'un message de demande ${\displaystyle (ts,i)}$, le site de réception ${\displaystyle P_{j}}$ :
  • Si le site ${\displaystyle 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 ${\displaystyle P_{j}}$ envoie un message d'accord (j) sur le site ${\displaystyle P_{i}}$.
  • Si le site ${\displaystyle P_{j}}$ a un accord en cours pour un processus avec une priorité plus élevée que la demande, alors le site ${\displaystyle P_{j}}$ envoie un message d'échec (j) sur le site ${\displaystyle P_{i}}$ et ${\displaystyle P_{j}}$ ajoute à sa file d'attente la demande du site ${\displaystyle P_{i}}$.
  • Si le site ${\displaystyle P_{j}}$ a un accord en cours pour un processus avec une priorité inférieure à la demande, alors le site ${\displaystyle P_{j}}$ envoie un message de sondage (j) au processus qui est actuellement autorisé à accéder à la section critique par le site ${\displaystyle 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 ${\displaystyle P_{k}}$ :
  • Envoie un message de restitution (k) sur le site ${\displaystyle P_{j}}$ si et seulement si le site ${\displaystyle P_{k}}$ a reçu un message d'échec d'un autre site, ou si ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle P_{k}}$ dans sa file d'attente.
• Lors de la réception d'un message de libération (i), le site ${\displaystyle P_{j}}$ :
  • Supprime ${\displaystyle P_{i}}$ de sa file d'attente.
  • Envoie un message d'accord à la première demande de sa file d'attente.

• Un site ${\displaystyle 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, ${\displaystyle P_{i}}$ envoie un message de libération (i) à tous les sites de Ri.

Un quorum doit respecter les propriétés suivantes :

1. ${\displaystyle \forall i\,\forall j\,[R_{i}\bigcap R_{j}\neq \emptyset ]}$
2. ${\displaystyle \forall i\,[P_{i}\in R_{i}]}$
3. ${\displaystyle \forall i\,[|R_{i}|=K]}$
4. Le site ${\displaystyle P_{i}}$ est contenu dans exactement K ensembles de requêtes

Ce qui implique:

• • ${\displaystyle |R_{i}|\geq {\sqrt {N-1}}}$

• (fr) « Description de l'algorithme de Maekawa »

• Portail de l'informatique théorique