No Better Time Page 2

  TCS researchers create mathematical models, rely on abstractions, and establish facts using proofs. They seek to answer questions such as how long an algorithm takes to run, what resources it requires, and how much noise it can tolerate—but they obtain answers through analysis, instead of conjecture or simulation.

  Over time, theoretical computer scientists have, in fact, made extraordinary contributions to the world. At MIT, one of the most celebrated inventions is public key encryption, created by professors Ron Rivest, Adi Shamir, and Leonard Aldeman. Developing what’s called the RSA algorithm, the three scientists came up with the system that now facilitates almost all online e-commerce, financial transactions, and secure Web site logins. Another MIT graduate, electrical engineer Andrew James Viterbi, is responsible for the invention of the Viterbi algorithm. At first, the algorithm was seen as nothing more than a beautiful theory. But eventually, with advancements in hardware technology, the value of Viterbi’s decoding algorithms became clear and they are now used in billions of cell phones and digital television sets around the world. Viterbi left MIT to co-found Qualcomm, the telecommunications giant, and is now a professor at the University of Southern California’s engineering school founded in his name.

  Despite these achievements, TCS was, and still is, relegated to a lower rank at universities around the country, mainly because its foundations remain abstract to all but a small minority, and it’s not the biggest catalyst of tangible, real-world results. “Back then, theory was at the bottom of the totem pole,” recalled Leighton. “It’s better now, but back then we were like the weak sister.” As a consequence, when it came to funding the research pioneering the Internet, TCS was never top of the list. Somehow Leighton still managed to secure government research funds in the late 1980s to explore ways to route and store data on the Internet from a mathematical perspective. But he was mostly on his own: “I was the token mathematician,” Leighton said. “I don’t think anyone was looking to me, or my group, for anything groundbreaking.” Leighton’s own research centered on parallel algorithms and architectures. So little was known about this area of computer science that it had not even been covered in textbooks. Leighton set out to write one, and it took him the better part of seven years. Published in 1992, the hefty, 831-page Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes became a seminal text in computer science.

  By his late thirties, Leighton had reached an enviable place in life. He was a tenured professor at MIT and one of the world’s preeminent authorities on algorithms for computing. Academia was his lifeblood, and his research garnered him a wide array of prestigious accolades, including the Machty Award and the National Science Foundation’s Young Investigator Award. Occasionally, he even turned a profit outside of MIT by patenting his ideas. One idea, which he sold to Polaroid, is still used to create the 2-D barcode on the back of drivers’ licenses.

  Leighton married Bonnie Berger, also a professor at LCS and a renowned expert in randomized algorithms. A petite woman with large brown eyes and the industrious energy of excessive brainpower, Berger was the first female in MIT’s math department to earn tenure. She and Leighton met at an MIT party before Berger began graduate work at the university, and Berger said she knew almost instantly he was the man she wanted to marry. It was not until a decade later that they became engaged. Berger still remembered her mother’s response to the news that her daughter was settling down with a math professor. “My mother said to keep in mind that I was marrying a math professor and my life would not be up to the standards that I was accustomed to,” she recounted. Leighton and Berger had a son, Alexander. They lived in a beautiful home outside Cambridge and worked in offices across the hall from one another in MIT’s Tech Square building.

  Leighton was, and still is, full of quiet ambition. But the mid-90s, when Danny Lewin arrived at MIT, Leighton was also keenly aware that he’d worked long and hard to reach a point at which he was challenged yet also content. “I could have solved proofs all day that no one would ever read,” Leighton admitted. “And I would have been happy doing that.”

  Tom Leighton was Lewin’s one and only mentor at MIT, but he wasn’t the first professor to earn the unflagging admiration of the eager young computer scientist. At the Israel Institute of Technology (Technion), Professor Alfred “Freddy” Bruckstein, who taught electrical engineering and computer science for nearly a decade, remembered clearly the fall of 1992, when Lewin arrived in his office in much the same way he greeted Leighton years later. Lewin, an undergraduate, was not one of Bruckstein’s students, but he came bursting in one day excited to discuss one of the professor’s most challenging areas of interest: knot theory.

  “His brightness was a given, but it was his enthusiasm that I remember the most,” explained Bruckstein, who today serves as the Ollendorff Chair of Science at the Technion. “His eyes were scintillating. He was immersed, interested, and had this fantastic drive.”

  Bruckstein was working to develop software that he could use to program robots to manipulate knots flexibly. According to Bruckstein, the problem was easy to state but extremely difficult to solve using math. Unlike the frustration he saw in countless other students grappling with unwieldy science, Bruckstein saw nothing but enjoyment in Lewin. “Knots are complex, and he loved them,” Bruckstein related. “In fact, I think he loved them for their complexity.”

  An award-winning computer scientist and mathematician, Bruckstein was, and remains, the consummate professor. He wakes up in the mornings looking forward to hours immersed in labs or textbooks. Bruckstein’s research has always focused on quirky mathematics, robotics, and imaging. He has studied the response of movement-sensing neurons in the eyes of a fly and has created a mathematical model to analyze the perfectly straight trails of ants marching in pursuit of food. Eccentric to some, to Lewin these studies were captivating.

  Like the majority of students at the Technion, Lewin was searching for a topic for his first paper. He proposed to Bruckstein a project that would use algorithms to program robots working with knots. Bruckstein didn’t expect much in the way of results from a first-year student, but he was so taken with Lewin that he approved the project, sending him off with some words of encouragement. Lewin spent several weeks working on the paper with another student, friend Orli Gann. When they delivered their paper, titled “Trivial or Knot,” to Bruckstein, he was so impressed that he encouraged them to publish their results. “It was a beautiful project, and I didn’t expect to get such nicely documented results,” said Bruckstein, who still uses the software today.

  Over the next few years, Freddy Bruckstein and Danny Lewin became friends. Although Bruckstein, at age thirty-eight, was fifteen years older than Lewin, they could talk endlessly about science, politics, and life. Bruckstein and his family lived in the apartment building directly next door to Danny, Anne, and their first son, Eitan. Bruckstein’s son, Ariel, played often with Eitan in the small park outside their apartment complex. Bruckstein recalled feeling a sense of sadness when, in July of 1996, Lewin handed him a letter stating that he would be leaving the Technion, where he had planned to pursue a PhD, to attend MIT. Bruckstein said he was sorry to bid farewell to a dear friend, but he was comforted by Lewin’s hope to return one day to teach at the Technion. He was also filled with pride: “I told him to go, of course. MIT is top of the world.”

  At MIT, Lewin found a new mentor in Tom Leighton. And Leighton found a cerebral match and enthusiastic collaborator in Lewin. An intellectual courtship began. Leighton and Lewin were both fluent in the language of mathematics, a precise vernacular punctuated by statements such as if/then and true/false. The two of them would toss ideas back and forth, elaborating on the most exciting ones until those concepts took on lives of their own. The brainstorming, Leighton said, became both conscious and subconscious. Oftentimes, ideas made their way into his dreams, jolting him out of sleep at odd hours. The same was true for Lewin, who was known to fire off lengthy, thoughtful e-mail
