PODC 2017 Program

Full papers

Seeing is Believing: A client-centric specification of database isolation, Natacha Crooks (University of Texas), Youer Pu (Cornell University), Lorenzo Alvisi (University of Texas) and Allen Clement (Google)

The Space Requirement of Local Forwarding on Acyclic Networks, Boaz Patt-Shamir (Tel Aviv University) and Will Rosenbaum (Tel Aviv University)

Optimal Distance Labeling Schemes for Trees, Ofer Freedman (University of Haifa), Pawel Gawrychowski (University of Haifa), Patrick Nicholson (Bell Labs) and Oren Weimann (University of Haifa)

Communication Primitives in Cognitive Radio Networks, Seth Gilbert (National University of Singapore), Fabian Kuhn (University of Freiburg) and Chaodong Zheng (Nanjing University)

Distributed Approximation of Maximum Independent Set and Maximum Matching, Reuven Bar-Yehuda (Technion IIT), Keren Censor-Hillel (Technion IIT), Mohsen Ghaffari (MIT) and Gregory Schwartzman (Technion IIT)

Coordination Without Prior Agreement, Gadi Taubenfeld (The Interdisciplinary Center)

Broadcasting in Noisy Radio Networks, Bernhard Haeupler (Carnegie Mellon University), Ellis Hershkowitz (Carnegie Mellon University), Goran Zuzic (Carnegie Mellon University) and Keren Censor-Hillel (Technion)

Fruitchains: A Fair Blockchain, Rafael Pass (Cornell Tech) and Elaine Shi (Cornell)

The Power of Choice in Priority Scheduling, Dan Alistarh (ETH), Justin Kopinsky (MIT), Jerry Li (MIT) and Giorgi Nadiradze (ETH)

Triangle Finding and Listing in CONGEST networks, Taisuke Izumi (Nagoya Institute of Technology) and Francois Le Gall (Kyoto University)

Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity, Leonid Barenboim (Open University of Israel), Michael Elkin (Ben-Gurion University of the Negev) and Tzalik Maimon (Open University of Israel)

Gossip in a Smartphone Peer-to-Peer Network, Calvin Newport (Georgetown University)

Symmetry Breaking with Noisy Processes, Seth Gilbert (National University of Singapore) and Calvin Newport (Georgetown University)

What can be sampled locally?, Weiming Feng (Nanjing University), Yuxin Sun (Nanjing University) and Yitong Yin (Nanjing University)

Towards Efficient Verification of Population Protocols, Michael Blondin (Technische Universität München), Javier Esparza (Technische Universität München), Stefan Jaax (Technische Universität München) and Philipp J. Meyer (Technische Universität München)

Ignore or Comply? On Breaking Symmetry in Consensus, Petra Berenbrink (University of Hamburg), Andrea Clementi (Università di Roma Tor Vergata), Robert Elsässer (University of Salzburg), Peter Kling (University of Hamburg), Frederik Mallmann-Trenn (École normale supérieure) and Emanuele Natale (Max-Planck-Institut)

Effectiveness of Delaying Timestamp Computation, Sandeep Kulkarni (Michigan State University) and Nitin Vaidya (UIUC)

Recoverable Mutual Exclusion in Sub-logarithmic Time, Wojciech Golab (University of Waterloo) and Danny Hendler (Ben-Gurion University)

A Distributed Learning Dynamics in Social Groups, L. Elisa Celis (EPFL), Peter Krafft (MIT) and Nisheeth Vishnoi (EPFL)

On The Multiparty Communication Complexity of Testing Triangle-Freeness, Orr Fischer (Tel Aviv University), Shay Gershtein (Tel Aviv University) and Rotem Oshman (Tel Aviv University)

Life Beyond Set Agreement, David Yu Cheng Chan (University of Toronto), Vassos Hadzilacos (University of Toronto) and Sam Toueg (University of Toronto)

A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities, Michael Elkin (Ben-Gurion University of the Negev)

The Space Hierarchy of Fault Tolerant Register Emulations, Gregory Chockler (Royal Holloway, University of London) and Alexander Spiegelman (Technion)

Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks, Artur Czumaj (University of Warwick) and Peter Davies (University of Warwick)

Self-organized segregation on the grid, Hamed Omidvar (UCSD) and Massimo Franceschetti (UCSD)

Distributed MST and Routing in Almost Mixing Time, Mohsen Ghaffari (ETH Zurich), Fabian Kuhn (University of Freiburg) and Hsin-Hao Su (MIT)

Analyzing Contention and Backoff in Asynchronous Shared Memory, Naama Ben-David (Carnegie Mellon University) and Guy Blelloch (Carnegie Mellon University)

Greedy Routing and the Algorithmic Small-World Phenomenon, Karl Bringmann (Max Planck Institute for Informatics), Ralph Keusch (ETH Zurich), Johannes Lengler (ETH Zurich), Yannic Maus (University of Freiburg) and Anisur Molla (NISER Bhubaneswar)

Distributed MIS via All-to-All Communication, Mohsen Ghaffari (ETH Zurich)

Asynchronous Shared Channel, Gianluca De Marco (University of Salerno) and Grzegorz Stachowiak (University of Wroclaw)

A Layered Architecture for Erasure-Coded Consistent Distributed Storage, Kishori Konwar (MIT), Prakash Narayana Moorthy (MIT), Nancy Lynch (MIT) and Muriel Medard (MIT)

LCL problems on grids, Sebastian Brandt (ETH Zürich), Juho Hirvonen (IRIF, CNRS and University Paris Diderot), Janne H. Korhonen (Aalto University), Tuomo Lempiäinen (Aalto University), Patric R. J. Östergård (Aalto University), Christopher Purcell (Aalto University), Joel Rybicki (Aalto University), Jukka Suomela (Aalto University) and Przemyslaw Uznanski (ETH Zürich)

