Labo 3 - Synchroniseur tolérant aux pannes

Informations Générales

Notez enfin que l’objectif étant pour vous d’apprendre, vous serez toujours légitimes et bienvenu.e.s à nous poser des questions : sur la théorie, sur vos idées, sur vos blocages. Si vous vous sentez perdu.e.s ou coincé.e.s, c’est qu’il faut nous demander.

Le fil rouge du semestre

Rappelez-vous le fil rouge du semestre. Au labo 2, vous avez élu un leader dans un monde où les pannes sont possibles. Ce labo est la troisième étape : utiliser le leader pour synchroniser les processus. Au labo 4, cette synchronisation servira à atteindre le consensus.

Ce labo s’appuie sur les deux précédents, mais n’en dépend pas. Votre couche utilise l’élection du labo 2, et peut utiliser la diffusion fiable du labo 1. Le repo qu’on vous remet contient les nôtres, et c’est sur elles que votre rendu est évalué ; un labo 1 ou 2 raté ne vous coûte rien ici. Vous pouvez aussi les remplacer par les vôtres, telles quelles ou améliorées, mais cela ne rapporte aucun point.


Les suppositions


Le synchroniseur

Vous avez vu en cours ce qu’est un algorithme synchrone : les processus avancent par battements. Dans chaque battement, un processus peut envoyer au plus un message à chaque autre processus, éventuellement un message différent à chacun, éventuellement aucun ; il reçoit ceux qui lui ont été envoyés dans ce battement, et s’en sert au battement suivant.

Vous implémenterez un synchroniseur : une couche qui fait avancer les battements 0, 1, 2, … pour la couche du dessus. Au début de chaque battement k, votre couche délivre à la couche du dessus les messages envoyés pour le battement k − 1, et envoie ceux qu’elle lui retourne pour le battement k.

Les synchroniseurs alpha et beta vus en cours ne tolèrent aucune panne : même une panne bloque les battements pour toujours. Le vôtre doit continuer d’avancer malgré les pannes. Vous verrez vite que, par conséquent, certains messages, au début, risquent nécessairement de ne pas être reçus dans le bon battement ; ils doivent alors être ignorés et sont perdus. C’est le prix à payer de la tolérance aux pannes.

Un battement vu du processus Q : les messages reçus pendant le battement k − 1 lui sont délivrés au début de k ; un message envoyé pour k − 1 qui arrive pendant k n'est jamais délivré.

Votre couche doit garantir les propriétés suivantes :

Notez que parce que la Synchronie est “un jour”, des messages peuvent être perdus avant un certain battement, notamment pendant que le réseau est lent ou que l’élection ne s’est pas encore stabilisée. C’est seulement une fois le réseau et l’élection stabilisées qu’aucun message ne doit plus l’être.


Contraintes sur votre solution

Les propriétés ci-dessus disent ce qu’est un synchroniseur correct. Elles ne suffisent pas pour que votre solution soit acceptée ; nous exigeons en plus les contraintes suivantes.

  1. Votre solution doit être telle que c’est un élu qui a la responsabilité de décider quand passer au battement suivant.
  2. Sur un réseau calme, avec ou sans pannes, la durée des battements cesse de croître.

Enfin, la durée initiale d’un battement, comme celle de tout délai de suspicion de panne, ne doit pas dépasser 400 unités de temps.

Pour votre information, un ordre de grandeur : sur un réseau calme et rapide, un message met une vingtaine d’unités de temps à arriver. D’autres réseaux peuvent être plus lents, ou connaitre des pics de délai. La borne sur la durée de transit reste, quoi qu’il arrive, inconnue.

Notez aussi qu’un processus ne remet pas tous ses messages au réseau au même instant : ils partent l’un après l’autre, et écrire à tous les autres peut prendre jusqu’à une centaine d’unités de temps.

Un indice : un message peut arriver après la fin du battement auquel il était destiné. Il n’est alors pas délivré, mais son arrivée retardée est une information de valeur.


L’interface avec l’outillage

L’outillage est celui des labos 1 et 2 : votre programme est le comportement d’un processus, il lit ses événements sur stdin et écrit les siens sur stdout, et cuelight simule le réseau entre les processus.

Si vous utilisez notre squelette, vous n’aurez que les points suivants à implémenter :

C’est par ces appels que nous apprenons quels battements vous traversez, et ce que vous délivrez à chacun.

Les interfaces de votre synchroniseur : au-dessus, la couche applicative ; en dessous, l'élection, la diffusion fiable et le nœud cuelight, avec les fonctions appelées dans chaque sens.


Une contrainte technique

Elle est la même qu’aux labos 1 et 2, et pour la même raison : au labo suivant, nous pourrons remplacer cette couche par notre propre implémentation.

  1. Votre nœud doit être une fonction pure des événements. Pas d’horloge système, pas de threads, pas d’aléatoire non initialisé. C’est ce qui rend une exécution rejouable, et c’est vérifié avant tout le reste : si votre code ne se rejoue pas à l’identique, rien d’autre n’est évalué.
  2. Aucune opération n’est autorisée à bloquer en attendant une réponse. Votre processus est un gestionnaire d’événements mono-thread, et le temps logique n’avance qu’une fois que l’événement est traité. Si une de vos fonctions bloque, alors le temps arrête d’avancer.

Concrètement : attendre la fin d’un battement ne veut pas dire bloquer. Cela veut dire armer un minuteur, retourner, et décider de la suite lorsqu’il se déclenche ou lorsqu’un message arrive.

Évaluation

Nous vous fournissons le vérificateur lab3-check, que vous construisez vous-même et qui exécute tous les tests fournis avec le code. Ces tests sont des scénarios décrivant une séquence de pannes, de ralentissements et de changements d’aptitude, donc d’élu. Leur exécution dépend d’une graine (seed) : pour chaque graine, les pannes et les délais sont différents. lab3-check exécute les 200 premières graines de chacun ; nous en exécuterons d’autres lors de l’évaluation de votre rendu.

Référez-vous au README de votre repo pour plus de détails sur la construction et l’exécution de lab3-check.

Votre rendu sera évalué sur ces tests, sur la relecture de votre code pour la première contrainte, ainsi que sur un quiz individuel juste après le rendu. L’objectif sera de vérifier que vous possédez les choix architecturaux, logiques et algorithmiques de votre solution, et que vous avez compris leurs enjeux. Le quiz sera donné sur Opendidac, d’une durée de 30 minutes max et sans accès à votre code.

Vous ajouterez à votre README une section décrivant votre utilisation de l’IA : ce qu’elle a fait, quelles responsabilités vous avez gardées et lesquelles vous lui avez déléguées, etc. Elle est demandée par souci de transparence, et ne sera pas un critère d’évaluation.

Votre note finale sera égale à min(labo, quiz + 1.5), où labo et quiz sont votre note sur 6 au labo et au quiz, respectivement.