agthorr at cs.uoregon.edu
Wed Mar 8 04:55:52 UTC 2006
On Tue, Mar 07, 2006 at 07:43:39PM -0800, 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? I mean,
> from each node's perspective, it might look a bit like
> a small world -- in Kademlia, for instance, my routing
> tables will center around my own ID space.
DHTs typically are small worlds.
The small-world characteristics are short path lengths (comparable to
a random graph) and high clustering (much more than a random graph).
DHTs certainly have short path lengths (that's the point). All the
DHTs I can think of also have high clustering. A node's neighbors are
likely to also be neighbors.
> But the network, as a whole, isn't small world, and isn't vulnerable
> to vertex-order attacks, right? Or am I missing something?
I believe you are thinking of power-law graphs (also called
"scale-free") which have a few very-high-degree peers that make juicy
targets. Power-law graphs frequently (but don't necessarily) exhibit
small-world characteristics. Almost everyone is connected to some of
the high-degree peers who are all connected together, so there is a
lot of clustering. The high degree peers also provide short-paths
everywhere. As a result, they're small worlds.
However, not all small-worlds are power-law graphs. In particular,
DHTs are not power-law graphs. There are not exceptionally high or
low degree peers.
Daniel Stutzbach Computer Science Ph.D Student
http://www.barsoom.org/~agthorr University of Oregon
More information about the P2p-hackers