Unreliable Distributed Timing Scrutinizer to Converge toward Decision Conditions

Emmanuelle Anceaume (1, 2) , Eric Mourgaya (3) , Philippe Raïpin-Parvédy (3)

1 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
2 CIDER
3 ADEPT - Algorithms for Dynamic Dependable Systems

In this paper, we propose to extend the condition-based approach introduced and developed by Most'efaoui et al. in 2001 by characterizing Vn f , the set of all the possible input vectors containing the values proposed by n processes. The condition-based approach consists in identifying sets of input vectors for which the consensus is directly solvable (i.e., in one communication step) in a pure asynchronous model despite up to f crashes. We focus on all the other input vectors. Among them, we identify those that allow to solve the consensus problem in two communication steps still in a pure asynchronous model. For the other ones, we rely on a distributed oracle that enables the input vectors to converge toward a good patterned vector with probability one. We specify a protocol that benefits from this approach to solve the consensus problem very simply and efficiently.

Mots clés: Unreliable systems; convergence; consensus

Domaines: Informatique et théorie des jeux [cs.GT]

Emmanuelle Anceaume, Eric Mourgaya, Philippe Raïpin-Parvédy. Unreliable Distributed Timing Scrutinizer to Converge toward Decision Conditions. Studia Informatica Universalis, 2008, 6 (2), pp.23--50. ⟨hal-00916690⟩