IBM Research


Microsoft Research - Inria Joint Centre

Oracle Labs

University of the Basque Country

PODC 2015 Program

(Tentative as of May 28, 2015)

Monday 20 July

18:00 – 19:00 Alexander A. Shvartsman: 60th Birthday Celebration
19:00 – 21:00 Reception

Tuesday 21 July

08:55 – 09:00 Welcome Address
09:00 – 10:00 Keynote Address

Cortical Computation
Christos Papadimitriou

10:00 – 10:20 Coffee break

10:20 – 11:35 Session 1: 3 regular talks + 1 brief announcement (Chair: Friedhelm Meyer auf der Heide)

10:20 Near-Optimal Scheduling of Distributed Algorithms (Best student paper award)
Mohsen Ghaffari
10:43 Scheduling Loop-free Network Updates: It’s Good to Relax!
Arne Ludwig, Jasiek Marcinkowski and Stefan Schmid
11:06 New routing techniques and their applications
Liam Roditty and Roei Tov
11:29 Brief Announcement: Routing the internet with less than fifteen entries
Cyril Gavoille, Christian Glacet, Nicolas Hanusse and David Ilcinkas

11:35 – 12:50 Session 2: 3 regular talks + 1 brief announcement (Chair: Paul Spirakis)

11:35 Terminating Distributed Construction of Shapes and Patterns in a Fair Solution of Automata
Othon Michail
11:58 Fast and Exact Majority in Population Protocols
Dan Alistarh, Rati Gelashvili and Milan Vojnovic
12:21 Distributed House-Hunting in Ant Colonies
Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva and Nancy Lynch
12:44 Brief Announcement: On the Feasibility of Leader Election and Shape Formation with Self-Organizing Programmable Matter
Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida Bazzi, Andrea Richa and Christian Scheideler

12:50 – 14:30 Lunch break

14:30 – 16:02 Session 3: 4 regular talks (Chair: Antonio Fernández Anta)

14:30 Construction and impromptu repair of an MST in a distributed network with $o(m)$ communication
Valerie King, Shay Kutten and Mikkel Thorup
14:53 Near-Optimal Distributed Maximum Flow
Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen and Boaz Patt-Shamir
15:16 Toward Optimal Bounds in the Congested Clique: Graph Connectivity and MST
James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh and Michele Scquizzato
15:39 Fast distributed almost stable matchings
Rafail Ostrovsky and Will Rosenbaum

16:02 – 16:22 Coffee break

16:22 – 17:37 Session 4: 3 regular talks + 1 brief announcement (Chair: Christian Scheideler)

16:22 A (Truly) Local Broadcast Layer for Unreliable Radio Networks
Nancy Lynch and Calvin Newport
16:45 Efficient Communication in Cognitive Radio Networks
Seth Gilbert, Fabian Kuhn, Calvin Newport and Chaodong Zheng
17:08 A Local Broadcast Layer for the SINR Network Model
Magnus M. Halldorsson, Stephan Holzer and Nancy Lynch
17:31 Brief Announcement: Fast and Simple Node Coloring in the SINR Model
Fabian Fuchs

17:37 – 18:35 Session 5: 2 regular talks + 2 brief announcements (Chair: Thomas Erlebach)

17:37 Algebraic Methods in the Congested Clique
Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz and Jukka Suomela
18:00 Fast Partial Distance Estimation and Applications
Christoph Lenzen and Boaz Patt-Shamir
18:23 Brief Announcement: Distributed Single-Source Reachability
Mohsen Ghaffari and Rajan Udwani
18:29 Brief Announcement: A Hierarchy of Congested Clique Models: From Broadcast to Unicast
Florent Becker, Antonio Fernandez Anta, Ivan Rapaport and Eric Rémila

18:35 – 20:30 Doctoral Dissertation Award Ceremony + Business meeting

Wednesday 22 July

09:00 – 10:00 Keynote Address

The Mobile Adversary Paradigm in Distributed Computation and Systems
Moti Yung

10:00 – 10:20 Coffee break

10:20 – 11:35 Session 6: 3 regular talks + 1 brief announcement (Chair: Nitin Vaidya)

10:20 Trading Fences with RMRs and Separating Memory Models
Hagit Attiya, Danny Hendler and Philipp Woelfel
10:43 The Price of being Adaptive
Ohad Ben-Baruch and Danny Hendler
11:06 On the Time and Space Complexity of ABA Prevention and Detection
Zahra Aghazadeh and Philipp Woelfel
11:29 Brief Announcement: Fault-tolerant Broadcast in Anonymous Distributed Systems with Fair Lossy Communication Channels
Jian Tang, Mikel Larrea, Sergio Arévalo and Ernesto Jiménez

11:35 – 12:50 Session 7: 3 regular talks + 1 brief announcement (Chair: Eric Ruppert)

