Sergio Rajsbaum

Eric Goubault, Roman Kniazev, Jeremy Ledent et al.

In recent years, several authors have been investigating simplicial models, a model of epistemic logic based on higher-dimensional structures called simplicial complexes. In the original formulation, simplicial models were always assumed to be pure, meaning that all worlds have the same dimension. This is equivalent to the standard S5n semantics of epistemic logic, based on Kripke models. By removing the assumption that models must be pure, we can go beyond the usual Kripke semantics and study epistemic logics where the number of agents participating in a world can vary. This approach has been developed in a number of papers, with applications in fault-tolerant distributed computing where processes may crash during the execution of a system. A difficulty that arises is that subtle design choices in the definition of impure simplicial models can result in different axioms of the resulting logic. In this paper, we classify those design choices systematically, and axiomatize the corresponding logics. We illustrate them via distributed computing examples of synchronous systems where processes may crash.

Gilde Valeria Rodríguez, Borzoo Bonakdarpour, Armando Castañeda et al.

We introduce c-Lattice Aggregation, a fault-tolerant reconstruction problem for distributed verification under crash and Byzantine failures. In our setting, n asynchronous processes supervise a concurrent execution I: each process holds a local sample, and must collaboratively reconstruct I from partial, potentially overlapping observations. A protocol solves c-Lattice Aggregation if at least c correct processes output the complete execution I, while all correct outputs are comparable and bounded by I. This strengthens Lattice Agreement [Attiya, Herlihy and Rachman, 1995] and Byzantine Lattice Agreement [Di Luna et al., 2020; Zheng and Garg, 2020]. We parameterize inputs by a redundancy parameter x -- every element of I appears in at least x initial samples -- and establish tight feasibility thresholds. Under crash failures with at most t faulty processes, Lattice Aggregation is solvable if and only if x >= t + 1. Under Byzantine failures with t < n/3, c-Lattice Aggregation is solvable if and only if x >= 2t + c. All bounds are tight: we present matching algorithms based on SCD-broadcast [Imbs et al., 2018; Khanchandani and Wattenhofer, 2024] and indistinguishability-based lower bounds. Finally, we define globally dependent languages -- those for which no partial view can certify correctness, including consensus, linearizability, k-set agreement, and leader election -- and prove that soundness of any monitoring system is achievable if and only if c-Lattice Aggregation is solved, yielding the first complete characterization of fault-tolerant verification under Byzantine failures.

Augustin Albert, Sergio Rajsbaum

We consider $n$ asynchronous processes prone to crashes, communicating via shared read-write registers, and study the wait-free solvability of approximate agreement: given inputs, processes must output values that are close to each other, and satisfy a validity property. At the very least, if inputs are identical, all outputs must equal that input. The problem has been studied for various input spaces: continuous, discrete, one-dimensional or multidimensional. For metric spaces, validity requires outputs to lie in the convex hull of the inputs. For graphs, and more generally simplicial complexes, several conditions exist. We focus on simplex validity: if inputs span a simplex $σ$, then outputs are in $σ$. Agreement requires that outputs span a simplex. Solvability depends on the input space, validity condition, and number of processes. For example, the problem is solvable for all $n$ in the plane, but only for $n \leq 2$ when removing a point. For a graph, solvability for $n=2$ holds iff the graph is connected, but $n\geq 3$ requires acyclicity. In the continuous setting, we consider CUB spaces: a broad class of metric spaces admitting a unique convexity definition, subsuming classical $ε$-agreement on $[0,1]$ and $m$-dimensional approximate agreement. Our results show that $ε$-agreement is solvable in every CUB space. In the discrete case, we prove that simplex agreement on a simplicial complex $\mathcal{C}$ is solvable for $n+1$ processes iff $\mathcal{C}$ is $(n-1)$-connected. We discuss several consequences, including a proof of a conjecture by Ledent.

Sophia Knight, David Lehnherr, Sergio Rajsbaum

The coordinated attack problem models the challenge of coordinating a joint action within a bounded time by communicating over unreliable links. It was the first distributed computing problem proven unsolvable. Its analysis also revealed the importance of common knowledge, a central concept in epistemic logic. However, the randomized version of coordinated attack, which is solvable, has not, to the best of our knowledge, been studied through the lens of probabilistic epistemic logic, where processes generate randomness by flipping coins. We present an epistemic logic framework for studying randomized algorithms that execute for a bounded number of rounds. The framework applies to coordinated attack, approximate agreement, and consensus, and supports dynamic graph models: synchronous systems in which reliable processes execute a bounded number of rounds while an adversary determines which messages are lost. Our approach combines techniques from the logical characterization of dynamic networks and task solvability with ideas from probabilistic dynamic epistemic logic. It is inspired by the operational model of Varghese and Lynch for randomized coordinated attack. More broadly, the resulting notion of probabilistic epistemic task solvability provides a foundation for the epistemic study of randomized distributed computation. Using this framework, we analyze the Varghese-Lynch algorithm from a knowledge-theoretic perspective, providing a formal treatment of the algorithm and its lower bound. As a byproduct, we strengthen the lower bound and show it is tight. The proof relies on indistinguishability arguments, demonstrating that reasoning about knowledge remains essential in the probabilistic setting. We also formalize the notion of information level introduced by Varghese and Lynch, showing that it corresponds to a specific epistemic formula.

Éric Goubault, Jérémy Ledent, Sergio Rajsbaum

The standard semantics of multi-agent epistemic logic S5 is based on Kripke models whose accessibility relations are reflexive, symmetric and transitive. This one dimensional structure contains implicit higher-dimensional information beyond pairwise interactions, that we formalized as pure simplicial models in a previous work (Information and Computation, 2021). Here we extend the theory to encompass simplicial models that are not necessarily pure. The corresponding class of Kripke models are those where the accessibility relation is symmetric and transitive, but might not be reflexive. Such models correspond to the epistemic logic KB4 . Impure simplicial models arise in situations where two possible worlds may not have the same set of agents. We illustrate it with distributed computing examples of synchronous systems where processes may crash.

Sergio Rajsbaum

The problem of $A$ privately transmitting information to $B$ by a public announcement overheard by an eavesdropper $C$ is considered. To do so by a deterministic protocol, their inputs must be correlated. Dependent inputs are represented using a deck of cards. There is a publicly known signature $(a,b,c)$, where $n = a + b + c + r$, and $A$ gets $a$ cards, $B$ gets $b$ cards, and $C$ gets $c$ cards, out of the deck of $n$ cards. Using a deterministic protocol, $A$ decides its announcement based on her hand. Using techniques from coding theory, Johnson graphs, and additive number theory, a novel perspective inspired by distributed computing theory is provided, to analyze the amount of information that $A$ needs to send, while preventing $C$ from learning a single card of her hand. In one extreme, the generalized Russian cards problem, $B$ wants to learn all of $A$'s cards, and in the other, $B$ wishes to learn something about $A$'s hand.