(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.