Report from PODC 2009 (Guest Post, Aaron Sterling)

Aaron Sterling reports from PODC:

I'm in Calgary, where PODC 2009, the Twenty-Eighth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, has just ended. Lorenzo Alvisi was the Program Chair and Srikanta Tirthapura was the General Chair. However, the clear consensus was that the heroes of the conference were Local Arrangement Chairs Lisa Highman and Philipp Woelfel, who ensured the event ran smoothly, and raised a large amount of money from Canadian sources. This, for example, allowed the organizers to reduce the student registration to $120, and provide significant student support on top of that. Impressive.

My favorite talk of the program was by invited speaker Bruce Hendrickson, who argued for the position that we are in a brand new situation with regard to parallelism in computing -- and not because of "multicore." Rather, he foresaw a growing demand for scientific computation by disciplines (like economics and sociology) that study graphs with fundamentally different structures from the physics-type problems that has previously been the bread and butter of scientific computing. This will require creation of architectures that relate to memory significantly differently, because, to paraphrase Hendrickson, "Computation is limited by memory access, not by processor speed." At the same time, he saw a brand new situation in terms of desktop architecture and programming, because, for the first time ever, "Silicon is essentially free" -- meaning, a chip designer could encode circuitry used by everyone and still have enough space left over to lay down circuitry that would only be used by a small fraction of users, like customers interested in scientific computing. Hendrickson claimed adding this additional functionality would not significantly increase production cost, meaning we are in a brand-new period of architecture design.

Both Hendrickson and invited speaker Robbert van Renesse advocated teaching undergraduates much more about parallelism than is currently in the curriculum. Renesse presented a new method for explaining consensus algorithms step-by-step. The third invited speaker, Sarita Adve -- who also gave a superb presentation -- called more explicitly for the creation of new tools. In particular, she stated the need for new parallel programming languages that would, for example, prevent programmers from constructing data races.

Moving to the refereed program, Christoph Lenzen presented "Tight Bounds
for Clock Synchronization," which won the Best Paper Award. This is joint work with Thomas Locher and Roger Wattenhofer, and is a tour de force, providing tight upper and lower bounds for (both global and local) clock synchronization in a network, finally solving a problem many authors have been working on, in some sense, since the 1980s. Keren Censor won the Best Student Paper Award for "Max Registers, Counters, and Monotone Circuits." This is joint work with Jim Aspnes and Hagit Attiya. I thought Censor gave the best presentation of the conference, out of all the refereed submissions. Her takeaway message was, "Lower bounds do not always have the last word," because she was able to "beat" a lower bound by investigating the proof, and then modifying the shared objects she used so they no longer had the problem the proof technique took advantage of.

Given the blog I'm guestposting on, I cannot resist telling this story. Christoph and I met at DISC 2008, where we both presented papers. We hit it off, and learned that we both intended to submit to STOC 2009, so we laid down a friendly challenge that we would next see each other at STOC. As I posted here previously, my STOC submission was rejected, I upgraded it, submitted it elsewhere, and was quite happy with the result. Christoph's STOC submission was rejected also, and, sure enough, he resubmitted to PODC and won Best Paper for it. So, once again, rejection from a conference is far from the end of the world.

The business meeting was animated. The least controversial
agenda item was the elections. Andrjez Pelc is the new Steering
Committee chair (replacing Faith Ellen), and Jennifer Welch is the new
Steering Committee Member-at-Large (replacing Michel Raynal). There
was extensive discussion on nonbinding votes to give direction to the
Steering Committee. Perhaps of most interest to readers of this blog,
the business meeting voted overwhelmingly that full proofs of results
should be included in future PODC submissions, in an appendix if
appropriate. There was (unresolved) debate over whether to publish
abstracts along with the list of accepted papers. Some people from
industry were opposed to this, because they thought it might start the
"patent clock" a few months earlier. Lastly, I will mention that
there was discussion about whether to separate PODC from the ACM,
because of concerns that ACM was not providing value for the amount of
money they were charging the conference. No consensus was reached
here, but there were definitely strong opinions.

PODC 2010 will be organized by Roger Wattenhofer in Zurich.
I'm sure it will be great, but he has a tough act to follow.