Skip to content

Instantly share code, notes, and snippets.

@ept
Last active May 20, 2024 03:03
Show Gist options
  • Save ept/b6872fc541a68a321a26198b53b3896b to your computer and use it in GitHub Desktop.
Save ept/b6872fc541a68a321a26198b53b3896b to your computer and use it in GitHub Desktop.

Correctness proofs of distributed systems with Isabelle

This Gist accompanies a Talk by Martin Kleppmann:

Download Isabelle to play with the proofs. Have fun!

Abstract

Testing systems is great, but tests can only explore a finite set of inputs and behaviors. Many real systems, especially distributed systems, have a potentially infinite state space. If you want to be sure that a program does the right thing in all possible situations, testing is not sufficient: you need proof. Only mathematical proof, e.g. by induction, can cover an infinite state space.

Pen-and-paper proofs are well established in mathematics, but they need to be laboriously checked by hand, and humans sometimes make mistakes. Automated theorem provers and computerized proof assistants can help here. This talk introduces Isabelle/HOL, an interactive proof assistant that can be used to formally prove the correctness of algorithms. It is somewhat like a programming language and REPL for proofs.

In this talk we will explore how Isabelle can be used to analyze algorithms for distributed systems, and prove them correct. We will work through some example problems in live demos, and prove real theorems about some simple algorithms. Proof assistants still have a pretty steep learning curve, and this talk won’t be able to teach you everything, but you will get a sense of the style of reasoning, and maybe you will be tempted to try it for yourself.

