HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

The stable configuration in acyclic preference-based systems

Fabien Mathieu 1, 2 Gheorghe Postelnicu 3 Julien Reynier 4
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
4 TREC - Theory of networks and communications
DI-ENS - Département d'informatique - ENS Paris, Inria Paris-Rocquencourt
Abstract : Acyclic preferences recently appeared as an elegant way to model many distributed systems. An acyclic instance admits a unique stable configuration, which can reveal the performance of the system. In this paper, we give the statistical properties of the stable configuration for three classes of acyclic preferences: node-based preferences, distance-based preferences, and random acyclic systems. Using random overlay graphs, we prove using mean-field and fluid-limit techniques that these systems have an asymptotically continuous independent rank distribution for a proper scaling, and the analytical solution is compared to simulations. These results provide a theoretical ground for validating the performance of bandwidth-based or proximity-based unstructured systems.
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Fabien Mathieu Connect in order to contact the contributor
Submitted on : Thursday, September 4, 2008 - 2:32:41 PM
Last modification on : Thursday, March 17, 2022 - 10:08:29 AM
Long-term archiving on: : Thursday, June 3, 2010 - 8:33:04 PM


Files produced by the author(s)


  • HAL Id : inria-00318621, version 1
  • ARXIV : 0809.0833


Fabien Mathieu, Gheorghe Postelnicu, Julien Reynier. The stable configuration in acyclic preference-based systems. [Research Report] RR-6628, INRIA. 2008, pp.26. ⟨inria-00318621⟩



Record views


Files downloads