paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Towards Verifying Crash Consistency

迈向崩溃一致性验证
OOPSLA 9(OOPSLA2)2025匹配度 3/10 · 该论文属于 PL 形式化验证(类型系统保证崩溃一致性),与用户关注的“形式化验证”领域有远端交集,但完全不涉及 LLM/Agent、浮点程序分析、贝叶斯程序分析,也没有将静态分析应用于 ML 系统或 Agentic 程序,因而未触及用户研究画像中的核心问题。引用 0 inbox
Keonho Lee, Conan Truong, Brian Demsky
crossref: 2026-09-10

AI 速览

一句话:提出 CrashLang 语言与类型系统,保证良类型数据结构实现崩溃一致,并实现编译器验证五个基准。

持久内存、CXL 内存共享等技术使数据可跨越崩溃事件,但如何保证崩溃后数据仍一致且可安全访问仍是难题;已有工具多用于找 bug,无法保证程序崩溃一致。本文提出 CrashLang 语言及其类型系统,利用 commit-store 模式:单个存储操作在逻辑上提交整个数据结构操作,从而通过类型系统静态保证良类型实现具有崩溃一致性。作者证明了良类型程序的崩溃一致性,并实现 CrashLang 编译器原型。评估覆盖 Harris 链表、Treiber 栈、Michael-Scott 队列、RCU 二叉搜索树和 Cache-Line 哈希表五个基准,实验验证各实现均能在崩溃后正确存活。

问题
持久内存与 CXL 等技术支持数据跨崩溃存活,但现有 bug 查找工具无法保证程序在崩溃后数据一致且可安全访问。
方法
设计 CrashLang 语言及其类型系统,基于 commit-store 模式将单次存储视为整个数据结构操作的逻辑提交,并证明良类型程序崩溃一致,同时实现编译器原型。
评估
在 Harris 链表、Treiber 栈、Michael-Scott 队列、RCU 二叉搜索树和 Cache-Line 哈希表五个基准上实验验证实现能正确跨越崩溃。
原文摘要(Abstract)

Compute Express Link (CXL) memory sharing, persistent memory, and other related technologies allow data to survive crash events. A key challenge is ensuring that data is consistent after crashes such that it can be safely accessed. While there has been much work on bug-finding tools for persistent memory programs, these tools cannot guarantee that a program is crash-consistent. In this paper, we present a language, CrashLang , and its type system, that together guarantee that well-typed data structure implementations written in CrashLang are crash-consistent. CrashLang leverages the well-known commit-store pattern in which a single store logically commits an entire data structure operation. In this paper, we prove that well-typed CrashLang programs are crash-consistent, and provide a prototype implementation of the CrashLang compiler. We have evaluated CrashLang on five benchmarks: the Harris linked list, the Treiber stack, the Michael–Scott queue, a Read-Copy-Update binary search tree, and a Cache-Line Hash Table. We experimentally verified that each implementation correctly survives crashes.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot2952,
  title = {Towards Verifying Crash Consistency},
  author = {Keonho Lee and Conan Truong and Brian Demsky},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {9},
  number = {OOPSLA2},
  year = {2025},
  doi = {10.1145/3763077}
}