Review of PODC 2012

Siddhartha Sen

Department of Computer Science
Princeton University
sssix@cs.princeton.edu

This report appeared in Distributed Computing Column, SIGACT News 43(4) December 2012, pp. 98-122 edited by Idit Keidar and is reprinted here by permission of author Siddhartha Sen.

The 31st Annual ACM Symposium on Principles of Distributed Computing (PODC) took place on July 16 – 18, 2012 in Madeira, Portugal, an archipelago in the Atlantic Ocean about 1,000 km of the European continent. This makes it arguably the most exotic location in PODC’s 31-year history! When the view from your hotel and a stroll with your colleagues look like the pictures below, the conference transforms into a rejuvenating retreat, the kind that fosters great ideas and makes you forget (for a while) that you have to give that talk on the third day.

 Figure 1: (left) A tourist-carrying galleon seen from the conference hotel, CS Madeira Atlantic Hotel and Sea Spa. (right) Walking by the water towards the conference banquet.

PODC was co-located with three interesting workshops: the 8th International Workshop on Foundations of Mobile Computing (FOMC), the 6th Workshop on Large Scale Distributed Systems and Middleware (LADIS), and the 4thWorkshop on the Theory of Transactional Memory (WTTM). The workshops took place on July 18 – 19 and were attended by many of the PODC participants, who were happy to extend their stay in Madeira. This review focuses on the PODC conference.

In a nutshell, the PODC program consisted of the following: 2 keynote talks, one of which was held jointly with the LADIS workshop, 1 invited industry session, 11 full paper sessions, 3 brief announcements sessions, 3 lunches, 1 business meeting, 1 wine tasting, and 1 banquet. Amazingly, there was still time for participants to go for a swim in the ocean!

We begin by reviewing the research elements of the program, and then review the fun elements (including awards). We’ll end by thanking the hardworking individuals who made PODC 2012 such a smooth and enjoyable experience.

Research Program

While primarily a theoretical venue, in recent years PODC has become increasingly interested in the best practices of large-scale industry systems. This year’s program featured an invited industry session with talks from Oracle Labs and Facebook, a keynote talk on bringing theoretical rigor to software-defined networking, and a keynote talk underscoring the difficulty of analyzing realistic wireless communication models. Indeed, bridging theory and practice is difficult to do in practice, and is something I am personally deeply interested in. The problem, as the invited speakers attested, is that often one side is more tractable or interesting than the other, leading to oversimplification or even neglect of the other side. Nevertheless, this kind of research is important because it keeps theory relevant and practice well-founded, and conferences like PODC are gradually making it more mainstream. All theory and no practice, and vice versa, make Jack a dull boy!

Keynote talks

David Peleg gave the first talk of the conference with his keynote “Towards an Algorithmically Usable SINR Model for Wireless Communication”. In the signal to interference plus noise ratio (SINR) model, the energy of a wireless signal fades with some power of the distance, and a receiver successfully receives a message only if the signal is strong enough to overcome interference from simultaneous transmissions and background noise. SINR diagrams map the successful reception zones of transmitting stations in the plane; unfortunately, Peleg observed, they are theoretically not well understood. Most prior works study simplified models that abstract away any interference-related complications, making them easier to analyze but much less realistic. Peleg and his colleagues [2] brave the theory-practice gap and prove some basic properties about SINR diagrams, like the fact that reception zones are convex if transmissions have uniform power. They use this to develop an efficient approximation algorithm for answering point location queries.

Scott Shenker gave the second keynote, “Software-Defined Networking: History, Hype, and Hope”, on the third day in a joint session with LADIS. This talk was not so much about bridging a theory-practice gap, as it was a call for theoretical rigor in a practice that has become too complicated and ad hoc. Software-defined networking (SDN) decouples the network’s control plane logic from its data plane forwarding state, allowing software controllers like NOX [4] to program commodity network switches via interfaces like OpenFlow [7]. Shenker argues that the control plane has evolved to an ad hoc mess of protocols, and with networks hitting their complexity limits (a single datacenter can have 100,000 machines and 10,000 switches!), a theoretical intervention is needed. He believes the PODC community is well-poised to build abstractions for the control plane. Specifically, he wants abstractions for computing and specifying the distributed state of switches – state that correctly routes packets – subject to unreliable communication and failures.

