Sunday, July 15

17h00 - 19h30: Registration

18h30 - 19h30: Welcome Reception

Monday, July 16

8h30 - 9h20: Keynote

David Peleg, Weizmann Institute
Towards an Algorithmically Usable SINR Model for Wireless Communication.

9h20 - 10h35: Session 1: Shared Memory I

Session chair: Valerie King (University of Victoria)

Faster Randomized Consensus with an Oblivious Adversary
James Aspnes

On the Liveness of Transactional Memory
Victor Bushkov, Rachid Guerraoui, and Michal Kapalka

On the Time and Space Complexity of Randomized Test-And-Set
George Giakkoupis and Philipp Woelfel

10h35 - 11h00: Break

11h00 - 12h15: Session 2: Information Spreading, Random Walks

Session chair: Lucia Draque Penso (University of Ulm)

Random Walks which Prefer Unvisited Edges and Exploring High Girth Even Degree Expanders in Linear Time
Petra Berenbrink, Colin Cooper, and Tom Friedetzky

Information Spreading in Dynamic Graphs
Andrea Clementi, Riccardo Silvestri, and Luca Trevisan

Coalescing Random Walks and Voting on Graphs
Colin Cooper, Robert Elsasser, Hirotaka Ono, and Tomasz Radzik

12h15 - 13h45: Lunch

13h45 - 15h00: Session 3: Communication Complexity

Alessandro Panconesi (Sapienza, University of Rome)

The Cost of Fault-Tolerance in Multi-Party Communication Complexity
Binbin Chen, Haifeng Yu, Yuda Zhao, and Phillip Gibbons

The Communication Complexity of Distributed Task Allocation
Andrew Drucker, Fabian Kuhn, and Rotem Oshman

Collaborative Search on the Plane without Communication
Amos Korman, Ofer Feinerman, Zvi Lotker, and Jean-Sebastien Sereni

15h00 - 16h00: Session 4: Brief Announcements

Session chair: Christian Scheideler (University of Paderborn)

What Can be Computed without Communications?
Heger Arfaoui and Pierre Fraigniaud

Distributed Algorithms for Throughput Performance in Wireless Networks
Eyjolfur Asgeirsson, Magnus M. Halldorsson, and Pradipta Mitra

Distributed Cryptography using TrInc
Michael Backes, Fabian Bendun, and Aniket Kate

Reconfigurable State Machine Replication from Non-Reconfigurable Building Blocks
Vita Bortnikov, Gregory Chockler, Dmitri Perelman, Alexey Roytman, Shlomit Shachor, and Ilya Shnayderman

All-to-all Gradecast using Coding with Byzantine Failures
John Bridgman and Vijay Garg

There are Plenty of Tasks Weaker than Perfect Renaming and Stronger than $(n-1)$-set Agreement
Armando Castaneda, Sergio Rajsbaum, and Michel Raynal

Waiting in Dynamic Networks
Arnaud Casteigts, Paola Flocchini, Emmanuel Godard, Nicola Santoro, and Masafumi Yamashita

Optimal Amortized Secret Sharing with Cheater Identification
Ashish Choudhury

Efficient Optimally Resilient Statistical AVSS and Its Applications
Ashish Choudhury and Arpita Patra

16h00 - 16h30: Break

16h30 - 17h45: Session 5: Wait Freedom

Session chair: Victor Luchangco (Oracle)

Wait-Freedom with Advice
Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Petr Kuznetsov

Universal Constructions that Ensure Disjoint-Access Parallelism and Wait-Freedom
Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, and Corentin Travers

Generalized Lattice Agreement
Jose Faleiro, Sriram Rajamani, Kaushik Rajan, Ganesan Ramalingam, and Kapil Vaswani

18h30 - 19h30: Wine tasting

Tuesday, July 17

8h30 - 9h20: Industrial Track

Dave Dice, Oracle
Synchronization - A practicioner's Report

Harry Li, Facebook
Practical Consistency Tradeoffs

9h20 - 10h35: Session 6: Game Theory and Security

Session chair: Calvin Newport (Georgetown University)

Distributed Selfish Load Balancing with Weights and Speeds
Clemens Adolphs and Petra Berenbrink

Making Evildoers Pay: Resource-Competitive Broadcast in Sensor Networks
Seth Gilbert and Maxwell Young

Distributed Public Key Schemes Secure against Continual Leakage
Adi Akavia, Shafi Goldwasser, and Carmit Hazay

10h35 - 11h00: Break

11h00 - 12h15: Session 7: Locality

Session chair: Philipp Woelfel (University of Calgary)

Distributed Maximal Matching: Greedy is Optimal
Juho Hirvonen and Jukka Suomela

Lower Bounds for Local Approximation
Mika Goos, Juho Hirvonen, and Jukka Suomela

Weak Models of Distributed Computing, with Connections to Modal Logic
Lauri Hella, Matti Jarvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiainen, Kerkko Luosto, Jukka Suomela, and Jonni Virtema

12h15 - 13h45: Lunch

13h45 - 15h00: Session 8: Ad-hoc Networks

Session chair: Valerie King (University of Victoria)

Aggregation in Dynamic Networks
Alejandro Cornejo, Seth Gilbert, and Calvin Newport

Distributed Connectivity of Wireless Networks
Magnus M. Halldorsson and Pradipta Mitra

Leader Election in Shared Spectrum Radio Networks
Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin Newport

15h00 - 16h00: Session 9: Brief announcements

Session chair: Lucia Draque Penso (University of Ulm)

