The 2022 Turing Award

Source with photo by Kim Kulish

Simple. More in a moment.

The Insight

The concept of Ethernet has its roots in the late 1960s and the University of Hawaii’s Aloha Network. Aloha was a radio-communications network connecting the Hawaiian Islands to a central computer on the main campus, in Oahu.

Aloha was often referred to as one of the first wireless packet networks. It used two radio frequencies, separating send and receive data that passed between user terminals and the main hub connected to the computer. Designed for simplicity, the network followed two key rules:

• Send a packet when you’re ready and wait for a receipt acknowledgement.

• If no acknowledgement occurs, resend at some random time.

Kind of like:

Talk before you listen.

As use of the network grew, it became obvious that packet collision would severely limit the capacity of the network. Researching the problem for his doctoral thesis, Bob Metcalfe devised a solution. His innovation earned him not only his Harvard Ph.D. but a place in history as the inventor of the Ethernet. Metcalfe’s solution: Listen before you talk. Simple insight, but brilliant insight. Here’s how it led to the Turing Award.

How It Worked

The two methods are either Talk-Listen or Listen-Talk. The point is that under reasonable traffic the first method can essentially stop totally while the second will continue to get some information thru.

• Talk-Listen: Imagine some packet is in progress and someone else talks. Then the two packets are destroyed. This can happen at a high enough rate so that essentially all traffic fails.

• Listen-Talk: Imagine some packet is in progress. Then others will listen and they will not send. Thus the information will get thru.

Is there extra work for listening for the proximity of something that might not get delivered to you? Yes. But the local effort to listen is linear. Moreover, the expected enforced delay is a constant—it goes as the local network load. Any impact on rate can thus be more-than-compensated by improvements in the base speed of hardware.

Good Laws and Bad Predictions

Metcalfe is among those we’ve sometimes blogged about who have a “law” named for them. Metcalfe’s Law, in its original form, states

The value of an -user network scales as .

This makes sense on the face of it: if the network is connecting peer users then each avails connections of equal value. The equal-value assertion was rejected in a 2006 paper by Robert Briscoe, Andrew Odlyzko, and Benjamin Tilly, who argued that value scales as . Recent studies of large-scale network usage, however, have inclined toward the higher rate—including a 2013 paper by Metcalfe himself.

Metcalfe is also known for a spectacularly wrong prediction. He wrote in 1995 that owing to an expected overload as people tried to connect, the Internet would “go spectacularly supernova and in 1996 catastrophically collapse.” It did not. He later jokingly ate his words on a paper copy of the article including this comment and swallowing it before the audience of a keynote speech.

According to this telling, his view of the overload was that would grow exponentially, not that order- usage would overwhelm it. He had, after all, designed Ethernet to scale up.

Open Problems

While on the subject of predictions, we wonder whether Turing Awards are any easier to predict than Oscars for film or Nobels in science. Some insights into the makeup of Turing Awards are in this paper, including this rundown of winners by university affiliation at the time of the main cited work:

• Stanford University 22

• Massachusetts Institute of Technology 19

• University of California, Berkeley 13

• Carnegie Mellon University 10

• Princeton University 7

• Harvard University 7

• New York University 5

• University of Oxford 4

• University of Toronto 4

• Weizmann Institute of Science 3

• Cornell University 3

• University of Edinburgh 2