[p2p-hackers] clustering
Michael Rogers
m.rogers at cs.ucl.ac.uk
Wed Mar 8 08:35:54 UTC 2006
Gary Jefferson wrote:
> Just a general question for the list: DHTs don't
> exhibit small-world characteristics, at least not in
> the overlay network view of things, right?
That depends on your definition of 'small world'. Most people take it to
mean short paths and high clustering, but as far as I know the Freenet
work uses a more specific definition due to Jon Kleinberg: a graph is a
small world if it can be embedded in a metric space such that the length
of the edges follows a power law distribution, where the magnitude of
the power law exponent is equal to the number of dimensions in the
metric space[1]. Kleinberg showed that greedy routing in such a graph is
efficient, but if the power law exponent has any other value then greedy
routing is inefficient[2,3]. However, it's also possible that the length
distribution doesn't follow a power law at all (eg Chord, where the
length distribution is exponential and greedy routing is efficient).
Most DHTs aren't small worlds in the sense used in the Freenet work;
Symphony[4] is an exception.
Cheers,
Michael
[1] http://www.cs.cornell.edu/home/kleinber/nips14.ps
[2] http://www.cs.cornell.edu/home/kleinber/nat00.pdf
[3] http://www.cs.cornell.edu/home/kleinber/swn.pdf
[4] http://www-db.stanford.edu/~bawa/Pub/symphony.pdf
More information about the P2p-hackers
mailing list