Reference. A Language-Agnostic Logical Relation for Message-Passing Protocols

Today’s computing landscape has been gradually shifting to applications targeting distributed and heterogeneous systems, such as cloud computing and Internet of Things (IoT) applications. These applications are predominantly concurrent, employ message-passing, and interface with foreign objects, ranging from externally implemented code to actual physical devices such as sensors. Verifying that the resulting systems adhere to the intended protocol of interaction is challenging – the usual assumption of a common implementation language, let alone a type system, no longer applies, ruling out any verification method based on them. This paper develops a framework for certifying protocol compliance of heterogeneous message-passing systems. It contributes the first mechanization of a language-agnostic logical relation, asserting that its inhabitants comply with the protocol specified. This definition relies entirely on a labelled transition-based semantics, accommodating arbitrary inhabitants, typed and untyped alike, including foreign objects. As a case study, the paper considers two scenarios: (1) per-instance verification of a specific application or hardware device, and (2) once-and-for-all verification of well-typed applications for a given type system. The logical relation and both scenarios are mechanized in the Coq theorem prover.

Cite

Cite as @zhang-2025-a (helia, typst) · \cite{zhang-2025-a} (LaTeX)
BibTeX
bibtex · 8 lines
@misc{zhang-2025-a,
  author = {Tesla Zhang and Sonya Simkin and Rui Li and Yue Yao and Stephanie Balzer},
  title = {A Language-Agnostic Logical Relation for Message-Passing Protocols},
  year = {2025},
  month = {6},
  eprint = {2506.10026},
  archiveprefix = {arXiv}
}
hayagriva YAML (typst)
yaml · 12 lines
zhang-2025-a:
  type: misc
  title: A Language-Agnostic Logical Relation for Message-Passing Protocols
  author:
  - Zhang, Tesla
  - Simkin, Sonya
  - Li, Rui
  - Yao, Yue
  - Balzer, Stephanie
  date: 2025-06
  serial-number:
    arxiv: '2506.10026'
Cited by (1)

Mechanizing Synthetic Tait Computability in Istari li_etal_2025

Categorical gluing is a powerful technique for proving meta-theorems of type theories such as canonicity and normalization. Synthetic Tait Computability (STC) provides an abstract treatment of the complex gluing models by internalizing the gluing category into a modal dependent type theory with a phase distinction. This work presents a mechanization of STC in the Istari proof assistant. Istari is a Martin-Löf-style extensional type theory with equality reflection, which avoids much of the explicit transport reasoning typically found in intensional proof assistants. This work develops a reusable library for synthetic phase distinction, including modalities, extension types, and strict glue types, and applies it to two case studies: (1) a canonicity model for dependent type theory with dependent products and booleans with large elimination, and (2) a Kripke canonicity model for the cost-aware logical framework. Our results demonstrate that the core STC constructions can be formalized essentially verbatim in Istari, preserving the elegance of the on-paper arguments while ensuring machine-checked correctness.
PDF · DOI · arXiv · pldb
Cites 41 works (2 here)
With notes (2)

A Logical Approach to Type Soundness timany-2024-a

Type soundness, which asserts that “well-typed programs cannot go wrong,” is widely viewed as the canonical theorem one must prove to establish that a type system is doing its job. It is commonly proved using the so-called syntactic approach (also known as progress and preservation ), which has had a huge impact on the study and teaching of programming language foundations. Unfortunately, syntactic type soundness is a rather weak theorem. It only applies to programs that are well typed in their entirety and thus tells us nothing about the many programs written in “safe” languages that make use of “unsafe” language features. Even worse, it tells us nothing about whether type systems achieve one of their main goals: enforcement of data abstraction. One can easily define a language that enjoys syntactic type soundness and yet fails to support even the most basic modular reasoning principles for abstraction mechanisms like closures, objects, and abstract data types. Given these concerns, we argue that programming languages researchers should no longer be satisfied with proving syntactic type soundness and should instead start proving semantic type soundness , a more useful theorem that captures more accurately what type systems are actually good for. Semantic type soundness is an old idea—Milner’s original account of type soundness from 1978 was semantic—but it fell out of favor in the 1990s due to limitations and complexities of denotational models. In the succeeding decades, thanks to a series of technical advances—notably, step-indexed Kripke logical relations constructed over operational semantics and higher-order concurrent separation logic as consolidated in the Iris framework in Coq—we can now build (machine-checked) semantic soundness proofs at a much higher level of abstraction than was previously possible. The resulting “logical” approach to semantic type soundness has already been employed to great effect in a number of recent papers, but those papers typically (a) concern advanced problem scenarios that complicate the presentation, (b) assume significant prior knowledge of the reader, and (c) suppress many details of the proofs. Here, we aim to provide a gentler, more pedagogically motivated introduction to logical type soundness, targeted at a broader audience that may or may not be familiar with logical relations and Iris. As a bonus, we also show how logical type soundness proofs can easily be generalized to establish an even stronger relational property— representation independence —for realistic type systems.
DOI

Session Types as Intuitionistic Linear Propositions caires-2010-session

DOI
External (39)
zhang-2025-a reference entries/refs/zhang-2025-a/zhang-2025-a.hel