Acyclic Preference Systems in P2P NetworksReport as inadecuate

Acyclic Preference Systems in P2P Networks - Download this document for free, or read online. Document in PDF available to download.

1 GYROWEB - Dynamic graphs and the web graph Inria Paris-Rocquencourt 2 FT R&D - France Télécom Recherche & Développement 3 LIAFA - Laboratoire d-informatique Algorithmique : Fondements et Applications 4 LIENS - Laboratoire d-informatique de l-école normale supérieure

Abstract : In this work we study preference systems natural for the Peer-to-Peer paradigm. Most of them fall in three categories: global, symmetric and complementary. All these systems share an acyclicity property. As a consequence, they admit a stable or Pareto efficient configuration, where no participant can collaborate with better partners than their current ones. We analyze the representation of the such preference systems and show that any acyclic system can be represented with a symmetric mark matrix. This gives a method to merge acyclic preference systems and retain the acyclicity. We also consider such properties of the corresponding collaboration graph, as clustering coefficient and diameter. In particular, studying the example of preferences based on real latency measurements, we observe that its stable configuration is a small-world graph.

Author: Anh-Tuan Gai - Dmitry Lebedev - Fabien Mathieu - Fabien De Montgolfier - Julien Reynier - Laurent Viennot -



Related documents