Consesus Protocol

Présentation

Sujet : Consesus Protocol

Enseignants : D. Donsez, GP. Bonneau

Auteur : Rama CODAZZI

Introduction

Le problème du consensus est peut-être le problème majeur en application répartie et possède un intérêt certain, autant sur le plan pratique que théorique.

Le problème du consensus peut être rapidement définit, de manière informelle, de la façon suivante : «Soit un ensemble de processus, chacun proposant une valeur, trouver un protocole réparti afin de mettre tous les processus d’accord sur une des valeurs proposées initialement».

L’intérêt d’un tel protocole vient du fait que, si nous étions capable de résoudre le problème du consensus, nous serions alors capable d’implémenter des services tolérants aux fautes. En pratique pour mettre en place un système tolérant aux fautes, il suffit de répartir le calcul sur plusieurs ordinateurs.

Ainsi, si l’un d’entre eux vient à tomber en panne, le système continuera à marcher de manière transparente, les autres ordinateurs continuant à fournir le service. La principale difficulté d’un tel schéma, est qu’il est nécessaire de s’assurer de la cohérence du service, et pour cela tous les ordinateurs doivent effectuer les différents calculs dans le même ordre.

Propriétés du Consensus

Propriétés des Consensus

• Accord : la valeur décidée est la même pour tous les processus corrects

• Intégrité : tout processus décide au plus une fois (sa décision est définitive)

• Validité : la valeur décidée est l’une des valeurs proposées

• Terminaison : tout processus correct décide au bout d’un temps fini

Type de défaillance d'un processus

• Arrêt (crash failure ou panne franche) : le processus fonctionne correctement jusqu’à un point où il cesse définitivement d’agir.

• Omission
  • omission en émission : le processus omet certaines émissions qu’il aurait dû faire, ou cesse définitivement.
  • omission en réception : le processus ignore certains messages en réception, ou cesse définitivement.

• Arbitraire (byzantine failure) : le processus ment (par omission ou par contenu arbitraire des messages envoyés)

Mise en place de l'Algorithme paxos

Les hypothèses

• Communication
  • Asynchrone
  • Pas d’altération de messages
  • Possibilité de pertes
• Processus
  • Nombre fixe
  • Fautes franches avec possibilité de reprise (crash-recovery). Chaque processus possède un état persistant

Principe de algorithme Paxos

Repose sur un leader (utilisation d’un détecteur Ω)

• Le leader démarre un nouveau “ballot” (i.e.,ronde, vue, scrutin)
• Cherche à joindre une majorité d’agents
  • Les agents rejoigne toujours les “ballots” les plus récents (ignore les “ballots” anciens)
  • Deux phases :
    • Collecter les résultats des scrutins (ballot) précédents de la part d’une majorité d’agent
    • Puis proposer une nouvelle valeur, et obtenir une majorité pour l'approuver
• L’algorithme s’arrête si il existe un leader unique pendant les 2 tours d’échanges avec une majorité de d’agents

un balot est de la forme : Paire <num, process_id>

Le leader courant p choisit localement un numéro unique croissant : –Si le dernier ballot connu est <n, q> alors p choisit <n+1, p>

Exemple d’exécution

Il y a 3 phases lors de l’exécution de l’algorithme :

• Phase 1 : Préparation (Prepare)
  • Objectif : demander à joindre le tour (ballot) courant et collecter les informations des décisions passées

• Phase 2 : Acceptation
  • Le leader reçoit une majorité de ACK avec et renvoie un accept à tous
  • les autres process reçoivent le accept et le renvoie à tous

• Phase 3 : Décision

Remarques :

• Il peut y avoir plusieurs leader concurrents
• Les numéros de ballot permettent de distinguer les valeurs proposées par les différents leader

Fig. 1 : Exemple d’exécution avec 1 leader

Fig. 1 : Exemple d’exécution avec un client

Lien avec Zookeeper

Is Zab just a special implementation of Paxos? No, Zab is a different protocol than Paxos, although it shares with it some key aspects, as for example: A leader proposes values to the followers Leaders wait for acknowledgements from a quorum of followers before considering a proposal committed (learned) Proposals include epoch numbers, which are similar to ballot numbers in Paxos The main conceptual difference between Zab and Paxos is that it is primarily designed for primary-backup systems, like Zookeeper, rather than for state machine replication.

Un exemple d’implémentation

tuto zookeeper

Références

• https://fr.wikipedia.org/wiki/Paxos_(informatique)
• https://cwiki.apache.org/confluence/display/ZOOKEEPER/Zab+vs.+Paxos
• https://fr.wikipedia.org/wiki/Consensus_(informatique)
• http://www.tcs.hut.fi/Studies/T-79.5001/reports/2012-deSouzaMedeiros.pdf
• https://www-master.ufr-info-p6.jussieu.fr/2012/spip.php?action=acceder_document&arg=209&cle=c9f1b363ce1c738d7ca56551f12a02e50a01f020&file=pdf%2FConsensus-Paxos-ARA.pdf