A Template For Implementing Fast Lock-free Trees Using HTM, Trevor Brown (University of Toronto)

Adding Concurrency to Smart Contracts, Thomas Dickerson (Brown University), Paul Gazzillo (Yale University), Maurice Herlihy (Brown University) and Eric Koskinen (Yale University)

Clocked population protocols, James Aspnes (Yale University)

Randomized Abortable Mutual Exclusion with Constant Amortized RMR Complexity on the CC, George Giakkoupis (INRIA Rennes) and Philipp Woelfel (University of Calgary)

Transactional Lock Elision Meets Combining, Alex Kogan (Oracle Labs) and Yossi Lev (Oracle Labs)

On Using Time Without Clocks via Zigzag Causality, Asa Dan (Technion), Rajit Manohar (Yale) and Yoram Moses (Technion)

Brief announcements

An Efficient Silent Self-Stabilizing 1-Maximal Matching Algorithm under Distributed Daemon for Arbitrary Networks, Michiko Inoue (Nara Institute of Science and Technology), Fukuhito Ooshita (Nara Institute of Science and Technology) and Sebastien Tixeuil (UPMC Sorbonne Universites)

Distributed Approximation for Tree Augmentation, Keren Censor-Hillel (Technion) and Michal Dory (Technion)

Gossiping with Latencies, Seth Gilbert (National University of Singapore), Peter Robinson (Royal Holloway, University of London) and Suman Sourav (National University of Singapore)

Stateless Computation, Danny Dolev (Hebrew University), Michael Erdmann (Carnegie Mellon University), Neil Lutz (Rutgers University), Michael Schapira (Hebrew University) and Adva Zair (The Hebrew University of Jerusalem)

How large is your graph?, Varun Kanade (University of Oxford), Frederik Mallmann-Trenn (École normale supérieure) and Victor Verdugo (École normale supérieure)

Optimal address-oblivious epidemic dissemination, Hugues Mercier (Université de Neuchâtel), Laurent Hayez (Université de Neuchâtel) and Miguel Matos (Universidade de Lisboa)

Friend or Foe? Population Protocols can perform Community Detection, Luca Becchetti (University of Rome “La Sapienza”), Andrea Clementi (University of Rome ”Tor Vergata”), Emanuele Natale (Sapienza Università di Roma), Francesco Pasquale (Sapienza Università di Roma), Prasad Raghavendra (U.C. Berkeley, Berkeley) and Luca Trevisan (U.C. Berkeley, Berkeley)

Proust: A Design Space for Highly-Concurrent Transactional Data Structures, Thomas Dickerson (Brown University), Paul Gazzillo (Yale University), Eric Koskinen (Yale University) and Maurice Herlihy (Brown University)

Object Oriented Consensus, Danny Vainstein (Tel-Aviv University), Yehuda Afek (Tel-Aviv University), James Aspnes (Yale University) and Edo Cohen (Tel-Aviv University)

A Probabilistic Performance Model and Tuning Framework for Eventually Consistent Distributed Storage Systems, Shankha Chatterjee (University of Waterloo) and Wojciech Golab (University of Waterloo)

Population protocols for leader election and exact majority with $O(\log^2 n)$ states and $O(\log^2 n) convergence time, Andreas Bilke (University of Salzburg), Colin Cooper (King’s College London), Robert Elsaesser (University of Salzburg) and Tomasz Radzik (King’s College London)

Rapid Asynchronous Plurality Consensus, Robert Elsässer (University of Salzburg), Tom Friedetzky (Durham University), Dominik Kaaser (Universität Hamburg), Frederik Mallmann-Trenn (Simon Fraser University) and Horst Trinker (University of Salzburg)

Symmetry Breaking in the CONGEST Model: Message- and Time-Efficient Algorithms for Ruling Sets, Shreyas Pai (The University of Iowa), Gopal Pandurangan (University of Houston), Sriram Pemmaraju (The University of Iowa), Talal Riaz (The University of Iowa) and Peter Robinson Royal Holloway, (University of London)

Digital Liquid Democracy: How to Vote Your Delegation Statement, Bingsheng Zhang (Lancaster University) and Hong-Sheng Zhou (Virginia Commonwealth University)

Brief Announcement: Fast Shared Counting using O(n) Compare-and-Swap Registers, Pankaj Khanchandani (ETH) and Roger Wattenhofer (ETH)

Fence Insertion for Straight-line Programs is in P, Mohsen Lesani (University of California, Riverside)

Brief Announcement: Leader Election in SINR using Arbitrary Transmission Power Control, Magnús Halldórsson (Reykjavik University), Stephan Holzer (MIT) and Evangelia Anna Markatou (MIT)

Brief Announcement: Certified Multiplicative Weights Update, or Verified Learning Without Regret, Alexander Bagnall (Ohio University), Samuel Merten (Ohio University) and Gordon Stewart (Ohio University)

Hierarchical Consensus, Benjamin Bengfort (University of Maryland) and Pete Keleher (University of Maryland)

Readers of Unbounded Registers Must Write, Eric Ruppert (York University)

Self-stabilizing Secure Computation, Karim Eldefrawy (SRI International), Shlomi Dolev (Ben-Gurion University of the Negev), Rafail Ostrovsky (UCLA), Moti Yung (Columbia University), Muni Venkateswarlu K (Ben-Gurion University of the Negev) and Juan Garay (Yahoo Research Labs)

Byzantine-Tolerant Machine Learning, Peva Blanchard (EPFL), El Mhamdi (Ecole polytechnique), Rachid Guerraoui (EPFL), Julien Stainer (EPFL)