Currently confirmed. The schedule is tentative and will be updated later.
Monday, June 16
Workshop: Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems (ApPLIED)
Time: Full day
TPC Co-chairs: Wojciech Golab and Andrea Vitaletti
General Co-chairs: Amy Babay, Ioannis Chatzigiannakis, and Elad Michael Schiller
Website: https://www.cse.chalmers.se/~elad/ApPLIED2025/
Friday, June 20
Tutorial: Information Theory and Applications
Organizer: Rotem Oshman
Time: morning/early afternoon
Abstract: The tutorial will cover the basics of information theory, including Shannon entropy and KL divergence, and their relationship to lossless coding. Using these tools we will tackle several communication complexity lower bounds and applications in distributed computing, such as the linear lower bound on the randomized communication complexity of set disjointness, and the lower bound of Izumi and Le Gall on listing triangles in CONGEST.
Date is undecided
Tutorial: Machine-Verifying Concurrent Algorithms
Organizer: Siddhartha Jayanti (siddhartha.visveswara.jayanti@dartmouth.edu)
Time: late morning/early afternoon
Abstract: Concurrent algorithms are intricate and their execution patterns on modern multiprocessors are extremely complex due to scheduling asynchrony, thus machine-certified proofs of their correctness are invaluable in ensuring reliability. This need for formal verification is bolstered by several examples of tragic outcomes due to failure to formally machine-verify concurrent algorithms. In fact, history has shown that the consequences of incorrect concurrent code can be catastrophic: a subtle priority inversion bug in its concurrent code crashed the Pathfinder Rover days after its deployment on Mars and jeopardized the entire multi-million dollar NASA space mission [Jones, 2013]; a race condition in the Northeast power grid’s energy management system started a cascading electrical outage that affected an estimated 55 million people in eight U.S. states and Ontario, Canada [Poulsen, 2004]; race conditions in the Therac-25 radiation therapy machine caused it to administer radiation doses that were over a hundred times as potent as the intended dose, which caused the deaths of at least three people and several more injuries [Leveson and Turner, 1993; Lim, 1998]. Examples of errors in published concurrent data structures are also not left wanting [Colvin and Groves, 2005; Doherty, 2003]. These fatal bugs all point to the importance of machine-verification of intricate concurrent algorithms, like the concurrent data structures we design in the distributed computing community.
Last year, we introduced meta-configurations tracking—a forward reasoning proof method that aids in producing machine-certified proofs of linearizability [Jayanti et al., POPL 2024]. Meta-configurations tracking is sound, complete, and universal, meaning that it can be used to produce a proof of linearizability for any correct data structure implementation of any type—including so-called future linearizable and far-future linearizable implementations which have traditionally been considered very hard to prove by the formal methods community. For example, we have used meta-configurations tracking to produce machine-certified proofs of Herlihy and Wing’s queue [Herlihy and Wing, 1990], MemSnap [Jayanti, Jayanti, and Jayanti, 2024], and Jayanti and Tarjan’s set union object [Jayanti and Tarjan, 2016]. The last of these is deployed in Google’s open-source graph-mining library and enables “shared memory parallel clustering algorithms which scale to graphs with tens of billions of edges”. Our work received a Google Code Health Platinum Award for Formal Verification of Multiprocessor Algorithms that Underlie Large-Scale Clustering.
In this tutorial, I will explain the meta-configurations tracking method for producing formal proofs of the linearizability of concurrent objects. I will also explain how to deploy the method to produce machine-certified proofs using TLA+ (temporal language of actions) and TLAPS (TLA+ proof system). Two goals of this tutorial are: (1) to introduce more members of the distributed computing community to formal methods and machine-verification; and (2) enable concurrent algorithmists to machine-verify their own data structures. The tutorial is designed to be accessible to a wide-audience in the distributed computing community.