<<

. 29
( 41 .)



>>

wasn™t likely to change anyone™s mind one way or the other.
On the other hand, there were serious questions about whether dis-
tributed computing could ever develop into a kind of global network of
computing power that could be coordinated to attack large, complex
problems.
The idea of having many clients work on problems that can be paral-
lelized wasn™t new either. Ever since the 1970s, when Xerox™s Palo Alto
Research Center (PARC) started working with “worm” programs that
would copy themselves from one computer to another, researchers have
thought about how to harness the power of many independent comput-
ers working together, cooperatively performing some computation that

199
200 CHAPTER 28

could not be done by one machine in a reasonable amount of time. By
the mid 1990s, many universities were using the techniques on various
computer networks for handling problems like rendering graphics.
Universities and research facilities weren™t the only ones working in
the area either. In 1995, Pixar amazed the world with its full-length
feature ¬lm Toy Story. To render the photo-realistic images needed
to create the ¬lm, Pixar used a network of Sun UltraSPARC systems
working cooperatively as if they were one huge computer.
DESCHALL was di¬erent from these distributed computing e¬orts
in a critical way, however. Rather than being a highly centralized ef-
fort to coordinate the e¬ort of many computers all under the same
ownership and administration, DESCHALL was only loosely coordi-
nated. Like the projects that worked on RSA™s factoring challenges
since 1993, machines participating in DESCHALL had many di¬er-
ent owners, with many di¬erent computing platforms involved, could
start and stop their participation freely, and were communicating over
a public network that had no single owner.
Some other distributed computing projects like DESCHALL were
around. Adam L. Beberg and some others who had started on the
RC5 Bovine project decided that it would be a good idea to have
a single place to coordinate large-scale computations that could be
tackled using distributed-computing methods. Besides the RSA Se-
cret Key Challenge and Factoring Challenge contests, there were other
groups harnessing computing power in the same way. One such project
is SETI@HOME, a scienti¬c experiment that uses Internet-connected
computers in the Search for Extraterrestrial Intelligence (SETI). Partic-
ipants run a free program that downloads and analyzes radio telescope
data.
Another project is the Great Internet Mersenne Prime Search
(GIMPS), which looks for prime numbers”those divisible only by
themselves and one”in the special form of being one less than a power
of two (that is, 2P ’ 1). For example, 10 is not prime because it is
divisible by 2 and 5, in addition to 1 and itself. Five is a prime number,
but it is not a Mersenne prime because it is not 1 less than a power of
2. Seven is a Mersenne prime, because not only is it prime, but it is 1
less than the eighth power of 2, i.e., 28 ’ 1 = 7.
Seeing the success with earlier RC5 key cracks, factoring of RSA
keys, and the progress of DESCHALL, RC5 Bovine coordinators had
plenty of evidence to support their suspicion that distributed comput-
Distributed 201

ing was ready to be taken beyond the realm of single organizations
trying to harness the power of their own machines and into the age of
the Internet tying together coordinating clients to perform large-scale
computations. With this view of the future clearly in mind, Beberg reg-
istered the domain distributed.net and described the goal of his project
as bringing together all the computing power possible to tackle a sin-
gle task. From that domain, the RC5 Bovine group would undertake
numerous large-scale computations after DESCHALL ¬nished its work.
Meanwhile, the Coderpunks mailing list carried a debate on how to
manage the integrity of such distributed computing projects and how
to convince people to run the software needed to participate in those
projects.
Minar watched the Coderpunks discussion but decided against par-
ticipating in it directly. Instead, when the topic came up on the DES-
CHALL mailing list, he pointed out a key social aspect of the project
that people looking at motivations from a purely theoretical standpoint
were consistently missing. As his own experience with DESCHALL
demonstrated, he had fun checking the project statistics every day,
watching his university™s progress, seeing how others ranked in compar-
ison, and keeping track of just how many keys the project was testing
per second overall.
Having some active role in a project that was testing over 2 billion
keys per second and working with others had a simple social appeal
that was proving critical for getting new participants and keeping them
involved in the project after they started running the client software.


