CS Paper Radar

Simplicial Actions for Distributed Protocols

Philip Sink

cs.LO math.LO ·submitted 2026-08-17 17:57 UTC · v1

Abstract

This paper captures and extends some of the core results from the tech memo "A New Semantics for Belief Revision in Simplicial Complexes". As such, we set out to explore the implementation of action models in the setting of simplicial semantics for modal logic. Such an idea is not entirely new to the literature, showing up in both "A simplicial complex model for dynamic epistemic logic to study distributed task computability" and "Knowledge and Simplicial Complexes". However, we will explore action models in a more general setting. In particular, we will allow for action models for simplicial models for belief, as in "A Semantics for Belief in Simplicial Complexes". This will let us incorporate the notion of belief revision, as developed in "Simplicial Semantics for Belief Revision", into these action models. Moreover, we explicitly connect action models in the simplicial setting to distributed protocols as defined in the textbook "Distributed Computing Through Combinatorial Topology". We conclude with some speculation on how we might interpret distributed protocols with revision.

Closest papers

Nearest neighbours by meaning across the whole index.

Simplicial Semantics for Belief Revision

cs.LO math.LO ·2026-08-13 ·Philip Sink
similarity 0.72
Abstract

This paper will give a definition of belief revision within simplicial semantics. Starting from the work presented in "A Semantics for Belief in Simplicial Complexes" as a baseline, this paper modifies the semantics for belief given there to allow atomic formulae to be assigned to nodes, not facets. Conceptually and philosophically, this version of the semantics is better suited if one wishes to interpret the nodes of a simplicial model of epistemic logic as a "perspective" assigned to a particular agent. If nodes are perspectives, it then follows that worlds, or the facets of a simplicial model, are composed themselves of perspectives. This allows us to say that two worlds are more similar, or "nearer", if they share more perspectives. With this conceptual notion of nearness in hand, two different formal presentations of revision are given. We conclude by exploring some conceptual pitfalls surrounding these definitions under iterated revision, and motivate a few potential solutions that involve giving the agents a "memory" of what has been announced so far.

0.04

Unbelievably Complex

cs.LO ·2026-10-26 ·Hans van Ditmarsch, Djanira Gomes, Rojo Randrianomentsoa, Thomas Studer
similarity 0.62
Abstract

We present the directed simplicial complex: this is an extension of a simplicial complex with a direction on its faces. This enables us to model a local notion of belief in a three-valued semantics, in which formulas may be true, false, or undefined. Of particular interest is a class of directed simplicial complexes called cups, in which any maximal set of vertices of different colors is a facet. Cups permit a more concise relational representation. We give examples and applications of our logical semantics. We then provide a sound and complete axiomatization for the class of directed simplicial complexes and extend it to an axiomatization for the class of cups. We include a detailed technical comparison with other works on belief on complexes. Our work generalizes a prior axiomatization for knowledge on (undirected) impure simplicial complexes.

0.23

Scenario Proofs for Verification of Distributed Protocols

cs.PL ·2026-10-11 ·Zhendong Ang, George Pîrlea, Umang Mathur
similarity 0.56
Abstract

Formal verification of distributed protocols is still dominated by inductive-invariant proofs, whose central challenge is discovering strengthening assertions that rule out unreachable states. This burden is often misaligned with how protocol designers reason: they explain correctness by following representative executions, causal histories, and phase-structured interactions among nodes. This paper introduces scenario proofs, a verification methodology that makes such execution-oriented reasoning formal. A scenario is a structured expression describing representative protocol executions, enriched with ghost variables. Rather than enumerate all possible interleavings, a scenario describes canonical executions and uses a sound semi-commutation relation to account for reorderings that preserve feasibility and final states. Verification then factors into two main obligations. Coverage shows that every feasible protocol execution is equivalent, up to semi-commutation, to one described by the scenario; this obligation is independent of the safety property and serves as a reusable behavioral characterization of the protocol. Correctness proves the desired safety property only over the representative executions, using Hoare-style weakest-precondition reasoning along the scenario structure. We formalize the scenario language, its layered semantics, and proof rules for coverage and correctness. Through case studies of ring leader election, two-phase commit, a decentralized lock, two variants of multi-signature payment, and single-decree Paxos, we show how scenario proofs capture the causal and phase-based arguments used informally by protocol designers. These examples illustrate that scenario proofs can replace monolithic invariant discovery with structured reasoning over representative executions, while retaining a rigorous connection to all feasible protocol behaviors.

0.24

Evidence-Carrying Transport Across Effects

cs.LO ·2026-11-13 ·Félix Castro, Liron Cohen, Ariel Grunfeld, Étienne Miquey
similarity 0.54
Abstract

A program logic proved sound against one effectful semantics need not remain sound when the effect is re-implemented, yet the semantic relationship between reasoning before and after a change of effect is usually left implicit and re-established by hand. This paper provides a uniform, proof-relevant account of it. Working in realizability, where a notion of computation determines a model whose entailments carry explicit program evidence, we introduce simulations between effectful realizability cores, generalizing Longley's applicative morphisms to computation over an arbitrary strong monad. A single simulation transports the source logic along a ladder: it induces a morphism of the associated evidenced frames and, functorially, of the induced triposes. These passages are $2$-fully-faithful, so the three levels agree and a change of effect carries the entire higher-order program logic together with the evidence witnessing each derivation. A computationally dense simulation moreover computes a modality on the source logic, a nucleus through which the transport factors and which marks exactly the reasoning stable under the change, read off from the translation rather than postulated. This recovers known examples such as the double-negation modality of classical realizability, and examples such as sheafification arise from a modal refinement of the construction. Overall, the framework makes a change of effect a first-class object, one that can be composed, factored through its modality, and shown in cases not to exist, opening a path to transporting verified reasoning across effects.

