Verified Causal Broadcast with Liquid Haskell

Protocols to ensure that messages are delivered in causal order are a ubiquitous building block of distributed systems. For instance, key-value stores can use causally ordered message delivery to ensure causal consistency -- a sweet spot in the availability/consistency trade-off space -- and replicated data structures rely on the existence of an underlying causally-ordered messaging layer to ensure that geo-distributed replicas eventually converge to the same state. A causal delivery protocol ensures that when a message is delivered to a process, any causally preceding messages sent to the same process have already been delivered to it. While causal message delivery protocols are widely used in distributed systems, verification of the correctness of those protocols is less common, much less machine-checked proofs about executable implementations. We implemented a standard causal broadcast protocol in Haskell and used the Liquid Haskell solver-aided verification system to express and mechanically prove that messages will never be delivered to a process in an order that violates causality. To do so, we express a process-local causal delivery property using refinement types, and we prove that it holds of our implementation using Liquid Haskell's theorem-proving facilities, resulting in the first machine-checked proof of correctness of an executable causal broadcast implementation. We then put our verified causal broadcast implementation to work as the foundation of a distributed key-value store implemented in Haskell.