Abstract
Peer-to-peer (P2P) document retrieval systems often face a trade-off between the rigid efficiency of Distributed Hash Tables (DHTs) and the high bandwidth consumption of unstructured flooding. This paper presents PROSA (P2P Resource Organisation by Social Acquaintances), a self-organizing system that routes queries based on semantic relevance and social-like relationships. By evolving links from basic acquaintances to deep semantic connections, PROSA achieves high search success rates and small-world efficiency without centralized indexing.
Introduction
In the mid-2000s, the P2P landscape was divided between structured DHTs (e.g., Chord, Pastry) and unstructured networks (e.g., Gnutella). While DHTs offer fast lookups, they struggle with complex keyword-based searching and node volatility. Unstructured systems allow flexible queries but typically rely on "flooding," which is inefficient. PROSA addresses this by modeling the network as a directed graph where links represent "social acquaintances," allowing nodes to find rare documents by leveraging local knowledge of their neighbors' expertise.
System Architecture
PROSA models network connections through a hierarchy of links that evolve over time:
- Acquaintance-Link (AL): A basic connection established when a node joins the network.
- Temporary Semantic-Link (TSL): A connection based on hints from previous successful queries.
- Full Semantic-Link (FSL): A strong bond established when a peer has verified the specific content hosted by another node.
When a new node (peer s) joins the network, it is initialized with a set of random parent links, as detailed in the JOIN algorithm below.
As nodes interact, they perform local routing decisions. Instead of flooding, a node forwards queries to neighbors most likely to possess relevant documents. If a node has partial matches, it may initiate a limited "semantic flood" to neighbors passing a relevance threshold.
Evaluation Methodology
The system was evaluated using an event-driven Python simulator. The knowledge base consisted of 1,490 scientific articles categorized into two domains: Mathematics (740 articles) and Philosophy (750 articles). Documents were represented using a Vector Space Model (VSM) with the top 100 TF-IDF (Term Frequency-Inverse Document Frequency) weights characterizing the content.
Performance Evaluation
PROSA was compared against standard Flooding and Random Walk strategies across networks ranging from 200 to 800 nodes. Key metrics included the success rate of queries and the volume of documents retrieved.
Key Results
- Success Rate: PROSA achieved a success rate between 84% and 92%, nearly matching the optimal but resource-intensive Flooding strategy (~94%) and significantly outperforming Random Walks.
- Search Efficiency: PROSA maintained an average query depth of approximately 3 levels. In contrast, Flooding and Random Walks required depths of 30 to 600 levels to achieve comparable results.
- Small-World Emergence: The network naturally evolved into a "small-world" structure characterized by high clustering (similar nodes grouping together) and short path lengths.
Conclusion
PROSA demonstrates that local routing decisions based on semantic similarity can lead to global efficiency in P2P networks. By mimicking human social learning—starting with random acquaintances and building a mental map of experts—the system excels at retrieving rare documents with minimal overhead. Future work will explore the scalability of PROSA in million-node environments and its performance across more diverse topic distributions.
Summary updated