9/11 And The Web
How we observed this day
Danny Lewin entered MIT’s Ph.D. program, then co-founded Akamai Technologies with his advisor Tom Leighton, all before boarding American Airlines Flight 11 in Boston on September 11, 2001.
Yesterday, Sunday, was ten years since the 9/11 attack on America. The attack left almost three thousand dead and affected thousands more indirectly—some who lost family; some who lost neighbors; some who barely survived; some who tried to help, but could not. Ken and I cannot possibly speak for those who lost loved ones—the closest we come is that Ken’s father was in the North Tower at ground level and escaped unhurt. Countless others watched from afar, but were touched and forever changed by this attack. It is impossible for us to forget where we were that day and what we saw. Impossible.
We thought it right to remember one of the victims of the attack. Every victim has a story, and every one did not deserve what happened that day. But one victim, Lewin, was a member of our community, and it seems correct to remember him. Perhaps talking about his brilliant work will not stop the pain that many still feel—and will feel forever, one telling me (Ken) that he cannot bear to read the part of Lewin’s Wikipedia page that describes his death. Perhaps nothing can help, yet talking about his work seems to us one way to remember and mourn the loss of a brilliant researcher, who otherwise would have had the last ten years to add to our understanding of the world.
Lewin had seat 9B forward in business class, seated among the hijackers. It is believed that he confronted them single-handedly; it is known that he was killed even before the plane turned to follow the Hudson River south toward New York City. This is known because a flight attendant got through on the American Airlines emergency line and reported what had happened, ascribing the killing to a hijacker seated just behind Lewin. Communications between passengers on the planes and their loved ones enabled those on United Airlines Flight 93, which was over Pennsylvania and headed toward Washington, DC, to learn the hijackers’ homicidal intent, and to take organized action against them.
Lewin’s Research on Polynomials
The work by Danny Lewin that first came to both our attention was his STOC 1998 paper with Salil Vadhan. It broadened results on polynomial identity checking by Zhi-Zhong Chen and Ming-Yang Kao which had appeared at the previous FOCS.
Chen and Kao considered the classic problem, given a polynomial over the rational numbers, how easy is it to tell whether is identically zero? The sense in which the polynomial is given is key. If it were given as a sum of terms, where `term’ means a monomial multiplied by a coefficient, you could just add the terms to see if everything cancels. Things become trickier if it is given by a formula that includes products of polynomials, because multiplying out the products might create exponentially many terms. The polynomial might be given with parts stated to be the determinant or permanent of some matrix of terms. It might even be given as a “black box” allowing you to present arguments and receive the value , but not telling you anything about its structure, except possibly a bound on its total degree .
No deterministic polynomial-time algorithm is known for this problem. However, except over small finite fields, the zero set of a non-zero polynomial will be small in various senses that a poly-time randomized algorithm can exploit. We have written on this before. The simplest idea is to choose points at random, so that with high probability a witnessing point will be found for nonzero . To gain greater confidence after a sequence of answers that is really zero, one can try more points—at the cost of more random bits.
Chen and Kao’s idea was to define irrational points that are guaranteed by Galois theory to lie outside of regarded as a subset of the reals. Because is topologically closed, all sufficiently close rational approximations to lie outside of , but how close do we have to go? They showed that with high probability over random bits used once and once only to choose , a moderate number of leading bits of coordinates of suffice to find a witness . To increase the confidence that really means is identically zero, one need only increase . The key is that this does not require increasing the number of random bits. The hitch, however, is that their algorithm is wedded to how the rationals sit inside the reals, and their analysis works only when has integer coefficients.
What Lewin and Vadhan recognized is that beyond the tricks with sums of square roots of prime numbers, and notions of approximation which don’t apply over finite fields, were structural ideas that hold for any field . Their paper explains this beautifully already, and we cannot do better than to quote them as a perfect example of game-changing:
|Primes||Irreducible Polynomials in|
|Square Roots||Infinite Power Series over|
|Approximation||Square Roots mod|
Well we have led off with this because we are interested in polynomials. We actually have a similar situation with our own paper together with Atri Rudra, which I (Ken) just presented at MFCS 2011 and today at the 4th Eastern Great Lakes Theory Workshop organized by Atri and Alan Selman and Bobby Kleinberg of Cornell. We have one construction in that paper that is algebraically natural but doesn’t give polynomial time, and another that gives nearly linear time but uses coding tricks that work only over finite fields. Can we symmetrize an arbitrary polynomial without losing information in a way that is both efficient and algebraically natural over any field?—perhaps you will see something we’re missing.
The Paper That Begat a Company
One might think that fussing with probabilities and economizing on random bits is not the road to riches, but one would be wrong. The famous STOC 1997 paper with Leighton and Lewin and four other MIT authors that gave rise to Akamai was all about randomized algorithms and their analysis. Usually we would link just the word `paper’ to reduce link-colored words, but here we give the long URL used by Akamai to store the paper in full, because paying reverence to the paper’s subtitle is the point:
Today we can’t help thinking of “relieving hot spots” as a phrase relating to the war on terror, but anything that makes the Web more redundant and robust will help there too.
The nub is to make the hash mapping of keys to slots robust under adding or removing a few hash buckets. A standard hash function like will fail because incrementing or decrementing changes the values modulo in unpredictable ways.
Their solution was to create a relationship of geometric closeness between the values that hash to a given slot and an anchor for each bucket, while giving each bucket multiple anchors spread out in random locations over the domain of possible keys. When a new bucket is added, it affects only those keys near the locations chosen for its anchors. Deleting a bucket forces re-mapping of only those keys that were close to its anchors. Each affected key will find the next-closest anchor, and significantly, the new anchors in different locations will typically not belong to the same bucket, but mostly to different buckets, thus sharing the increased load evenly.
Ironically the load-sharing feature of Akamai’s network had its first extreme test on 9/11/01 itself. To quote this article:
By 10 a.m. that day, as employees struggled to come to grips with Lewin’s death, Akamai’s servers were being hammered by millions of visitors looking for information about the attacks. Inside Akamai’s network operations command center, engineers’ eyes widened as they watched the situation unfold. “Our employees were in shock,” recalls [then-president Paul] Sagan, who was at the Cambridge offices that morning. “But traffic was going crazy.” Remarkably, Akamai’s network and employees absorbed the stress, so that customers like CNN, which used Akamai to cache and deliver Web content, were able to accommodate the extra traffic without a hitch.
Now the company routinely handles loads that are an order of magnitude higher, and on a typical day about 20% of Internet traffic is delivered by its servers.
A nice explanation of consistent hashing is here. We note that the STOC paper promised a full version proving they only required limited independence, but Leighton and Lewin were soon more interested in field-testing their algorithms. They and their group drew up a business plan, and entered the MIT 100K Entrepreneurship Competition, which was then 50K. They made the finals of six out of 100 entries, but we are told they lost out to an online dog-food marketing scheme that flopped. Oh well.
Akamai and Communication
Now Akamai is a thriving company, providing fast, reliable, secure communication on the World Wide Web. This success stems from smart implementations of novel network routing algorithms, and from good business partnership sense. Much of this owes to current CEO Sagan, as told in the above-quoted article. Bobby Kleinberg worked at Akamai during Lewin’s time as Chief Technology Officer and shares with us some of his memories of Lewin. The company’s success depends on having servers running their algorithms, of course, but these servers must be physically located all over the world. Latency is a big factor in the scheme laid out in the 1997 STOC paper, which needed nothing short of a world vision to realize.
Placing servers physically around the world requires negotiating with many countries, each with their own concerns, languages, and cultures. Even more complex, each country may have distinct technical concerns. For instance, some countries differentiate less between the cost of uploads and downloads because most of their cables go through oceans, and this affects the terms under which Akamai can attach its servers to their systems. This requires communication skills of the first order. Lewin’s nature was to be not only on top of everything analytically but also engaged with everyone personally, and this plus the acumen of those who joined him and Leighton to lead made it happen.
Communication within the company was also vital. As an icebreaker once Lewin, who used to organize softball games for the MIT theory group, arranged a paintball match pitting the four top company officers against all other employees. The other three executives quickly took cover behind Lewin as the hundred on the other side advanced. Using his training and four years of service in an elite Israeli Defense Forces unit, and general sang-froid, Lewin calmly took deterministic accurate aim while being randomly pelted, and picked off quite a few of the assailants by the rules of the game.
We would wish for the world that no one would face a situation any more highly charged than that, as Lewin himself did on 9/11. Several times on Sunday, in person and on the radio, we heard references from ancient books to a future world where people would war no more. That world may seem no closer now than then. However, the presence of entities we need to defend that like the Web are truly world-wide, rather than country-bound, may provide one vital step.
Memorials for Danny Lewin include a page attesting his ardent humor maintained by MIT, and a page at Akamai. The ACM STOC Best Student Paper Award is named for him, and also a square in hailing distance of MIT’s Stata Center. Among online memorials we note CNN’s tribute page for him.
We thank Kleinberg also for contributing a theoretical problem from Akamai days that is still open after these ten years. It is from another paper by Lewin and Leighton, with Mor Harchol-Balter. It concerns how long it takes for all nodes in a weakly-connected directed graph to learn about each other while keeping total communication close to the minimum.
Initially every node knows and can communicate with only its out-neighbors . It can send one-or-more its “address book” of out-neighbors, which then become out-neighbors of too, and/or request the neighbors of , which then become merged with its own address book. Making such requests of every neighbor in every round as the graph’s edges grow, however, uses quadratic communication requests which is too much. Each may choose one neighbor in each round, and either
- “Ask In”: request the address book of .
- “Name-Drop”: push its address book onto .
The latter may seem anti-social, but they show that when is chosen uniformly at random, it works much better than the former: rounds with high probability, versus rounds needed by the former. As their paper’s last page says, the resulting “Name-Dropper Algorithm” was implemented by Akamai.
The open problems are whether in fact every becomes the -clique with high probability in rounds, or whether the basic lower bound can be raised, or whether some other message-passing strategy can do better. The last page also cites a personal communication from Dick asking how important it is that each know the total size of the graph in advance; note that even when knows all nodes it may still need to inform some about them.