Saturday, May 10, 2:06 P.M.
MIT, Boston, Massachusetts

Even though our project was really moving, we had no time to rest on
our laurels.
Since late April, Karl Runge performed statistical calculations to
report not only overall progress, but to try to predict how our growth
rates would continue. By plotting the number of keys that we had
tested per day, Runge could predict what our growth was likely be in
the future. By knowing the rate at which we could expect to increase
our processing power and the amount of processing power needed to
search the entire keyspace, Runge could predict when we would likely
202 CHAPTER 28

be ¬nished and what our
chances were of ¬nding the key
at various points between the
present and total exhaustion of
the keyspace.
Runge plotted the DES-
CHALL project™s progress on
a graph and sent it to the mail-
ing list. In addition to the ac-
tual daily progress (the jittery
line), Runge plotted a straight
line showing linear growth,
and a smoothly curved line
showing exponential growth.
Seeing the progress graphically
was powerful, but when trying
to predict where the project
would be ¬fteen days in the fu- Fig. 8. DESCHALL Key Testing Rate, Com-
ture, there was plenty of room pared to Statistical Curves
for debate. The di¬erence be-
tween linear and exponential
growth was not pronounced at this stage of the game, but it would
make a big di¬erence soon.
Looking at the same data, Dennis Okon at MIT did some analysis
of his own. He built a model that showed how long it would take DES-
CHALL to get through the keyspace if the key testing rate followed
an exponential growth curve, a steep linear curve that would plot to
roughly sixty degrees, and a less aggressive linear curve that would plot
to forty-¬ve degrees. In that model, Okon showed that if exponential
growth held, the DESCHALL project had a 50 percent chance of ¬nd-
ing the right key by May 31 and a 100 percent chance of ¬nding the
key by June 8. If the linear growth remained aggressive, Okon™s model
showed a ¬fty percent chance of ¬nding the key by July 10 and a 100
percent chance by August 8. Finally, moderate linear growth would get
us to the halfway point on September 4 and through the entire keyspace
on November 11.
When looking at data through May 10, Okon concluded that we
actually reached the end of our exponential growth spurt and that
we were instead following a path of aggressive linear growth, along
Distributed 203

the lines of Runge™s linear growth prediction. After performing this
analysis, Okon conceded that we really couldn™t be sure of the impact
of summer breaks on our computing power, although he thought that
the school holidays could have a dramatic impact on his projections as
the summer began.


Wednesday, May 14, 11:43 P.M.
The Ohio State University, Columbus, Ohio

Addressing the DESCHALL mailing list, Justin Dolske recounted the
progress of the last few days. Sustaining a search rate of over 3 bil-
lion keys per second with 9600 computers running our client software,
we crossed another threshold: a total of 4.4 quadrillion keys tested,
amounting to just over six percent of the total DES keyspace.
While encouraging participants to continue to ¬nd new machines
and new volunteers was important, DESCHALL developers and co-
ordinators had to be much more than cheerleaders: we had to keep
producing software that would make people feel motivated to stay in-
volved.
Dolske™s announcement included three new bitslice clients for 64-
bit machines, namely Hewlett-Packard PA-RISC, HAL SPARC64, and
SGI MIPS. We also had an improved version of the gateway software.
Since the keyserver was keeping track of how clients were participat-
ing based on the IP addresses of the computers reporting keys tested,
all participants using the gateways had their reports appear to come
from the same computer as all other users of that gateway. The end
result for the statistics was that all gateway users were participating
anonymously”all gateway activity got lumped together and reported
in aggregate. Some gateway users wanted to have their contributions
reported uniquely so they could show their contributions just like other
DESCHALL participants could. The new version of the U2T/T2U gate-
way software gave them that option.
Finally, a new Macintosh client was available. That Mac client was
produced by the latest participant to join the ranks of DESCHALL
developers, Andrew Meggs of Antennahead Industries, Inc. While the
footers of his e-mail messages would carry titles like “Defender of the
Universe,” “Content Provider,” and “Head 3D Superfreak,” Meggs
proved himself a ¬rst-rate programmer with an excellent mastery of the
low-level workings of the PowerPC processor”the brains of the Mac-
204 CHAPTER 28

