[rc5] distributed computing vs applications of distributed computing
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
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.
More information about the rc5