No Better Time

by Molly Knight Raskin

  Their focus was still on using math to relieve the congestion plaguing the complex architecture of the Internet. Specifically, they were still searching for a solution to the the problem of the World Wide Wait. Tim Berners-Lee had pushed to the fore of the theory group’s work. Under the supervision of Tom Leighton and fellow LCS professor David Karger—an award-winning computer scientist with an expertise in applied algorithms—Lewin, Lehman, Panigrahy, and Levine were trying to improve on one of the existing approaches to hot spots, called “caching.” As described earlier, caching allows for much faster delivery of Web pages to users because it skips over the numerous routers and transition points that form the Internet. Moving data over the Internet, such as downloading Web pages, tends to be a highly repetitive process. For each object on a page (such as pictures, text, logos and ads, etc.) multiple round trips are required between the server and the user’s browser. Considering that the average Web page contains anywhere from ten to thirty objects and that the server might be thousands of miles from the requesting computer, it’s easy to understand why slowdowns are a problem.

  There are several ways to cache content, and all of them involve high-level math and engineering. That’s because, to function efficiently, caches need to “think.” An efficient caching system is able to refresh or change content so as to reflect changes to the Web pages. It is also able to understand the construction of Web pages so it can refresh only the objects that change often. Caching is accomplished through servers, which are positioned between the source of the content and the user requesting it.

  Lewin scrutinized the most sophisticated math underlying caching software and eventually created the foundation for a new Web caching technique called “consistent hashing.” Hashing (not to be confused with “caching”) is a method of accessing data by assigning it a set of unique numbers. Hashing schemes work well when the number of servers is known and fixed. But on the Internet, where the number of servers is always in flux, it’s relatively useless—unless particular algorithms instruct the servers on how to readjust their respective loads. With this in mind, Lewin set out to develop a new set of algorithms that that would claim something no other caching strategy could: fault-tolerance.

  A useful, non-mathematical metaphor for understanding consistent hashing is the storage of files. Say you are given a task which, at the outset, appears easy: to store a large stack of files in several cabinets in some particular order, a system you can remember later when you want to retrieve a particular file. Obviously, there are several ways the files can be organized. One of the most obvious is by alphabet—the A’s on one shelf, the B’s on the next, and so on. This strategy functions well until there is a surplus of A files. Suddenly that cabinet is full, and you’re left with no logical place to store them. If they go into the cabinet for the B files, the B’s might get squeezed out, meaning some B’s would have to be shifted to the C cabinet, some C’s would move to the D cabinet, and so on. To make matter worse, what if two of the filing cabinets break, forcing you to remove all of the files they contain and stuff them into the cabinets with extra room? There would no longer be a clear destination for any one file. The system, once working smoothly, now becomes messy. Using algorithms, consistent hashing offered a way of organizing files—or any kind of data—optimally. Consistent hashing meant that when a new “cabinet” was added or a new set of files was introduced, they would be spread evenly and consistently across said “cabinets.”

  Eric Lehman distinctly recalled the day Lewin shared this new idea with him and just how insecure he was about its potential. “We were walking together across campus and Danny was kind of down on his research,” said Lehman. “He told me about consistent hashing, and I’ll never forget it because he said, ‘Consistent hashing is a pathetic idea, but it’s my idea.’”

  Mathematicians often describe proofs, theorems, and algorithms using the same adjectives one might use to describe a woman or a work of art. Sometimes their work is elegant and beautiful. In rare cases, it is stunning. According to Lehman, Lewin originally thought his idea of consistent hashing was simplistic and impractical: “He was worried it was small and worthless, just something cute.” To clarify, in mathematical jargon, “cute” means the work looks good on the surface, but lacks utility and mathematical sophistication. Lewin and Lehman thought they had a cute idea to work with, but they knew they needed to improve it somehow. Lehman, though, was uncertain if this could be done: “Honestly, we didn’t know very much about how the Internet worked at the time, and we were struggling with how to convert this real world problem of file storage into a mathematical model. On paper, our mathematical model didn’t seem that realistic, so the whole thing seemed kind of shaky to me.”

  However pathetic Lewin himself felt it to be, however, he did believe consistent hashing might have some practical utility. “In that same conversation in which he called it pathetic,” Lehman added, “I remember Danny saying he really thought something like this could exist.” With this in mind, Lewin and Lehman forged ahead, and, at some point, decided to present their research their adviser, David Karger. A brilliant mathematician, Karger earned his PhD at Harvard. Nonetheless, Lewin and Lehman both found him difficult to interact with because he was often prickly and dismissive of their ideas. Consequently, they approached Karger with some apprehension. According to Lehman, the meeting did not go well. Karger didn’t think Lewin’s idea had legs, so to speak, and even referred to it as insignificant. Lehman reported that he and Lewin were deflated: “It was really upsetting, and it almost pushed us over the edge.”{20}

  However frustrated he might have been, though, Lewin wasn’t about to let the idea of consistent hashing go. He still had faith in it, and told Lehman he’d will it into greatness if he had to. But first they needed a second opinion, and there was no question who they would approach to get it: Tom Leighton.

  If there exists a mathematical concept that is as logical and precise as it is confusing and abstract, it is the algorithm. The mere mention of the term has the power to illicit a baffled shrug or a shudder in those who are not mathematically inclined. What, exactly, is an algorithm? When posed to a dozen people, the question is likely to produce a dozen different replies. The answer, however, is almost deceptively simple. An algorithm is a precise, finite set of instructions for carrying out a procedure or solving a problem. And although an algorithm is a mathematical concept, the finite instructions themselves (or, in layman’s terms, “recipes”) needn’t involve math. We use algorithms almost daily for tasks as varied as baking a cake, driving from one place to another, looking up a word in the dictionary, or filing taxes. Algorithms are the methodologies we use to solve problems, and they govern everyday life.

  To walk through a basic example of an algorithm outside of computing, consider planning a trip from one city to another. There are several ways you can make the trip, and each one can be mapped using a basic algorithm. In scenario one, you get in your car and drive from City A to City B. In scenario two, you take a taxi to the train station and board a train from City A to City B. And in yet another scenario, you take a taxi to the airport and catch a flight from City A to City B. These are three algorithms with three very different ways of accomplishing the exact same goal. The same is true for computer programming. Often, many different algorithms can be used to accomplish a task with the same end result, but each algorithm results in varying degrees of time or cost or both.

  Why, then, is there so often an aura of complexity or mystery surrounding the algorithm? The answer is ironically simple: the algorithms worth talking about, those that have accomplished great tasks, are not easy to follow. And in computer science, they are often so difficult and mathematically rigorous that they seem almost illusory to anyone outside of the field. Computer programmers use these types of algorithms to instruct machines to execute certain functions in the most efficient way possible. They’re still step-by-step recipes with an end result, but, in computer science, the steps to reach that
