Friday, August 14, 2009

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.


proaonuiq said...

I agree with Hendricksoon and Renesse.

Anonymous said...

I don't understand what's special about the rejected STOC paper being accepted to PODC; isn't that a classic case of a paper being rejected from a tier 1 conference and ending up publishing in a tier 2 conference?

Aaron Sterling said...

I'll leave to one side the "tier" of PODC, though I doubt everyone would call it "tier two." My point, in multiple blog posts and comments now, is that people get far too worked up over acceptance/rejection into STOC and FOCS. There is excellent work being published in other conferences -- and, in fact, I've had conversations with "famous"
theoretical computer scientists who have told me they don't read the list of STOC accepted papers, because the material in that conference isn't sufficiently related to their interests.

People take conference rejection far too personally. A PC isn't passing judgment on the inherent quality of the paper -- at least, not necessarily. The PC is saying the submission isn't a good fit for the program they are putting together, in their (necessarily rushed) judgment. So my "special" message is that if you get rejected from somewhere, chill out, upgrade your paper, and resubmit.

Amitabh T said...

Thanks Aaron for the nice post. I would also invite readers to look at my daily guest post from PODC'09 at Jared Saia's blog

Anonymous said...

The average STOC/FOCS pc's have very little expertise in distributed computing, thus the acceptance decision is even more random than in other fields. I'm willing to bet that the quality of the reviews were low.
The same goes for other domains that are not hardcore STOC/FOCS material.

Anonymous said...

And yet, distributed computing papers keep getting submitted to STOC/FOCS. I submit that this is because STOC/FOCS are regarded more highly as TCS venus, and so researchers that come up with (what they believe to be) deep and/or important results submit there.

True, a rejection might be due to a random PC decision. But in this case, why not submit to the next STOC/FOCS? I believe that some rejections more-or-less spell out that the paper will never be accepted to STOC/FOCS, so off to PODC or whatever it goes.

--anon #1

Anonymous said...

There seems to be some confusion, both in this post and in the name "PODC", between distributed computing and parallel computing. My impression is that these are fairly distinct at this point. In particular, parallel programming techniques seem very far away from distributed consensus algorithms. Am I missing something?

Anonymous said...

Regarding the confusion between "distributed" and "parallel": this year PODC ("distributed") was co-located with SPAA ("parallel"). Two of the keynote talks were organised in collaboration between PODC and SPAA.

Anonymous said...

Aaron, thanks for a nice post on PODC. With high probability, I will present a paper in PODC 2010, my first attendance of PODC. Your post gives me a first impression of the conference - more friendly than my advisor told me about the distributed computing community. I made an anonymous comment to protect him:P