PODC 2017 Proceedings

SESSION: Keynote 1

Some Sequential Algorithms are Almost Always Parallel

  • Guy E. Blelloch

SESSION: Session 1

  • Jennifer Welch

Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks

  • Artur Czumaj
  • Peter Davies

The Space Requirement of Local Forwarding on Acyclic Networks

  • Boaz Patt-Shamir
  • Will Rosenbaum

Communication Primitives in Cognitive Radio Networks

  • Seth Gilbert
  • Fabian Kuhn
  • Chaodong Zheng

Broadcasting in Noisy Radio Networks

  • Keren Censor-Hillel
  • Bernhard Haeupler
  • D. Ellis Hershkowitz
  • Goran Zuzic

Gossip in a Smartphone Peer-to-Peer Network

  • Calvin Newport

SESSION: Session 2

  • Faith Ellen

Analyzing Contention and Backoff in Asynchronous Shared Memory

  • Naama Ben-David
  • Guy E. Blelloch

A Layered Architecture for Erasure-Coded Consistent Distributed Storage

  • Kishori M. Konwar
  • N. Prakash
  • Nancy Lynch
  • Muriel Médard

Seeing is Believing: A Client-Centric Specification of Database Isolation

  • Natacha Crooks
  • Youer Pu
  • Lorenzo Alvisi
  • Allen Clement

Space Complexity of Fault-Tolerant Register Emulations

  • Gregory Chockler
  • Alexander Spiegelman

Brief Announcement: Readers of Wait-Free Unbounded Registers Must Write

  • Eric Ruppert

Brief Announcement: Fast Shared Counting using (O(n)) Compare-and-Swap Registers

  • Pankaj Khanchandani
  • Roger Wattenhofer

Brief Announcement: Fence Insertion for Straight-line Programs is in P

  • Mohsen Lesani

SESSION: Session 3

  • Kishori Konwar

LCL Problems on Grids

  • Sebastian Brandt
  • Juho Hirvonen
  • Janne H. Korhonen
  • Tuomo Lempiäinen
  • Patric R.J. Östergård
  • Christopher Purcell
  • Joel Rybicki
  • Jukka Suomela
  • Przemysław Uznański

On the Multiparty Communication Complexity of Testing Triangle-Freeness

  • Orr Fischer
  • Shay Gershtein
  • Rotem Oshman

What Can be Sampled Locally?

  • Weiming Feng
  • Yuxin Sun
  • Yitong Yin

Distributed MST and Routing in Almost Mixing Time

  • Mohsen Ghaffari
  • Fabian Kuhn
  • Hsin-Hao Su

Distributed MIS via All-to-All Communication

  • Mohsen Ghaffari

Brief Announcement: Optimal Address-Oblivious Epidemic Dissemination

  • Hugues Mercier
  • Laurent Hayez
  • Miguel Matos

SESSION: Keynote 2

Blockchains and the Future of Distributed Computing (slides)

  • Maurice Herlihy

SESSION: Session 4

  • Calvin Newport

A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities

  • Michael Elkin

Distributed Approximation of Maximum Independent Set and Maximum Matching

  • Reuven Bar-Yehuda
  • Keren Censor-Hillel
  • Mohsen Ghaffari
  • Gregory Schwartzman

Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity

  • Leonid Barenboim
  • Michael Elkin
  • Tzalik Maimon

Optimal Distance Labeling Schemes for Trees

  • Ofer Freedman
  • Paweł Gawrychowski
  • Patrick K. Nicholson
  • Oren Weimann

Brief Announcement: How Large is your Graph?

  • Varun Kanade
  • Frederik Mallmann-Trenn
  • Victor Verdugo

Brief Announcement: Distributed Approximation for Tree Augmentation

  • Keren Censor-Hillel
  • Michal Dory

Brief Announcement: Leader Election in SINR Model with Arbitrary Power Control

  • Magnús M. Halldórsson
  • Stephan Holzer
  • Evangelia Anna Markatou

Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets

  • Shreyas Pai
  • Gopal Pandurangan
  • Sriram V. Pemmaraju
  • Talal Riaz
  • Peter Robinson

SESSION: Session 5

  • Nancy Lynch

Recoverable Mutual Exclusion in Sub-logarithmic Time

  • Wojciech Golab
  • Danny Hendler

Randomized Abortable Mutual Exclusion with Constant Amortized RMR Complexity on the CC Model

  • George Giakkoupis
  • Philipp Woelfel

Transactional Lock Elision Meets Combining

  • Alex Kogan
  • Yossi Lev

On Using Time Without Clocks via Zigzag Causality

  • Asa Dan
  • Rajit Manohar
  • Yoram Moses

