مجله محاسبات موازی و توزیع شده

Nature is a great source of inspiration for scientists, because natural systems seem to be able to find the best way to solve a given problem by using simple and robust mechanisms. Studying complex natural systems, scientists usually find that simple local dynamics lead to sophisticated macroscopic structures and behaviour. It seems that some kind of local interaction rules naturally allow the system to auto-organize itself as an efficient and robust structure, which can easily solve different tasks. Examples of such complex systems are social networks, where a small set of basic interaction rules leads to a relatively robust and efficient communication structure. In this paper, we present PROSA, a semantic peer-to-peer (P2P) overlay network inspired by social dynamics. The way queries are forwarded and links among peers are established in PROSA resemble the way people ask other people for collaboration, help or information. Behaving as a social network of peers, PROSA naturally evolves to a small world, where all peers can be reached in a fast and efficient way. The underlying algorithm used for query forwarding, based only on local choices, is both reliable and effective: peers sharing similar resources are eventually connected with each other, allowing queries to be successfully answered in a really small amount of time. The resulting emergent structure can guarantee fast responses and good query recall.

In the last decades, sociologists have been focused on studying social networks in order to understand why the collaboration of several people with different behaviour could magically result in an organized community of people. This field is becoming even more interesting for physicists, because many structural similarities between social networks and discrete matter organization have been discovered. Studies performed by Newman, Albert, Barabasi [23], [24], [25], [45] and [2], and others underline the fact that almost all networks of cooperating elements, even if cooperation is based on really simple rules, naturally evolves to a small world. The existence of small worlds in social networks was empirically demonstrated by Milgram [22]. Through a famous experiment, he showed that two randomly chosen American people are connected by a very short chain of relationships. This result is at the same time surprising and astonishing: how it is possible that all of two hundred millions people are connected by just “six degrees of separation”? A first model of the small-world effect was proposed by Watts and Strogatz [44]: they supposed to add random links to an ordered mesh of nodes, and discovered that the average path length among nodes was dramatically lowered by the addition of just a few long-distance links. On the other hand, not only networks of people and collaborations, but also some artificial networks, such as the Internet or the World Wide Web (WWW), are small worlds. The most appreciable characteristic of a small world is that messages from one node of the network to any other one can be delivered in a few steps, thanks to long-distance links. Since one of the main issues of many peer-to-peer (P2P) overlay networks is that searching and retrieving documents is slow and inefficient, we propose a novel P2P overlay structure called PROSA (P2P Resource Organization by Social Acquaintances) [5] and [6], that tries to mimic the way social links among peers are established and evolve, in order to build an efficient and self-organizing P2P network for resource sharing. The paper is organized as follows. Section 2 is a brief overview of recent studies in the field of semantic-driven P2P networks; Section 3 explains the basic ideas PROSA is inspired by; in Section 4 we give a formal description of the algorithms involved; Section 5 describes the simulation framework used to test PROSA features; in Section 6 topological aspects of the network are discussed, aside with simulation results; Section 7 reports PROSA performance in resource retrieval; Section 8 reports some results about PROSA robustness and Section 9 summarizes obtained results.

Nature has inspired many improvements to human artefacts, actions, and behaviour. Actual peer-to-peer networks suffer many drawbacks, such as network overhead, inefficient or suboptimal routing protocols, and lack of semantics. In this paper we have described PROSA, a peer-to-peer architecture inspired by social networks, which naturally evolves to a small world by linking “similar” peers together. The proposed model is quite independent from the knowledge model used to represent resources, and the given formalization allows us to use different models by just redefining functions involved in query routing and relevance computing. Network management and organization is fully distributed and decentralized, leading to a robust and effective structure. Links among peers are established as a consequence of query forwarding and answering, using no more messages than those needed to route queries throughout the network and to collect answers. The resulting network has a really small average path length, a relevant clustering coefficient and an “almost-democratic” distribution of links, while links usage has a typical power-law shape. Resources can be efficiently searched and retrieved, using natural language and involving a small number of nodes obtaining high recall, especially for rare and uncommon documents. The overall quality of algorithms and routing techniques resembles a real social network, where messages flow in a fast and efficient way through convenient paths, chosen step-by-step by each peer involved using only local information.