PODC 2018 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:Laboratoire
  • 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 Mitrovi{\’c}, 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 Függer, 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, Przemysław Uznański
  • 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, Andréa 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