Open lemmy opened 1 week ago
This proof works:
THEOREM DeadlockFreedom == Spec => []Invariant
<1>1. Init => IInv BY SMT DEF IInv
<1>2. TypeInv /\ IInv /\ [Next]_vars => IInv' BY DEF IInv
<1>3. IInv => Invariant BY DEF IInv
<1>4. QED BY TypeCorrect, <1>1,<1>2,<1>3,PTL
Here, I added the use of TypeCorrect
.
Maybe @muenchnerkindl could comment on whether that's a regression or proof that has to be updated.
This proof works:
THEOREM DeadlockFreedom == Spec => []Invariant <1>1. Init => IInv BY SMT DEF IInv <1>2. TypeInv /\ IInv /\ [Next]_vars => IInv' BY DEF IInv <1>3. IInv => Invariant BY DEF IInv <1>4. QED BY TypeCorrect, <1>1,<1>2,<1>3,PTL
Apparently, it also suffices to "just" add TypeInv!1
to IInv
(see below). This is interesting because when I first wrote the proof, I intentionally removed TypeInv!1
, as you can see in https://github.com/lemmy/BlockingQueue/commit/dc3b3aabbfa6c2f5e9445548b5b17f97b228c4fc.
diff --git a/BlockingQueue.tla b/BlockingQueue.tla
index 29be666..b8ea33e 100644
--- a/BlockingQueue.tla
+++ b/BlockingQueue.tla
@@ -92,7 +92,8 @@ LEMMA TypeCorrect == Spec => []TypeInv
\* The naive thing to do is to check if the conjunct of TypeInv /\ Invariant
\* is inductive.
-IInv == /\ TypeInv!2
+IInv == /\ TypeInv!1
+ /\ TypeInv!2
/\ TypeInv!3
/\ Invariant
\* When the buffer is empty, a consumer will be added to the waitSet.
Proof at https://github.com/lemmy/BlockingQueue/blob/main/BlockingQueue.tla