end result contain the symbols and language of computer programming: nodes, inputs, outputs, and variables. If you don’t speak the language, it becomes an abstraction. In his book The Advent of the Algorithm, author David Berlinski summed up the elusive nature of the algorithm as “an abstract instrument of coordination, supplying procedural means to various ends…algorithms, like thoughts, reside in a world beyond time.”{21}

  Notably, algorithms used in early computer science are practically synonymous with Alan Turing, who preceded Tom Leighton at Princeton by four decades. Turing was a pioneer in many fields, including information theory, mathematics, and cryptography. But Turing is best known for the machine bearing his name—the “Turing machine”—an imaginary problem-solving device that existed only on paper. Presaging the invention of the modern computer, Turing designed a virtual construct that could store and run sets of instructions, or algorithms. He dreamed up the idea before real, programmable computing devices existed. It was so revolutionary that it sparked a new era of modern computing driven by algorithms and rigorous mathematical proofs.{22}

  Algorithms have been used for historic breakthroughs in all areas of science, from computational biology to quantum computing. But they occupy an exclusive place in the field of computer science because they are finite and discreet. As Berlinski explained, they “specify only a series of numbers, the conversion of those numbers into a pattern for the mathematician to decide.” As computer scientists like to say, a computer is a storyteller and algorithms are its tales. In the eye of certain beholders, an algorithm can be beautiful. Francis Sullivan, an American theologian, likened algorithms to literature: “For me, great algorithms are the poetry of computation. Just like verse, they can be terse, allusive, dense, and even mysterious. But once unlocked, they cast a brilliant new light on some aspect of computing.”

  The most influential twentieth-century advocate for the power of algorithms in computer science was Stanford professor Donald Knuth. Knuth was born in Milwaukee, Wisconsin, where his father owned a small printing business and taught bookkeeping. Knuth’s intelligence made him a standout from an early age, both for his academic acumen and for the sometimes peculiar ways he applied it. In eighth grade, he won a contest by finding over 4,500 words that could be formed from the letters in “Ziegler’s Giant Bar”; the judges themselves had only about 2,500 words on their master list. In 1957, during his senior year, Knuth won the Westinghouse Talent Search, the same scholarship awarded to Leighton in 1974. He hoped to pursue a career in music, but his plans changed when the Case Institute (later Case Western Reserve) offered him a full scholarship in physics. He soon realized that he loved math more than physics, specifically the area of discreet mathematics. In 1963, he earned a PhD in mathematics from the California Institute of Technology and began working there as associate professor.

  Knuth argued passionately for the marriage of math and computer science, based on his firm belief that the two fields could do nothing but enrich each other. It wasn’t a popular stance, particularly to traditional mathematicians. But Knuth knew that, at its highest levels, math—specifically the study of algorithms—could be applied to our understanding and creation of computers. Computer science was just emerging, with caution, onto the scene. Knuth wrote: “It was a totally new field, with no real identity. And the standard of available publications was not that high. A lot of the papers coming out were quite simply wrong.… So one of my motivations was to put straight a story that had been very badly told.”{23}

  Knuth authored a seven-volume tome that became the bible of computer science: The Art of Computer Programming was first published in 1968. One of its first lessons is on hashing.

  By the time Lewin and Lehman arranged a meeting with Tom Leighton, though, they hadn’t gained a great deal of confidence in consistent hashing. Leighton remembered the two of them appearing slightly embarrassed when they approached him for feedback. “They presented it almost as an afterthought,” Leighton said. “They told me about the concept in what was an apologetic way.”

  Almost instantly, however, Leighton saw something significant. “I thought, oh, my goodness because they had a whole bunch of stuff—proof of this, proof of that, all these things. I said, ‘Wow, that’s a gem; that’s really cool [and] you wouldn’t expect you could do this.’” Leighton had never thought about hashing the way Lewin and Lehman presented it. In fact, their approach seemed almost impossible. But there it was in front of him, stapled neatly and sitting on his desk. Lewin didn’t yet have the deep proofs, but he had something. And to Leighton, it was beautiful.

  “I remember being struck,” Leighton confessed. “It wasn’t a tour de force technically, and in mathematics you often want to have that kind of thing, but it was just—I thought it was elegant and fundamental, and I remember just appreciating the beauty, the elegance, and what I thought was going to be the importance of it.”

  According to Leighton, the potential power of consistent hashing was rooted in its simplicity. Lewin had taken a succinct problem—one that was easy to state but seemingly impossible to solve—and created a solution so simple and elegant it was almost…obvious. “Mathematics has a lot of examples like this, where you could take a thousand people and they wouldn’t be able to solve the problem, but they could all quickly agree when you show them the solution that it’s easy,” Leighton clarified. “It’s a weird thing, to be convinced that a solution works is much different than coming up with one.”

  At the time, Leighton looked at Lewin and Lehman and exclaimed, “You’ve done it. This is really important, and you’ve got to give it a name and state the definition of the problem because this sounds useful.”

  It was the beginning of the end of the World Wide Wait.

  Chapter 4

  May Madness

  “A significant invention must be startling, unexpected. It must come to a world that is not prepared for it. If the world were prepared for it, it would not be much of an invention.”

  — DR. EDWIN LAND,

  Polaroid founder, 1975 interview in Forbes magazine

  LIKE SO MANY GRADUATE STUDENTS living on meager stipends, Danny and Anne were struggling financially. Naturally, their student loans were mounting. To ease the strain, Lewin took a job sweeping the halls of their apartment complex in exchange for a discount on rent. But life with two kids meant unforeseen and often unremitting expenses. Some weeks, in an exercise of frugality, they cut the more costly items, like meat, from their grocery list. Friends recalled Lewin wrestling with the seemingly small decision of whether or not to replace one of the boy’s lunchboxes, which had been dented. Lewin had always been resourceful, taking on a newspaper route in Colorado on his own initiative when he was in the fourth grade. In Israel, he always found ways to financially emancipate himself from his parents. He worked at a pizza parlor as a teenager, and later, in exchange for a membership at Samson’s gym, he took a job cleaning the locker rooms. But now the demands of school and home didn’t allow him the time to take on any more odd jobs—and the money woes were keeping him and Anne up at night. Lewin needed funds, and he needed them fast.

  Lewin’s neighbor and close friend Preetish Nijhawan, a second-year student at MIT’s Sloan School of Business, knew how stressed Danny and Anne were. Nijhawan had a family of his own, and, as mentioned earlier, his wife Shirin pulled in extra money by babysitting a few kids during the week, including Eitan and Itamar Lewin. One afternoon in 1997, Nijhawan came to Lewin with an idea—one he felt could be their ticket to riches. It was a business contest hosted by the students at the Sloan School. And unlike other student-organized events, this one—called the MIT $50K Entrepreneurship Competition—could mean real money. Nijhawan, who formerly worked for Intel, understood Lewin’s core work on consistent hashing, and saw the possibility of applying it to the Internet. Over lunch with Lewin, Nijhawan proposed an idea: he and Lewin should build a business plan out of the research Lewin was doing with Tom Leighton and enter the 50K. Lewin was unsure, until Nijhawa
