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'algorithme 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 :
Le premier objectif du stage est d'étudier et de comparer les versions existantes de l’algorithme de la boulangerie utilisant une numérotation bornée [3, 4, 5, 6].
Le deuxième objectif du stage est d’établir une version auto-stabilisante de l’algorithme de la boulangerie.
Auto-stabilisation est un concept de tolérance aux fautes en algorithmique répartie [2]. Un algorithme est auto-stabilisant s’il converge automatiquement vers un fonctionnement correct à partir de n’importe quel état. Extrait des notes de Leslie Lamport sur ces papiers: “Now self-stabilization is a regular subfield of distributed computing. I regard the resurrection of Dijkstra's brilliant work on self-stabilization to be one of my greatest contributions to computer science”.
Références :
[1] A New Solution of Dijkstra's Concurrent Programming Problem, L. Lamport, Communications of the ACM 17(8) 453-455 ,1974
[2] Self-stabilizing systems in spite of distributed control, E.W. Dijkstra, Commun. ACM 17(11) 643-644, 1974
[3] Bakery algorithms, by U. Uri Abraham, Proc. of the Concurrency, Specification and Programming Workshop, H.-D. Burkhard, L. Czaja and P. Starke eds., 7-40. 1993
[4] Bounding Lamport's Bakery Algorithm, by Prasad Jayanti, King Tan, Gregory Friedland and Amir Katz, Proceedings of the 28th Conference on Current Trends in Theory and Practice of Informatics Piestany: Theory and Practice of Informatics, LNCS 2234, Springer Verlag, 261-270, 2001
[5] Simple Mutual Exclusion Algorithms Based on Bounded Tickets on the Asynchronous Shared Memory Model, Masataka Takamura,Yoshihide Igarashi, Proceedings of the 8th Annual International Conference, LNCS 2387, 2002
[6] The Black-White Bakery Algorithm, G. Taubenfeld, Proceedings of the 18th international symposium on distributed computing, LNCS 3274, Springer Verlag, 56-70, 2004