Paxos (informatique)

Les protocoles de consensus sont les bases de l'approche de la machine à état (en) à l'informatique distribuée, comme suggéré par Leslie Lamport^[3] et par Fred Schneider^[4]. L'approche de la machine à état est une technique pour convertir un algorithme en un algorithme résistant aux pannes et distribué. Les techniques plus basiques pouvant laisser de nombreux cas de pannes non gérés. La principale approche proposée par Lamport et Al. assure que tous les cas sont gérés de façon sûre.

Le protocole Paxos a été publié pour la première fois en 1989 et nommé d'après des élections législatives fictives sur l'ile Grecque de Paxos^[5]. Il a été ensuite publié comme un article de journal en 1998^[6].

La famille de protocoles Paxos inclut des échanges entre les nœuds, le temps entre chaque réponse à un message avant de prendre une décision, le niveau d’activité des participants, le nombre de messages envoyés, et les types de pannes. Aucun algorithme de consensus résistant aux pannes ne permet de garantir de progresser (s’exécuter jusqu'à apporter une réponse valable) sur un réseau asynchrone (un résultat prouvé par un article de Fischer, Lynch et Paterson^[7]), Paxos garantit la sécurité (pas d’incohérence possible), et les conditions qui peuvent l'empêcher de progresser sont difficiles à créer^{[6],[8],[9],[10],[11]}.

Paxos est couramment utilisé dans des situations qui demandent de la durabilité (par exemple, pour répliquer des fichiers ou des bases de données). Le protocole essaye de progresser même pendant les périodes où un nombre limité de réplicats de données sont en panne. Un mécanisme de reconfiguration existe et peut être utilisé pour sortir un nœud des réplicats ou en ajouter.

Paxos garantit l'intégrité si moins de la moitié des processus est en panne^[12].

Paxos définit plusieurs rôles pour ces acteurs : client, acceptor, proposer, learner, et leader. Généralement un seul processeur peut jouer plusieurs rôles au même instant. Ce n'est pas un problème pour le protocole, et c'est d'usage courant pour baisser la latence entre les messages.

Client

Le Client fait des requêtes aux systèmes distribués, et attend une réponse. Par exemple une requête d'écriture sur un système de fichiers distribué.

Acceptor (Votants)

Les Acceptors servent de mémoire résistante aux pannes. Les Acceptors sont regroupés en groupes nommés Quorums. Chaque message envoyé à un Acceptor doit l'être au Quorum entier. Un message reçu sur un Acceptor qui n'a pas été reçu sur tous les autres Acceptors du Quorum est ignoré.

Proposer

Un Proposer pousse la requête du client, il a pour but de convaincre les Acceptors de tomber d'accord, et agit comme coordinateur pour avancer quand un conflit se présente.

Learner

Les Learners servent à la réplication. Une fois qu'une requête d'un Client a été acceptée par les Acceptors, le Learner peut agir (i.e.: exécuter une requête et envoyer la réponse au client). Pour augmenter la disponibilité on peut ajouter des Learners.

Leader

Paxos nécessite un Proposer différent (appelé le leader) pour avancer. Plusieurs processus peuvent croire être le leader, mais le protocole ne garantit l'avancement que si l'un d'eux est choisi. Si deux processus croient qu'ils sont leader, ils peuvent bloquer le protocole en envoyant continuellement des propositions conflictuelles. Mais l'intégrité des données est toujours préservée dans ce cas.