[mnet-devel] Grid Of Trust -- pre-design

[Jim Dixon]

On 28 Nov 2003, Zooko O'Whielacronx wrote:

> My first question is: why start with a CAN-like DHT instead of a Chord-like DHT?

You imply that ring structures are a natural first choice. However,
this is an odd assumption.  In fact hypercubes have a long history.
People have been building hypercube-based computers for at least twenty
years and for a substantial part of that period hypercube machines have
been among the fastest in the world (Intel iPSC and Paragon XP, for
example).

> I don't grok CAN as deeply, and I don't like it as well, so this makes it
> harder for me to understand your idea.

The proposal is not CAN, it's hypercube.  CAN has a lot of distracting
non-hypercube features like realities.  CAN is also a torus in
D-dimensional space, whereas this is a simple hypercube.

Mind you, if you look more closely, this isn't a classic hypercube, in
which nodes communicate with and through their nearest neighbors.  In a
hypercube with D dimensions, a node not on the edge has 2*D neighbors, a
neighbor on either side in each dimension.  In this proposal, a node has
many more than that.  He allows x nodes per cell, with g cells along each
axis.  Any node visible along any axis is a neighbor, so a node has
(correcting a minor error in his formula):

  x*((g-1)*D + 1) - 1 neighbors

In a uniformly populated lattice, the number of nodes would be x * g^D
If x = 4, g = 16, D = 4, the population would be 2^20 or about a million
nodes.  If full connections were maintained, a node would have

  4*( 15*4 + 1) - 1 = 243 neighbors

In practice rather than having x neighbors per cell, a lattice like this
would probably maintain a list of all x nodes but prefer the closest in
terms of ping time (RTT).  This would reduce the number of active
neighbors to

  (g-1)*D

and add one hop to maximum message delivery times.  Our node would now
have

  3*4 = 12 neighbors

and messages would take a maximum of D + 1 = 5 hops.

In its natural form, a ring of any size is a very poor communications
architecture. Fingers are added to give reasonable performance.

Hypercubes have reasonable performance if communications pass through
next-cell neighbors and the number of dimensions D is significant.  (A
ring is a 1-dimensional hypercube; because D is so small, communications
are very slow.)  The GOT proposal uses axes like fingers.  All nodes have
neighbors in all cells along all axes, so cell-to-cell communications take
at most D hops, except where one or both parties to the communication are
just joining the network where an extra hop or two might be necessary.

As in Chord, information could be replicated along the search path and
among cell members.  Cell members would be randomly scattered over the
underlying network, the Internet, so the chance of simultaneous failure
of all the nodes in a cell would be low in a large network.  Because the
actual number of nodes/cell would vary if node IDs were randomly assigned,
there would have to be some facility for dealing with the occasional
empty cell.

Overall, performance seems likely to be better than that of Chord.

> Regards,
>
> Zooko
>
> >                                  Grid Of Trust
> >
> >    This isn't a design document.  It's more of a proposal for what could be
> >    to make sure all the attacks are really covered.
> >
> > Topology
> >
> >    Nodes are distributed randomly into cells of a hypercube with d
> >    dimensionals.  Each axis is broken down into g pieces such that the
> >    hypercube contains gd cells.

--
Jim Dixon  jdd at dixons.org   tel +44 117 982 0786  mobile +44 797 373 7881



-------------------------------------------------------
This SF.net email is sponsored by: SF.net Giveback Program.
Does SourceForge.net help you be more productive?  Does it
help you create better code?  SHARE THE LOVE, and help us help
YOU!  Click Here: http://sourceforge.net/donate/
_______________________________________________
mnet-devel mailing list
mnet-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mnet-devel