Brief Announcement: Proust: A Design Space for Highly-Concurrent Transactional Data Structures

  • Thomas Dickerson
  • Paul Gazzillo
  • Maurice Herlihy
  • Eric Koskinen

Brief Announcement: Gossiping with Latencies

  • Seth Gilbert
  • Peter Robinson
  • Suman Sourav

Brief Announcement: A Probabilistic Performance Model and Tuning Framework for Eventually Consistent Distributed Storage Systems

  • Shankha Chatterjee
  • Wojciech Golab

SESSION: Session 6

  • Gadi Taubenfeld

Effectiveness of Delaying Timestamp Computation

  • Sandeep S. Kulkarni
  • Nitin H. Vaidya

Symmetry Breaking with Noisy Processes

  • Seth Gilbert
  • Calvin Newport

The Power of Choice in Priority Scheduling

  • Dan Alistarh
  • Justin Kopinsky
  • Jerry Li
  • Giorgi Nadiradze

A Template for Implementing Fast Lock-free Trees Using HTM

  • Trevor Brown

Adding Concurrency to Smart Contracts

  • Thomas Dickerson
  • Paul Gazzillo
  • Maurice Herlihy
  • Eric Koskinen

SESSION: Keynote 3

Verifiable Outsourced Computation: A Survey

  • Rosario Gennaro

SESSION: Session 7

  • Lorenzo Alvisi

FruitChains: A Fair Blockchain

  • Rafael Pass
  • Elaine Shi

Coordination Without Prior Agreement

  • Gadi Taubenfeld

Ignore or Comply?: On Breaking Symmetry in Consensus

  • Petra Berenbrink
  • Andrea Clementi
  • Robert Elsässer
  • Peter Kling
  • Frederik Mallmann-Trenn
  • Emanuele Natale

Life Beyond Set Agreement

  • David Yu Cheng Chan
  • Vassos Hadzilacos
  • Sam Toueg

Brief Announcement: Hierarchical Consensus

  • Benjamin Bengfort
  • Pete Keleher

Brief Announcement: Statement Voting and Liquid Democracy

  • Bingsheng Zhang
  • Hong-sheng Zhou

Brief Announcement: Rapid Asynchronous Plurality Consensus

  • Robert Elsässer
  • Tom Friedetzky
  • Dominik Kaaser
  • Frederik Mallmann-Trenn
  • Horst Trinker

Brief Announcement: Object Oriented Consensus

  • Yehuda Afek
  • James Aspnes
  • Edo Cohen
  • Danny Vainstein

SESSION: Session 8

  • Irina Calciu

Greedy Routing and the Algorithmic Small-World Phenomenon

  • Karl Bringmann
  • Ralph Keusch
  • Johannes Lengler
  • Yannic Maus
  • Anisur Rahaman Molla

Triangle Finding and Listing in CONGEST Networks

  • Taisuke Izumi
  • François Le Gall

Asynchronous Shared Channel

  • Gianluca De Marco
  • Grzegorz Stachowiak

Self-organized Segregation on the Grid

  • Hamed Omidvar
  • Massimo Franceschetti

Brief Announcement: Efficient Self-Stabilizing 1-Maximal Matching Algorithm for Arbitrary Networks

  • Michiko Inoue
  • Fukuhito Ooshita
  • Sébastien Tixeuil

Brief Announcement: Secure Self-Stabilizing Computation

  • Shlomi Dolev
  • Karim Eldefrawy
  • Juan Garay
  • Muni Venkateswarlu Kumaramangalam
  • Rafail Ostrovsky
  • Moti Yung

Stateless Computation

  • Danny Dolev
  • Michael Erdmann
  • Neil Lutz
  • Michael Schapira
  • Adva Zair

SESSION: Session 9

  • Alexander Schwarzmann

Towards Efficient Verification of Population Protocols

  • Michael Blondin
  • Javier Esparza
  • Stefan Jaax
  • Philipp J. Meyer

Clocked Population Protocols

  • James Aspnes

A Distributed Learning Dynamics in Social Groups

  • L. Elisa Celis
  • Peter M. Krafft
  • Nisheeth K. Vishnoi

Brief Announcement: Population Protocols for Leader Election and Exact Majority with O(log2 n) States and O(log2 n) Convergence Time

  • Andreas Bilke
  • Colin Cooper
  • Robert Elsässer
  • Tomasz Radzik

Brief Announcement: Byzantine-Tolerant Machine Learning

  • Peva Blanchard
  • El Mahdi El Mhamdi
  • Rachid Guerraoui
  • Julien Stainer

Brief Announcement: Certified Multiplicative Weights Update: Verified Learning Without Regret

  • Alexander Bagnall
  • Samuel Merten
  • Gordon Stewart