Prophecy-Based Automated Verification of Message-Passing Programs
Takashi Nagatomi, Musashi Katsura, Naoki Kobayashi, Yusuke Matsushita, Ken Sakayori · 2026
Read Prophecy-Based Automated Verification of Message-Passing Programs by Takashi Nagatomi, Musashi Katsura, Naoki Kobayashi, Yusuke Matsushita, Ken Sakayori (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-28066.txt.
Description
Verifying message-passing concurrent programs is hard. Takashi Nagatomi and four colleagues reduce the problem to constrained Horn clause solving in 2026. Their trick, inspired by RustHorn, is prophecy. Each sender channel is represented by the list of values it will send in the future. Sender and receiver threads then encode as clauses, module by module. Time stamps on each message capture causal links between channels.
The reduction is proved sound and complete. A program is free of assertion failures exactly when the clause system is satisfiable. A prototype verifier for Rust-like programs was implemented. Experiments confirm the approach's effectiveness. Prophecy variables let the encoding reason backwards from future behaviour. That is what makes modular treatment of senders and receivers possible. The work brings a Rust verification technique to message-passing concurrency generally.
Catalog record
| CREATOR | Takashi Nagatomi, Musashi Katsura, Naoki Kobayashi, Yusuke Matsushita, Ken Sakayori |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 121 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.28066