Figure 2: (left) Peleg giving his keynote. (right) The daily lunch, with beautiful outdoor seating.

Industry session

Two invited industry talks started the second conference day, and both presented interesting and sometimes unexpected facts from the field. Dave Dice from Oracle Labs spoke about practical synchronization techniques used in heavily-threaded Java software stacks. Locks are widely used here, techniques like barriers and lock-free structures are rare, and wait-free synchronization is nonexistent. Dice made an interesting observation that the locks used in practice are actually quite unfair; for example, admission may be strongly tied to cache coherence arbitration in hardware. These locks sacrifice short-term fairness for aggregate throughput, by favoring threads that are “hot” or resident in cache (context switches are expensive, costing 5,000+ cycles). One example are the cohort locks devised by Dice and his colleagues, which explicitly avoid lock migration across node sockets of a multi-core NUMA system.

Harry Li from Facebook gave the second talk, which was about practical consistency trade-offs at Facebook. Facebook has over a billion users, and uses an in-memory distributed cache that processes a billion operations per second. Their top priority is to ensure a fast, reliable, and consistent user experience. They use a geographically-diverse architecture of master and slave regions, where each region has its own web, cache, and database clusters. A slave region only serves read requests and uses MySQL replication to synchronize its database with the master, reducing a 70ms crosscountry access to 2ms. Though Facebook only guarantees eventual consistency, they use a neat trick to ensure a user reads her writes: if the user recently updated data, her subsequent requests are redirected to the master region for some time. Li’s talk reminded me of other geo-replicated storage systems like COPS [6] and Google’s Spanner [3], which provide causal consistency and linearizability, respectively. Spanner runs Paxos over the wide area! It is fascinating how demands for stronger consistency are pushing traditionally local-area protocols to the Internet.

Technical sessions

First, some statistics. PODC 2012 received 142 full paper submissions and accepted 35 (24.5%), compared to the 34/129 papers accepted in 2011. There were a total of 26 brief announcements. The most popular topics by submission were “fault tolerance”, “wireless and mobile”, and “graph algorithms”. Topics like “cluster and cloud computing” and “internet and social networks” were quite low on the list, but will hopefully move up in future years. The top submitting countries by affiliation were the United States, Israel and France, the same as last year, but this year the 4th spot went to Spain instead of Switzerland. We cannot possibly do justice to the wealth of ideas and contributions in the proceedings in this short review. We refer the reader to [1] for the full papers and extended abstracts. What follows is a breeze through the various sessions with a few sprinkled comments from my perspective.

The first and last sessions of the conference were on shared memory. Aspnes gave an energetic talk on faster randomized consensus algorithms in a shared-memory model with an oblivious adversary. Reading the introductions of his paper was very useful, because the sheer number of models used in consensus can make your head spin otherwise. Giakkoupis and Woelfel study randomized test-and-set implementations in asynchronous shared memory models. Besides proving new time and space upper bounds, they also prove the first non-trivial space complexity lower bound for test-and-set. This paper won the Best Paper Award.

The session on information spreading and random walks included a paper on coalescing random walks, where independent random walks merge upon meeting at a graph vertex. The abstract idea of “coalescence” appears in a suprising number of fields, including population genetics and Bose-Einstein statistics.

The session on communication complexity discussed diverse problems, including distributed task allocation, multiparty communication subject to faults, and cooperative biological ensembles. The proofs in these papers are always quite neat because they involve a decoder Bob (with apparently psychic powers) who is able to do more than what is information-theoretically possible.

Continuing the practical spirit of the invited speakers, the session on wait freedom included an algorithm for solving a generalization of lattice agreement that facilitates building replicated state machines whose update commands commute. A variety of recent systems have leveraged the power of commutative data types [8] to avoid concurrency control and conflict resolution.

