_README.md

Correctness proofs of distributed systems with Isabelle

This Gist accompanies a Talk by Martin Kleppmann:

• 40-minute version given at Strange Loop 2019 (slides)
• 40-minute version given at Code Mesh LDN 2019
• 2-hour extended version, which I recorded at home

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.

Consensus_Demo.thy

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

Network.thy

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

Only_Fives.thy

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