Skip to Content.
Sympa Menu

bluesky - market-based data location (was Scalability)

bluesky AT lists.ibiblio.org

Subject: Global-Scale Distributed Storage Systems

List archive

Chronological Thread  
  • From: Wei Dai <weidai AT eskimo.com>
  • To: Global-Scale Distributed Storage Systems <bluesky AT franklin.oit.unc.edu>
  • Subject: market-based data location (was Scalability)
  • Date: Mon, 26 Feb 2001 05:49:19 -0800


On Sun, Feb 25, 2001 at 08:10:55PM -0800, hal AT finney.org wrote:
> I'd like to see discussion of technical solutions to the problems of
> finding data without swamping the network. It would be especially good
> if this could handle a search search, something that Freenet does not
> even try to tackle yet. Mojo handles searching using the same content
> trackers that store file locations.

Have you looked at OceanStore's distributed data location algorithm? It's
described as a variation on Plaxton et. al.'s randomized hierarchical
distributed data structure. I think it should handle scalability quite
well, but is weak against denial of service attacks (censorship).
Designing a data location algorithm that is both scalable and
censorship-resistant seems to be a fairly difficult problem.

In OceanStore's scheme, each data object is assigned a number of root
nodes responsible for tracking its locations. This assignment is based on
the closeness of salted hashes of the object and the IDs of the nodes,
which are also hashes. The attack is just to generate potential node IDs
until you obtain IDs that would be closest to the salted hashes of the
target object, and then start servers with those IDs. Those servers
become roots for the object, and you can just instruct them to respond to
all requests for it with a reply of "no known location."

I think the final solution for the data location problem will have to be
market-based, involving both payment and reputation schemes. Without a
payment system you can't prevent an attacker from simply overwhelming a
server with requests, and there is no incentive for people to contribute
resources into the system instead of just leaching from it. Without a
reputation scheme, attackers can introduce their own servers and supply
the system with bad data, either to censor some data or to cheat people
out of their money, and users will have no way of avoiding these corrupt
servers.

The idea I'm playing with (and have been discussing with Ted Anderson
before creating this list) is for each data location server to self
select, based on market conditions, some criteria for what data to track,
for example any data located in a radius of x from itself, and has a
(content-hash based) GUID inside a radius of y from it's own GUID. It
would then accept paid or unpaid advertisement from data storage servers,
and answer paid or unpaid queries for data location. It can also query
other data location servers to fill its own database. Besides tracking
data, it would also track other location servers whose ranges overlap with
its own, so that if it can't answer a query directly it will return a list
of other location servers (along with their tracking and pricing policies)
who might be able to or at least get you closer to such a server, and
attest to their reliability and comprehensiveness.

With this system you would see locations servers that are specialized for
different market niches. Some would be neighborhood trackers, with a small
network radius and a large GUID radius. Some would be global tracks, with
a large network radius and a small GUID radius. Some would be highly
priced and specialize in censored data. Some would acquire a reputation
for reliability and make money from long-term paid advertisements. Some
would have a low query price and make money from queries for popular data.
Some would only track other location servers and essentially provide a
reputation service. It would be really cool to watch this market
self-organize.

I think that almost certainly only some scheme that looks like this can
scale and be censorship-resistant. The hard part is to work out what
strategies the location servers, storage servers, and user agents should
use to avoid being cheated and to maximize profits or at least break even,
and to build the necessary support infrastructure, for example interface
standards and payment systems.




Archive powered by MHonArc 2.6.24.

Top of Page