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 <egs@cs.cornell.edu>; 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 <egs@cs.cornell.edu>; Wed, 5 Dec 2001 21:06:55 -0500 (EST)
Subject: 615 PAPER #75
From: Walter Bell <wbell@CS.Cornell.EDU>
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.