CS Paper Radar

Safe Composition of CFSM Systems via Partial Gateways

Franco Barbanera

cs.LO ·submitted 2026-09-28 11:25 UTC · v1
publishedtheory

Abstract

The Participants-as-Interfaces (PaI) methodology for system composition proposes that system participants can be regarded as interfaces. For each system in a given collection, one participant is designated to serve as its interface. When the systems are composed, these interface participants are replaced with gateways that communicate with one another by forwarding messages. We generalise the approach to partial gateways, where gateways can forward only a chosen set of messages. As for the standard PaI approach, we exploit such extended version for systems of communicating finite state machines (CFSMs). This extension is fully detailed for the binary case, and can be scaled up to the multicomposition case. We prove that many relevant communication properties (deadlock-freeness, reception-error-freeness, etc.) are preserved by PaI composition via partial gateways in case also the connection policy (i.e. the system representing the way we wish gateways interact with each other) enjoys the same properties. Such a proof turns out to be just a corollary of a property preservation result for a restricted and partial composition method, dubbed fusion-composition. Fusion-composition hence turns out to be at the heart of the PaI composition approach.

Comment
In Proceedings ICE 2026, arXiv:2609.30353
Journal ref
EPTCS 453, 2026, pp. 2-22
DOI
10.4204/EPTCS.453.2

Closest papers

Nearest neighbours by meaning across the whole index.

Coexponential Exploration in the Clef Programming Language

cs.PL cs.DCcs.LO ·2026-10-09 ·Houston Haynes
theory similarity 0.64
Abstract · 36 pages, 4 figures, 3 tables. Updated for contributions from Karwowski et al. and clarified Padovani's fair-termination result

Clef was created as a concurrent programming language whose compiler tracks state ownership, waiting computations and request dependencies. We develop a coexponential account of stateful services and their client pools within this design. Delimited continuations retain the computation and resources needed to complete each interaction. These structures give our compiler premises for verifying service composition and preserving it through native lowering to multiple hardware targets. We connect finite actor state transitions to the initial, service and final rules of a coexponential server. A separate operational account relates actor dispatch to single-use continuation frames. We prove state-ownership and reply preservation, give a finite communication-summary analysis, and derive circular-wait exclusion under stated assumptions. A further result identifies when changing service order preserves both state and replies. Our Program Semantic Graph retains these facts through compilation. We are researching reusable proofs to confirm the ownership and communication interfaces, while our BAREWire implementation connects message meaning to its unboxed representation across respective endpoints. A distributed worker example preserves request identity across suspension, reordered replies and boundary conversion. Urschel's growth bounds inform a solver service; a distributed ADM update additionally preserves joint samples, metric evidence and request identity. Our two-category account connects component refinement, reusable proof terms and native realization. Protocols determine the admissible interactions, continuations expose their storage requirements, and retained dependencies support differential compilation. Developers can express ordinary stateful services while the compiler carries the conditions for their correct composition across execution targets.

0.19

Composition without a Host: Carrying the Spatiotemporal-Composability Guarantee of Plugin-Based Agents across Processes

cs.AI cs.MA ·2026-08-28 ·Hanzhang Jia, Liheng Zeng, Hao Cheng, Yi Gao, Bo Ma +1 more
benchmarktheory similarity 0.64
Abstract · Still just draft, version 0.4.1. The author contributions are still under discussion, and the draft doesn't represent the final decision

Plugin-based agents assemble capabilities at runtime, and the spatiotemporal-composability calculus proves a reversibility guarantee for this assembly. However, the guarantee is carried by a single process, which confines all components, sessions, and recovery records to one failure domain, where a fault spreads past the plugin boundary, and process death interrupts every session the process hosts. Resting only on the hypotheses the calculus already states and the stateless interface of the model call, this paper relaxes the single-process restriction of the calculus to an arbitrary assignment of components and records to processes, gives four sufficient conditions, and proves with Theorem 1, derived from the four lemmas, that the reversibility guarantee holds across processes when these conditions are met. Based on Theorem 1, this paper constructs Logos, a cross-process plugin-based agent in the peer-process and name-routed form of ROS, where a plugin is a process, the router holds only a rebuildable routing table, and the session state needed for recovery lives in an append-only transcript owned by no process. Under one fault on two hundred benchmark tasks across three configurations, the single-process reference lost every session and scored 1.5 percent on the official validator, the MCP configuration kept its sessions while spending 1099 calls on a dead endpoint, and Logos kept every session alive, wasted zero calls, and succeeded on 120 tasks against 102 for both configurations combined. At the mechanism level, eighty sessions terminated at four points of the tool-call cycle all resumed with no repeated action, 3,500 concurrent calls paired with zero violations, and one bus hop cost 1 in 823 of the model's first token. The results show that the reversibility guarantee holds across processes and that assembly itself can leave the host process.

0.16

Scenario Proofs for Verification of Distributed Protocols

cs.PL ·2026-10-11 ·Zhendong Ang, George Pîrlea, Umang Mathur
similarity 0.62
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

A Type System for Communication-Safe Hardware Design

cs.PL cs.ARcs.LO ·2026-10-19 ·Aditya Ranjan Jha, Jason Zhijingcheng Yu, Umang Mathur, Prateek Saxena
top venuecode/data similarity 0.59
Abstract · 69 pages, 4 figures, 3 tables. Conditionally accepted to POPL 2027

