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
|