Monday, July 25
8:00 — 17:30 Workshops
16:30 — 18:00 Faith Ellen Birthday Celebration
18:00 — 19:30 Reception
Tuesday, July 26
8:30 — 8:40 Opening
8:40 — 9:40 Keynote Lecture 1
- New Opportunities for PODC?: Massive, Volatile, but Highly Predictable Resources
Andrew A. Chien (The University of Chicago, Argonne National Laboratory)
9:40 — 10:00 Coffee break
10:00 — 11:56 Session 1
Session Chair: Calvin Newport (Georgetown University, USA)
- 10:00 — 10:23
A Distributed (2+ε)-Approximation for Vertex Cover in O(log(Δ)/ε log log(Δ)) Rounds (Best Student Paper Award)
Reuven Bar-Yehuda, Keren Censor-Hillel and Gregory Schwartzman - 10:23 — 10:46
The Greedy Spanner is Existentially Optimal (Best Student Paper Award)
Arnold Filtser and Shay Solomon - 10:46 — 11:09
MST in Log-Star Rounds of Congested Clique
Mohsen Ghaffari and Merav Parter - 11:09 — 11:32
Distributed Algorithms for Planar Networks I: Planar Embedding
Mohsen Ghaffari and Bernhard Haeupler - 11:32 — 11:38
Brief Announcement: Labeling Schemes for Power-Law Graphs
Noy Rotbart, Casper Petersen, Jakob Grue Simonsen and Christian Wulff-Nilsen - 11:38 — 11:44
Brief Announcement: Sublinear-Space Distance Labeling using Hubs
Pawel Gawrychowski, Adrian Kosowski and Przemyslaw Uznanski - 11:44 — 11:50
Brief Announcement: Optimal leader election in multi-hop radio networks
Artur Czumaj and Peter Davies - 11:50 — 11:56
Brief Announcement: The Small World of Curious Beings
Soroush Alamdari
12:00 — 13:30 Lunch
13:30 — 15:08 Session 2
Session Chair: Oksana Denysyuk (University of Calgary, Canada)
- 13:30 — 13:53
Analysing Snapshot Isolation (Best Paper Award)
Andrea Cerone and Alexey Gotsman - 13:53 — 14:16
Recoverable Mutual Exclusion
Wojciech Golab and Aditya Ramaraju - 14:16 — 14:39
A Randomized Concurrent Algorithm for Disjoint Set Union
Siddhartha V. Jayanti and Robert E. Tarjan - 14:39 — 15:02
Self-stabilizing Balls & Bins in Batches
Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars Nagel and Christopher Wastell - 15:02 — 15:08
Brief Announcement: Local Independent Set Approximation
Marijke H. L. Bodlaender, Magnus M. Halldorsson, Christian Konrad and Fabian Kuhn
15:10 — 15:30 Coffee break
15:30 — 17:31 Session 3
Session Chair: Wojciech Golab (University of Waterloo, Canada)
- 15:30 — 15:53
Deterministic Objects: Life beyond Consensus
Yehuda Afek, Faith Ellen and Eli Gafni - 15:53 — 16:16
Unbeatable Set Consensus via Topological and Combinatorial Reasoning
Armando Castañeda, Yannai A. Gonczarowski and Yoram Moses - 16:16 — 16:39
A Polylogarithmic Gossip Algorithm for Plurality Consensus
Mohsen Ghaffari and Merav Parter - 16:39 — 17:02
Noisy Rumor Spreading and Plurality Consensus
Pierre Fraigniaud and Emanuele Natale - 17:02 — 17:25
Rational Consensus: Extended Abstract
Joseph Halpern and Xavier Vilaça - 17:25 — 17:31
Brief Announcement: A Tight Space Bound for Consensus
Leqi Zhu
17:31 – 19:15 Business Meeting (open to all PODC attendees)
Wednesday, July 27
8:40 — 9:40 Keynote Lecture 2
- Concurrent Data Structures (slides)
Faith Ellen (University of Toronto)
9:40 — 10:00 Coffee break
10:00 — 11:56 Session 4
Session Chair: Andrea Richa (Arizona State, USA)
- 10:00 — 10:23
Contention Resolution on a Fading Channel
Jeremy T. Fineman, Seth Gilbert, Fabian Kuhn and Calvin Newport - 10:23 — 10:46
Reliable Communication over Highly Connected Noisy Networks
Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles and Bernhard Haeupler - 10:46 — 11:09
Contention Resolution on Multiple Channels with Collision Detection
Jeremy Fineman, Calvin Newport and Tonghe Wang - 11:09 — 11:32
How Asynchrony Affects Rumor Spreading Time
George Giakkoupis, Yasamin Nazari and Philipp Woelfel - 11:32 — 11:38
Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
Yi-Jun Chang, Tsvi Kopelowitz and Seth Pettie - 11:38 — 11:44
Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks
Magnus M. Halldorsson, Tigran Tonoyan, Yuexuan Wang and Dongxiao Yu - 11:44 — 11:50
Brief Announcement: Reliable Message Transmission under Partial Knowledge and General Adversaries
Aris Pagourtzis, Giorgos Panagiotakos and Dimitris Sakavalas - 11:50 — 11:56
Brief Announcement: Self-Stabilizing Clock Synchronization with 3-bit messages
Lucas Boczkowski, Amos Korman and Emanuele Natale
12:00 — 13:30 Lunch
13:30 — 15:08 Session 5
Session Chair: Merav Parter (MIT, USA)
- 13:30 — 13:53
Distributed Strong Diameter Network Decomposition
Michael Elkin and Ofer Neiman - 13:53 — 14:16
Optimal Dynamic Distributed MIS
Keren Censor-Hillel, Elad Haramaty and Zohar Karnin - 14:16 — 14:39
A Local Constant Factor MDS Approximation for Bounded Genus Graphs
Saeed Akhoondian Amiri, Stefan Schmid and Sebastian Siebertz - 14:39 — 15:02
On Efficient Distributed Construction of Near Optimal Routing Schemes
Michael Elkin and Ofer Neiman - 15:02 — 15:08
Brief anouncement: Deterministic Graph Connectivity in the Broadcast Congested Clique
Pedro Montealegre and Ioan Todinca
15:10 — 15:30 Coffee break
15:30 — 17:31 Session 6
Session Chair: Gadi Taubenfeld (IDC Herzliya, Israel)
- 15:30 — 15:53
Space Bounds for Reliable Storage: Fundamental Limits of Coding
Alexander Spiegelman, Yuval Cassuto, Gregory Chockler and Idit Keidar - 15:53 — 16:16
Specification and Complexity of Collaborative Text Editing
Hagit Attiya, Sebastian Burckhardt, Alexey Gotsman, Adam Morrison, Hongseok Yang and Marek Zawirski - 16:16 — 16:39
Optimal Mobile Byzantine Fault Tolerant Distributed Storage
Silvia Bonomi, Antonella Del Pozzo, Maria Potop-Butucaru and Sebastien Tixeuil - 16:39 — 17:02
A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems
Sarah Cannon, Josh Daymude, Dana Randall and Andrea Richa - 17:02 — 17:25
A Complexity-Based Hierarchy for Multiprocessor Synchronization
Faith Ellen, Rati Gelashvili, Nir Shavit and Leqi Zhu - 17:25 — 17:31
Brief Announcement: Asynchronous Coordination With Preferences and Constraints
Armando Castañeda, Pierre Fraigniaud, Eli Gafni, Sergio Rajsbaum and Matthieu Roy - 17:31 — 17:37
Brief Announcement: A Key-Value Map for Massive Real-Time Analytics
Dmitry Basin, Edward Bortnikov, Anastasia Braginsky, Guy Golan Gueta, Eshcar Hillel, Moshe Sulamy and Idit Keidar
18:00 – 21:00 Banquet (at Hotel Palomar Chicago, 505 North State Street, Chicago, IL 60654)
Thursday, July 28
8:40 — 9:40 Keynote Lecture 3
- How Emerging Memory Technologies Will Have You Rethinking Algorithm Design
Phillip B. Gibbons (Carnegie Mellon University)
9:40 — 10:00 Coffee break
10:00 — 11:56 Session 7
Session Chair: Yehuda Afek (Tel-Aviv University, Israel)
- 10:00 — 10:23
Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation
Viveck Cadambe, Zhiying Wang and Nancy Lynch - 10:23 — 10:46
On the Complexity of Reader-Writer Locks
Danny Hendler - 10:46 — 11:09
An algorithm for replicated objects with efficient reads
Tushar Chandra, Vassos Hadzilacos and Sam Toueg - 11:09 — 11:32
Are Shared Objects Composable under an Oblivious Adversary?
Oksana Denysyuk and Philipp Woelfel - 11:32 — 11:38
Brief Announcement: A Family of Leaderless Generalized-Consensus Algorithms
Giuliano Losa, Sebastiano Peluso and Binoy Ravindran - 11:38 — 11:44
Brief Announcement: Computing in the Presence of Weak Crash Failures
Gadi Taubenfeld - 11:44 — 11:50
Brief Announcement: Oh-RAM! One and a Half Round Read/Write Atomic Memory
Theophanis Hadjistasi, Alexander Schwarzmann and Nicolas Nicolaou - 11:50 — 11:56
Brief Announcement: Space-Time Tradeoffs for Distributed Verification
Mor Baruch, Rafail Ostrovsky and Will Rosenbaum
12:00 — 13:30 Lunch
13:30 — 15:08 Session 8
Session Chair: Marcos K. Aguilera (VMware Research Group, USA)
- 13:30 — 13:53
A Faster Distributed Radio Broadcast Primitive (Extended Abstract)
Bernhard Haeupler and David Wajc - 13:53 — 14:16
Broadcast Extensions with Optimal Communication and Round Complexity
Chaya Ganesh and Arpita Patra - 14:16 — 14:39
Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems
Achour Mostéfaoui and Michel Raynal - 14:39 — 15:02
How proofs are prepared at Camelot
Andreas Björklund and Petteri Kaski - 15:02 — 15:08
Brief Announcement: Proactive Secret Sharing with a Dishonest Majority
Shlomi Dolev, Karim Eldefrawy, Joshua Lampkins, Rafail Ostrovsky and Moti Yung
15:10 — 15:30 Coffee break
15:30 — 17:03 Session 9
Session Chair: Adrian Kosowski (LIAFA, Paris Diderot, France)
- 15:30 — 15:53
Search on a Line with Faulty Robots
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan and Jaroslav Opatrny - 15:53 — 16:16
Uniform deployment of mobile agents in asynchronous rings
Masahiro Shibata, Toshiya Mega, Fukuhito Ooshita, Hirotsugu Kakugawa and Toshimitsu Masuzawa - 16:16 — 16:39
Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms
Lili Su and Nitin Vaidya - 16:39 –16:45
Brief Announcement: Active Information Spread in Networks
Gennaro Cordasco, Luisa Gargano, Adele Rescigno and Ugo Vaccaro - 16:45 — 16:51
Brief Announcement: Certified Universal Gathering in R2 for Oblivious Mobile Robots
Pierre Courtieu, Lionel Rieg, Sebastien Tixeuil and Xavier Urbain - 15:51 — 16:57
Brief Announcement: Probabilistic Asynchronous Arbitrary Pattern Formation
Quentin Bramas and Sebastien Tixeuil - 16:57 — 17:03
Brief Announcement: Pattern Formation Problem for Synchronous Mobile Robots in the Three Dimensional Euclidean Space
Yukiko Yamauchi, Taichi Uehara and Masafumi Yamashita
17:15 — 18:42 Session 10
Session Chair: Philipp Woelfel (University of Calgary, Canada)
- 17:15 — 17:38
Low-Congestion Shortcuts without Embedding
Bernhard Haeupler, Taisuke Izumi and Goran Zuzic - 17:38 — 18:01
The coalescing-branching random walk on expanders and the dual epidemic process
Colin Cooper, Tomasz Radzik and Nicolas Rivera - 18:01 — 18:24
Ant-Inspired Density Estimation via Random Walks
Cameron Musco, Hsin-Hao Su and Nancy Lynch - 18:24 — 18:30
Brief Announcement: Multi-Broadcasting under the SINR Model
Shailesh Vaya and Sai Praneeth Reddy K - 18:30 — 18:36
Brief Announcement: Using Read-k Inequalities to Analyze a Distributed MIS Algorithm
Sriram Pemmaraju and Talal Riaz
18:36 — 18:45 Closing of PODC 2016
Friday, July 29
8:00 — 17:30 Workshops