(For PDF version of program: click here)

Sunday, June 5

18:00 - 19:15 FCRC Plenary Session

2010 ACM Turing Award Winner Leslie G. Valiant (Harvard University)

Monday, June 6

08:00-09:00 Breakfast

08:50-09:00 Opening

09:00 - 10:00 Session 1 (Consensus and Agreement) chair: Pierre Fraigniaud

Coordinated Consensus in Dynamic Networks
Fabian Kuhn, Yoram Moses and Rotem Oshman

Error-Free Multi-Valued Consensus with Byzantine Failures
Guanfeng Liang and Nitin Vaidya

Byzantine Agreement with Homonyms
Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert and Hung Tran-The

10:00-10:20 Coffee Break

10:20 - 11:20 Session 2 (Local Algorithms) chair: Michael Elkin

Distributed Coloring in Few Rounds
Kishore Kothapalli and Sriram Pemmaraju

MIS on Trees
Christoph Lenzen and Roger Wattenhofer

Toward more Localized Local Algorithms: Removing Assumptions concerning Global Knowledge
Amos Korman, Jean-Sebastien Sereni and Laurent Viennot

11:30 - 12:30 FCRC Plenary Session

IBM's Watson/DeepQA David A. Ferrucci (IBM)

12:30 - 13:30 Lunch

14:00 - 15:20 Session 3 (Reliable and Robust Algorithms) chair: Mark Moir

The Complexity of Robust Atomic Storage
Dan Dobre, Rachid Guerraoui, Matthias Majuntke, Neeraj Suri and Marko Vukolić.

Resilience of Mutual Exclusion Algorithms to Transient Memory Faults
Thomas Moscibroda and Rotem Oshman.

Structuring Unreliable Radio Networks
Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch and Calvin Newport

The Impact of Memory Models on Software Reliability in Multiprocessors
Alexander Jaffe, Thomas Moscibroda, Laura Effinger-Dean, Luis Ceze, and Karin Strauss

15:30-16:00 Coffee Break

16:00 - 17:00 Session 4 (Coherency and Concurrency) chair: Faith Ellen

On The Power of Hardware Transactional Memory to Simplify Memory Management
Aleksandar Dragojevic, Maurice Herlihy, Yossi Lev and Mark Moir.

A Complexity Separation Between Cache-Coherent and Distributed Shared Memory Models
Wojciech Golab.

From Bounded to Unbounded Concurrency Objects and Back
Yehuda Afek, Adam Morrison and Guy Wertheim.

17:00-17:10 Break

17:10 - 18:00 Session 5 (Best Papers) chair: Yehuda Afek

Best Student Paper:
Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence Leonid Barenboim and Michael Elkin.

Best Paper:
The Space Complexity of Long-Lived and One-Shot Timestamp Implementations Maryam Helmi, Lisa Higham, Eduardo Pacheco and Philipp Woelfel.

18:00 - 20:00 PODC Business Meeting

Tuesday, June 7

08:00-09:00 Breakfast

09:00-10:00 Session 6 (Compact or Sparse Distributed Structures) chair: Amos Korman

Compact Policy Routing
Gábor Rétvári, András Gulyás, Zalán Heszberger and Márton Csernai.

Locally checkable proofs
Mika Göös and Jukka Suomela.

Fault-Tolerant Spanners: Better and Simpler
Michael Dinitz and Robert Krauthgamer.

10:00-10:20 Coffee Break

10:20-11:20 Session 7 (Security and Consistency) chair: Dahlia Malkhi

Adaptively Secure Broadcast, Revisited
Juan Garay, Jonathan Katz, Ranjit Kumaresan and Hong-Sheng Zhou.

Scalable Rational Secret Sharing
Varsha Dani, Mahnush Movahedi, Yamel Rodriguez and Jared Saia.

Analyzing consistency properties for fun and profit
Wojciech Golab, Xiaozhou Li and Mehul Shah.

11:30 - 12:30 FCRC Plenary Session

Algorithms: Recent Highlights and Challenges Ravi Kannan (Microsoft Research)

12:30-13:30 Lunch

14:00-15:30 Session 8 (Brief Announcements) chair: Phillip Gibbons

Brief Announcement: Distributed k-Core Decomposition
Alberto Montresor, Francesco De Pellegrini and Daniele Miorandi.

Brief Announcement: Fork-Consistent Constructions From Registers
Matthias Majuntke, Dan Dobre and Neeraj Suri.

Brief Announcement: Unbounded Contention Resolution in Multiple-Access Channels
Antonio Fernandez Anta, Miguel A. Mosteiro and Jorge Ramón Muñoz.

Brief Announcement: Tracking Distributed Aggregates over Time-based Sliding Windows
Graham Cormode and Ke Yi.

Brief Announcement: Accurate Byzantine Agreement with Feedback
Bharath Balasubramanian, John Bridgman and Vijay Garg.

Brief Announcement: B-Neck: A Distributed and Quiescent Max-min Fair Algorithm
Alberto Mozo Velasco, José Luis López-Presa and Antonio Fernandez Anta.

Brief Announcement: Time-Optimal Information Exchange on Multiple Channels
Stephan Holzer, Yvonne Anne Pignolet, Jasmin Smula and Roger Wattenhofer.

Brief Announcement: Robust Data Sharing with Key-Value Stores
Cristina Basescu, Christian Cachin, Ittay Eyal, Robert Haas and Marko Vukolić

Brief Announcement: Network Synchronization and Localization based on Stolen Signals
Christian Schindelhauer, Zvi Lotker and Johannes Wendeberg.

Brief Announcement: Solvability of Regular Registers in Dynamic Distributed Systems with Byzantine Processes
Roberto Baldoni, Silvia Bonomi and Amir Soltani Nezhad.

