Opening

Diana Ghinea

Byzantine-Resilient Approximate Agreement (tutorial)

Abstract: Consider a set of parties in a network holding real-valued inputs, and assume that some of these parties may be byzantine (i.e., malicious). Approximate Agreement requires the honest parties to obtain "very close" outputs that lie within the range of the honest parties' inputs. In this tutorial, we will dive into this problem and explore key results, including optimal resilience and optimal synchronous round complexity.

Stephan Felber

The Topological Characterization of Stabilizing Consensus

Abstract: Stabilizing consensus is a non-terminating variant of the canonical terminating consensus problem: Instead of irrevocably terminating on one common value, processes may change their minds arbitrarily often as long as they eventually "stabilize" on a single common output value. Clearly, stabilizing consensus is solvable whenever terminating consensus is. However, exactly which models admit a solution has remained an open question since Charron-Bost and Moran introduced the MinMax algorithm.

We showcase the blurred nature of the solvability boundary in terms of message adversaries via examples, highlighting why a complete characterization has remained elusive. We then present a sharp solvability boundary in topological terms. Our result both solves an open problem and represents an excellent example of how topology can provide crucial insights into distributed computing.

Timothé Albouy

Exploring the Decidability of Task Problems with Output Sets

Abstract: This talk addresses the decidability of task problems, i.e., distributed problems expressed as sets of distributed tasks. We introduce a new class of task problems called Set of Output Sets (SOS) problems, and defined by the set $O$ (called SOS) of distinct sets of output values that can be produced across all executions of the system. We then demonstrate that this class of problems is decidable: there is a procedure determining whether any SOS problem is solvable asynchronously under $f$ crashes. The decision rule is as follows: An SOS problem is always solvable when $f=0$, and it is solvable under $f > 0$ if and only if the graph $G=(O,\subset)$ (linking two output sets if one includes the other) is connected. This demonstrates a fundamental gap between consensus and $k$-set agreement. Indeed, if we replace validity by a weaker completeness property (guaranteeing that all output sets of size at most $k$ are produced), consensus becomes impossible if $f>0$, but $k{\geq}2$-set agreement is solvable under any number of crashes $f$. Finally, we study a novel family of SOS problems called $d$-disagreement, which requires the system to always produce $d$ different output values, and we show that its implementability condition is related to the harmonic series.

Yannis Coutouly

The general message adversary framework and the t-resilient model

Abstract: In this talk, we introduce and motivate the general message adversary setting of IIS. Then, we will discuss several representations of the t-resilient model and relate them to existing intuition in the distributed community.  Finally, we will see how the number of holes in the geometrization of a general message adversary is not necessarily a good indicator of its computability power. 

Faith Ellen

How Exhaustive Does an Extension-Based Proof Need to Be?

Abstract: The class of extension-based proofs encompasses traditional valency arguments. It has been shown that they are insufficient to establish the impossibility of (n-1)-set agreement among n ≥ 3 processes in an asynchronous system with crash failures. We generalize this definition to k-exhaustive extension-based proofs, in which a prover can learn the maximum length of all executions involving a set of at most k processes from a specified configuration (which may be infinite). An upper bound on the length of these executions enables the prover to determine the outputs of all these executions. When k = n, this enables the prover to perform an exhaustive search of all reachable configurations, so it knows everything about the protocol. On the other hand, extension based proofs are as powerful as 1-exhaustive extension-based proofs. For any task with no deterministic, wait-free solution among n ≥ 2 processes, we show that there is an (n-1)-exhaustive extension-based proof of its impossibility. This is done using a new characterization of such tasks. In contrast, we prove that for 1 ≤ k ≤ n-2, there is no k-exhaustive extension-based proof of the impossibility of (n-1)-set agreement.

This is joint work with Shihao Liu, Leqi Zhu, Eli Gafni, and Rati Gelashvili and appeared at OPODIS 2025.

Hagit Attiya, Ami Paz

Wait-free solvability of general tasks

Abstract: We present a direct characterization of wait-free solvability for general chromatic tasks: a task $T=(\calI,\calO,\Delta)$ is wait-free solvable if and only if there exists a $\Delta$-carried piecewise-linear map $f:|\calI|\to|\calO|$ that is finite-to-one. Thus, solvability is characterized entirely in terms of the input and output complexes, without quantifying over subdivisions.

Maurice Herlihy

Cross-Chain consensus requires signatures

Abstract: We introduce a new connectivity-based technique for proving lower bounds and impossibility for cross-chain consensus in a realistic blockchain model. We show that cross-chain consensus is unattainable through authenticated channels alone; it strictly requires a common cryptographic signature scheme that enables third-party verification. Furthermore, the same proof techniques extend to show that even given such a scheme, XC-consensus requires at least $m$ communication rounds, where $m$ is the number of participants. This $m$-round bound is shown to be tight through a constructive protocol

Closing

Ulrich Schmid