Best Paper:
The DISC Program Committee selected the following paper to receive the DISC 2022 best paper award:
Smoothed Analysis of Information Spreading in Dynamic Networks
by Michael Dinitz, Jeremy Fineman, Seth Gilbert, and Calvin Newport.
This paper applies smoothed analysis to the study of $k$-message broadcast in dynamic networks. It shows that even with a small amount of smoothing, a simple distributed random broadcast strategy can significantly outperform the existing worst-case lower bounds. In addition to that, it proves that in static networks the runtime of this strategy further improves, establishing that even in the context of smoothing, changing topologies remain more difficult to move information through than their static counterparts. Interestingly, the tools developed for these analyses can be applied to improve the best-known bounds for k-message broadcast, without smoothing, in the well-mixed dynamic network setting.
Best Student Paper:
The DISC Program Committee selected the following two papers to receive the DISC 2022 best student paper award:
Polynomial-Time Verification and Testing of Implementations of the Snapshot Data Structure
by Gal Amram, Avi Hayoun, Lior Mizrahi and Gera Weiss
and
Byzantine Consensus is Θ(n²): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!
by Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira.
The first paper focuses on the correctness of implementations of the snapshot data structure in terms of linearizability and shows that such implementations can be verified in polynomial time. This presents a significant improvement considering that verifying linearizability of implementations of concurrent data structures, in general, is EXPSPACE-complete in the number of program states, and testing linearizability is NP-complete in the length of the tested execution.
The second paper presents SQUAD, a partially synchronous Byzantine consensus protocol with quadratic worst-case communication complexity. The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has at least quadratic communication complexity in the worst-case, but a protocol with such a complexity was only known for synchronous environments and the previously best protocols for partial synchrony had a cubic communication complexity.
