[rc5] distributed computing vs applications of distributed computing

Thompson, Christopher CThompson at suncor.com
Thu Oct 2 08:51:55 EDT 1997


>Date: Wed, 1 Oct 97 13:16:22 PDT
>From: mikes at gammalink.com (Mike Spann)
>Subject: [rc5] distributed computing vs applications of distributed computing
>
>gambling that the key will be found in the first pass.  While it is possible 
>to go back and 'fill in the holes' as numerous people have stated, unless 
>care has been taken to make this process efficient, it is highly likely 
>that there will be a whole bunch of idle clients when the master key server 
>is forced to issue keys one by one to the proxies, who then issue them to 
>the clients.  Remember, it is going to have to go through 2^28 blocks, 
>one at a time, to see which have been completed and which have not.  2^28 is 
>a rather big number.  A simple bit vector where each block is represented
[cut]
>This is a scary thought.  Once all 2^28 blocks have been scan'ed the second 
>time, the third iteration will begin, and the fourth, and ... until the 
>winning block is found or we realize that the key was missed. 

2^28 is only just over a quarter of a billion.  Not a particularly big
number.

When the keyservers are about to reissue the blocks, all they have to do
is _ONE_ Order(N) search through the keyspace and build an array of all
the outstanding blocks.  Then this becomes the new database of keys.
They could then issue the keys as fast as they currently do.

If we don't find it on the first pass of outstanding key blocks, we
build another array (O(N)) of the outstanding keys based on the current
array, and so on.

Assuming no false negatives, the odds that it would take more than two
passes through the outstanding key blocks are pretty negligible.  If we
do have false negatives to contend with, one of the other groups will
probably find the correct key block.

>We have seen a note by the project coordinator who says they have picked
>the next project.  I think this is a good thing.  We have seen notes by 
>people who say that the 64 bit key is the same as the 56 bit key, just a 
>bit bigger.  I think those people simply do not understand the magnitude 
>of scale of trying to expand a project of this nature.  Based solely on 
>what I have observed as an outsider, the current bovine architecture is 
>stretched past its breaking point.  To embark on the 64 bit key based on 
>the stated assumption that more and faster machines will join the project, 
>without understanding that more and faster machines would just break the 
>underlying infrastructure is not very wise.  It is for that reason, and

I disagree.  You just distribute the key servers so that each server is
responsible for only part of the key space.  Add more key servers,
rewrite the stat handling routines, etc.  It shouldn't be too hard to do
because they've already handled distributing the work to thousands of
clients.

>
----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.



More information about the rc5 mailing list