From wbell@CS.Cornell.EDU Wed Dec 5 21:06:57 2001 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fB626u606433 for ; Wed, 5 Dec 2001 21:06:57 -0500 (EST) Received: from [192.168.1.100] (syr-66-24-16-64.twcny.rr.com [66.24.16.64]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id VAA00819 for ; Wed, 5 Dec 2001 21:06:55 -0500 (EST) Subject: 615 PAPER #75 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.99.1+cvs.2001.11.07.16.47 (Preview Release) Date: 05 Dec 2001 21:06:34 -0500 Message-Id: <1007604417.1388.2.camel@brute> Mime-Version: 1.0 75) Peer to Peer and the Small World Phenomenon Here we see an introspection into the stability and scalability of self-organizing networks, which invokes some well-known psychology literature to make a very strong point. This paper examinies the scalability and fault-tolerance of the gnutella and freenet networks. It points out that although the average number of connections for a user is 3, the average number of hops between hosts is usually much smaller than the log_3 N. This works because a few nodes with more than 3 connections can quickly lower the average hop length of a graph by becoming short-cuts for other nodes in the graph. The paper makes the assertion that this effect is likely to be seen in the world because of the inherent randomness and non-regularity that exists in the host distribution of networks. The discussion continues to discuss the scalability and fault-tolerance of freenet and gnutella. Freenet has good scalability in that searches only take a logarithmic number of hops, and has high tolerance to random failures, but low tolerance to targeted attacks. In freenet, certain nodes play more important roles than others, and if those important nodes are attacked, the stability of the network suffers. Gnutella seems to have the opposite properties of freenet; while searches can potentially be unbounded, the network is very well suited to handling both attacks and failures, since each node is identical to all others.