Achieving Reliability in Master-Worker Computing via Evolutionary Dynamics
Evgenia Christoforou, Antonio Fernandez Anta, Chryssis Georgiou, Miguel Mosteiro, and Angel Sanchez

Breaking the O(nm) Bit Barrier: Secure Multiparty Computation with a Static Adversary
Varsha Dani, Valerie King, Mahnush Movahedi, and Jared Saia

Maintaining Large Dense Subgraphs on Dynamic Networks
Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, and Amitabh Trehan

Decentralized Network Supercomputing in the Presence of Malicious and Crash-Prone Workers
Seda Davtyan, Kishori Konwar, and Alexander Shvartsman

Order-preserving Renaming in Synchronous Message Passing Systems with Byzantine Faults
Oksana Denysyuk and Luis Rodrigues

An Obstacle to Scalability in Wireless Networks
Andras Farago

On the Resilience of Routing Tables
Joan Feigenbaum, Brighten Godfrey, Aurojit Panda, Michael Schapira, Ankit Singla, and Scott Shenker

Tight RMR Lower Bounds for Randomized Mutual Exclusion
George Giakkoupis and Philipp Woelfel

From Sequential to Concurrent: Correctness and Relative Efficiency
Vincent Gramoli, Petr Kuznetsov, and Srivatsan Ravi

16h00 - 16h30: Break

16h30 - 17h45: Session 10: Fault Tolerance

Session chair: Prasad Jayanti (Dartmouth)

Asynchronous Failure Detectors
Alejandro Cornejo, Nancy Lynch, and Srikanth Sastry

Simulations and Reductions for Colorless Tasks
Maurice Herlihy and Sergio Rajsbaum

A Closer Look at Fault Tolerance
Gadi Taubenfeld

18h00 - 19h00: Business meeting (and refreshments)

20h00 - 23h00: Banquet

Wednesday, July 18

8h30 - 9h15: Edsger W. Dijkstra Prize Ceremony

9h15 - 10h30: Session 11: Load Balancing and Scheduling

Session chair: Christian Scheideler (University of Paderborn)

A Simple Approach for Adapting Continuous Load Balancing Processes to Discrete Settings
Hoda Akbari, Petra Berenbrink, and Thomas Sauerwald

Dynamic Packet Scheduling in Wireless Networks
Thomas Kesselheim

Competitive and Fair Throughput for Co-Existing Networks Under Adversarial Interference
Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang

10h30 - 11h00: Break

11h00 - 12h15: Session 12: Byzantine Agreements

Session chair: Victor Luchangco (Oracle)

On the (Limited) Power of Non-Equivocation
Allen Clement, Flavio Junqueira, Aniket Kate, and Rodrigo Rodrigues

On the Price of Equivocation in Byzantine Agreement
Alexander Jaffe, Thomas Moscibroda, and Siddhartha Sen

Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding
Guanfeng Liang and Nitin Vaidya

12h15 - 13h45: Lunch

13h45: The LADIS workshop begins

13h45 - 14h35: Keynote (Joint Session PODC and LADIS)

Scott Shenker, UC Berkeley and ICSI
Software-Defined Networking: History, Hype, and Hope

14h35 - 15h25: Session 13: Brief announcements

Session chair: Keren Censor-Hillel (MIT)

Network Formation Games Can Give Rise to Realistic Networks
Andrs Gulys, Attila Korsi, Gbor Rtvri, and Jzsef Br

Network Destabilizing Attacks
Robert Lychev, Sharon Goldberg, and Michael Schapira

Tolerating Permanent and Transient Value Faults
Zarko Milosevic, Martin Hutle, and Andr Schiper

Decoupling Version Identification from Causality Tracking Information in Distributed Storage Systems
Nuno Preguica, Carlos Baquero, Paulo Srgio Almeida, Victor Fonte, and Ricardo Gonalves

Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors
Michel Raynal and Julien Stainer

Delay or Deliver Dilemma in Organization Networks
Shailesh Vaya

Live Streaming with Utilities, Quality and Cost
Ymir Vigfusson, Ken Birman, Daniel Freedman, Qi Huang, Kristjan Jonsson, and Gunnar Sveinbjornsson

A Calculus of Policy-Based Routing Systems
Anduo Wang, Carolyn Talcott, Alexander J. T. Gurney, Boon Thau Loo, and Andre Scedrov

15h25 - 16h40: Session 14: Distributed Graph Algorithms

Session chair: Philipp Woelfel (University of Calgary)

Distributed algorithms for scheduling on line and tree networks
Venkatesan Chakaravarthy, Sambuddha Roy, and Yogish Sabharwal

Optimal Distributed All Pairs Shortest Paths and Applications
Stephan Holzer and Roger Wattenhofer

Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs
Nitin Vaidya, Lewis Tseng, and Guanfeng Liang

16h40 - 17h10: Break

17h10 - 18h00: Session 15: Shared Memory II

Session chair: Calvin Newport (Georgetown University)

Faster than Optimal Snapshots (for a While)
James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen

Strongly Linearizable Implementations: Possibilities and Impossibilities
Maryam Helmi, Lisa Higham, and Philipp Woelfel

Thursday, July 19

FOMC 2012: The 8th ACM SIGACT International Workshop on Foundations of Mobile Computing (Formerly known as DIALM-POMC)

LADIS 2012: The 6th ACM SIGOPS/SIGACT Workshop on Large Scale Distributed Systems and Middleware
(starting on Wednesday)

WTTM 2012: The 4th Workshop on the Theory of Transactional Memory