Program in pdf.

    Sunday August 9    

17:30-20:30 Reception (Nickle Arts Museum)

    Monday August 10    

Regular Papers (ICT 121)
Session Chair: Maurice Herlihy

08:20 Preventing versus Curing: Avoiding Conflicts in Transactional Memories
Aleksandar Dragojevic, Rachid Guerraoui, Anmol V. Singh, Vasu Singh

08:45 Dynamic Atomic Storage Without Consensus
Marcos Aguilera, Idit Keidar, Dahlia Malkhi, Alexander Shraer

09:10 Randomized Mutual Exclusion in O(log N/log log N) RMRs
Danny Hendler, Philipp Woelfel

09:35 Max Registers, Counters, and Monotone Circuits
James Aspnes, Hagit Attiya, Keren Censor

Coffee Break (Foyer ICT 121/122) 10:00-10:30

Brief Announcements (ICT 121)
Session Chair: Fabian Kuhn

10:30 Stateless Distributed Algorithms for Generalized Packing Linear Programs
Baruch Awerbuch, Zhenghua Fu, and Rohit Khandekar

10:35 Concurrent Non-commutative Boosted Transactions
Eric Koskinen and Maurice Herlihy

10:40 Distributed Phase Synchronization of Dynamic Set of Processes
R.K. Shyamasundar and Shivali Agarwal

10:45 How to Speed-up Fault-Tolerant Clock Generation in VLSI Systems-on-Chip via Pipelining
Andreas Dielacher, Matthias Fugger, and Ulrich Schmid

10:50 Perfectly Secure Message Transmission in Directed Networks Re-Visited
Arpita Patra, Ashish Choudhary, and C. Pandu Rangan

10:55 Virtual World Consistency: a new Condition for STM Systems
Damien Imbs and Michel Raynal

Brief Announcements (ICT 122)
Session Chair: Marcos Aguilera

10:30 A Note on Distributed Stable Matching
Alex Kipnis and Boaz Patt-Shamir

10:35 On a Selfish Caching Game
Pietro Michiardi, Carla-Fabiana Chiasserini, Claudio Casetti,
Chi-Anh La, and Marco Fiore

10:40 Non-Self-Stabilizing and Self-Stabilizing Gathering in Networks of
Mobile Agents-the Notion of Speed
Joffroy Beauquier, Janna Burman, Julien Clement, and Shay Kutten

10:45 The Disagreement Power of an Adversary
Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Andreas Tielmann

10:50 Weakest failure detectors via an egg-laying simulation
Antonio Fernandez, Sergio Rajsbaum, Corentin Travers

10:55 Optimization Based Rate Allocation for Application Layer Multicast
Jinyao Yan, Martin May, and Bernhard Plattner

Keynote Talk (ICT 121)

11:10 Refining the Way to Consensus
Robbert van Renesse

Lunch Break 12:20 Lunch provided for PODC participants (Dining Centre, Alberta Room)

Regular Papers (ICT 121)
Session Chair: Michel Raynal

13:45 Tight Bounds for Clock Synchronization
Christoph Lenzen, Thomas Locher, Roger Wattenhofer

14:10 Load Balancing Without Regret in the Bulletin Board Model
Robert Kleinberg, Georgios Piliouras, Eva Tardos

14:35 Concurrent Imitation Dynamics in Congestion Games
Heiner Ackermann, Petra Berenbrink, Simon Fischer, Martin Hoefer

15:00 Extracting Quorum Failure Detectors
Vibhor Bhatt, Nicholas Christman, Prasad Jayanti

Coffee Break (Foyer ICT 121/122) 15:25-15:55

Regular Papers (ICT 121)
Session Chair: Dahlia Malkhi

15:55 The Weakest Failure Detector for Solving k-Set Agreement
Eli Gafni, Petr Kuznetsov

16:20 Simple and Efficient Asynchronous Byzantine Agreement with Optimal Resilience
Arpita Patra, Ashish Choudhary, C. Pandu Rangan