n told him about the prize money. The winner of the contest, he said, received a staggering sum: $50,000. To Lewin, this sounded like all the money in the world. He didn’t need any more convincing. He and Nijhawan talked it over, and decided that if consistent hashing had the potential to improve the speed and efficiency of the Internet, it had the potential to inspire a winning business plan—one that would sell software (powered by complex math and consistent hashing) to companies on the promise that it would change the way they delivered content on the Internet.

  That same afternoon, Lewin and Nijhawan went directly to Leighton’s office hoping to convince him to join their just-formed business team. Leighton was surprised. He had a bit of business experience selling some of his patents to Polaroid but never planned to start up anything of his own, even on paper. “Danny and I had been proving theorems, but we hadn’t been thinking at all about a business aspect,” Leighton said. “I might have been the most unlikely person in the world to start a company.” In addition, he wasn’t entirely certain that, where he saw beauty, others would see potential. He also worried because, at his own urging, Lewin had submitted, to no avail, an initial paper on consistent hashing to a renowned conference called the Symposium on Discreet Algorithms. In the rejection notice, the conference committee members stated that they didn’t think consistent hashing had any hope of being useful.

  But Lewin managed to persuade Leighton, with his characteristic zeal, that they had nothing to lose. It was just an academic exercise; at least, that’s one way Leighton could look at it. By the time Lewin and Nijhawan left Leighton’s office, he was on board.

  The first challenge in the lead up to the 50K was the business plan itself. Lewin and Leighton had some great ideas, but nothing close to a compelling proposition for a startup. “Designing a system was a very different endeavor for us,” said Leighton. “It was still on paper, but it wasn’t going to be mathematical anymore.” Lewin went to the library and checked out a stack of books on business plans and startups. He then passed them on to Leighton, insisting that he read them, too. Bonnie Berger said she’ll never forget her husband arriving home with volumes of instructional manuals and staying up two nights in a row reading them. “They really had no idea what they were doing,” commented Berger. “I remember Tom started getting really interested in this contest with Danny and I remember it evolving, and I remember Danny would be coming by with all his energy and sucking Tom into it even more every time.” Leighton, though, remembered being sucked in willingly and marveling at Lewin’s spirited approach to the contest. “It was through that process that I really got the impression that Danny had tremendous drive and no fear,” recalled Leighton. “If he didn’t know something, he’d go learn it.”