[mnet-devel] notes on skip graphs

[Zooko]

I read a paper about a new emergent network design, and I put some notes on my web page:

Skip graphs 2003-09-14 [1] v1.0.0

Like Koorde [2], this is a new emergent network with novel properties, and like
Koorde the concept is simple enough to be sketched in a few sentences.

   skip lists

First, you ought to understand traditional skip lists. (If you already do, you
can skip (ha ha) this paragraph.) Take a normal old linked list, and add a
randomized "height" to each node. About half of the nodes have height 1, a
quarter of them have height 2, and in general about 2^-n of the nodes have
height n. Now make each node which is at least 2 tall have a link to the next
node which is at least 2 tall, in addition to having a link to the very next
node in the list. (You can see that by following those level-2 links, you can
"skip" about half of the nodes while searching the list.) Likewise, make sure
that each node which is at least l tall has a link to the next node which is at
least l tall, in addition to its other links. Now you have a skip list, which is
probabilistically about as efficient for searching and inserting as is a
balanced tree, while being pleasingly simple in concept.

   decentralized skip lists

Now this paper is about translating the skip list concept into a decentralized
data structure. Make each node in the list be a separate node (machine) in the
network. Now you have a decentralized data structure which is as efficient as a
DHT (e.g. log(n) hops per lookup), while having the novel property that the
nodes do not need to be evenly distributed throughout some space. (All current
DHTs of which I am aware require that the nodes be evenly distributed throughout
a certain space, and typically achieve this even distribution by using a hash
function to determine the node's placement in the space. Some of them such as
CAN -- Content Addressable Network -- have apparently tried with limited success
to ease this requirement.)

   robust decentralized skip lists -- skip graphs

But the structure that we just designed is not very robust -- any single node
that disappears partitions the network! So now add redundancy. The naive way to
add redundancy, to my way of thinking, is to add k extra successor links to each
node (as DHTs like Chord typically do). However, the designers of the skip graph
want each node to participate in more of the "higher level" linked lists -- they
don't want half of the nodes to be of height 1 and to participate solely in the
basic linked list. So in essence they just make k redundant skip lists starting
from the same basic linked list.

The way they actually build the redundant skip lists is pleasingly elegant, and
the paper has a concrete implementation with pseudocode, plus extensive
analysis.

   what I think about it

I haven't yet grokked this concept in its fullness. The freedom of placement of
the nodes is constrained only by the one-dimensionality of the space! In the
terms of Topology-Aware Routing [3], skip graphs offer topology-based nodeId
assignment. At the same time, skip graphs offer a high degree of free choice in
peer selection. The only constraints are probabilistic and system-wide -- there
are no hard constraints on any individual node, but the network of all of the
nodes has to fit the probabilistic distribution of a skip graph if the (proofs
of the) emergent properties are to hold. This combination of freedoms is
intriguing.

There is one major point in this paper that I don't understand: they say that
skip graphs require log(n) links per resource, which compares unfavorably with
the log(n) links per machine of DHTs, but I don't see why skip graphs couldn't
implement machine-based topology nor why DHTs couldn't implement resource-based
topology, so the issue seems separate to me.

[1] http://www.zooko.com/reading.html#notes_Skip_graphs
[2] http://www.zooko.com/reading.html#notes_Koorde
[3] http://www.zooko.com/reading.html#notes_TopologyAware_Routing



-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
mnet-devel mailing list
mnet-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mnet-devel