16:45 Partial Synchrony Based on Set Timeliness
Marcos K. Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg

17:10 Fast Scalable Deterministic Consensus for Crash Failures
Bogdan S. Chlebus, Dariusz R. Kowalski, Michal Strojnowski

Business Meeting & Rump Session (ICT 116)

20:30-23:00

    Tuesday August 11    

Regular Papers (ICT 121)
Session Chair: Idit Keidar

08:20 The Forgiving Graph: A distributed data structure for low stretch under adversarial attack
Tom Hayes, Jared Saia, Amitabh Trehan

08:45 A Distributed Polylogarithmic Time Algorithm for Self-Stabilizing Skip Graphs
Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, Hanjo Täubig

09:10 The Flip Markov Chain and a Randomizing P2P Protocol
Colin Cooper, Martin Dyer, Andrew J. Handley

09:35 Correctness of Gossip-Based Membership under Message Loss
Maxim Gurevich, Idit Keidar

Coffee Break (Foyer ICT 121/122) 10:00-10:30

Brief Announcements (ICT 121)
Session Chair: Thomas Moscibroda

10:30 The Price of Anonymity: Optimal Consensus despite Asynchrony, Crash and Anonymity
Francois Bonnet and Michel Raynal

10:35 Minimum Spanning Trees and Cone-Based Topology Control
Alejandro Cornejo and Nancy Lynch

10:40 Locality-Based Aggregate Computation in Wireless Sensor Networks
Jen-Yeu Chen, Gopal Pandurangan, and Jianghai Hu

10:45 Tight Lower Bounds for Greedy Routing in Uniform Small World Rings
Martin Dietzfelbinger and Philipp Woelfel

10:50 Optimal Self-stabilizing Multi-token Ring: A Randomized Solution
Anurag Dasgupta, Sukumar Ghosh, and Andrew Berns

10:55 Fast Scalable Byzantine Agreement in the Full Information Model with a
Nonadaptive Adversary
Valerie King and Jared Saia

Brief Announcements (ICT 114)
Session Chair: Petr Kuznetsov

10:30 Push: a DISC shell
Eric Van Hensbergen and Noah Evans

10:35 Deaf, Dumb, and Chatting Robots: Enabling Distributed Computation &
Fault-Tolerance Among Stigmergic Robots
Yoann Dieudonn'e, Shlomi Dolev, Franck Petit, and Michael Segal

10:40 Global Consistency can be Easier than Point-to-Point Communication
Prasant Gopal, Anuj Gupta, Pranav K. Vasishta, Piyush Bansal, and Kannan Srinathan

10:45 Vertical Paxos and Primary-Backup Replication
Leslie Lamport, Dahlia Malkhi, and Lidong Zhou

10:50 Topology Knowledge Affects Probabilistic Reliable Communication
Pranav K. Vasishta, Prasant Gopal, Anuj Gupta, Piyush Bansal, and Kannan Srinathan

10:55 A Platform for Experimenting with Mobile Algorithms in a Laboratory
Matthieu Roy and Marc-Olivier Killijian

Keynote Talk (ICT 102)

11:10 Memory Models: A Case for Rethinking Parallel Languages and Hardware
Sarita V. Adve

Lunch Break 12:20
    Industry sponsored lunch for students, postdocs, and employees of industrial sponsors
(Dining Centre, Alberta Room)

    Lunch on your own for everyone else

Invited Session on Industrial Applications of Algorithms (ICT 102)
Session Chair: Marcos Aguilera

13:45 The life and times of a ZooKeeper
Flavio Junqueira, Benjamin Reed

14:15 Cassandra - A Structured Storage System on a P2P Network
Avinash Lakshman, Prashant Malik

14:45 Pregel: A System for Large-Scale Graph Processing
Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn,
Naty Leiser, Grzegorz Czajkowski

