PODC 2018 accepted papers:
https://www.podc.org/podc2018/program/


REGULAR PAPERS

Almost-Surely Terminating Asynchronous Byzantine Agreement Revisited
Laasya Bangalore, Ashish Choudhury, Arpita Patra

Atomic Cross-Chain Swaps
Maurice Herlihy

Round- and Message-Optimal Distributed Graph Algorithms
Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc

Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics
Mohsen Ghaffari, Johannes Lengler

Separating Lock-Freedom from Wait-Freedom
Hagit Attiya, Armando Castaneda, Danny Hendler, Matthieu Perrin

Distributed coloring in sparse graphs with fewer colors
Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, Louis Esperet

Passing Messages while Sharing Memory
Marcos K. Aguilera, Naama Ben-David, Irina Calciu, Rachid Guerraoui, Erez Petrank, Sam Toueg

Locking Timestamps Versus Locking Objects
Marcos K. Aguilera, Tudor David, Rachid Guerraoui, Junxiong Wang

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, Ronitt Rubinfeld

Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
Francois Le Gall, Frederic Magniez

Lower Bounds for Searching Robots, some Faulty
Andrey Kupavskii, Emo Welzl

Population stability: regulating size in the presence of an adversary
Shafi Goldwasser, Rafail Ostrovsky, Alessandra Scafuro, Adam Sealfon

Property Testing of Planarity in the CONGEST Model
Reut Levi, Moti Medina, Dana Ron

Revisionist Simulations: A New Approach to Proving Space Lower Bounds
Faith Ellen, Rati Gelashvili, Leqi Zhu

Congested Clique Algorithms for the Minimum Cut Problem
Mohsen Ghaffari, Krzysztof Nowicki

Sublinear Message Bounds for Randomized Agreement
John Augustine, Anisur Rahaman Molla, Gopal Pandurangan

Deterministic Digital Clustering of Wireless Ad Hoc Networks
Tomasz Jurdzinski, Dariusz R. Kowalski, Michal Rozanski, Grzegorz Stachowiak

Nesting-Safe Recoverable Linearizability: Modular Constructions for Non-Volatile Memory
Hagit Attiya, Ohad Ben-Baruch, Danny Hendler

Leader Election in Well-Connected Graphs
Seth Gilbert, Peter Robinson, Suman Sourav

Recoverable Mutual Exclusion Under System-Wide Failures
Wojciech Golab, Danny Hendler

Relaxed Schedulers Can Efficiently Parallelize Sequential Algorithms
Dan Alistarh, Trevor Brown, Justin Kopinsky, Giorgi Nadiradze

On Local Distributed Sampling and Counting
Weiming Feng, Yitong Yin

Distributed Spanner Approximation
Keren Censor-Hillel, Michal Dory

Deterministic Abortable Mutual Exclusion with Sublogarithmic Adaptive RMR Complexity
Adam Alon, Adam Morrison

Distributed Approximation of Minimum $k$-edge-connected Spanning Subgraphs
Michal Dory

Near-Optimal Distributed Routing with Low Memory
Michael Elkin, Ofer Neiman

Tight Bounds for Asymptotic and Approximate Consensus
Matthias Fugger, Thomas Nowak, Manfred Schwarz

The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
Dan Alistarh, Christopher De Sa, Nikola Konstantinov

Improved Distributed Delta-Coloring
Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus

An Asynchronous Computability Theorem for Fair Adversaries
Petr Kuznetsov, Thibault Rieutord, Yuan He

Leveraging Indirect Signaling for Topology Inference and Fast Broadcast
Magnus M. Halldorsson, Tigran Tonoyan

Fair Leader Election for Rational Agents in Asynchronous Rings and Networks
Assaf Yifrach, Yishay Mansour

Silence!
Guy Goren, Yoram Moses

Locally-Iterative Distributed (Delta + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models
Leonid Barenboim, Michael Elkin, Uri Goldenberg

Optimal Gossip Algorithms for Exact and Approximate Quantile Computations
Bernhard Haeupler, Jeet Mohapatra, Hsin-Hao Su

Interactive Distributed Proofs
Gillat Kol, Rotem Oshman, Raghuvansh R. Saxena

Distributed Uniformity Testing
Orr Fischer, Uri Meir, Rotem Oshman

A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in $\tilde{O}(n^{3/2})$ Rounds
Udit Agarwal, Vijaya Ramachandran, Valerie King, Matteo Pontecorvi

The Energy Complexity of Broadcast
Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, Seth Pettie

On the Classification of Deterministic Objects via Set Agreement Power
David Yu Cheng Chan, Vassos Hadzilacos, Sam Toueg

Minor Excluded Network Families Admit Fast Distributed Algorithms
Bernhard Haeupler, Jason Li, Goran Zuzic


BRIEF ANNOUNCEMENTS

Brief Announcement: Asynchronous Secure Distributed Computing with Transferrable Non-equivocation Revisited
Rishabh Bhadauria, Ashish Choudhury

Brief Announcement: Specification and Implementation of Replicated List
Hengfeng Wei, Yu Huang, Jian Lu

Brief Announcement: Beeping a Time-Optimal Leader Election
Fabien Dufoulon, Janna Burman, Joffroy Beauquier

Brief Announcement: Graph Exploration Using Constant-Size Memory and Storage
Naoki Kitamura, Kazuki Kakizawa, Yuya Kawabata, Taisuke Izumi

Brief Announcement: Sustainable Blockchains through Proof of eXercise
Ali Shoker

Brief Announcement: MUSIC: Multi-Site Entry Consistency for Geo-Distributed Services
Bharath Balasubramanian, Richard Schlichting, Pamela Zave

Brief Announcement: Persistent Multi-Word Compare-And-Swap
Matej Pavlovic, Alex Kogan, Virendra J. Marathe, Tim Harris

Brief Announcement: Automatic log enhancement for fault diagnosis
Jia Tong, Li Ying

Brief Announcement: Performance Prediction for Coarse-Grained Locking
Vitaly Aksenov, Dan Alistarh, Petr Kuznetsov

Brief Announcement: Broadcast in radio networks: time vs. energy tradeoffs.
Marek Klonowski, Dominik Pajak

Brief Announcement: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
Christian Konrad, Viktor Zamaraev

Brief Announcement: Population Protocols Are Fast
Adrian Kosowski, Przemyslaw Uznanski

Brief Announcement: Optimal Record and Replay under Causal Consistency
Russell L. Jones, Muhammad S. Khan, Nitin H. Vaidya

Brief Announcement: Partially Replicated Causally Consistent Shared Memory: Lower Bounds and An Algorithm
Zhuolun Xiang, Nitin H. Vaidya

Brief Announcement: Space-Optimal Naming in Population Protocols
Janna Burman, Joffroy Beauquier, Devan Sohier

Brief Announcement: A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems
Sarah Cannon, Joshua J. Daymude, Cem Gokmen, Dana Randall, Andrea W. Richa

Brief Announcement: Simple and Local Independent Set Approximation
Ravi B. Boppana, Magnus M. Halldorsson, Dror Rawitz

Brief Announcement: 2D-Stack: A scalable lock-free stack design that continuously relaxes semantics for better performance
Aras Atalar, Adones Rukundo, Philippas Tsigas