Cours de fiabilité logicielle



TD 5 : RAFT (partie 2/3)

Question de cours

Question 1 : Donnez une définition du problème de l’Élection.

Question 2 : Peut-on résoudre le Consensus si on sait résoudre l’Élection ? Peut-on résoudre l’Élection si on sait résoudre le Consensus ?

L’algorithme Raft

Se référer à l’abstract et l’introduction de l’article sur RAFT.

Partie 1 : Élection (base)

Question 3 : Décrire l’algorithme d’Élection dans Raft.

Question 4 : À quelles conditions cet algorithme fonctionne-t-il ? Est-ce que ces conditions vous paraissent réalistes ?

On considère les scénarios suivants avec 6 processus :

  1. la temporisation de 4 se termine vite, celle de 5 bien plus tard. 5 reçoit un message de 4 après la fin de sa temporisation.
  2. la temporisation de 4 et celle de 5 se termine quasi en même temps, et chacun reçoit 2 votes des autres processus.

Question 5 : Que se passera-t-il pour chacun d’entre eux ?

Question 6 : La terminaison de l’Élection est-elle toujours garantie même lorsque tous les serveurs sont fonctionnels ?

Question 7 : La correction de l’Élection est-elle toujours garantie ?

Partie 2 : Réplication de Journal

Se référer au résumé de l’algorithme en page 4.

Question 8 : Qu’est-ce qu’une machine à état (state machine) ?

Question 9 : Qu’est-ce qu’une requête dans ce contexte ? Quel est le rôle du processus Élu ? Comment en pratique pourrait-on s’assurer que les clients contactent bien l’élu ?

Se référer à la partie 5.3 de l’article.

Question 10 : Quels sont les paramètres et états possibles pour une entrée de journal ?

Question 11 : Donner un exemple d’exécution à 5 processus où les entrées (proposées) de journal sont différentes.

Question 12 : Par quel mécanisme une entrée de journal passe-t-elle de proposée à validée ?

Question 13 : Comment l’algorithme garantit-il que les entrées validées ?

  • à terme identiques sur tous les processus
  • ne sont jamais invalidées sur l’ÉLU

Partie 3 : Sûreté

On revient vers le mécanisme d’élection répétée.

Question 14 : Est-il possible d’optimiser ce mécanisme en temps ou espace ?

Question 15 : En termes de règne (term dans l’article), quelles sont les propriétés que doit satisfaire un candidat ? Est-il possible d’avoir un élu pour un règne plus petit que le règne maximum à un moment donné ?

Question 16 : En Section 5.4.1 de l’article, quelles sont les restrictions sur les processus qui peuvent être élus ?