Combining the use of clustering and scale-free nature of user exchanges into a simple and efficient P2P system

Pierre Fraigniaud, Philippe Gauron and Matthieu Latapy

LNCS, proceedings of the 11-th international conference Euro-Par, 2005, Lisbonne, Portugal

It appeared recently that user interests in a P2P system possess clustering properties that may be used to reduce significantly the amount of traffic of flooding-based search strategies. It was also observed that they possess scale-free properties that may be used for the design of efficient routing-based search strategies. In this paper, we show that the combination of these two properties make it possible to design an efficient and simple fully decentralized search strategy. Further, simulations processed on real-world traces show that other unidentified properties hidden in actual queries make our protocol even more efficient, performing searches in logarithmic expected number of steps.