Coffee Break (Foyer ICT 121/122) 15:15-15:45

Regular Papers (ICT 121)
(Session Chair: Faith Ellen)

15:45 Fast Distributed Random Walks
Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan

16:10 Distributed and Parallel Algorithms for Weighted Vertex Cover and other Covering Problems
Christos Koufogiannakis, Neal E. Young

16:35 Return of the Primal-Dual: Distributed Metric Facility Location
Saurav Pandit, Sriram Pemmaraju

Banquet (Calgary Zoo) 18:00

    Wednesday August 12    

Regular Papers (ICT 121)
Session Chair: Pierre Fraigniaud

08:20 The Wireless Synchronization Problem
Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Fabian Kuhn, Calvin Newport

08:45 SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks
Chen Avin, Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg, Liam Roditty

09:10 Coloring Unstructured Wireless Multi-Hop Networks
Johannes Schneider, Roger Wattenhofer

09:35 Oblivious Interference Scheduling
Alexander Fanghänel, Thomas Keßelheim, Harald Räcke, Berthold Vöcking

Coffee Break (Foyer ICT 121/122) 10:00-10:30

Brief Announcements (ICT 121)
Session Chair: Andrea Richa

10:30 The Theory Of Network Tracing
H. B. Acharya and M. G. Gouda

10:35 Efficient Pruning of Ad-Hoc Wireless Networks
Enoch Peserico

10:40 Self-Assembly as Graph Grammar as Distributed System
Aaron Sterling

10:45 Distributed Discovery of Large Near-Cliques
Zvika Brakerski and Boaz Patt-Shamir

10:50 Lightweight Key Agreement and Digital Certificates for Wireless Sensor Networks
Oscar Garcia-Morchon, Tobias Heer, Ludo Tolhuizen, and Klaus Wehrle

10:55 Distributed Algorithms for Approximating Wireless Network Capacity
Michael Dinitz

Keynote Talk (ICT 102)

11:10 Emerging Challenges and Opportunities in Parallel Computing: The Cretaceous Redux?
Bruce A. Hendrickson

Lunch Break 12:20 BBQ for PODC/SPAA participants (Dining Centre, Patio)

Regular Papers (ICT 121)
Session Chair: Boaz Patt-Shamir

13:45 Efficient Broadcasting in Known Topology Radio Networks with Long-range Interference
Frantisek Galcik, Leszek Gasieniec, Andrzej Lingas

14:10 The Effect of Power-Law Degrees on the Navigability of Small Worlds
Pierre Fraigniaud, George Giakkoupis

14:35 Bounding the Locality of Distributed Routing Algorithms
Prosenjit Bose, Paz Carmi, Stephane Durocher

15:00 Parsimonious Flooding in Dynamic Graphs
Herv'e Baumann, Pierluigi Crescenzi, Pierre Fraigniaud

Coffee Break (Foyer ICT 121/122) 15:25-15:55

Brief Announcements (ICT 121)
Session Chair: Ittai Abraham

15:55 Hardness of Broadcasting in Wireless Networks with Unreliable Communication
Fabian Kuhn, Nancy Lynch, and Calvin Newport

16:00 Complexity Analysis and Algorithm Design for Pipeline Configuration in Distributed Networks
Yi Gu, Qishi Wu, Anne Benoit, and Yves Robert

16:05 Exactly Electing a Unique Leader is not Harder than Computing Symmetric Functions
on Anonymous Quantum Networks
Hirotada Kobayashi, Keiji Matsumoto, and Seiichiro Tani

16:10 Impossibility Results for Optimistic Fair Exchange with Multiple Autonomous Arbiters
Alptekin Küpçü and Anna Lysyanskaya

16:15 Collaborative Measurement of Upload Speeds in P2P Systems
John R. Douceur, James Mickens, Thomas Moscibroda, and Debmalya Panigrahi

16:20 New Bounds for the Controller Problem
Yuval Emek and Amos Korman