Cyclic Message Histories for Automated Safety Verification of Distributed Algorithms

This conference talk presents innovative research on automated safety verification for distributed systems using the actor model. Learn about a novel separation logic approach that leverages message histories to identify execution cycles in distributed algorithms like Paxos. The researchers demonstrate how properly over-approximating cyclic message histories enables sound automated verification through goal-directed abstract interpretation, eliminating the need for manually specified inductive invariants. This breakthrough allows for the first-ever automated safety proof of Paxos without user intervention. The presentation was delivered at the Theory and Practice of Static Analysis workshop (TPSA'25) in January 2025, sponsored by ACM SIGPLAN.