theory
Consensus_Demo
imports
Network
begin
datatype 'val msg
= Propose 'val
| Accept 'val
fun acceptor_step where
\<open>acceptor_step state (Receive sender (Propose val)) =
(case state of
None \<Rightarrow> (Some val, {Send sender (Accept val)}) |
Some v \<Rightarrow> (Some v, {Send sender (Accept v)}))\<close> |
\<open>acceptor_step state _ = (state, {})\<close>
fun proposer_step where
\<open>proposer_step None (Request val) = (None, {Send 0 (Propose val)})\<close> |
\<open>proposer_step None (Receive _ (Accept val)) = (Some val, {})\<close> |
\<open>proposer_step state _ = (state, {})\<close>
fun consensus_step where
\<open>consensus_step proc =
(if proc = 0 then acceptor_step else proposer_step)\<close>
(* Invariant 1: for any proposer p, if p's state is ``Some val'',
then there exists a process that has sent a message
``Accept val'' to p. *)
definition inv1 where
\<open>inv1 msgs states \<longleftrightarrow>
(\<forall>proc val. proc \<noteq> 0 \<and> states proc = Some val \<longrightarrow>
(\<exists>sender. (sender, Send proc (Accept val)) \<in> msgs))\<close>
(* Invariant 2: if a message ``Accept val'' has been sent, then
the acceptor is in the state ``Some val''. *)
definition inv2 where
\<open>inv2 msgs states \<longleftrightarrow>
(\<forall>sender recpt val. (sender, Send recpt (Accept val)) \<in> msgs \<longrightarrow>
states 0 = Some val)\<close>
lemma invariant_propose:
assumes \<open>msgs' = msgs \<union> {(proc, Send 0 (Propose val))}\<close>
and \<open>inv1 msgs states \<and> inv2 msgs states\<close>
shows \<open>inv1 msgs' states \<and> inv2 msgs' states\<close>
proof -
have \<open>\<forall>sender proc val.
(sender, Send proc (Accept val)) \<in> msgs' \<longleftrightarrow>
(sender, Send proc (Accept val)) \<in> msgs\<close>
using assms(1) by blast
then show ?thesis
by (meson assms(2) inv1_def inv2_def)
qed
lemma invariant_decide:
assumes \<open>states' = states (0 := Some val)\<close>
and \<open>msgs' = msgs \<union> {(0, Send sender (Accept val))}\<close>
and \<open>states 0 = None \<or> states 0 = Some val\<close>
and \<open>inv1 msgs states \<and> inv2 msgs states\<close>
shows \<open>inv1 msgs' states' \<and> inv2 msgs' states'\<close>
proof -
{
fix p v
assume asm: \<open>p \<noteq> 0 \<and> states' p = Some v\<close>
hence \<open>states p = Some v\<close>
by (simp add: asm assms(1))
hence \<open>\<exists>sender. (sender, Send p (Accept v)) \<in> msgs\<close>
by (meson asm assms(4) inv1_def)
hence \<open>\<exists>sender. (sender, Send p (Accept v)) \<in> msgs'\<close>
using assms(2) by blast
}
moreover {
fix p1 p2 v
assume asm: \<open>(p1, Send p2 (Accept v)) \<in> msgs'\<close>
have \<open>states' 0 = Some v\<close>
proof (cases \<open>(p1, Send p2 (Accept v)) \<in> msgs\<close>)
case True
then show ?thesis
by (metis assms(1) assms(3) assms(4) fun_upd_same inv2_def option.distinct(1))
next
case False
then show ?thesis
using asm assms(1) assms(2) by auto
qed
}
ultimately show ?thesis
by (simp add: inv1_def inv2_def)
qed
lemma invariant_learn:
assumes \<open>states' = states (proc := Some val)\<close>
and \<open>(sender, Send proc (Accept val)) \<in> msgs\<close>
and \<open>inv1 msgs states \<and> inv2 msgs states\<close>
shows \<open>inv1 msgs states' \<and> inv2 msgs states'\<close>
proof -
{
fix p v
assume asm: \<open>p \<noteq> 0 \<and> states' p = Some v\<close>
have \<open>\<exists>sender. (sender, Send p (Accept v)) \<in> msgs\<close>
proof (cases \<open>p = proc\<close>)
case True
then show ?thesis
using asm assms(1) assms(2) by auto
next
case False
then show ?thesis
by (metis asm assms(1) assms(3) fun_upd_apply inv1_def)
qed
}
moreover {
fix p1 p2 v
assume \<open>(p1, Send p2 (Accept v)) \<in> msgs\<close>
hence \<open>states' 0 = Some v\<close>
by (metis assms fun_upd_apply inv2_def)
}
ultimately show ?thesis
by (simp add: inv1_def inv2_def)
qed
lemma invariant_proposer:
assumes \<open>proposer_step (states proc) event = (new_state, sent)\<close>
and \<open>msgs' = msgs \<union> ((\<lambda>msg. (proc, msg)) ` sent)\<close>
and \<open>states' = states (proc := new_state)\<close>
and \<open>execute consensus_step (\<lambda>p. None) UNIV (events @ [(proc, event)]) msgs' states'\<close>
and \<open>inv1 msgs states \<and> inv2 msgs states\<close>
shows \<open>inv1 msgs' states' \<and> inv2 msgs' states'\<close>
proof (cases event)
case (Receive sender msg)
then show ?thesis
proof (cases msg)
case (Propose val)
then show ?thesis
using Receive assms by auto
next
case (Accept val) (* proposer receives Accept message: learn the decided value *)
then show ?thesis
proof (cases \<open>states proc\<close>)
case None
hence \<open>states' = states (proc := Some val) \<and> msgs' = msgs\<close>
using Accept Receive assms(1) assms(2) assms(3) by auto
then show ?thesis
by (metis Accept Receive assms(4) assms(5) execute_receive invariant_learn)
next
case (Some v)
then show ?thesis
using assms by auto
qed
qed
next
(* on a Request event, proposer sends a Propose message if its state
is None, or ignores the event if already learnt a decision *)
case (Request val)
then show \<open>inv1 msgs' states' \<and> inv2 msgs' states'\<close>
proof (cases \<open>states proc\<close>)
case None
hence \<open>states' = states \<and> msgs' = msgs \<union> {(proc, Send 0 (Propose val))}\<close>
using Request assms(1) assms(2) assms(3) by auto
then show ?thesis
by (simp add: assms(5) invariant_propose)
next
case (Some v)
then show ?thesis using assms by auto
qed
next
case Timeout
then show \<open>inv1 msgs' states' \<and> inv2 msgs' states'\<close>
using assms by auto
qed
lemma invariant_acceptor:
assumes \<open>acceptor_step (states 0) event = (new_state, sent)\<close>
and \<open>msgs' = msgs \<union> ((\<lambda>msg. (0, msg)) ` sent)\<close>
and \<open>states' = states (0 := new_state)\<close>
and \<open>execute consensus_step (\<lambda>p. None) UNIV (events @ [(0, event)]) msgs' states'\<close>
and \<open>inv1 msgs states \<and> inv2 msgs states\<close>
shows \<open>inv1 msgs' states' \<and> inv2 msgs' states'\<close>
proof (cases event)
case (Receive sender msg)
then show \<open>inv1 msgs' states' \<and> inv2 msgs' states'\<close>
proof (cases msg)
case (Propose val)
then show ?thesis
proof (cases \<open>states 0\<close>)
case None (* not decided yet: decide now *)
hence \<open>states' = states (0 := Some val) \<and>
msgs' = msgs \<union> {(0, Send sender (Accept val))}\<close>
using Receive Propose assms(1) assms(2) assms(3) by auto
(* for some reason sledgehammer couldn't find the line above *)
then show ?thesis
by (simp add: None assms(5) invariant_decide)
next
case (Some val') (* already decided previously *)
hence \<open>states' = states \<and>
msgs' = msgs \<union> {(0, Send sender (Accept val'))}\<close>
using Receive Propose assms(1) assms(2) assms(3) by auto
(* for some reason sledgehammer couldn't find the line above *)
then show ?thesis
by (metis Some assms(3) assms(5) fun_upd_same invariant_decide)
qed
next
case (Accept val)
then show ?thesis
using Receive assms by auto
qed
next
case (Request val)
then show \<open>inv1 msgs' states' \<and> inv2 msgs' states'\<close>
using assms by auto
next
case Timeout
then show \<open>inv1 msgs' states' \<and> inv2 msgs' states'\<close>
using assms by auto
qed
lemma invariants:
assumes \<open>execute consensus_step (\<lambda>x. None) UNIV events msgs' states'\<close>
shows \<open>inv1 msgs' states' \<and> inv2 msgs' states'\<close>
using assms proof(induction events arbitrary: msgs' states' rule: List.rev_induct)
case Nil
from this show \<open>inv1 msgs' states' \<and> inv2 msgs' states'\<close>
using execute_init inv1_def inv2_def by fastforce
next
case (snoc x events)
obtain proc event where \<open>x = (proc, event)\<close>
by fastforce
hence exec: \<open>execute consensus_step (\<lambda>p. None) UNIV
(events @ [(proc, event)]) msgs' states'\<close>
using snoc.prems by blast
from this obtain msgs states sent new_state
where step_rel1: \<open>execute consensus_step (\<lambda>x. None) UNIV events msgs states\<close>
and step_rel2: \<open>consensus_step proc (states proc) event = (new_state, sent)\<close>
and step_rel3: \<open>msgs' = msgs \<union> ((\<lambda>msg. (proc, msg)) ` sent)\<close>
and step_rel4: \<open>states' = states (proc := new_state)\<close>
by auto
have inv_before: \<open>inv1 msgs states \<and> inv2 msgs states\<close>
using snoc.IH step_rel1 by fastforce
then show \<open>inv1 msgs' states' \<and> inv2 msgs' states'\<close>
proof (cases \<open>proc = 0\<close>)
case True
then show ?thesis
by (metis consensus_step.simps exec inv_before invariant_acceptor
step_rel2 step_rel3 step_rel4)
next
case False
then show ?thesis
by (metis consensus_step.simps exec inv_before invariant_proposer
step_rel2 step_rel3 step_rel4)
qed
qed
theorem agreement:
assumes \<open>execute consensus_step (\<lambda>x. None) UNIV events msgs states\<close>
and \<open>states proc1 = Some val1\<close> and \<open>states proc2 = Some val2\<close>
shows \<open>val1 = val2\<close>
proof -
have \<open>states 0 = Some val1\<close>
by (metis assms(1) assms(2) inv1_def inv2_def invariants)
moreover have \<open>states 0 = Some val2\<close>
by (metis assms(1) assms(3) inv1_def inv2_def invariants)
ultimately show \<open>val1 = val2\<close>
by simp
qed
end
section \<open>Network model\<close>
text \<open>We define a simple model of a distributed system. The system consists of
a set of processes, each of which has a unique identifier and local state that
it can update. There is no shared state between processes; processes can
communicate only by sending messages to each other. The communication is
\emph{asynchronous} -- that is, messages may be delayed arbitrarily,
reordered, duplicated, or dropped entirely.
In reality, processes execute concurrently, possibly at different speeds (in
particular, a process may fail by stopping execution entirely). To model this,
we say that the system as a whole makes progress by one of the processes
performing an execution step, and processes may perform steps in any order.
An execution step involves a process handling an \emph{event}. An event could
be one of several things: a request from a user, receiving a message from
another process, or the elapsing of a timeout. In response to such an event,
a process can update its local state, and/or send messages to other processes.\<close>
theory
Network
imports
Main
begin
text \<open>A message is always sent to a particular recipient. This datatype
encapsulates the name of the recipient process and the message being sent.\<close>
datatype ('proc, 'msg) send
= Send (msg_recipient: 'proc) (send_msg: 'msg)
text \<open>An event that a process may handle: receiving a message from another
process, or a request from a user, or an elapsed timeout.\<close>
datatype ('proc, 'msg, 'val) event
= Receive (msg_sender: 'proc) (recv_msg: 'msg)
| Request 'val
| Timeout
text \<open>A step function takes three arguments: the name of the process that is
executing, its current local state, and the event being handled. It returns two
things: the new local state, and a set of messages to send to other processes.\<close>
type_synonym ('proc, 'state, 'msg, 'val) step_func =
\<open>'proc \<Rightarrow> 'state \<Rightarrow> ('proc, 'msg, 'val) event \<Rightarrow> ('state \<times> ('proc, 'msg) send set)\<close>
text \<open>A process may only receive a message from a given sender if that sender
process did previously send that message. Request and Timeout events can occur
at any time.\<close>
fun valid_event :: \<open>('proc, 'msg, 'val) event \<Rightarrow> 'proc \<Rightarrow>
('proc \<times> ('proc, 'msg) send) set \<Rightarrow> bool\<close> where
\<open>valid_event (Receive sender msg) proc msgs = ((sender, Send proc msg) \<in> msgs)\<close> |
\<open>valid_event (Request _) _ _ = True\<close> |
\<open>valid_event Timeout _ _ = True\<close>
text \<open>A valid execution of a distributed algorithm is a sequence of execution
steps. At each step, any of the processes handles any valid event. We call the
step function to compute the next state for that process, and any messages it
sends are added to a global set of all messages ever sent.\<close>
inductive execute ::
\<open>('proc, 'state, 'msg, 'val) step_func \<Rightarrow> ('proc \<Rightarrow> 'state) \<Rightarrow> 'proc set \<Rightarrow>
('proc \<times> ('proc, 'msg, 'val) event) list \<Rightarrow>
('proc \<times> ('proc, 'msg) send) set \<Rightarrow> ('proc \<Rightarrow> 'state) \<Rightarrow> bool\<close> where
\<open>execute step init procs [] {} init\<close> |
\<open>\<lbrakk>execute step init procs events msgs states;
proc \<in> procs;
valid_event event proc msgs;
step proc (states proc) event = (new_state, sent);
events' = events @ [(proc, event)];
msgs' = msgs \<union> ((\<lambda>msg. (proc, msg)) ` sent);
states' = states (proc := new_state)
\<rbrakk> \<Longrightarrow> execute step init procs events' msgs' states'\<close>
subsection \<open>Lemmas for the network model\<close>
text \<open>We prove a few lemmas that are useful when working with the above network model.\<close>
inductive_cases execute_indcases: \<open>execute step init procs events msg states\<close>
lemma execute_init:
assumes \<open>execute step init procs [] msgs states\<close>
shows \<open>msgs = {} \<and> states = init\<close>
using assms by(auto elim: execute.cases)
inductive_cases execute_snocE [elim!]:
\<open>execute step init procs (events @ [(proc, event)]) msgs' states'\<close>
lemma execute_step:
assumes \<open>execute step init procs (events @ [(proc, event)]) msgs' states'\<close>
shows \<open>\<exists>msgs states sent new_state.
execute step init procs events msgs states \<and>
proc \<in> procs \<and>
valid_event event proc msgs \<and>
step proc (states proc) event = (new_state, sent) \<and>
msgs' = msgs \<union> ((\<lambda>msg. (proc, msg)) ` sent) \<and>
states' = states (proc := new_state)\<close>
using assms by auto
lemma execute_receive:
assumes \<open>execute step init procs (events @ [(recpt, Receive sender msg)]) msgs' states'\<close>
shows \<open>(sender, Send recpt msg) \<in> msgs'\<close>
using assms execute_step by fastforce
end
theory
Only_Fives
imports
Main
begin
inductive only_fives :: \<open>nat list \<Rightarrow> bool\<close> where
\<open>only_fives []\<close> |
\<open>\<lbrakk>only_fives xs\<rbrakk> \<Longrightarrow> only_fives (xs @ [5])\<close>
theorem only_fives_concat:
assumes \<open>only_fives xs\<close> and \<open>only_fives ys\<close>
shows \<open>only_fives (xs @ ys)\<close>
using assms proof (induction ys rule: List.rev_induct)
case Nil
then show \<open>only_fives (xs @ [])\<close>
by simp
next
case (snoc y ys)
hence \<open>only_fives ys\<close>
using only_fives.cases by auto
hence \<open>only_fives (xs @ ys)\<close>
by (simp add: snoc.IH snoc.prems(1))
moreover have \<open>y = 5\<close>
using only_fives.cases snoc.prems(2) by blast
ultimately show \<open>only_fives (xs @ ys @ [y])\<close>
using only_fives.intros(2) by fastforce
qed
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment