Paxos (informatique)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur les redirections « Paxos » redirige ici. Pour les autres significations, voir Paxos (homonymie).

Paxos est une famille de protocole pour résoudre le consensus dans un réseau de nœuds faillibles. Consensus est le processus permettant de parvenir à une décision sur un résultat pour plusieurs nœuds[1]. Ce problème devient difficile quand les nœuds ou leurs moyen de communications ont des pannes[2].

Les protocoles de consensus sont les bases de l'approche de la machine a état à l'informatique distribué, 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égislative 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 demande 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 sont en panne[12].

Rôles[modifier | modifier le code]

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 au systèmes distribué, 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 au panne. Les Acceptors sont regroupés en groupe nommés Quorums. Chaque message envoyés à 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 agît 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é 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 uniquement 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é dans ce cas.

Références[modifier | modifier le code]

  1. {{lien web es | nom = Lamport | prénom = Leslie | année = 2004 | titre = Lower Bounds for Asynchronous Consensus | url = http://research.microsoft.com/users/lamport/pubs/pubs.html#lower-bound }}
  2. Marshall Pease, « Reaching Agreement in the Presence of Faults », Journal of the Association for Computing Machinery, vol. 27, no 2,‎ avril 1980 (lire en ligne)
  3. Leslie Lamport, « Time, Clocks and the Ordering of Events in a Distributed System », Communications of the ACM, vol. 21, no 7,‎ juillet 1978, p. 558–565 (DOI 10.1145/359545.359563, lire en ligne)
  4. Fred Schneider, « Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial », ACM Computing Surveys, vol. 22,‎ 1990, 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,‎ mai 1998, p. 133–169 (DOI 10.1145/279227.279229, lire en ligne)
  7. M. Fischer, « Impossibility of distributed consensus with one faulty process », Journal of the ACM, vol. 32, no 2,‎ avril 1985, p. 374–382 (DOI 10.1145/3149.214121, lire en ligne)
  8. Lamport, Leslie; Mike Massa (2004). « Cheap Paxos » Proceedings of the International Conference on Dependable Systems and Networks (DSN 2004). 
  9. {{lien web es | nom = Lamport | prénom = Leslie | année = 2005 | titre = Fast Paxos | url = http://research.microsoft.com/users/lamport/pubs/pubs.html#fast-paxos }}
  10. {{article es | nom = Lamport | prénom = Leslie | année = 2005 | titre = Generalized Consensus and Paxos | url = http://research.microsoft.com/users/lamport/pubs/pubs.html#generalized }}
  11. {{lien brisé es | nom = Castro | prénom = Miguel | année = 2001 | titre = Practical Byzantine Fault Tolerance | url = http://citeseer.ist.psu.edu/castro01practical.html }}
  12. Chandra–Toueg consensus algorithm

Liens externes[modifier | modifier le code]