Hardware components communicate through clock-cycle-sensitive protocols. Hardware Description Languages (HDLs), however, provide limited support for expressing these protocols or for checking that independently developed components agree on them. When components disagree, the composed design can perform unsynchronized exchanges or stop making progress. We call these failures communication-safety violations. Communication safety is thus a global property, determined by interactions between components. This makes it difficult to check modularly. This paper presents Pact, a typed extension of Anvil for modular verification of communication safety in synchronous hardware. Pact types describe message-passing, control-flow, and clock-cycle behaviour. Each component is checked against its type. Compatible types guarantee that the components compose into a communication-safe system. Pact also supports incremental design. It can check a subsystem before the rest of the system exists. The check produces a summary type that captures the communication behaviour left for future compositions. To reduce annotation burden, Pact infers types by abstracting payload values while preserving communication, timing, control, and fairness. These inferred types are optimal for the checker: whenever some checker-accepted types can prove compatibility, the inferred types can prove it as well. Type inference and type checking are decidable, and compatibility is decided by a sound and complete algorithm. We implement Pact by extending the Anvil compiler and evaluate it along five dimensions: detecting communication errors in incremental design, expressiveness on ten clock-cycle-accurate translations of open-source hardware IPs, compatibility-checking time, generated hardware overhead, and annotation burden. Pact expresses realistic protocols and verifies all ten benchmarks in reasonable time.

0.73

A Principled Approach to Concurrency, Nondeterminism, and Asynchrony in Choreographies

cs.PL ·2026-11-18 ·Xueying Qin, Marco Peressotti, Fabrizio Montesi
theory similarity 0.59
Abstract · 31 pages including appendix

Choreographic programming (CP) describes a distributed system as a global program and compiles it into communicating network programs via endpoint projection (EPP). Asynchrony captures the independent progress of communicating processes, while nondeterminism captures the range of behaviours that can arise from their interactions. However, the integration of both features into a theory of CP is absent. We present Nyarlathotep, the first asynchronous nondeterministic CP framework. We define its operational semantics of choreographies and networks using labelled transition systems. Besides asynchrony and choreographic nondeterminism, Nyarlathotep supports expressive features including general branching, out-of-order execution, and general recursion with parameterised procedures that processes can enter independently. We prove EPP sound and complete, establishing strong behavioural equivalence between the semantics of choreographies and their projected networks. We prove that projected networks are communication-safe and deadlock-free. We mechanised all our results in Lean 4.

0.16

Parameterized Reachability for Register Machines with Data

cs.FL ·2026-10-06 ·Parosh Aziz Abdulla, Mohammed Faouzi Atig, Abhijith R Nair, K Narayan Kumar, Prakash Saivasan
similarity 0.58
Abstract

We investigate the parameterized reachability problem for concurrent register machines over infinite data domains. In this framework, each machine is a program equipped with a set of local registers, the communication across machines is mediated through a set of shared registers. Both local and shared registers can take values from an infinite data domain. The program's primitive operations include copying values between registers, assigning constants, comparing registers for (dis-)equality, and nondeterministic assignments that store an arbitrary domain value into a local register. The parameterized reachability problem considers a program and a target location, asking whether there exists some n in Naturals such that an execution of n identical machines (referred to as instances) results in at least one instance reaching the specified location. We show that this problem is Pspace-complete in the general case and it becomes undecidable if a freshness assumption (i.e., each assignment must produce a unique value distinct from all constants) is applied to nondeterministic assignments. This undecidability persists even for systems restricted to two shared and two local registers. Finally, we establish optimal decidability results for two restricted settings: when each thread is limited to a single local register, or when the system utilizes only one shared register.

0.30

Finite State Machine-Based Traffic Orchestration for Multi-Engine Analysis Platforms

cs.SE ·2026-10-05 ·Ankit Kumar, Thirumoorthi Thangamani
similarity 0.58
Abstract

Modern application-security platforms route live traffic from a single proxy into several independent analysis engines -- behavioral anomaly detection, authentication analysis, resource discovery, access-control inspection, among others. Each engine's appetite for traffic changes on its own schedule, yet the proxy can honor only one forwarding instruction per resource. We present a traffic-orchestration method that models the combined needs of all engines as a single composite finite state machine (FSM) whose state space is the Cartesian product of per-engine states. Every reachable composite state pre-maps to one forwarding configuration, so runtime reduces to a lookup rather than a negotiation. We add two refinements: time-based expiry treated as a first-class FSM transition enabling declarative traffic decay, and per-state multi-tier outputs that let one machine serve every service level. The design is fully declarative, engine-agnostic, and scales to N engines without re-architecture.

0.28

Mechanizing Choreographic Programs and Hoare Logic with State Transformers

cs.PL ·2026-08-17 ·Timon Böhler, Simon Daniel, David Richter, Pascal Weisenburger, Mira Mezini
theory similarity 0.58
Abstract · To be published in the TyDe 2026 proceedings

Choreographic programming is a programming model for developing distributed applications where an entire communication protocol is written as a single program, which a compiler then projects to one process per participant. Choreographic programming abstracts over low-level network communication primitives such as sockets, and provides a high degree of safety guarantees with deadlock freedom ensured by construction. Mechanizing choreographies necessarily deals with both operations specific to distributed programming and standard (local) operations that also occur in non-distributed programs, as well as the typical issues of binding and substitution. We aim to sidestep the latter issues, thereby obtaining a more concise mechanization that focuses on the essential distributed aspects of choreographies. To this end, we use a method recently proposed by Thiemann to elegantly model deadlock-free processes in a dependently typed language: Using state transformers to represent the computations performed by each process. We bring the state transformer model to choreographies, allowing us to reduce the usual mechanization effort around binding and substitution, and to abstract over the details of the "local" aspects of the language. We mechanize in Lean a choreographic language that supports point-to-point communication, broadcasting, recursive procedures, and local stateful methods, allowing each participant to be assigned a different set of methods. We prove soundness and completeness of endpoint projection, establish deadlock freedom for the projected processes, prove confluence, and verify a Hoare logic for choreographies.

0.33