Given the rise of side-channel attacks on computer memory, such as the cold-boot attack [5], it was nice to see a paper on this topic in the session on game theory and security. Akavia et al. devise distributed public key schemes that are secure against continual memory leakage, even leakage that occurs while the secret keys are being refreshed.

Figure 3: Bridging the theory-practice gap: (left) learning about Madeira wine; (right) tasting it.

In the session on locality, Göös et al. proved that for a large class of problems on boundeddegree graphs, including vertex covers and edge dominating sets, local algorithms (constant-time distributed algorithms) that achieve constant-factor approximations with the help of unique identi fiers can do so without this help. Their paper was co-winner of the Best Student Paper award. Holzer and Wattenhofer also tackled a distributed graph problem in the session on distributed algorithms. They give an algorithm for all pairs shortest paths that runs on O(n) rounds, which is optimal. They also present lower and upper bounds for approximating the diameter of a graph.

The session on ad-hoc networks covered problems in different wireless models. It is instructive to compare these models to the SINR model in Peleg’s keynote, to understand the choices that were made to trade off reality with tractability. The session on load balancing and scheduling also included a paper by Kesselheim on dynamic packet injection in wireless networks. The model he considers is quite general and covers virtually all interference models, including the SINR model.

The session on fault tolerance featured some elegant insights. Herlihy and Rajsbaum made the simple yet elegant observation that it is more important to know that one model of distributed computation simulates another, than to explicitly construct the simulation. They define simulation with respect to colorless tasks using combinatorial topology, and show how to prove they exist without finding them. Taubenfield generalized the traditional “all-or-nothing” notion of fault tolerance to count the number of correct processes that terminate properly. Studying a slew of classical problems with this new notion, he shows that some have solutions which guarantee that most correct processors properly terminate despite any number of faults, whereas others can’t even guarantee that one correct processor properly terminates despite just one fault.

Moving to the malicious setting, the session on Byzantine Agreement analyzed the power of non-equivocation in reducing replication costs. Clement et al. showed that non-equivocation alone does not reduce the number of processors required for asynchronous reliable broadcast, but that the addition of transferable authentication (e.g. digital signatures) does. Sen et al. apply 3-processor partial broadcast channels to a variety of models and show that Byzantine Agreement is possible for all n = 2f+1, 2f+2, …, 3f, where n is the number of processors needed to tolerate f faults. They give asymptotically tight bounds on the number of necessary and sufficient 3-processor channels. Their paper was the other co-winner of the Best Student Paper award.

There were three brief announcement sessions spread over the three conference days. I particularly enjoy these sessions because they are like a rapid fire of ideas and topics aimed at your brain. Some of the problems considered include computing without any communication, queuing in highly dynamic networks, scalable secure multiparty communication, Internet-scale and human computing, a tight lower bound for randomized mutual exclusion, network formation games that generate realistic networks, and failure detectors that equalize models of computation. If you are tired after reading that list, then you know what it’s like to sit in one of these sessions!

Figure 4: (left) Rooftop cocktail hour before dinner. (right) The dinner.

Fun Program

The organizers of PODC interspersed fun activities throughout the technical program, giving participants time to socialize, enjoy the outdoors, and digest their meals and theorems. Even the daily buffet lunches were exalted by excellent views from the hotel’s seaside facade. Below is a photo-guided run-down of the fun events at PODC!

Dijsktra award

Yes, awards are part of the fun program, because the hard work has already been done! This year, the prestigious Edsger W. Dijkstra Prize in Distributed Computing was awarded at PODC. The prize is given to oustanding papers on the principles of distributed computing whose impact has been evident for over a decade. The 2012 recipients were Maurice Herlihy and J. Eliot B. Moss for their paper “Transactional Memory: Architectural Support for Lock-Free Data Structures”; and Nir Shavit and Dan Touitou for their paper “Software Transactional Memory”. Given the pervasive impact of transactional memory today, from software runtimes to compilers like gcc to hardware implementations like Intel’s, this award could truly not be more deserved.

Wine tasting

