Observer des algorithmes autostabilisants Vers une évaluation du co?t

摘要

Cet article traite du co?t de l'implémentation de la tolérance aux fautes dans les systèmes distribués. Pour ce faire, nous utilisons la notion d'observateur probabiliste local introduit dans (Beauquier et al., 2005). Cette notion a été développée à partir d'un algorithme autostabilisant qui calcule la taille d'un anneau anonyme. Nous évaluons le co?t de l'observation en calculant la complexité de cet algorithme. De plus, nous suggérons une nouvelle méthode ? Peu co?teuse ? Permettant d'observer des algorithmes autostabilisants.%This paper deals with the cost of implementing fault tolerance in distributed networks. For this purpose, we use the notion of local probabilistic observer introduced in (Beauquier et al., 2005). It has been studied on a synchronous self-stabilizing algorithm whose goal was to compute the size of an anonymous ring. In this paper, we evaluate the cost of the observation, by computing the complexity of this algorithm. Moreover, we suggest a way to observe classical self-stabilizing algorithms for cheap.