Wikipédia

Paxos (informatique)

Page d’aide sur l’homonymie

Pour les articles homonymes, voir Paxos (homonymie).

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[1], et c'est une opération difficile quand les nœuds ou leurs moyens de communications ont des pannes[2].

Description

modifier

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].

Rôles

modifier

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.

Références

modifier
  1. ↑ Leslie Lamport, « Lower Bounds for Asynchronous Consensus »,
  2. ↑ Marshall Pease, « Reaching Agreement in the Presence of Faults », Journal of the Association for Computing Machinery, vol. 27, no 2,‎ (lire en ligne, consulté le )
  3. ↑ Leslie Lamport, « Time, Clocks and the Ordering of Events in a Distributed System », Communications of the ACM, vol. 21, no 7,‎ , p. 558–565 (DOI 10.1145/359545.359563, lire en ligne, consulté le )
  4. ↑ Fred Schneider, « Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial », ACM Computing Surveys, vol. 22,‎ , p. 299 (DOI 10.1145/98163.98167, lire en ligne)
  5. ↑ Leslie Lamport's history of the paper
  6. ↑ a et b Leslie Lamport, « The Part-Time Parliament », ACM Transactions on Computer Systems, vol. 16, no 2,‎ , p. 133–169 (DOI 10.1145/279227.279229, lire en ligne, consulté le )
  7. ↑ M. Fischer, « Impossibility of distributed consensus with one faulty process », Journal of the ACM, vol. 32, no 2,‎ , p. 374–382 (DOI 10.1145/3149.214121, lire en ligne)
  8. ↑ Leslie Lamport, Mike Massa « Cheap Paxos » () (lire en ligne)
    — « (ibid.) », dans Proceedings of the International Conference on Dependable Systems and Networks (DSN 2004)
  9. ↑ Leslie Lamport, « Fast Paxos »,
  10. ↑ Leslie Lamport, « Generalized Consensus and Paxos », Microsoft Research,
  11. ↑ Miguel Castro, « Practical Byzantine Fault Tolerance »(Archive.org • Wikiwix • Archive.is • Google • Que faire ?),
  12. ↑ Chandra–Toueg consensus algorithm

Liens externes

modifier
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Paxos_(informatique)&oldid=204680512 ».