The Distributed Prize

And a ‘new’ computing ‘blog’ with over 1,300 sizable ‘posts’ unearthed

Edsger Dijkstra contributed to many aspects of computing. His name is attached to Dijkstra’s Algorithm, of course, but his 1972 Turing Award citation does not mention it. His 1974 paper on self-stabilization of distributed programs won the Influential Paper Award awarded during the annual ACM Principles of Distributed Computing (PODC) conference in July 2002. The award was subsequently co-sponsored by the EATCS Symposium on Distributed Computing (DISC) and named for Dijkstra after he passed away a month later in 2002.

Today we recognize this year’s winners.

This year’s prize lives up to its subject by being well-distributed. There are no fewer than 7 winners: Michael Ben-Or, David Chaum, Claude Crepeau, Ivan Damgard, Shafi Goldwasser, Tal Rabin, and Avi Wigderson. They clustered into the following three papers, Ben-Or twice:

1. Completeness Theorem for Non-Cryptographic Fault-Tolerant Distributed Computation, by Michael Ben-Or, Shafi Goldwasser and Avi Wigderson.

2. Multiparty Unconditionally Secure Protocols, by David Chaum, Claude Crepeau and Ivan Damgard.

3. Verifiable Secret Sharing and Multiparty Protocols with Honest Majority, by Tal Rabin and Michael Ben-Or.

Previous Winners

This is indeed the most concurrent winners of the award in its history. Previous years saw:

• 2022: Maged Michael, Maurice Herlihy, Victor Luchangco, Mark Moir.

• 2021: Paris Kanellakis, Scott Smolka.

• 2020: Dana Angluin, James Aspnes, Zoe Diamadi, Michael Fischer, Rene Peralta.

• 2019: Alessandro Panconesi, Aravind Srinivasan.

• 2018: Bowen Alpern, Fred Schneider,

• 2017: Elizabeth Borowsky, Eli Gafni.

• 2016: Noga Alon, Laszlo Babai, Alon Itai, Michael Luby.

• 2015: Michael Ben-Or, Michael Rabin.

• 2014: Kanianthra M. Chandy, Leslie Lamport.

• 2013: Nati Linial.

• 2012: Maurice Herlihy, J. Eliot Moss, Nir Shavit, Dan Touitou.

• 2011: Hagit Attiya, Amotz Bar-Noy, Danny Dolev.

• 2010: Tushar Chandra, Vassos Hadzilacos, Sam Toueg.

• 2009: Joseph Halpern, Yoram Moses.

• 2008: Baruch Awerbuch, David Peleg.

• 2007: Cynthia Dwork, Nancy Lynch, Larry Stockmeyer.

• 2006: John Mellor-Crummey, Michael Scott.

• 2005: Marshall Pease, Robert Shostak, Leslie Lamport.

• 2004: Robert Gallager, Pierre Humblet, Philip Spira.

• 2003: Maurice Herlihy.

• 2002: Edsger Dijkstra.

• 2001: Michael Fischer, Nancy Lynch, Michael Paterson.

• 2000: Leslie Lamport.

This is also the first year when more than two papers have been recognized. We have not indicated which of the prior years are for two papers and which for only one. This sets up a puzzle for those who take idle pleasure in framing questions about lists of names:

Why is one line before 2022 listed out of alphabetical order?

Another fun question is, who is related to another winner? Note from the example here that ChatGPT 3.5, or even GPT 4.0, might not be able to help you answer this reliably.

Dijkstra’s Mode of Distribution

Dijkstra was famously averse to technology in his personal life. He never used a word processor, not even TeX, to prepare papers. Even after he became accustomed to a manual typewriter, he increasingly often handwrote his manuscripts. Nor did he employ anyone to type them up, or to prepare correspondence on departmental letterhead at UT Austin where he taught from 1984 on. There is a font that replicates his clear hand-printing.

He also gave all his university lectures as chalk talks. His polestar was that proper structure of thought optimized learning. He was absorbed in how to present mathematical proofs in programmatic form. He used rhetorical pauses to highlight the structure and to involve his listeners in how to build the framework for the next stage of argument. Anything he subsequently said had to bear full weight. He did his own grading and often handwrote copious comments on individual assignments.

He did purchase a Macintosh computer and use it for email and browsing the World Wide Web, such as it was before 2002. This was before the idea of blogging really took off. I do not know if that way of circulating his ideas ever occurred to him. He was never shy about circulating his ideas.

Instead, the best word to describe how he circulated his ideas—even what became his published papers—is samizdat. He would handwrite or sometimes type manuscripts and pass them in hardcopy to selected friends and colleagues, originally including his contacts at the Burroughs Corporation. They would get Xeroxed and passed around. Only some got published, but with Dijkstra’s own fanout averaging about 20 and further replication by his recipients, they were available to others who sought them.

The EWD “Blog”

One saving grace is that in the manner of the catalogs of classical composers he admired, he numbered every manuscript. The number was written after his initials EWD. For instance, the source for his famous 1968 “Go To Statement Considered Harmful” article is EWD215. The numbering facilitated the later gathering of many—not all—of his manuscripts.

These are available and cross-indexed at the E. W. Dijkstra Archive maintained by UT Austin. In all there are 1,318 of them, reckoned as over 7,700 physical pages. They range from fictional fantasies to travelogues to professional opinions to pathbreaking technical work that saw the light of day. I had forgotten about this and Ken was unaware, so our realization hits with sudden force:

This is essentially the first high-volume personal computing blog.

To compare more with GLL: We are nearing but not yet over the 1,100 mark. Ken and I compose in LaTeX with a goal of limiting posts to 5 small-size pages: 4-inch lines and 7.5-inch text height in the default article style. This post is 4.5 pages including the photos. Some like the last post are longer. Dijkstra went up to 15 pages per post, but some are less than a page. Overall our notions of “page” seem similar by volume. So in that measure, too, we stand at about 5,500—maybe 6,000—to Dijkstra’s 7,700. Still quite a ways to go to catch him.

The archive is also searchable. I have five mentions—and maybe you can guess what they are mainly about from what we’ve written above about Dijkstra’s approach to proofs. The stem one is in EWD638 and is sharp enough to be mentioned in both the wonderful UT memorial to Dijkstra and in Krzysztof Apt’s 2010 appreciation. I may as well quote the source, which bears the underlined title “A political pamphlet from the Middle Ages”:

This note concerns a very ugly paper [1]. Its authors seem to claim that trying to prove the correctness of programs is a futile effort and, therefore, a bad idea.

Of course, [1] = my paper with Rich de Millo and Alan Perlis, “Social Processes and Proofs of Theorems and Programs,” which we last debated here.

There is also a live blog on Dijkstra, which is written by Edgar Graham Daylight. The UT archive gives the title or head matter of each MS, but Daylight organizes by topics that seem closer to themes we would address here. he runs his own developments alongside his channeling of what he calls Dijkstra’s “rallying cries.”

Open Problems

I should also mention that David Parnas played a major role in distributed computing. He was my PhD advisor—years ago. See the reference list for a connection through Alan Perlis to Parnas to me and other PhDs.

[inserted “besides 2022”; other slight edits]