Charron
Le Jeudi 1er Mars 2001 à 14h30
au LRI, Salle 101
(LIX)
Le consensus uniforme est plus difficile que le consensus
Résumé/Abstract :
Dans ce travail, nous comparons les problèmes de consensus et de
consensus uniforme dans les systèmes synchrones. Contrairement
au consensus, le consensus uniforme n'est pas résoluble en
présence de défaillances byzantines. Ce résultat
est encore vrai pour des défaillances de type omission si une
majorité de processus sont susceptibles d'etre défaillants.
Pour des défaillances byzantines ou de type omission, le consensus
uniforme est donc plus difficile que le consensus en terme de
résolubilité. Pour le modèle de défaillance
de type ``crash'' (arrêt définitif prématuré),
le consensus et le consensus uniforme sont tous deux résolubles quel
que soit le nombre des processus défaillants. Nous évaluons
alors la complexité en temps d'un algorithme de consensus ou de
consensus uniforme par le nombre de rounds nécessaires pour que les
processus décident. Nous montrons que, si l'accord uniforme est
exigé, un round supplémentaire est nécessaire pour
décider. Pour des défaillances de type crash, le consensus
uniforme est donc là encore plus difficile que le consensus.
Ce résultat constitue un nouveau résultat de borne
inférieure pour le modèle synchrone. Enfin, nous construisons
un algorithme de consensus uniforme réalisant cette borne
inférieure.
Travail en collaboration avec André Schiper (EPFL).