missives in the middle of the night. “It’s like working on a crossword puzzle; you get stuck and you put it away,” Leighton clarified. “Then you won’t think about it for a while and suddenly—bang! You have the answer, because the brain works even though you’re not aware of it. That’s what happens with math.”

  With Lewin in lock step, Leighton’s life began to move just a bit faster. Even Bonnie Berger said she couldn’t help but poke her head in her husband’s office when she heard Lewin stop by. “It was quite a circus when Danny arrived,” recalled Berger. “He just was the most energetic force that you could imagine; it was hard to ignore. I’d come in and listen, and he would be jumping around the whiteboard with this muscular, physical power.”

  The more Lewin got to know Leighton, the more professionally enamored he became, routinely telling friends he’d met the “smartest man in the world.” Leighton was also incredibly nice, which impressed Lewin, who had no tolerance for self-importance. Genteel and soft-spoken, Leighton had none of the airs of an ivory tower professor.

  And yet they were an unlikely pair, the professor and the student. More than ten years Lewin’s senior, Leighton was calm and measured, in sharp contrast to Lewin’s fiery, often impetuous nature. Even in physical appearance, they were an unusual duo. Leighton was lean and serious looking, with prematurely graying hair, piercing blue eyes and the ramrod straight posture of an admiral. Lewin was strong and stocky, with the burly physique of a soldier. They spent the bulk of their time together, rarely disagreeing. “They were just such a good match,” Berger confirmed. “They were both really smart, and Tom totally appreciated Danny. I also think Tom was a calming influence. Danny was young and impulsive at times, and Tom would say, ‘What are you thinking?’ I also think they were an amazing pair because they both completely trusted each other.”

  Leighton was reserved but possessed of steadfast determination. Lewin was unabashedly outspoken and indomitable. Both of them were drawn, in their own ways, to the toughest problems facing their field.

  It’s hard to imagine from the vantage point of today’s hyper-wired world, but going online in the late 1990s meant cranking up a modem and waiting an average of twenty seconds as it chirped and beeped, straining to connect with the seemingly magical, futuristic world of cyberspace. In 1996, only twenty million Americans had access to the Internet. For most people, it remained a source of fascination and bewilderment. As the largest Internet Service Provider (ISP) at the time, America Online (AOL) led the pack with five million subscribers. AOL also had the most popular Web site, AOL.com, by virtue of the fact that when its members dialed into the Web, they were immediately directed to the company’s home page. That summer marked the launch of the first webmail site, Hotmail, but there was no instant messaging or music trading. No streaming music or video. The question on most people’s minds was how, exactly, could the Internet be used? It was the new American frontier.{4}

  At the time, the Internet functioned fairly well within small communities like academic institutions, but, otherwise, it remained seriously flawed. A common scenario in those days involved a user who dialed into the Internet using a home telephone line, which allowed him or her to access information at speeds of only tens of kilobytes per second, compared with tens of megabytes today (more than a tenfold increase). These wait times were frustrating, arising mainly because a server—the powerful computer that responds to requests for information—could be sitting anywhere in the country and it took time for the information stream to move.

  The root of the problem lay in the Internet’s architecture, originally designed like highways connected by various tunnels, or a “network of networks.” The inner workings of this architecture are highly technical and complex, but a basic understanding of how the Web works is surprisingly easy using a familiar analogy: the Pony Express.

  When you click on a Web link, think of it as the act of dispatching a rider from your browser to a storage facility known as a web server. The first thing the rider has to do is figure out where the storage facility is. To get the address, the rider consults the Internet address book, also known as the Domain Name System (DNS). Just as your address book can tell you that your friend Joe Smith lives at 10 High Street, Cambridge, DNS can tell the rider that www.cnn.com “lives” at IP address 157.166.266.25, for example. With the address, the rider is off to that destination.

  As with the Pony Express, the trip to the storage location and back is not direct. The rider has to stop at several locations (known as routers or “hops”) between the starting point (your browser) and final destination (the Web server) to ask for directions. There can be twenty or more stops for each trip. At each stop, the rider has to ask for directions to the final address. Unfortunately, the staff at the stop does not actually know how to get to the final destination. Rather, they use a tool called the Border Gateway Protocol (BGP), which tells them only the next stop on the journey. Eventually, the rider makes it to the storage facility, asks for the Web file, retrieves it, then heads back to your browser using the same method used to get there—traversing the various “hops” and routes along the way. The rider may stop at the same locations on the return trip or take a completely different route.

  Once the rider returns, your browser opens the file and notices that there are a bunch of related objects needed to view the complete Web page—pictures, videos, ads, etc. In this case, the rider must be dispatched again to the same storage facility, this time to retrieve all the component parts. Each page can have twenty to thirty related objects—only one of which the rider can collect at a time—and the storage facility can be thousands of miles away. All of this makes the process of getting a complete Web page time-consuming and cumbersome. It is worth noting that, while the initial Web page file is usually small, the related objects can be big and unwieldy (videos, for example), making them difficult to transport.

  While this whole process sounds quite tedious, there is one thing that makes it relatively quick—light or, more accurately, the speed of light. Most of the stops on the rider’s journey are connected by fiber optic cables, which allow the rider to travel the roads between stops at the speed of light—186,000 miles per second. That’s fast enough to circle the globe seven times in one second. So, while the stops are many and the distance great, the speed is fast enough to mask the challenges, at least most of the time.

  Still today, the potential problems with this system include the following:

  1. Lots of riders may be asking the DNS server for addresses, leading to delays.

  2. The stops might be closed, forcing the rider to backtrack and find an alternate route.

  3. There might be a lot of riders on the roads between stops, leading to congestion and delays.

  4. There might be a lot of riders at the stops asking for directions leading to further delays.

  5. The storage facility itself might be closed.

  6. There might be lots of riders at the storage facility asking for files, leading to more delays.

  There are a few ways to mitigate these potential problems, and one of the most popular is called “caching.” The idea behind caching is straightforward: it’s a method that moves Web content closer to the user requesting it. Rather than forcing the rider to travel across many hops, a copy of the requested files are kept at a storage location closer to the browser known as a cache server. This way the rider only has to travel two or three hops to the cache server to get the file, rather than the twenty hops on the route to the original file storage facility. Not only does this make for a shorter trip; it also decreases the likelihood of running into problems during the longer journey. While this sounds quite simple in theory, in practice caches can be hard to manage.

  For these reasons and more, the Internet was experiencing intense growing pains in the 1990s. By late 1995, networking pioneer Robert “Bob” Metcalfe of MIT’s Project MAC sounded the alarm in a string of speeches, columns, and interviews. “The Internet has outgrown its design and needs to be fixed,
