paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Modal Crash Types for WAR-Aware Intermittent Computing

面向 WAR 感知间歇计算的模态崩溃类型
TOPLAS ACM Transactions on Programming Languages and Systems2025匹配度 2/10 · 该论文是类型系统与模态逻辑的形式化工作,面向间歇计算中的检查点与重执行正确性,与用户核心关注的 PL↔AI、LLM/Agent 改进静态分析、浮点程序分析、贝叶斯程序分析均无直接交集;仅在 PL 形式语义/类型系统层面有边缘关联。引用 0 inbox
Myra Dotzel, Farzaneh Derakhshan, Milijana Surbatovich, Limin Jia
crossref: 2026-09-10

AI 速览

一句话:提出崩溃类型系统与模态逻辑基础,用于建模并证明间歇计算中检查点与重执行的正确性。

能量收集设备等间歇执行环境随时可能断电,系统需在运行时保存检查点并在崩溃后恢复、重执行,且重执行必须等价于持续供电下的执行。本文研究间歇计算的逻辑基础,将检查点、崩溃、恢复和重执行建模为对“崩溃类型”的计算,并借鉴伴随逻辑引入两个伴随模态算子,分别刻画部分(重)执行中的持久与瞬态内存值,以及检查点和恢复引发的状态转换。该形式化可容纳多种检查点策略。作者为核心演算定义崩溃类型系统,并设计一种面向崩溃类型的新型逻辑关系,以证明间歇系统的正确性。

问题
间歇计算设备会发生任意断电,其检查点与恢复后的重执行必须能被持续供电执行所模拟,如何为其提供类型与逻辑基础尚不明确。
方法
借鉴伴随逻辑,引入两个伴随模态算子定义崩溃类型,将检查点、崩溃、恢复和重执行建模为类型计算,并为核心演算建立崩溃类型系统与新型逻辑关系。
评估
评估以形式化证明为主:通过所定义的崩溃类型系统和逻辑关系证明间歇系统执行的正确性,并说明该形式化可适配多种检查点策略。
原文摘要(Abstract)

Programs are executed intermittently on devices that experience arbitrary power failures such as Energy Harvesting Devices (EHDs). To ensure progress, intermittent systems need runtime support to checkpoint state and re-execute after power failure by restoring the last saved state. Such re-execution should be correct , i.e., simulated by a continuously-powered execution. We study the logical underpinning of intermittent computing and model checkpoint, crash, restore, and re-execution operations as computation on crash types. We draw inspiration from adjoint logic and define crash types by introducing two adjoint modality operators to model persistent and transient memory values of partial (re-)executions and the transitions between them caused by checkpoints and restoration. Our formalism is general enough to accommodate a variety of checkpointing policies. We define a crash type system for a core calculus. To prove the correctness of intermittent systems, we define a novel logical relation for crash types.

链接与引用

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

BibTeX
@inproceedings{DotzelDSJ25,
  title = {Modal Crash Types for WAR-Aware Intermittent Computing},
  author = {Myra Dotzel and Farzaneh Derakhshan and Milijana Surbatovich and Limin Jia},
  booktitle = {TOPLAS},
  year = {2025},
  doi = {10.1145/3716311}
}