Abstract FR:

Nous nous intéressons aux problèmes de décision, qui sont une généralisation de la notion de vote : N entités doivent se mettre d'accord sur un ou plusieurs valeurs communes. Ce type de problème est largement utilisé dans les systèmes répartis. Ce problème n'a pas de solution dans un système asynchrone ; nous développons ici une nouvelle approche en nous intéressant non pas au système, mais aux données. Nous montrons qu'il est possible d'écrire des protocoles qui résolvent ce type de problème lorsque les valeurs proposées par les processus satisfont certaines contraintes connues a priori. Cette classe de protocoles peut être définie par des propriétés simples, et permet des algorithmes génériques pour plusieurs problèmes d'accord. Tous les protocoles présentés sont sûrs : ils ne donnent jamais de résultat erroné. Nous présentons un algorithme à qualité de service modulable, qui montre un compromis entre la convergence et la communication nécessaire.