[RC5] Tree search algorithms and the next d.net

Greg Hewgill greg at hewgill.com
Mon Apr 19 23:28:35 EDT 1999

On Mon, Apr 19, 1999 at 01:10:34PM -0700, Adam Zilinskas wrote:
> Hmmm this makes me think of a different kind of D.net.

The OGR search is indeed a tree search. It is a very broad tree compared to its
depth - for an N-mark ruler it is N levels deep, but the number of leaves under
a given node can easily exceed 100 for N between 20 and 30.

Because of this breadth, it becomes impractical from a bandwidth standpoint for
clients to 'return' subtrees to an upstream server. The way the d.net OGR
server is structured is the server is responsible for generating the full tree
out to about depth 5 or so. Then the clients connect to the proxy network,
obtaining subtrees of depth about N-5 (the subtrees rooted at the leaves of the
master tree). These subtrees can each be searched completely in a resonable
amount of time (roughly equivalent to an RC5 block).

>  Now what keeps anyone from submitting their problem
>  to a hub? As long as the problem was deemed "nice and proper" 
>  for the system to perform, nothing should stop it. I think then
>  we call can benefit from each other's spare CPU cycles. 

Distributed.net has certainly put some thought into this. There are a number of
issues that need to be considered:

1. There must be a general enough way of specifying a problem that work units
   can flow through the network in a sensible way.

2. There needs to be a way of distributing the "cores" (the parts of the
   program that actually do the work) so that participants can be assured that
   the code is coming from a trusted source.

3. Most problems will need some kind of master server(s) with sufficient
   bandwidth to handle all the requests and responses that it will need to

4. The problem submitter will need some way to trust the results coming back
   from the network. This is necessary to protect against some or all of the
   network's integrity being compromised in some way.

The first three items are relatively easy to solve. Public-key digital
signatures can provide participants with the required level of confidence that
the code they are running comes from a trusted source (and therefore presumably
does not contain a trojan or virus). With code distribution, a suitably general
network infrastructure, and a good place for the master server(s), the only
remaining issue is results verification.

Results verification is a tricky issue. There are various ways this can be
done, but it mostly boils down to redoing some or all of the work. For example,
GIMPS (http://www.mersenne.org/prime.htm) performs full double checking of
all results, though double checking lags a couple of years behind first-
time checking. Today distributed.net does effectively the same thing - if we
were to reach the very end of the keyspace and the key was not found, we
would have to start over (whether we would actually do this for RC5-64 would
remain to be seen :). But it could happen for a future DES contest, with the
speed of d.net approximately doubling every six months.

Greg Hewgill
distributed.net Coding Team

To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list