[rc5] distributed computing vs applications of distributed computing

Mike Spann mikes at gammalink.com
Wed Oct 1 14:16:22 EDT 1997


I find all this discussion of the various applications of distributed
computing very interesting.  There seem to be lots of good applications.
I, for one, am very interested in the science of distributed computing.
I have been for years.  The recent explosion of the internet provided a 
unique oportunity to explore efficient uses of loosly coupled, 
non-homonogeneous multi-processor systems.  And, while there are some 
issues that are common between applications, there are other issues that 
are application specific.

Take the current RC5-56 task as an example.  It appears that that the main
key server issues super-blocks to proxies, but does not require closure of 
the super blocks before issuing more super-blocks.  I see no evidence of
block expiration or super-block closure.  If this is true, it is basically 
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
by a single bit is 32 megabytes.  If more data is maintained in a data base, 
this data base will be even bigger and will be somewhat slow to search.  At 
todays run rate, the main key server would need to find six block per seconds 
and get them to the clients to keep all clients busy.  By the time the first 
pass through the key space is completed, the rate will be several times that.
If each block is not being tracked in a data base, then every log file 
will need to be searched for each block to see if it has been completed.  
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. 

If you accept that a false negative may have been submitted, then you can 
see that this process is going to have some severe race conditions as the 
iterations increase.  A block will be submitted to a proxy, who issues it 
to a client set at 200 blocks on his 386/16 (or mac se) who sits on it for 
a month.  That block will need to be expired and given to another client 
that is capable of processing it faster.
 
A traditional 'divide an conqure' algorithm would not give up on a super-
block until it were completed.  The main key server would then only have
to worry about issuing super-blocks to the proxies and noting when the
super-blocks had been completed.  In the case of RC5-56, this reduces
the number of entities the main key server must track from 2^30 to a
much smaller number (based on the size of the super-block).  The challanges 
then become how to coordinate the distributed data-base of outstanding 
blocks, which btw is not a terribly difficult task.  I for one would be 
interested in discussions along the lines of how to efficiently divide 
tasks and issue them to the various service processes available over 
an unreliable communications media that is characterized by intermitant 
links (dialups), neo-nazi firewalls, radically dispariant processing 
powers and other such problems.
 
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
that reason alone that I personally would have thought that the 64 bit
RC5 would have been a better choice.  Besides, I can use the thousand
bucks when my 386/25 breaks the winning key :)  
 
Is this mailing list the forum for discussing the architecure of the bovine
distributed computing model and how to improve it, or is there a better
forum?

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



More information about the rc5 mailing list