11:35 Impossibility Results for Distributed Transactional Memory
Costas Busch, Maurice Herlihy, Miroslav Popovic and Gokarna Sharma
11:58 Disjoint-Access Parallelism: Impossibility, Possibility, and Cost of Transactional Memory Implementations
Sebastiano Peluso, Roberto Palmieri, Paolo Romano, Binoy Ravindran and Francesco Quaglia
12:21 Safety-Liveness Exclusion in Distributed Computing
Victor Bushkov and Rachid Guerraoui
12:44 Brief Announcement: Eventually consistent linearizability
Tadeusz Kobus, Maciej Kokociński and Paweł T. Wojciechowski

12:50 – 14:30 Lunch break

14:30 – 16:02 Session 8: 4 regular talks (Chair: Alexander Shvartsman)

14:30 Help!
Keren Censor-Hillel, Erez Petrank and Shahar Timnat
14:53 Lock-Free Algorithms under High Memory Contention
Dan Alistarh, Thomas Sauerwald and Milan Vojnovic
15:16 Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way
Trevor Brown
15:39 On the Space Complexity of Set Agreement
Carole Delporte-Gallet, Hugues Fauconnier, Petr Kuznetsov and Eric Ruppert

16:02 – 16:22 Coffee break

16:22 – 17:37 Session 9: 3 regular talks + 1 brief announcement (Chair: Moti Yung)

16:22 How Fair is Your Protocol? A Utility-based Approach to Protocol Optimality
Juan A. Garay, Jonathan Katz, Björn Tackmann and Vassilis Zikas
16:45 Adaptively Secure Computation with Partial Erasures
Carmit Hazay, Yehuda Lindell and Arpita Patra
17:08 Improved Analysis of Deterministic Load-Balancing Schemes
Petra Berenbrink, Ralf Klasing, Adrian Kosowski, Frederik Mallmann-Trenn and Przemysław Uznański
17:31 Brief Announcement: Robust and Private Distributed Shared Atomic Memory in Message Passing Networks
Shlomi Dolev, Thomas Petig and Elad Michael Schiller

17:37 – 18:35 Session 10: 2 regular talks + 2 brief announcements (Chair: Othon Michail)

17:37 Randomized Proof-Labeling Schemes
Mor Baruch, Pierre Fraigniaud and Boaz Patt-Shamir
18:00 Distributed Convex Thresholding
Ran Wolff
18:23 Brief Announcement: Average Complexity for the LOCAL Model
Laurent Feuilloley
18:29 Brief Announcement: Investigating the cost of Anonymity on Dynamic Networks
Giuseppe Antonio Di Luna and Roberto Baldoni

*** Conference banquet ***

Thursday 23 July

09:00 – 10:00 Keynote Address

Online Resource Leasing
Friedhelm Meyer auf der Heide

10:00 – 10:20 Coffee break

10:20 – 11:29 Session 11: 3 regular talks (Chair: Elad Schiller)

10:20 Deterministic (Delta + 1)-Coloring in Sublinear (in Delta) Time in Static, Dynamic and Faulty Networks (Best paper award)
Leonid Barenboim
10:43 On Information Complexity in the Broadcast Model
Mark Braverman and Rotem Oshman
11:06 How to Elect a Leader Faster than a Tournament
Dan Alistarh, Rati Gelashvili and Adrian Vladu

11:35 – 12:44 Session 12: 3 regular talks (Chair: Michel Raynal)

11:35 The Weakest Failure Detector for Eventual Consistency
Swan Dubois, Rachid Guerraoui, Petr Kuznetsov, Franck Petit and Pierre Sens
11:58 Limitations of Highly-Available Eventually-Consistent Data Stores
Hagit Attiya, Faith Ellen and Adam Morrison
12:21 Computing Weak Consistency in Polynomial Time
Wojciech Golab, Xiaozhou Steve Li, Alejandro Lopez-Ortiz and Naomi Nishimura

12:44 – 14:30 Lunch break

14:30 – 16:02 Session 13: 4 regular talks (Chair: Shlomi Dolev)

14:30 On the push&pull protocol for rumour spreading
Huseyin Acan, Andrea Collevecchio, Abbas Mehrabian and Nick Wormald
14:53 Distributed Resource Discovery in Sub-Logarithmic Time
Bernhard Haeupler and Dahlia Malkhi
15:16 The Cost of Synchronizing Multiple-Access Channels
Tomasz Jurdzinski and Grzegorz Stachowiak
15:39 Leveraging Multiple Channels in Ad Hoc Networks
Magnus M. Halldorsson, Yuexuan Wang and Dongxiao Yu

16:02 – 16:22 Coffee break

16:22 – 18:17 Session 14: 5 regular talks (Chair: Danny Hendler)

16:22 Dual Failure Resilient BFS Structure
Merav Parter
16:45 Fault-Tolerant Consensus in Directed Graphs
Lewis Tseng and Nitin Vaidya
17:08 Minimal Synchrony for Asynchronous Byzantine Consensus
Zohir Bouzid, Achour Mostéfaoui and Michel Raynal
17:31 Stabilizing Server-Based Storage in Byzantine Asynchronous Message-Passing Systems
Silvia Bonomi, Shlomi Dolev, Maria Potop-Butucaru and Michel Raynal
17:54 Towards Optimal Synchronous Counting
Christoph Lenzen, Joel Rybicki and Jukka Suomela