Cost-effective broadcast for fully decentralized peer-to-peer networks

Fully unstructured and decentralized peer-to-peer networks such as Gnutella are appealing for a variety of applications, among which file-sharing is the most prominent one. The decentralized nature of these systems provides a high degree of robustness and the ability to cope with a highly dynamic and transient network environment. However, the lack of centralized directory nodes makes the task of searching more expensive and difficult. In completely unstructured peer-to-peer networks, searching can only be realized via application-layer broadcast, where query messages are routed to every node in the network. Gnutella implements application-layer broadcast by using flooding as the underlying message routing mechanism. Flooding creates a large amount of traffic and can quickly exhaust the resources of nodes in a large network. In this paper, we explore Rumor mongering (also known as Gossip) as a more cost-effective and scalable alternative to flooding for implementing services such as searching in decentralized peer-to-peer networks. We further present a new variant of the Rumor mongering protocol, which exploits the power-law characteristics of typical peer-to-peer networks and achieves a significant further reduction in cost. (C) 2002 Elsevier Science B.V. All rights reserved