At the end of the first day, PODC participants were escorted to a wine tasting at the Instituto Do Vinho Da Madeira. There, we tasted the famous Madeira wine, both sweet and dry versions, and heard a presentation about the wine’s history. Madeira wine is uniquely known for its estufagem aging process, which simulates the effect of long sea voyages through tropical climates. Being a fortified wine, the estufagem process can last up to 100 years! A wine tasting before dinner implies rapid inebriation, so it was an interesting (random) walk (stumble) back home.

Business meeting

Our PC Chair Alessandro Panconesi ran the business meeting, which was full of statistics about the submission process and the budget, accompanied by interesting local refreshments. The student grant program this year was particularly generous, more so than any conference (both theory and systems) I have been to.

At the meeting, Alexander Shvartsman was unanimously elected as chair of the steering committee, replacing Andrzej Pelc. Looking forward, Gadi Taubenfeld will be the PC Chair of PODC 2013, which will take place in Montreal, Quebec, Canada, on July 22 – 24. Banquet and awards The conference banquet was held at the nearby Restaurante do Forte. The dinner began with a cocktail hour atop the restaurant, which had fantastic views of Madeira and the ocean. As with all other meals at the conference, the banquet was filled with good food and good company. Around dessert time, Alessandro Panconesi announced this year’s award papers. The Best Student Paper award was given to two papers: Mika Göös, Juho Hirvonen, and Jukka Suomela received it for their paper “Lower Bounds for Local Approximation”; and Alexander Jaffe, Thomas Moscibroda, and Siddhartha Sen received it for their paper “On the Price of Equivocation in Byzantine Agreement”. The awards were given by Maria da Graca Lus of Madeira’s Regional Secretariat for Culture, Tourism, and Transportation, whose presence elevated the event.

Though technically not part of PODC’s fun program, an interesting (but dramatic) event took place the following day during the LADIS banquet. A fire broke out atop the Madeira hills, and while the locals told us this was a common occurrence, it eventually spread to an unprecedented size. Fortunately, no one was injured during the event, though several homes were affected. It was an amazing thing to see.

Figure 5: A massive fire broke out on the island on July 18, seen here from the LADIS banquet.

Thank You

PODC would not have been the fantastic conference it was without the work of Alessandro Panconesi and the Program, Conference, and Steering Committee members. Special thanks go to Oksana Denysyuk and Lus Rodrigues for their amazing job with the local arrangements. They were visible at every corner, making things run smoothly for everyone. We can’t thank all of you enough!

References

1. PODC ’12: Proceedings of the 2012 ACM symposium on Principles of distributed computing, 2012. General Chair: Dariusz Kowalski; Program chair: Alessandro Panconesi.
2. C. Avin, Y. Emek, E. Kantor, Z. Lotker, D. Peleg, and L. Roditty. SINR diagrams: Convexity and its applications in wireless networks. Journal of the ACM, 59(4):18, 2012.
3. J. Corbett, J. Dean, M. Epstein, C. Frost, J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford. Spanner: Google’s globally-distributed database. In Proc. Symposium on Operating System Design and Implementation, 2012.
4. N. Gude, T. Koponen, J. Pettit, B. Pfaff, M. Casado, N. McKeown, and S. Shenker. NOX: towards an operating system for networks. ACM Computer Communication Review, 38(3):105-110, 2008.
5. J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, A. J. Feldman, J. Appelbaum, and E. W. Felten. Lest we remember: cold-boot attacks on encryption keys. Communications of the ACM, 52(5):91-98, 2009. ACM SIGACT News 110 December 2012 Vol. 43, No. 4
6. W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen. Don’t settle for eventual: scalable causal consistency for wide-area storage with COPS. In Proc. ACM Symposium on Operating Systems Principles 2011, pages 401-416, 2011.
7. N. McKeown, T. Anderson, H. Balakrishnan, G. M. Parulkar, L. L. Peterson, J. Rexford, S. Shenker, and J. S. Turner. Openflow: enabling innovation in campus networks. ACM Computer Communication Review, 38(2):69-74, 2008.
8. M. Shapiro, N. Preguica, C. Masquero, and M. Zawirski. Conflict-free replicated data types. In International Symposium on Stabilization, Safety and Security of Distributed Systems, pages 386-400, 2011.