Brief Announcement: Easy Impossibility Proofs for k-Set Agreement in Message Passing Systems
Martin Biely, Peter Robinson and Ulrich Schmid.

Brief Announcement: Solving the At-Most-Once Problem with Nearly Optimal Effectiveness
Sotirios Kentros and Aggelos Kiayias.

15:30-16:00 Coffee Break

16:00-17:00 Session 9 (Distributed Algorithms) chair: James Aspnes

Transforming Worst-case Optimal Solutions for Simultaneous Tasks into All-case Optimal Solutions
Yoram Moses, Mark Tuttle and Maurice Herlihy.

Optimal-Time Adaptive Tight Renaming, with Applications to Counting
Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert and Morteza Zadimoghaddam.

The Round Complexity of Distributed Sorting
Boaz Patt-Shamir and Marat Teplitsky.

17:00-17:10 Break

17:10-18:10 Session 10 (Communication and Congestion) chair: Yoram Moses

A tight unconditional lower bound on distributed random walk computation
Danupon Nanongkai, Atish Das Sarma and Gopal Pandurangan.

Minimum Congestion Mapping in a Cloud
Nikhil Bansal, Kang-Won Lee, Viswanath Nagarajan and Murtaza Zafer.

Conflict on a Communication Channel
Valerie King, Jared Saia and Maxwell Young.

19:00-22:00 Banquet

Wednesday, June 8

08:00-09:00 Breakfast

09:00-10:00 Session 11 (Brief Announcements) chair: Jared Saia

Brief Announcement: The Universe of Symmetry Breaking Tasks
Damien Imbs, Sergio Rajsbaum and Michel Raynal.

Brief Announcement: Rationality Authority for Provable Rational Behavior
Shlomi Dolev, Panagiota N. Panagopoulou, Mikael Rabie, Elad Michael Schiller and Paul G. Spirakis.

Brief Announcement: Secure Datastructures based on Multiparty Computation
Tomas Toft.

Brief Announcement: Robust Network Supercomputing Without Centralized Control
Seda Davtyan, Kishori Konwar and Alexander Shvartsman.

Brief Announcement: On the Hardness and Approximation of Minimum Topic Connected Overlay
Monika Steinová.

Brief Announcement: A Generalization of Multiple Choice Balls-into-Bins
Gahyun Park.

Brief Announcement: A Theory of Goal-Oriented Communication
Oded Goldreich, Brendan Juba and Madhu Sudan.

10:00-10:20 Coffee Break

10:20-11:20 Session 12 (Self-* Systems) chair: Boaz Patt-Shamir

Xheal: Localized Self-Healing Using Expanders
Gopal Pandurangan and Amitabh Trehan

Fast and Compact Self-Stabilizing Verification, Computation, and Fault Detection of an MST
Amos Korman, Shay Kutten and Toshimitsu Masuzawa.

Stability of a Peer-to-Peer Communication System
Ji Zhu and Bruce Hajek.

11:30-12:30 FCRC Plenary Session

Warehouse-Scale Computing: Entering the Teenage Decade Luiz Andre Barroso (Google)

12:30-13:30 Lunch

14:00-15:30 Session 13 (Brief Announcements) chair: Pierre Fraigniaud

Brief Announcement: Scalability versus Semantics of Concurrent FIFO Queues
Hannes Payer, Harald Roeck, Christoph Kirsch and Ana Sokolova.

Brief Announcement: Distributed Computing with Rules of Thumb
Aaron D. Jaggard, Michael Schapira and Rebecca Wright.

Brief Announcement: Incentive-Compatible Distributed Greedy Protocols
Noam Nisan, Michael Schapira, Gregory Valiant and Aviv Zohar.

Brief Announcement: Sustaining Collaboration in Multicast despite Rational Collusion
Haifeng Yu, Phillip Gibbons and Chenwei Shi.

Brief Announcement: Reliable end-user communication under a changing packet network protocol
Brendan Juba.

Brief Announcement: Securing Social Networks
Michael Backes, Matteo Maffei and Kim Pecina.

Brief Announcement: Parallel and distributed programming extensions for mainstream languages based on pi-calculus primitives
Patrick Viry.

Brief Announcement: A Nonblocking Set Optimized for Querying the Minimum Value Yujie Liu and Michael Spear.

Brief Announcement: Time Bounds for Shared Objects in Partially Synchronous Systems
Jiaqi Wang, Jennifer Welch and Hyunyoung Lee.

Brief Announcement: The Inherent Difficulty of Timely Primary-Backup Replication
Pramod Koppol, Kedar Namjoshi, Thanos Stathopoulos and Gordon Wilfong.

Brief Announcement: Randomized Compact Routing in Decomposable Metrics
Goran Konjevod, Andrea Richa, Donglin Xia and Ling Zhou.

Brief Announcement: Partial Reversal Acyclicity
Tsvetomira Radeva and Nancy Lynch.

15:30-16:00 Coffee Break

16:00-17:20 Session 14 (Information Dissemination) chair: Fabian Kuhn

Tight Bounds on Information Dissemination in Sparse Mobile Networks
Alberto Pettarin, Andrea Pietracaprina, Geppino Pucci and Eli Upfal.

Order Optimal Information Spreading Using Algebraic Gossip
Chen Avin, Michael Borokhovich, Keren Censor-Hillel and Zvi Lotker.

Time-efficient randomized multiple-message broadcast in radio networks
Majid Khabbazian and Dariusz Kowalski.

Network Coding: Beating Token Forwarding Lower Bounds in Dynamic Networks
Bernhard Haeupler and David Karger.

17:20-17:30 Closing

17:30 End of Symposium