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
Reports

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

https://hal.inria.fr/inria-00318621
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

RR-6628.pdf
Files produced by the author(s)

Identifiers

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

Citation

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

Share

Metrics

Record views

184

Files downloads

256