Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- theory EWD840
- imports "HOL-TLA.TLA"
- begin
- section Utilities
- text ‹A handful of general lemmas that were useful along the way.›
- lemma temp_impI:
- assumes "sigma ⊨ P ⟹ sigma ⊨ Q"
- shows "sigma ⊨ P ⟶ Q"
- using assms by simp
- lemma imp_leadsto_reflexive: "⊢ S ⟶ (F ↝ F)" using LatticeReflexivity [where F = F] by auto
- lemma imp_leadsto_transitive:
- assumes "⊢ S ⟶ (F ↝ G)" "⊢ S ⟶ (G ↝ H)"
- shows "⊢ S ⟶ (F ↝ H)"
- proof (intro tempI temp_impI)
- fix sigma
- assume S: "S sigma"
- with assms have 1: "sigma ⊨ (F ↝ G)" "sigma ⊨ (G ↝ H)"
- by (auto simp add: Valid_def)
- from 1 LatticeTransitivity [where F = F and G = G and H = H]
- show "sigma ⊨ F ↝ H"
- by (auto simp add: Valid_def)
- qed
- lemma imp_leadsto_diamond:
- assumes "⊢ S ⟶ (A ↝ (B ∨ C))"
- assumes "⊢ S ⟶ (B ↝ D)"
- assumes "⊢ S ⟶ (C ↝ D)"
- shows "⊢ S ⟶ (A ↝ D)"
- proof (intro tempI temp_impI)
- fix sigma
- assume S: "sigma ⊨ S"
- with assms have
- ABC: "sigma ⊨ A ↝ (B ∨ C)" and
- BD: "sigma ⊨ B ↝ D" and
- CD: "sigma ⊨ C ↝ D"
- by (auto simp add: Valid_def)
- with LatticeDiamond [where A = A and B = B and C = C and D = D]
- show "sigma ⊨ A ↝ D"
- by (auto simp add: Valid_def)
- qed
- lemma temp_conj_eq_imp:
- assumes "⊢ P ⟶ (Q = R)"
- shows "⊢ (P ∧ Q) = (P ∧ R)"
- using assms by (auto simp add: Valid_def)
- text ‹The following lemma is particularly useful for a system that makes
- some progress which either reaches the desired state directly or which leaves it in
- a state that is definitely not the desired state but from which it can reach the desired state via
- some further progress.›
- lemma imp_leadsto_triangle_excl:
- assumes AB: "⊢ S ⟶ (A ↝ B)"
- assumes BC: "⊢ S ⟶ ((B ∧ ¬C) ↝ C)"
- shows "⊢ S ⟶ (A ↝ C)"
- proof -
- have "⊢ ((B ∧ ¬C) ∨ (B ∧ C)) = B" by auto
- from inteq_reflection [OF this] AB have ABCBC: "⊢ S ⟶ (A ↝ ((B ∧ ¬C) ∨ (B ∧ C)))" by simp
- show ?thesis
- proof (intro imp_leadsto_diamond [OF ABCBC] BC)
- from ImplLeadsto_simple [where F = "LIFT (B ∧ C)"]
- show "⊢ S ⟶ (B ∧ C ↝ C)"
- by (auto simp add: Valid_def)
- qed
- qed
- text ‹An action that updates a single value of a function.›
- definition updatedFun :: "('a ⇒ 'b) stfun ⇒ 'a ⇒ 'b trfun ⇒ action" where
- "updatedFun f x v ≡ ACT (∀n. id<f$,#n> = (if #n = #x then v else id<$f,#n>))"
- section Nodes
- text ‹There is a fixed, finite, set of nodes, which are numbered. Introduce a distinct type
- for node identifiers, and an ordering relation, and an induction principle.›
- axiomatization NodeCount :: nat where NodeCount_positive: "NodeCount > 0"
- typedef Node = "{0..<NodeCount}" using NodeCount_positive by auto
- definition FirstNode :: Node where "FirstNode == Abs_Node 0"
- definition LastNode :: Node where "LastNode == Abs_Node (NodeCount-1)"
- definition PreviousNode :: "Node ⇒ Node" where "PreviousNode == λn. Abs_Node (Rep_Node n - 1)"
- instantiation Node :: linorder
- begin
- definition less_eq_Node :: "Node ⇒ Node ⇒ bool" where "n ≤ m ≡ Rep_Node n ≤ Rep_Node m"
- definition less_Node :: "Node ⇒ Node ⇒ bool" where "n < m ≡ Rep_Node n < Rep_Node m"
- instance proof
- show "⋀(x::Node) y. (x < y) = (x ≤ y ∧ ¬ y ≤ x)" using less_Node_def less_eq_Node_def by force
- show "⋀(x::Node). x ≤ x" using less_eq_Node_def by force
- show "⋀(x::Node) y z. x ≤ y ⟹ y ≤ z ⟹ x ≤ z" using less_eq_Node_def by force
- show "⋀(x::Node) y. x ≤ y ∨ y ≤ x" using less_eq_Node_def by force
- show "⋀(x::Node) y. x ≤ y ⟹ y ≤ x ⟹ x = y" using less_Node_def less_eq_Node_def
- by (simp add: Rep_Node_inject)
- qed
- end
- lemma PreviousNode_fixed_point:
- assumes "n = PreviousNode n"
- shows "n = FirstNode"
- using assms
- unfolding PreviousNode_def FirstNode_def
- by (metis Abs_Node_inject One_nat_def Rep_Node Rep_Node_inverse atLeastLessThan_iff cancel_comm_monoid_add_class.diff_cancel diff_Suc_less diff_le_self le_less_trans le_neq_implies_less not_le)
- lemma Node_gt_PreviousNode:
- assumes "n ≠ FirstNode"
- shows "m > (PreviousNode n) = (m > n ∨ m = n)"
- using assms unfolding PreviousNode_def less_Node_def FirstNode_def
- by (smt Abs_Node_inverse Rep_Node Rep_Node_inject atLeastLessThan_iff diff_Suc_1 diff_is_0_eq' diff_le_self le_add_diff_inverse less_Suc_eq_le not_le_imp_less not_less_iff_gr_or_eq)
- lemma Node_gt_ne: "(m::Node) > n ⟹ m ≠ n" unfolding less_Node_def by blast
- lemma Node_gt_LastNode [simp]: "n > LastNode = False"
- unfolding LastNode_def less_Node_def
- using Abs_Node_inverse NodeCount_positive Rep_Node not_less_eq by auto
- lemma Node_induct [case_names FirstNode PreviousNode]:
- assumes FirstNode: "P FirstNode"
- assumes PreviousNode: "⋀n. n ≠ FirstNode ⟹ P (PreviousNode n) ⟹ P n"
- shows "P n"
- proof -
- define n_num where "n_num == Rep_Node n"
- have n_eq: "n = Abs_Node n_num"
- by (simp add: Rep_Node_inverse n_num_def)
- have "n_num < NodeCount" using Rep_Node n_num_def by auto
- thus ?thesis
- unfolding n_eq
- proof (induct n_num)
- case 0 with FirstNode show ?case by (simp add: FirstNode_def)
- next
- case (Suc n_num)
- hence hyp: "P (Abs_Node n_num)" by auto
- show ?case
- proof (rule PreviousNode)
- show "Abs_Node (Suc n_num) ≠ FirstNode" unfolding FirstNode_def
- by (simp add: Abs_Node_inject NodeCount_positive Suc.prems)
- from hyp Suc.prems show " P (PreviousNode (Abs_Node (Suc n_num)))"
- unfolding PreviousNode_def by (simp add: Abs_Node_inverse)
- qed
- qed
- qed
- datatype TerminationState = MaybeTerminated | NotTerminated
- axiomatization
- isNodeActive :: "(Node ⇒ bool) stfun" and
- nodeState :: "(Node ⇒ TerminationState) stfun" and
- tokenPosition :: "Node stfun" and
- tokenState :: "TerminationState stfun"
- where
- ewd_basevars: "basevars (isNodeActive, nodeState, tokenPosition, tokenState)"
- definition StartState :: stpred where
- "StartState == PRED tokenPosition = #FirstNode ∧ tokenState = #NotTerminated"
- definition InitiateProbe :: action where
- "InitiateProbe == ACT
- (($tokenPosition = #FirstNode)
- ∧ ($tokenState = #NotTerminated ∨ id<$nodeState,#FirstNode> = #NotTerminated)
- ∧ tokenPosition$ = #LastNode
- ∧ tokenState$ = #MaybeTerminated
- ∧ (unchanged isNodeActive)
- ∧ (updatedFun nodeState FirstNode (const MaybeTerminated)))"
- definition PassToken :: "Node ⇒ action" where
- "PassToken i == ACT
- (($tokenPosition = #i)
- ∧ ($tokenPosition ≠ #FirstNode)
- ∧ (¬ id<$isNodeActive,#i> ∨ id<$nodeState,#i> = #NotTerminated ∨ $tokenState = #NotTerminated)
- ∧ (tokenPosition$ = PreviousNode<$tokenPosition>)
- ∧ (tokenState$ = (if id<$nodeState,#i> = #NotTerminated then #NotTerminated else $tokenState))
- ∧ (unchanged isNodeActive)
- ∧ (updatedFun nodeState i (const MaybeTerminated)))"
- definition SendMsg :: "Node ⇒ action" where
- "SendMsg i == ACT
- id<$isNodeActive,#i>
- ∧ (∃ j. #j ≠ #i ∧ (updatedFun isNodeActive j (const True))
- ∧ (updatedFun nodeState i (ACT if #i < #j then #NotTerminated else id<$nodeState,#i>)))
- ∧ unchanged (tokenPosition, tokenState)"
- definition Deactivate :: "Node ⇒ action" where
- "Deactivate i == ACT
- id<$isNodeActive,#i>
- ∧ (updatedFun isNodeActive i (const False))
- ∧ unchanged (tokenPosition, tokenState, nodeState)"
- definition Controlled :: action where
- "Controlled ≡ ACT (InitiateProbe ∨ (∃ n. PassToken n))"
- definition Environment :: action where
- "Environment ≡ ACT (∃ n. SendMsg n ∨ Deactivate n)"
- definition Next :: action where
- "Next ≡ ACT (Controlled ∨ Environment)"
- definition Fairness :: temporal where
- "Fairness ≡ TEMP WF(Controlled)_(isNodeActive,nodeState,tokenPosition,tokenState)"
- definition Spec :: temporal where
- "Spec ≡ TEMP (Init StartState ∧ □[Next]_(isNodeActive,nodeState,tokenPosition,tokenState) ∧ Fairness)"
- definition TerminationDetected :: stpred where
- "TerminationDetected ≡ PRED
- (tokenPosition = #FirstNode
- ∧ tokenState = #MaybeTerminated
- ∧ id<nodeState,#FirstNode> = #MaybeTerminated
- ∧ ¬ id<isNodeActive,#FirstNode>)"
- lemma angle_Controlled_lifted: "⊢ <Controlled>_(isNodeActive, nodeState, tokenPosition, tokenState) = Controlled"
- unfolding angle_def Controlled_def InitiateProbe_def PassToken_def updatedFun_def
- using PreviousNode_fixed_point by auto
- lemmas angle_Controlled = inteq_reflection [OF angle_Controlled_lifted]
- lemma basevars_arbitrary:
- assumes "⋀u. ⟦ tokenPosition u = A; tokenState u = B; isNodeActive u = C; nodeState u = D ⟧ ⟹ P"
- shows P
- using assms ewd_basevars unfolding basevars_def surj_def apply auto by metis
- lemma enabled_controlled_lifted:
- "⊢ Enabled Controlled
- = (tokenState = #NotTerminated ∨ id<nodeState, tokenPosition> = #NotTerminated ∨ (tokenPosition ≠ #FirstNode ∧ ¬ id<isNodeActive, tokenPosition>))"
- proof -
- have 1: "⊢ Enabled Controlled = (Enabled InitiateProbe ∨ Enabled (∃n. PassToken n))"
- unfolding Controlled_def
- using enabled_disj by simp
- have 2: "⊢ Enabled InitiateProbe = (tokenPosition = #FirstNode ∧ (tokenState = #NotTerminated ∨ id<nodeState, #FirstNode> = #NotTerminated))"
- proof (intro intI)
- fix w
- show "w ⊨ Enabled InitiateProbe = (tokenPosition = #FirstNode ∧ (tokenState = #NotTerminated ∨ id<nodeState, #FirstNode> = #NotTerminated))"
- apply (rule basevars_arbitrary [of LastNode MaybeTerminated "isNodeActive w" "λn. if n = FirstNode then MaybeTerminated else nodeState w n"])
- unfolding InitiateProbe_def enabled_def updatedFun_def
- by auto
- qed
- have 3: "⊢ Enabled (∃n. PassToken n) = ((tokenPosition ≠ #FirstNode ∧ (¬ id<isNodeActive, tokenPosition> ∨ id<nodeState, tokenPosition> = #NotTerminated ∨ tokenState = #NotTerminated)))"
- proof (intro intI)
- fix w
- show "w ⊨ Enabled (∃n. PassToken n) = ((tokenPosition ≠ #FirstNode ∧ (¬ id<isNodeActive, tokenPosition> ∨ id<nodeState, tokenPosition> = #NotTerminated ∨ tokenState = #NotTerminated)))"
- apply (rule basevars_arbitrary [of "PreviousNode (tokenPosition w)" "if nodeState w (tokenPosition w) = NotTerminated then NotTerminated else tokenState w" "isNodeActive w" "λn. if n = tokenPosition w then MaybeTerminated else nodeState w n"])
- unfolding PassToken_def enabled_def updatedFun_def
- by auto
- qed
- have 4:
- "⊢ Enabled Controlled = ((tokenPosition = #FirstNode ∧ (tokenState = #NotTerminated ∨ id<nodeState, #FirstNode> = #NotTerminated))
- ∨ (tokenPosition ≠ #FirstNode ∧ (¬ id<isNodeActive, tokenPosition> ∨ id<nodeState, tokenPosition> = #NotTerminated ∨ tokenState = #NotTerminated)))"
- unfolding inteq_reflection [OF 1]
- inteq_reflection [OF 2]
- inteq_reflection [OF 3]
- by auto
- show ?thesis
- unfolding inteq_reflection [OF 4] by auto
- qed
- lemmas enabled_controlled = inteq_reflection [OF enabled_controlled_lifted]
- section Safety
- text ‹The safety property of the algorithm says that termination is detected only if all nodes
- are inactive. The proof works by showing that the safety invariant is actually an invariant,
- and that this invariant implies the desired safety property.›
- definition AllNodesInactive :: stpred where
- "AllNodesInactive ≡ PRED (∀ n. ¬ id<isNodeActive,#n>)"
- definition SafetyInvariant where
- "SafetyInvariant ≡ PRED
- (∀ n. (tokenPosition < #n) ⟶ ¬ id<isNodeActive,#n>)
- ∨ (∃ n. #n ≤ tokenPosition ∧ id<nodeState,#n> = #NotTerminated)
- ∨ tokenState = #NotTerminated"
- lemma safety:
- shows "⊢ Spec ⟶ □(TerminationDetected ⟶ AllNodesInactive)"
- proof -
- have "⊢ Spec ⟶ □SafetyInvariant"
- proof invariant
- fix sigma
- assume s: "Spec sigma"
- thus "sigma ⊨ Init SafetyInvariant"
- by (auto simp add: Spec_def SafetyInvariant_def StartState_def Init_def)
- show "sigma ⊨ stable SafetyInvariant"
- proof (intro Stable)
- from s show "sigma ⊨ □[Next]_(isNodeActive, nodeState, tokenPosition, tokenState)"
- by (simp add: Spec_def)
- show "⊢ $SafetyInvariant ∧ [Next]_(isNodeActive, nodeState, tokenPosition, tokenState) ⟶ SafetyInvariant$"
- proof clarsimp
- fix s t
- assume s: "SafetyInvariant s"
- and st: "(s, t) ⊨ [Next]_(isNodeActive, nodeState, tokenPosition, tokenState)"
- from st have
- "((s, t) ⊨ InitiateProbe)
- ∨ (∃n. (s, t) ⊨ PassToken n)
- ∨ (∃n. (s, t) ⊨ SendMsg n)
- ∨ (∃n. (s, t) ⊨ Deactivate n)
- ∨ ((s, t) ⊨ unchanged (isNodeActive, nodeState, tokenPosition, tokenState))"
- by (auto simp add: square_def Next_def Controlled_def Environment_def)
- thus "SafetyInvariant t"
- proof (elim disjE conjE exE)
- assume "(s, t) ⊨ unchanged (isNodeActive, nodeState, tokenPosition, tokenState)"
- with s show "SafetyInvariant t" by (simp add: SafetyInvariant_def)
- next
- assume "InitiateProbe (s, t)"
- hence step:
- "tokenPosition s = FirstNode" "tokenState s = NotTerminated ∨ nodeState s FirstNode = NotTerminated"
- "tokenPosition t = LastNode" "tokenState t = MaybeTerminated" "isNodeActive t = isNodeActive s"
- "⋀n. nodeState t n = (if n = FirstNode then MaybeTerminated else nodeState s n)"
- unfolding InitiateProbe_def updatedFun_def
- by auto
- note step_simps[simp] = `tokenPosition s = FirstNode` `tokenPosition t = LastNode` `tokenState t = MaybeTerminated` `isNodeActive t = isNodeActive s`
- `⋀n. nodeState t n = (if n = FirstNode then MaybeTerminated else nodeState s n)`
- show "SafetyInvariant t"
- unfolding SafetyInvariant_def
- apply (auto simp add: less_Node_def LastNode_def)
- by (metis Abs_Node_inverse Rep_Node Suc_pred atLeastLessThan_iff diff_Suc_less less_or_eq_imp_le neq0_conv not_less_eq)
- next
- fix n assume "Deactivate n (s, t)"
- hence step:
- "tokenPosition t = tokenPosition s" "tokenState t = tokenState s" "nodeState t = nodeState s" "⋀n. isNodeActive t n ⟹ isNodeActive s n"
- unfolding Deactivate_def updatedFun_def apply auto
- by (metis id_apply unl_before unl_con unl_lift2)
- from s show "SafetyInvariant t" by (auto simp add: less_Node_def LastNode_def SafetyInvariant_def step)
- next
- fix sender assume step: "SendMsg sender (s, t)"
- from step have step_simps[simp]: "tokenPosition t = tokenPosition s" "tokenState t = tokenState s" by (auto simp add: SendMsg_def)
- from step have n_active: "isNodeActive s sender" by (simp add: SendMsg_def)
- from step obtain receiver where receiver: "receiver ≠ sender"
- "⋀m. isNodeActive t m = (m = receiver ∨ isNodeActive s m)"
- "⋀m. nodeState t m = (if m = sender ∧ receiver > sender then NotTerminated else nodeState s m)"
- unfolding SendMsg_def updatedFun_def by auto
- show ?thesis
- proof (cases "receiver < tokenPosition s")
- case False
- with s show ?thesis
- unfolding SafetyInvariant_def less_Node_def
- apply auto
- apply (metis le_less_trans less_Node_def n_active not_le receiver(2) receiver(3))
- by (metis receiver(3))
- next
- case True
- with s receiver show ?thesis unfolding SafetyInvariant_def less_Node_def by fastforce
- qed
- next
- fix n assume step: "PassToken n (s,t)"
- hence step_tokenPosition[simp]: "tokenPosition s = n" "tokenPosition t = PreviousNode n" "n ≠ FirstNode" unfolding PassToken_def by auto
- from step have step_active[simp]: "isNodeActive t = isNodeActive s" unfolding PassToken_def by auto
- from step have step_colour: "⋀m. nodeState t m = (if m = n then MaybeTerminated else nodeState s m)"
- by (simp add: PassToken_def updatedFun_def)
- from step have step_tokenState: "tokenState t = (if nodeState s n = NotTerminated then NotTerminated else tokenState s)"
- unfolding PassToken_def by simp
- show ?thesis
- proof (cases "nodeState s n = NotTerminated ∨ tokenState s = NotTerminated")
- case True with step_tokenState show ?thesis by (auto simp add: SafetyInvariant_def)
- next
- case False
- with TerminationState.exhaust have whites: "nodeState s n = MaybeTerminated" "tokenState s = MaybeTerminated" by auto
- from whites step_colour step_tokenState have step_simps[simp]:
- "nodeState t = nodeState s" "tokenState t = tokenState s" by auto
- from step whites have n_inactive: "¬isNodeActive s n" unfolding PassToken_def by auto
- from step_tokenPosition(3)
- have gt1: "⋀m. m < n = (m < (PreviousNode n) ∨ m = PreviousNode n)"
- using Node_gt_PreviousNode not_less_iff_gr_or_eq by blast
- have gt2: "⋀m. n < m = ((PreviousNode n) < m ∧ m ≠ n)"
- using Node_gt_PreviousNode step_tokenPosition(3) by blast
- from s n_inactive show ?thesis
- unfolding SafetyInvariant_def
- apply (clarsimp simp add: gt1 gt2)
- by (metis TerminationState.simps(2) gt2 leD leI whites(1))
- qed
- qed
- qed
- qed
- qed
- moreover have "⊢ □SafetyInvariant ⟶ □(TerminationDetected ⟶ AllNodesInactive)"
- unfolding SafetyInvariant_def
- proof (intro STL4, clarsimp, intro conjI impI)
- fix w
- assume inactive_gt: "∀n. (tokenPosition w < n) ⟶ ¬ isNodeActive w n"
- show "TerminationDetected w ⟹ AllNodesInactive w"
- unfolding TerminationDetected_def AllNodesInactive_def
- proof clarsimp
- fix n assume a: "isNodeActive w n" "tokenPosition w = FirstNode" "¬ isNodeActive w FirstNode"
- with inactive_gt have "¬ n > FirstNode" by auto
- hence "n = FirstNode"
- unfolding less_Node_def FirstNode_def
- by (metis Abs_Node_inverse NodeCount_positive Rep_Node Rep_Node_inject atLeastLessThan_iff le_numeral_extra(3) nat_less_le)
- with a show False by simp
- qed
- next
- fix w
- assume "tokenState w = NotTerminated"
- thus "TerminationDetected w ⟹ AllNodesInactive w"
- unfolding TerminationDetected_def
- by auto
- next
- fix w
- assume "∃n. (n ≤ tokenPosition w) ∧ nodeState w n = NotTerminated"
- then obtain n where n: "n ≤ tokenPosition w" "nodeState w n = NotTerminated" by auto
- thus "TerminationDetected w ⟹ AllNodesInactive w"
- unfolding TerminationDetected_def AllNodesInactive_def
- proof clarsimp
- assume "tokenPosition w = FirstNode" "nodeState w FirstNode = MaybeTerminated"
- with n show False
- by (metis Abs_Node_inverse TerminationState.distinct(2) FirstNode_def NodeCount_positive Rep_Node_inverse atLeastLessThan_iff le_zero_eq less_eq_Node_def)
- qed
- qed
- ultimately show ?thesis by (simp add: Valid_def)
- qed
- section Liveness
- text ‹When all nodes become inactive the algorithm runs through up to three further distinct
- phases before detecting termination. The first phase is simply to return the token to the first
- node, without any constraints on its state or the states of the nodes. The second phase
- passes the token around the ring once more which sets each node's state to $MaybeTerminated$,
- although the token itself may be ``contaminated'' by a $NotTerminated$ state. The third phase
- passes the token around the ring one last time to remove any such contamination.›
- text ‹The following predicates correspond to each step of each of these phases.›
- definition AllNodesInactiveAndTokenAt where "AllNodesInactiveAndTokenAt n ≡ PRED
- (AllNodesInactive ∧ tokenPosition = #n)"
- definition NodeCleaningRunAt where "NodeCleaningRunAt n ≡ PRED
- (AllNodesInactiveAndTokenAt n
- ∧ id<nodeState,#FirstNode> = #MaybeTerminated
- ∧ (∀ m. #n < #m ⟶ id<nodeState,#m> = #MaybeTerminated))"
- definition TokenCleaningRunAt where "TokenCleaningRunAt n ≡ PRED
- (AllNodesInactiveAndTokenAt n
- ∧ tokenState = #MaybeTerminated
- ∧ (∀ m. id<nodeState,#m> = #MaybeTerminated))"
- text ‹The liveness proof now shows that each phase completes and either detects termination
- or leads to the next phase.›
- lemma step:
- assumes "⊢ P ⟶ AllNodesInactive"
- assumes "⊢ P ⟶ ¬ TerminationDetected"
- assumes "⊢ $P ∧ unchanged (isNodeActive, nodeState, tokenPosition, tokenState) ⟶ P$"
- assumes "⊢ $P ∧ Controlled ⟶ Q$"
- shows "⊢ Spec ⟶ (P ↝ Q)"
- proof -
- have "⊢ (□[Next]_(isNodeActive, nodeState, tokenPosition, tokenState)
- ∧ WF(Controlled)_(isNodeActive, nodeState, tokenPosition, tokenState)) ⟶ (P ↝ Q)"
- proof (intro WF1)
- from assms have no_Environment: "⋀s t. s ⊨ P ⟹ (s, t) ⊨ Environment ⟹ False"
- by (auto simp add: Environment_def AllNodesInactive_def Valid_def SendMsg_def Deactivate_def)
- with assms
- show "⊢ $P ∧ [Next]_(isNodeActive, nodeState, tokenPosition, tokenState) ⟶ P$ ∨ Q$"
- "⊢ ($P ∧ [Next]_(isNodeActive, nodeState, tokenPosition, tokenState)) ∧ <Controlled>_(isNodeActive, nodeState, tokenPosition, tokenState) ⟶ Q$"
- "⊢ $P ∧ [Next]_(isNodeActive, nodeState, tokenPosition, tokenState) ⟶ $Enabled (<Controlled>_(isNodeActive, nodeState, tokenPosition, tokenState))"
- unfolding angle_Controlled enabled_controlled Next_def square_def Valid_def AllNodesInactive_def TerminationDetected_def
- apply simp_all
- apply (meson TerminationState.exhaust, blast)
- by (metis (full_types) TerminationState.exhaust)
- qed
- thus ?thesis
- by (auto simp add: Spec_def Fairness_def)
- qed
- lemma liveness: "⊢ Spec ⟶ (AllNodesInactive ↝ TerminationDetected)"
- proof -
- note [simp] = TokenCleaningRunAt_def NodeCleaningRunAt_def
- AllNodesInactiveAndTokenAt_def AllNodesInactive_def
- square_def Controlled_def InitiateProbe_def PassToken_def updatedFun_def
- TerminationDetected_def
- have "⊢ Spec ⟶ (AllNodesInactive ↝ AllNodesInactiveAndTokenAt FirstNode)"
- proof -
- have "⊢ AllNodesInactive = (∃n. AllNodesInactiveAndTokenAt n)" unfolding AllNodesInactiveAndTokenAt_def by auto
- hence "⊢ (AllNodesInactive ↝ AllNodesInactiveAndTokenAt FirstNode)
- = (∀n. (AllNodesInactiveAndTokenAt n ↝ AllNodesInactiveAndTokenAt FirstNode))"
- by (metis inteq_reflection leadsto_exists)
- moreover {
- fix n
- have "⊢ Spec ⟶ (AllNodesInactiveAndTokenAt n ↝ AllNodesInactiveAndTokenAt FirstNode)"
- proof (induct n rule: Node_induct)
- case FirstNode show ?case by (intro imp_leadsto_reflexive)
- next
- case (PreviousNode n)
- hence "⊢ Spec ⟶ (AllNodesInactiveAndTokenAt n ↝ AllNodesInactiveAndTokenAt (PreviousNode n))"
- by (intro step, auto)
- with PreviousNode show ?case by (metis imp_leadsto_transitive)
- qed
- }
- ultimately show ?thesis by (auto simp add: Valid_def)
- qed
- moreover have "⊢ Spec ⟶ ((AllNodesInactiveAndTokenAt FirstNode ∧ ¬ TerminationDetected) ↝ NodeCleaningRunAt LastNode)"
- by (intro step, auto)
- moreover have "⋀n. ⊢ Spec ⟶ (NodeCleaningRunAt n ↝ NodeCleaningRunAt FirstNode)"
- proof -
- fix n show "?thesis n"
- proof (induct n rule: Node_induct)
- case FirstNode
- with LatticeReflexivity show ?case by auto
- next
- case (PreviousNode n)
- with Node_gt_PreviousNode Node_gt_ne
- have "⊢ Spec ⟶ (NodeCleaningRunAt n ↝ NodeCleaningRunAt (PreviousNode n))"
- by (intro step, auto)
- with PreviousNode show ?case by (metis imp_leadsto_transitive)
- qed
- qed
- moreover have "⊢ Spec ⟶ (NodeCleaningRunAt FirstNode ∧ ¬ TerminationDetected ↝ TokenCleaningRunAt LastNode)"
- proof -
- have firstNode_min: "⋀n. n = FirstNode ∨ FirstNode < n"
- using Abs_Node_inverse FirstNode_def NodeCount_positive le_less less_eq_Node_def by fastforce
- hence "⊢ NodeCleaningRunAt FirstNode
- = (AllNodesInactiveAndTokenAt FirstNode ∧ (∀ m. id<nodeState,#m> = #MaybeTerminated))"
- by (auto, force)
- thus ?thesis by (intro step, auto, metis firstNode_min)
- qed
- moreover have "⋀n. ⊢ Spec ⟶ (TokenCleaningRunAt n ↝ TerminationDetected)"
- proof -
- fix n
- show "?thesis n"
- proof (induct n rule: Node_induct)
- case FirstNode
- have "⊢ TokenCleaningRunAt FirstNode ⟶ TerminationDetected" by auto
- hence "⊢ TokenCleaningRunAt FirstNode ↝ TerminationDetected"
- using ImplLeadsto_simple by auto
- thus ?case by (auto simp add: ImplLeadsto_simple intI tempD)
- next
- case (PreviousNode n)
- hence "⊢ Spec ⟶ (TokenCleaningRunAt n ↝ TokenCleaningRunAt (PreviousNode n))"
- by (intro step, auto, blast)
- with PreviousNode show ?case by (metis imp_leadsto_transitive)
- qed
- qed
- ultimately show ?thesis
- by (metis imp_leadsto_transitive imp_leadsto_triangle_excl)
- qed
- end
Add Comment
Please, Sign In to add comment