Algorithms That Changed the World
Apr 21, 2004 3:52 AM PT
Algorithms -- or, in layman's terms, defined procedures for accomplishing a task or solving a problem -- abound throughout the computing industry. These protocols have shaped the ways in which people communicate, transact business and even pursue recreation using computers.
Certain algorithms are more well known than others. Some of the most famous include TCP/IP, which defines how the Internet transmits data; Google's search engine, which defines the way in which millions of people find information online; and HTTP, which underlies the World Wide Web and played a large part in the Internet's mid-1990s mainstream breakthrough.
Others are little known but still have a huge impact, David Clark, senior research scientist at MIT's Computer Science and Artificial Intelligence Lab, told the E-Commerce Times. One example is an algorithm, written by the University of Delaware's Dave Mills, that synchronizes all of the clocks on the Internet.
In this article, the E-Commerce Times profiles a few good algorithms.
One of the world's most important algorithms, TCP/IP -- which stands for Transmission Control Protocol/Internet Protocol -- was invented at a time when most computers were mainframes housed in cool rooms. In the 1960s, the U.S. Department of Defense's Advanced Research Projects Agency (ARPA) partnered with several universities and corporate research departments to create open standards-based multivendor networks, according to an article titled "The History of TCP/IP."
By 1969 -- the same year in which Nicklaus Wirth wrote the Pascal compiler -- the research partners had developed a four-node, packet-switched network dubbed ARPANET. Five years later, Vinton Cerf and Robert Kahn proposed a design for a new set of protocols, which became known as TCP/IP.
"The most basic bit of 'science' in current networks is the discovery that packet switching actually works," MIT's Clark told the E-Commerce Times. "From today's vantage point, it is worth remembering that when the idea was first proposed, lots of folks thought it would not work. It was not that 'the algorithm' could not be written; it was the concern that the queuing behavior of the overall system would be unstable."
In 1980, ARPA began converting its computers to TCP/IP, and three years later it mandated that all computers connected to ARPANET use this algorithm, according to various Web sites. TCP/IP went on to become the standard underpinning of today's Internet, which is used by hundreds of millions of people worldwide. Not bad for a once-obscure research project.
Safe and Sound
Sometimes, algorithms that change the world arise not as research for its own sake, but to answer a pressing need. One example of this type of innovation is encryption, which was created to defend against code-breakers who seek to steal or eavesdrop on vital data.
One encryption algorithm that evolved to safeguard code was RSA, named after its inventors, Ronald Rivest, Adi Shamir and Leonard Adleman. Rivest, Shamir and Adleman developed RSA at MIT in 1977, according to Bedford, Massachusetts-based RSA Security. It actually was introduced a few years after British cryptographer Clifford Cox developed his own variant of RSA. However, the British government had classified Cox' algorithm, RSA Laboratories said.
The RSA algorithm almost met the same fate. When Rivest, Shamir and Adleman published information about it in the September 1977 issue of Scientific American magazine, they also volunteered to provide their complete report to anyone who sent them a self-addressed stamped envelope, according to Susan Brenner, a professor at the University of Dayton School of Law in Ohio. The National Security Administration was not pleased by the thought of such widespread distribution of RSA and moved to stop dissemination of the report -- but the NSA never replied to a query about the legality of its cease-and-desist request, Brenner told the E-Commerce Times.
As a result, since there was no legal foundation to prevent them from doing so, the trio then published their algorithm in the Communications of the Association for Computing Machinery in 1978. RSA was off and running. Years later, in 1994, Rivest published a new algorithm called RC5 online, claiming it was more powerful than the Data Encryption Standard (DES), Brenner said.
In today's Internet-heavy environment, security algorithms such as RSA and its descendents play a critical role, according to Jeffrey Shallit, a professor of computer science at the University of Waterloo.
"[These algorithms] form the basis of secure electronic commerce by allowing transactions to be done online in encrypted format," Shallit told the E-Commerce Times.
Also, in today's world of rapidly transmitted information, algorithms that compress data and images are playing an increasingly important role in the workplace and in society.
"Algorithms for audio and video -- what makes Voice over IP or IP television work -- [are important]," MIT's Clark said.
Toward that goal, researchers and other innovators have written many algorithms designed to compress and send data. In 1991, for example, Steve Casner and Van Jacobsen of Cisco Systems co-developed the Compressed Real-Time Protocol (CRTP).
Meanwhile, in Germany, an algorithm that would alter the music industry landscape arose. In 1987, the University of Erlangen -- under the guidance of Professor Dieter Seitzer -- teamed with Fraunhofer Gesellschaft's Institut Integrierte Schaltungen (IIS) to create an audio algorithm that could condense music transmission and storage. The two teams developed MP3, designed to decrease by a factor of 12 the size of an original recording on a CD while maintaining the same level of audio quality. As many record labels no doubt would attest, the world has not been the same since.
As you can see, algorithms have the power to change the course of history. And the ones discussed in this article are only a few examples. Algorithms can be found everywhere you look -- in the linking structure of the Web, in the inner workings of an automobile and in the intricacies of stock markets and exchanges. In fact, if you can ask, "How does it work?" the answer most likely involves an algorithm. At its simplest, after all, an algorithm is just a description of the way something works.
Whatever their purpose -- compression, security, communication, speed, access or something entirely different -- algorithms no doubt will continue to shake up the status quo. The key for CIOs and IT managers is recognizing which algorithms will drive the direction of tomorrow's business world -- and then figuring out how to capitalize on them.