Etude et amélioration de l'algorithme de la boulangerie (Bakery Algorithm) de Leslie Lamport

Thématique: algorithmique distribuée


Nom et adresse électronique de la directrice du stage : Colette Johnen (johnen@labri.fr)


Laboratoire, institution et université : LaBRI UMR 5800,  Université Bordeaux

Ville : Talence, France


Présentation générale du domaine :


Un système distribué est un ensemble d'entités autonomes et communicantes. Chaque entité (aussi appelé noeud, processus, processeur, machine, ...) a son propre code, ses propres objectifs, sa vitesse d'exécution, ... .


L'algorithme de la boulangerie [1] est un algorithme distribué d'exclusion mutuelle (au plus un processus est admis dans la section critique).  L'algorihme est basé sur un mécanisme de la vie quotidienne : entrant dans la boulangerie, chaque client reçoit un ticket portant un numéro, le client ayant le plus petit numéro sera servi en premier (il entrera en section critique en premier).


Cet algorithme est remarquable car il ne nécessite pas d'opérations de synchronisation de bas niveau sur les accès « mémoire », une opération de lecture d'une variable peut chevaucher l'écriture d'une valeur dans cette variable.


L'objectif de ce stage est d'étudier cet algorithme et ses diverses variantes.


Objectif du stage :

Références :