[HD] EECS3342 F26 - 2026-11-05 (Thursday) - Lecture 15
Overview
Jackie Wang completes the M0 verification topic in EECS3342 by deriving invariant-establishment obligations for initialization, then formulating deadlock freedom for the bridge controller and attempting its proof. The lecture distinguishes pre-state and post-state reasoning, explains equality-substitution inference rules, and shows why the initial deadlock-freedom proof reaches an unprovable goal without an additional assumption such as D > 0.
Key takeaways
- An init event has no pre-state, so its assignments must specify constants rather than expressions involving the old value of a variable.
- M0's init assignment N := 0 establishes N ∈ ℕ and N ≤ D from the axiom D ∈ ℕ.
- Deadlock freedom for the bridge controller is the disjunction of its event guards, N < D or N > 0; deadlock itself is the conjunction of their negations.
- Invariant establishment uses post-states only, invariant preservation uses pre- and post-states, and deadlock freedom evaluates guards in pre-states only.
- The initial deadlock proof exposes a missing condition: when N = D, its branch requires D > 0, which does not follow from D being a natural number that may include zero.
- Equality-substitution direction matters: EQLR and EQRL can produce different proof goals from the same assumed equality.
Chapters
- Jackie Wang says Written Test 1 results and feedback will arrive by Friday or Sunday evening, with Monday office hours available for concerns.
- Written Test 2 is scheduled for November 18, with a study guide and practice questions planned for November 9.
- Lab 4 will be the final lab before the exam.
- M0 has two invariants and two regular events, ML out and ML in, creating four invariant-preservation proof obligations.
- The original unguarded events could not discharge every obligation, so guards such as N > 0 and N < D were added.
- Changing a model requires regenerating its proof obligations; the guard-placement decision is presented as a general modeling principle.
- Invariant establishment is compared with the base case of mathematical induction, while regular-event preservation resembles the inductive step.
- The init event has post-states but no pre-states, because it occurs before the system has an initialized state.
- Initialization must establish that the resulting state satisfies each invariant.
- Unlike ML out and ML in, init is expected to be unguarded so the system can always start.
- An init assignment such as N := 0 or N := D is syntactically valid when its right-hand side is a constant.
- An expression such as N := N + 1 is invalid for init because no pre-state value of N exists.
- Assigning N := -1 is syntactically legal, but it violates M0's invariant that N is a natural number.
- An invalid initial value makes the invariant-establishment obligation unprovable, even though the assignment itself is allowed in the model syntax.
- Establishment is distinct from preservation: init must make an invariant true for the first time, rather than maintain a previously true property.
- The establishment rule assumes axioms but does not assume invariants, because those invariants have not yet been established.
- The goal is generated separately for each invariant, indexed by the invariant number.
- Init effects use constants only, represented by K; regular-event effects use E and may involve variables as well as constants.
- One init event and two invariants generate two establishment obligations: init against invariant 1 and init against invariant 2.
- The invariants concern N being a natural number and N being at most D; post-state occurrences of N are replaced using the init effect.
- For N := 0, the resulting goals are that 0 is a natural number and 0 ≤ D, each under the axiom D is a natural number.
- The first obligation, D ∈ ℕ ⊢ 0 ∈ ℕ, is proved by removing the unused hypothesis with monotonicity and applying the natural-number rule.
- The second obligation, D ∈ ℕ ⊢ 0 ≤ D, follows by instantiating the order rule with D.
- The example illustrates why initialization proofs are often direct when variables are assigned suitable constants.
- Deadlock is undesirable for the bridge controller because it is a reactive system expected to keep responding to its environment.
- A celebrity-finding algorithm from Lab 3 may intentionally terminate when it finds the celebrity, so deadlock can represent success there.
- Whether to prove deadlock freedom depends on the system's purpose, not on deadlock being inherently bad.
- For an initialized system, deadlock means no non-init event is enabled; equivalently, every event guard is false.
- Writing the ML out and ML in guards as Gout and Gin, the deadlock condition is ¬Gout ∧ ¬Gin.
- For the bridge controller, deadlock freedom is the negation of that condition: Gout ∨ Gin.
- Deadlock freedom asks whether at least one event is enabled in the current pre-state, before any transition occurs.
- The M0 obligation assumes D ∈ ℕ, N ∈ ℕ, and N ≤ D, then aims to prove N < D ∨ N > 0.
- Only pre-state variables appear in the guards; the deadlock-freedom obligation has no post-state effects.
- Invariant establishment uses post-states only, because init has no pre-state.
- Invariant preservation uses both pre-states and post-states: assume an invariant before an event and prove it afterward.
- Deadlock freedom uses pre-state invariants and guards only, checking that some transition is available.
- The hypothesis rule proves a goal when that same predicate already appears among the assumptions.
- The top symbol denotes true and the bottom symbol denotes false; from a false hypothesis, any goal follows.
- The equality rules use an assumed equality to replace one side with the other while proving a predicate.
- With an equality E = F among the hypotheses, EQLR replaces free occurrences of the left side E with the right side F.
- EQRL performs the reverse substitution, replacing occurrences of F with E; the choice can lead to very different proof goals.
- The goal may involve both sides of the equality, so students must identify which occurrences a rule replaces rather than blindly rewriting everything.
- The proof first rewrites N ≤ D as N < D ∨ N = D, then splits the disjunctive hypothesis into two branches.
- The N < D branch proves the desired disjunction directly; in the N = D branch, EQLR substitutes D for N.
- That substitution leaves D < D ∨ D > 0, which reduces to D > 0 and is unprovable from the sole axiom D ∈ ℕ.
- The assigned exercise is to repeat the substitution using EQRL and compare the resulting proof sequence before the next lecture.
Transcript excerpt
0:05 All right. Just before we get started, I would like to take a look at the semester calendar, but before that, about your written test number one. I will release the result either later tomorrow, Friday, or definitely Sunday evening the latest. So, you can definitely get a result and also feedback. And also, if you got any concern, you can definitely talk to me. For example, the office hour on Monday. I know Wednesday is a drop deadline, but just in case that's relevant to you. All right. So, that's about written test one. Definitely either tomorrow, Friday, or Sunday, you'll get a result. And then, for the remaining semester, let's take a quick look. Semester calendar. Okay. Okay. Make it a bit larger. Okay. So, we are now here, November 5th.
0:55 We're doing lecture 15 today. And then, your written test number two will be on November 18th. So, I think most likely on Monday, the coming Monday, November 9th, I'm going to give you the guide and also some practice question for written test number two. So, you can definitely get ready for that. Just manage your time. I know it's getting to towards the end of the term. You must get also other commitments well. So, I'll give you the guide and practice question to you earlier. Okay. I'll confirm that. And of course, after that, I will also release lab number four. That'll be the last lab. So, after that, we also got exam etc., right? So, we just keep the pace. So, only one more assessment before the exam for this course. Okay?
1:42 Any questions? All good? Okay. If that's good, why don't we look at very quickly what we have done so far for M0. We haven't talked about any formal refinement just yet. So, my plan today
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Jackie Wang.