0.34

Runtime Semantic Discovery for Evolving Action Alphabets

cs.SE cs.FLcs.PL ·2026-10-19 ·Pietro Bernabei, Rosario Pugliese
published similarity 0.54
Abstract · 10 pages, 2 figures. Version presented at the VORTEX 2026 workshop (co-located with ECOOP 2026)

Runtime Verification typically assumes a fixed alphabet of observable actions. This assumption becomes fragile in evolving software systems, where updates, reconfigurations, or architectural changes may rename, split, or fuse actions while preserving the system's high-level intent. In these cases, previously valid monitors and specifications may become misaligned with the running system. In this paper, we study runtime semantic discovery, namely the problem of identifying whether newly observed actions play the same operational role as previously known ones, without reconstructing a global behavioral model. To this end, we propose a local and runtime-computable notion of action similarity based on the neighbor contexts in which actions occur within execution traces. We define a family of k-neighbor equivalences and use them to compare systems whose observable alphabets differ. Our approach is intentionally lightweight: it does not aim to fully characterize behavioral preservation, but rather to identify candidate semantic correspondences between actions in evolving systems. We discuss the expressive power and limitations of neighbor-based equivalence and show how inferred correspondences can support the adaptation of runtime monitors and specifications under selected classes of alphabet evolution.

0.40

Merging and Evolution of Data Bases: A Many-Logic Approach

cs.LO cs.DB ·2026-10-29 ·Manuel A. Martins, Abilio Rodrigues
published similarity 0.54
Abstract · In Proceedings NCL'26, arXiv:2610.34489

A new approach to information-based logics using many-logic modal structures (MLMSs) was recently proposed by Martins et al. In such a setting, it is possible to have worlds with different underlying logics within the same frame, all anchored to a base lattice that contains the semantics of each logic as a down-complete sublattice. In this paper, we take the lattice L6, defined by the six-valued semantics of the logic of evidence and truth LET + K , as our base lattice. We also consider four-, three-, and two-valued formal systems associated with down-complete sublattices of L6. These logics are capable of representing paracomplete, paraconsistent, and classical contexts with six, four, three, and two informational scenarios, respectively. As applications of MLMSs, we will discuss the merging and temporal evolution of databases whose underlying logics are two-, three-, four-, and six-valued. We will also investigate inconsistency measures in this context.

0.47

An Algebraic Perspective on Operational Semantics

cs.PL ·2026-11-12 ·Eric Bond, Max New
theory similarity 0.54
Abstract

Languages with effects are typically given two independently specified semantic accounts: a denotational semantics based on (free) models, and an operational semantics defined by effect-specific reduction rules. This separation leads to two independently constructed semantic structures whose relationship must then be established a posteriori. We present a unified construction in which both denotational interpretation and operational reduction are constructed from an algebraic theory specifying the effects. We work with call-by-push-value extended by the operations of an algebraic theory. We prove equational canonicity and give a tree-based operational semantics that reduces every closed computation to a tree of operations. When the free model monad is a monadic container, we derive from it a configuration-based small-step semantics. Configurations are elements of the free model. Every step preserves the denotation. Under a condition we call affinity, every reduction terminates and at ground types computes the denotation. We instantiate the framework with state, errors, writer, and weighted and pre-convex probabilistic choice. For errors, writer and weighted choice we recover the familiar rules. For state we get a machine that runs the program from every initial state at once.

0.30

Formal Model Construction Guided by Model-Based Proof Sketches

cs.SE ·2026-09-24 ·Hongshu Wang, Xinyue Zuo, Yufan Cai, Neeraj Kumar Singh, Yamine Ait Ameur +1 more
benchmark similarity 0.54
Abstract

Formal modeling provides strong guarantees about system correctness, but developing and repairing formal models remains labor-intensive and requires substantial expertise in logic and formal reasoning. Recent LLM-based autoformalization agents seek to reduce this burden by generating candidate formal models and revising them using feedback from formal tools. However, the existing approaches follow a generate-and-repair paradigm, in which repairs are driven by verification failures of the generated model and therefore depend heavily on both the granularity of the feedback and the LLM's repair capability. As a consequence, a repair targeting one level of verification may invalidate properties at another level, which requires reasoning over the complete set of event guards. To address these limitations, we propose Proof-Sketch-Guided Formal Model Synthesis (ProGS), an autoformalization method centered on model-based proof sketches. A model-based proof sketch represents the proof structure of the target formal system as a tree. Internal nodes capture case splits and inductive reasoning steps, while leaf nodes correspond to concrete state-transition events that realize individual subgoals. ProGS uses LLMs to generate and repair these sketches, with verification failures mapped back to specific nodes and subtrees to provide structured guidance for iterative repair. Our evaluation on a benchmark of 27 formal systems shows that ProGS improves over state-of-the-art agentic formal modeling approaches in syntactic validity, deductive verifiability, and behavioral correctness, demonstrating the benefit of organizing formal model construction around hierarchical proof sketches.

0.23