Skip to Content.
Sympa Menu

bluesky - Re: The Grapevine Project

bluesky AT lists.ibiblio.org

Subject: Global-Scale Distributed Storage Systems

List archive

Chronological Thread  
  • From: Oskar Sandberg <oskar AT freenetproject.org>
  • To: Global-Scale Distributed Storage Systems <bluesky AT franklin.oit.unc.edu>
  • Subject: Re: The Grapevine Project
  • Date: Sun, 9 Dec 2001 22:12:00 +0100


On Thu, Dec 06, 2001 at 01:32:54PM +1300, Stephen Blackheath wrote:
<>
> Grapevine and Freenet both work by the '6 degrees of separation' theory:
> If
> you have 100 neighbours, say, and the network has 1,000,000 nodes, then in
> an
> optimally connected network, you should be able to get to any point in 3
> hops.

I think the "6 degrees" theory has more to do with shortest pathlengths
in fixed random graphs than exponents - small world networks and all
that. There are proofs [1] to show that pretty much all random networks
have a logarithmic minimum pathlength between nodes, but that is rather
different from our situation of being able to control the graph
structure but wanting to be able to _find_ those paths.

Reaching 1,000,000 within 3 hops of 100 neighbors would imply starting
from the root of a balanced tree, but since you need to be able to start
at any of the nodes, you need more than one tree (in graph theory terms,
a spanning tree cannot be balanced at every node). The Plaxton model is
to have every node act as a part of K trees, and to have K sets of
neighbors as the children depending on whether it is reached on the 1st,
2nd ... Kth step. That gives

log(N) / p

steps for

log(N) * 2^p

neighbors at each node. I would be hard pressed to believe it is
possible to do better than that.

> Freenet is self-organizing, in that the connection of nodes dynamically
> changes. In practice, it doesn't organize all that well, and it can take
> tens of hops to retrieve a file. Grapevine has a more rigid structure,
> which
> sounds bad, but it gives near-optimal connectivity. It also gives better
> security, because it severely limits the number of neighbours you can
> discover, thus protecting against 'harvesting attacks'.

In my experience, a rigid structure is a nightmare. All the examples of
attempts to route within a rigid structure that I have seen have started
out as lovely models, but been forced into more and more elaborate
schemes in order to protect the integrity of the rigid structure - [2]
goes as far as to recommend rebuilding the entire graph structure once
every 24 hours.

<>
> 1. name lookup service: We want to map a name to a content-hash key (CHK).
>
> So, we hash that name and send it as a request. Because we require an
> authoritative answer to the question, we send the request to the most
> "trusted" nodes. There is an issue of file ownership, but to cut a long
> story short, it gets mapped to a CHK. How do we determine what nodes are
> "trusted"? This depends on the previously briefly described SAHP algorithm
> which achieves the following: If you have a "high" SAHP value, then this
> proves that you expended a large amount of CPU time to arrive at your
> location in the network. That is, it is unlikely that you chose your own
> "location" in the network. Nodes with high SAHP values will find it most
> difficult to collude, because it is extremely expensive to get a collection
> of them in the any target region of space.

It seems to me that a "pay for trust" model using a PoW system only
makes sense as long as you can definitely say that the cost invested in
the relationship is greater than what the party stands to gain by
breaking the trust. However, if you are using PoW based trust to verify
data, since the valitidy of the data is completely out of band, you have
no way of even beginning to calculate the value gained by betrayal,
making the whole thing somewhat fishy IMHO.

BTW, now that the the movie is almost out, how are we gonna know which
orc is you?

[1] http://www.arxiv.org/abs/cond-mat/0007235/
[2]
http://oceanstore.cs.berkeley.edu/publications/papers/pdf/tapestry_sigcomm_tr.pdf

--

Oskar Sandberg
oskar AT freenetproject.org




Archive powered by MHonArc 2.6.24.

Top of Page