# Paxos (informatique)

En informatique distribuée, Paxos est une famille de protocoles permettant de résoudre le consensus dans un réseau de nœuds faillibles, c'est-à-dire susceptible d'avoir des pannes. Le consensus désigne ici le fait que les différents nœuds se mettent d'accord sur un résultat, et c'est une opération difficile quand les nœuds ou leurs moyens de communications ont des pannes.

## Description

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 et par Fred Schneider. 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. Il a été ensuite publié comme un article de journal en 1998.
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), Paxos garantit la sécurité (pas d’incohérence possible), et les conditions qui peuvent l'empêcher de progresser sont difficiles à créer$^,$$^,$$^,$$^,$.
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.

## Rôles

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.