Pierre Abbat
2011-05-15 05:14:31 UTC
I read the Pitch Black paper and I think I've figured out a solution. Instead
of trying to fit a circular keyspace in a graph that's spread over the
surface of the earth with some long-distance links, I think it would be
better to make the keyspace have more dimensions. Here's my proposal:
Break a key or location into four equal parts. These are coordinates of the
point on a four-dimensional torus. Distance is measured in 8-space by
embedding each torus dimension as a circle.
Every 1024 times a node adds something to its store, it performs this
calculation: First it adds all the keys in its store as vectors in 8-space,
then reduces that to a 4-dimensional point on the torus. Then it adds all its
neighbors' locations and again reduces it to a point on the torus. The result
is its new location. The location will be close to its neighbors; if the
surface containing locations is curved, more of the store will be on the
outside of the curve. Young nodes with few keys stored will be pulled rapidly
toward their neighbors; old nodes will remain stably located near their data.
Unlike the current method, where the product of distances rewards nodes for
having locations next to each other, in this system nodes next to each other
will be pulled apart, spreading more evenly over the keyspace.
The number of dimensions could be any divisor of 32 (the number of bytes in a
hash). More than that and the notion of averaging in a dimension becomes
problematic. I have a hunch that the optimal number of dimensions is 4, where
two represent the surface of the earth and the other two different social
classes in a region. Could someone who has a Freenet simulator run some tests
and see how well this method performs for various numbers of dimensions?
Pierre
of trying to fit a circular keyspace in a graph that's spread over the
surface of the earth with some long-distance links, I think it would be
better to make the keyspace have more dimensions. Here's my proposal:
Break a key or location into four equal parts. These are coordinates of the
point on a four-dimensional torus. Distance is measured in 8-space by
embedding each torus dimension as a circle.
Every 1024 times a node adds something to its store, it performs this
calculation: First it adds all the keys in its store as vectors in 8-space,
then reduces that to a 4-dimensional point on the torus. Then it adds all its
neighbors' locations and again reduces it to a point on the torus. The result
is its new location. The location will be close to its neighbors; if the
surface containing locations is curved, more of the store will be on the
outside of the curve. Young nodes with few keys stored will be pulled rapidly
toward their neighbors; old nodes will remain stably located near their data.
Unlike the current method, where the product of distances rewards nodes for
having locations next to each other, in this system nodes next to each other
will be pulled apart, spreading more evenly over the keyspace.
The number of dimensions could be any divisor of 32 (the number of bytes in a
hash). More than that and the notion of averaging in a dimension becomes
problematic. I have a hunch that the optimal number of dimensions is 4, where
two represent the surface of the earth and the other two different social
classes in a region. Could someone who has a Freenet simulator run some tests
and see how well this method performs for various numbers of dimensions?
Pierre
--
I believe in Yellow when I'm in Sweden and in Black when I'm in Wales.
I believe in Yellow when I'm in Sweden and in Black when I'm in Wales.