Upper bounds for stabilization in acyclic preference-based systems

Fabien Mathieu 1, 2
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : Preference-based systems (p.b.s.) describe interactions between nodes of a system that can rank their neighbors. Previous work has shown that p.b.s. converge to a unique locally stable matching if an acyclicity property is verified. In the following we analyze acyclic p.b.s. with respect to the self-stabilization theory. We prove that the round complexity is bounded by n/2 for the adversarial daemon. The step complexity is equivalent to (n^2)/4 for the round robin daemon, and exponential for the general adversarial daemon.
Type de document :
Communication dans un congrès
SSS'07 - 9th international conference on Stabilization, Safety, and Security of Distributed Systems, 2007, Paris, France. Springer-Verlag, pp.372--382, 2007
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00668356
Contributeur : Fabien Mathieu <>
Soumis le : jeudi 9 février 2012 - 16:29:11
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : jeudi 10 mai 2012 - 02:50:43

Fichier

10.1.1.95.9032.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00668356, version 1

Collections

Citation

Fabien Mathieu. Upper bounds for stabilization in acyclic preference-based systems. SSS'07 - 9th international conference on Stabilization, Safety, and Security of Distributed Systems, 2007, Paris, France. Springer-Verlag, pp.372--382, 2007. 〈hal-00668356〉

Partager

Métriques

Consultations de la notice

238

Téléchargements de fichiers

125