| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Upper bounds for stabilization in acyclic preference-based systems
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.
Cited literature [12 references]
https://hal.inria.fr/hal-00668356
Contributor : Fabien Mathieu <>
Submitted on : Thursday, February 9, 2012 - 4:29:11 PM
Last modification on : Saturday, March 28, 2020 - 2:09:45 AM
Document(s) archivé(s) le : Thursday, May 10, 2012 - 2:50:43 AM
Contributor : Fabien Mathieu <>
Submitted on : Thursday, February 9, 2012 - 4:29:11 PM
Last modification on : Saturday, March 28, 2020 - 2:09:45 AM
Document(s) archivé(s) le : Thursday, May 10, 2012 - 2:50:43 AM
File
10.1.1.95.9032.pdf
Publisher files allowed on an open archive