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. 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 is an exception.
More information about the P2p-hackers