[mnet-devel] Grid Of Trust -- I'm back

[Some Guy]

 --- Jim Dixon <jdd at dixons.org> wrote: 
> On 28 Nov 2003, Zooko O'Whielacronx wrote:

Hi, guys I'm back now, thanks for discussing my idea.

> > 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).

Ok, so Jim likes hypercubes and Zooko likes rings.  I think you could design a sloppy chord like
system with similar techniques.  You'd have to make sure though that connections are established
only to other nodes in certain ranges of keyspace.  The width of these ranges would be configuared
down as you the network grew.

There was a more complicated idea from which this design grew.  Let's see what you guys think of
it.  I was thinking periodically to reorder on dimension at a time say once a week.  So for a week
you'd have you X and an X' based on a different salt.  To meet you new neihbors you'd have a bunch
of first-order neighbors who would have had a long term first order relationship with them.  The
idea was to keep advesarial nodes stired around.

The cost is of coarse that all important data would have to be transfered one hop per week.

New nodes might only get connected to neihbors in their own cell and slowly be able to route in
more dimensions as those are mixed.  This would force an adversary not just to boot a node to get
IPs, but actually run a productive node for a few weeks.

The system would need some kind of way of switching up g and D as it grew, switching up the salts
seems like it would fit in with that. 

Like? Don't like?

> > 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.

CAN makes that trade-off between neighbor count and speed where no P2P app can go.  That million
node network, if it where CAN routing, would average 8*4= 32 hops to route.  

> 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

Right, there's no reason to be stupid about it: if you've got x choices of where to route pick the
"best".  That might mean lowest ping for high priority messages, or lowest fractional load.  Much
of the time you can route in multiple dimensions giving you way more choices than x.  The average
would be about D*x/2.


__________________________________________________________________

Gesendet von Yahoo! Mail - http://mail.yahoo.de
Logos und Klingeltöne fürs Handy bei http://sms.yahoo.de


-------------------------------------------------------
This SF.net email is sponsored by: IBM Linux Tutorials.
Become an expert in LINUX or just sharpen your skills.  Sign up for IBM's
Free Linux Tutorials.  Learn everything from the bash shell to sys admin.
Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click
_______________________________________________
mnet-devel mailing list
mnet-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mnet-devel