inria-00072062, version 1
Validity Conditions in Agreement Problemsand Time Complexity
Bernadette Charron-Bost aFabrice Le Fessant
1
N° RR-4526 (2002)
Résumé : We study the time complexity of different agreement problems in the synchrono- us model with crash failures, by varying their validity condition. We first introduce a continuous class of agreement problems, the k-TAg problems, which includes both the Uniform Consensus and Non-Blocking Atomic Commitment. We then exhibit a general early-deciding algorithm, that we instanciate to solve every problem of this class. The algorithm always achieves the previously established lower-bounds for early-deciding, showing that these lower-bounds are tight.
- a – Polytechnique - X
- 1 : SOR (INRIA Rocquencourt)
- INRIA
- Domaine : Informatique/Autre
- Mots-clés : DISTRIBUTED CONSENSUS / SYNCHRONOUS MODEL / NON-BLOCKING ATOMIC COMMITMENT / ERALY-DECIDING ALGORITHM / K-TAG / LOWER-BOUNDS / VALIDITY CONDITIONS / TIME COMPLEXITY
- Référence interne : RR-4526
- Commentaire : Projet SOR
- inria-00072062, version 1
- http://hal.inria.fr/inria-00072062
- oai:hal.inria.fr:inria-00072062
- Contributeur : Rapport De Recherche Inria
- Soumis le : Mardi 23 Mai 2006, 19:40:38
- Dernière modification le : Jeudi 29 Mars 2007, 10:50:18
Documents associés
Exporter