” he argued. “There are going to be more outages, and they’re going to get worse.” In October, the Associated Press ran a story with the headline “Is the Internet Poised to Collapse?” in which journalist Elizabeth Weise wrote: “The Internet is broken. The evidence is everywhere. Outages drop millions offline for hours, sometimes days. The number of users has been doubling every year since 1988, and traffic on some long-distance routes doubles every four months. World Wide Web pages take forever to load because data pipes are clogged.”{5} It was a pressing problem, and one that was also on the mind of British physicist and computer scientist Tim Berners-Lee, known as the inventor of the World Wide Web.

  Berners-Lee moved to Cambridge in 1994 to found the W3C, an international body charged with governing the standards for the Internet. He came from CERN, the European Laboratory for Particle Physics, where he wrote the software that would eventually open the Web browser and provide its underlying protocol. Specifically, he created the hypertext markup language, or HTML, and the hypertext transfer protocol, the http:// that precedes the zillions of Web addresses (i.e., URLs) that are now as ubiquitous as ZIP codes. HTML, a coding language, provided a framework for enabling users to access electronic documents in a standard way. It also meant links could be built into documents themselves so that they could be connected together, rather than existing as separate and distinct pieces of data.

  One day, Berners-Lee, whose W3C office shared a floor with MIT’s theory group, walked down the hall to talk with Leighton about what he called the “hot spot” problem. The Web was not running smoothly, with bottlenecks contributing to a challenge Berners-Lee termed the “World Wide Wait.” Leighton had a crew of graduate students working on a better way to manage and distribute content over the Web, and Berners-Lee asked if they could come up with a way, mathematically, to scale the Internet. Leighton wasn’t sure his group could find a solution, but he said they would try. “In many ways Tim presented an ideal problem for me and my group to work on,” Leighton said. “We didn’t understand the Internet that well, but we knew a lot about the way information flowed and the math behind it, and we wanted to find an answer.”