Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Fabien Mathieu Connect in order to contact the contributor
Submitted on : Thursday, February 9, 2012 - 4:29:11 PM
Last modification on : Friday, January 21, 2022 - 3:13:59 AM
Long-term archiving on: : Thursday, May 10, 2012 - 2:50:43 AM

Publisher files allowed on an open archive


  • HAL Id : hal-00668356, version 1



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. pp.372--382. ⟨hal-00668356⟩



Record views


Files downloads