intosh. Putting his prowess to work less than a day after hearing about
DESCHALL, Meggs worked with Verser to produce a hand-optimized
version of the DESCHALL client for Macintosh systems. As a result,
the same kinds of clever tricks employed to make the Verser™s Intel
clients so fast were now available to Macintosh users with PowerPC
processors. That the complex and tedious work of hand-optimizing the
client software for the PowerPC was ¬nished less than two weeks after
it started was nothing short of tremendous.
Unbeknownst to the project participants as a whole, Karl Runge had
been compiling some great statistics on the DESCHALL client activity
per platform. Seeing how many keys were being tested per platform
became an important tool for us to see whether bringing the software
to new platforms would likely be worth the e¬ort. As we suspected,
showing keys tested per platform became yet another way to encour-
age friendly competition among participants: the zealous Linux, Mac-
intosh, and OS/2 users participating in the project could employ the
statistics to convince their likeminded friends to run the DESCHALL
client software on their own systems, so as to demonstrate for the world
the popularity of their favorite computing platform.

Keys Tested Platform
1322.516 trillion Windows-Intel
446.102 trillion Sun-Sparc
317.628 trillion Linux-Intel
235.998 trillion Unknown
200.052 trillion MacOS/PPC
71.292 trillion NetBSD-Intel
67.078 trillion HP/UX-hppa
66.635 trillion OS/2-Intel
56.358 trillion AIX-rs6000
55.330 trillion Irix-Mips
50.289 trillion DEC-Alpha
43.722 trillion SolarisX86-Intel
42.170 trillion ?
27.315 trillion BSDI-Intel
24.766 trillion DigitalUNIX
14.225 trillion IRIX-Mips
1.838 trillion MacOS/68k
1.088 trillion Linux-Alpha
0.318 trillion Linux-Sparc
Table 17. Platform Rankings from April 24 to May 12
Distributed 205

Runge showed the number of keys tested per platform between April
24 and May 12 (Table 17), the one-week period from May 5 to May 12
(Table 18), and then just for May 12 (Table 19).
The per-platform rankings were a bit strange in that they showed
minor di¬erences in some versions of the same client for a platform. For
example, the older clients for the SGI systems reported their platform
as “Irix-Mips” while the newer clients were reported as “IRIX-Mips.”
The platform rankings included such di¬erent clients separately.
The Windows-Intel platform dominated the keysearching, due in
part of the popularity of the platform and in part because of the sheer
speed advantage of Verser™s lightning code for the Intel processor. As
clients for various other platforms were improved and as users of the
less popular systems recruited like-minded advocates, client rankings
changed slowly over time. Looking at the rankings for the past week, for
example, showed that the Macintosh client for the PowerPC processor
family (MacOS/PPC) became more important to the project overall.

Keys Tested Platform
656.481 trillion Windows-Intel
238.486 trillion Sun-Sparc
156.061 trillion Linux-Intel
120.894 trillion MacOS/PPC
86.783 trillion Unknown
40.444 trillion ?
35.889 trillion NetBSD-Intel
31.935 trillion OS/2-Intel
31.895 trillion Irix-Mips
30.183 trillion HP/UX-hppa
28.764 trillion AIX-rs6000
24.766 trillion DigitalUNIX
22.412 trillion SolarisX86-Intel
19.512 trillion DEC-Alpha
14.872 trillion BSDI-Intel
13.926 trillion IRIX-Mips
1.229 trillion MacOS/68k
0.905 trillion Linux-Alpha
0.205 trillion Linux-Sparc
Table 18. Platform Rankings from May 5 to May 12



Unfortunately, there were several other issues with the platform
rankings. The keyserver couldn™t always tell which platform originated
a report on keys tested. Two di¬erent clients fell into the category”
206 CHAPTER 28

though we knew both were some variant of Unix”one was reported

<<

. 29
( 41 .)



>>