[HD] EECS3342 F26 - 2026-11-10 (Tuesday) - Lecture 16
Overview
Jackie Wang reviews Event-B proof obligations for invariant establishment, invariant preservation, and deadlock freedom, then diagnoses a deadlock in the bridge-controller model: the capacity constant D may be zero, leaving both event guards false immediately after initialization. Adding the axiom D > 0 makes the deadlock-freedom proof succeed; the lecture then introduces refinement M1, where abstract car count N is represented by concrete variables A, B, and C, linked by N = A + B + C and constrained to prevent opposing bridge traffic.
Key takeaways
- In the M0 bridge controller, N = 0 after initialization; if D = 0, both guards N < D and N > 0 are false, producing an immediate deadlock.
- The failed goal D > 0 combined with the typing constraint D ≥ 0 isolates D = 0 as the counterexample; adding D > 0 as an axiom removes that case and completes the deadlock-freedom proof.
- Equality inference rules replace every occurrence of one side of an equality in the goal, and EQ_RL versus EQ_LR can lead to substantially different proof branches.
- M1 represents the abstract total N using N = A + B + C, where B counts island cars and A and C count bridge traffic in opposite directions.
- The safety invariant A = 0 or C = 0 prevents opposing traffic while still allowing an empty bridge; requiring one direction to have positive traffic would unnecessarily exclude that valid state.
- Refinement distinguishes old events, which receive concrete versions in M1, from new events such as I_in and I_out, which exist only in the refined model.
Chapters
- Written Test 2 is scheduled for November 18 and covers material from the current and following lecture, with case-study coverage to be confirmed in a study guide.
- Lab 4 is the final lab and is planned for release the following week, possibly a few days early.
- Jackie Wang plans to open an eClass regrading request for Written Test 1, available for about one week.
- Deadlock occurs when every event guard is false; deadlock freedom requires at least one event guard to be enabled.
- The deadlock-freedom proof obligation combines the event guards with a disjunction, under the axioms and invariants.
- Invariant establishment, invariant preservation, and deadlock freedom differ in whether they use pre-state and post-state values.
- With the hypothesis N = D, EQ_RL replaces every occurrence of the right-hand side D in the goal with the left-hand side N.
- The resulting goal includes N < N or N > 0; selecting the second disjunct leaves N > 0 to prove.
- Choosing EQ_LR instead produces a different proof branch, so a useful but unprovable result can justify backtracking and trying the other equality rule.
- The proof sequence leaves D > 0 unprovable, identifying a possible model state in which the desired condition fails.
- The alternative N > 0 is too restrictive because initialization may legitimately set N to zero.
- The lecture therefore investigates whether D can equal zero, rather than imposing a positive lower bound on the system's current car count.
- Failure to prove D > 0 points to the possible countercondition D ≤ 0.
- The existing typing constraint says D is a natural number, so D ≥ 0.
- Together, D ≤ 0 and D ≥ 0 identify D = 0 as the capacity value that can violate deadlock freedom.
- Initialization sets the abstract car count N to zero.
- The two M0 guards are N < D for the event admitting a car and N > 0 for the event removing a car.
- When D = 0 and N = 0, both guards evaluate to false, so the model deadlocks immediately after initialization.
- The model excludes the counterexample by adding D > 0 as a new axiom, since D is a constant rather than a state variable.
- The added axiom becomes an additional hypothesis in the deadlock-freedom proof sequence.
- After the proof branches, the D > 0 hypothesis directly discharges the remaining goal; an equivalent natural-number typing constraint could also express the restriction.
- M0's static part contains constants and axioms, while its dynamic part contains the state variable and events.
- Guards were added to support invariant preservation, and the new D > 0 axiom fixes the deadlock-freedom proof.
- Refinement M1 adds concrete detail by separating the island from the bridge, while retaining M0's correctness criteria and introducing refinement checks.
- M0 is the more abstract model, representing the whole island-bridge compound with a single variable N.
- M1 refines M0 by distinguishing where cars are and which direction they travel on the one-way bridge.
- The M0 events describe cars entering or leaving the compound; their M1 counterparts give those movements more concrete meanings.
- M1 introduces B for cars on the island, A for cars on the bridge heading from the mainland toward the island, and C for cars heading in the opposite direction.
- The old M0 events have concrete versions in M1, with guards and actions expressed using A, B, and C rather than only N.
- A one-way bridge requires the model to distinguish the two directions so it can rule out simultaneous opposing traffic.
- M1 adds the new events I_in and I_out, which do not exist in M0.
- A refinement can add state variables and events, as well as more detailed axioms and invariants.
- M1 refines M0 by adding concreteness, particularly through A, B, and C to encode the one-way-bridge requirement.
- The first three M1 invariants type A, B, and C as natural-number counts, allowing values such as zero.
- Invariant 4 links the abstract state to the concrete state with N = A + B + C.
- This linking invariant accounts for every car in the compound across the island and both possible bridge directions.
- Invariant 5 states A = 0 or C = 0, ensuring that cars cannot occupy the bridge in opposite directions at the same time.
- The alternative A × C = 0 is mathematically equivalent but can make proofs harder by introducing multiplication.
- The condition A > 0 and C = 0, or C > 0 and A = 0, prevents collisions but is too restrictive because it disallows an empty bridge.
- The longer alternative A + C = A or A + C = C is equivalent to the compact invariant when the counts are natural numbers.
- Old events originate in M0 and have abstract and concrete versions; the concrete versions use M1's A, B, and C variables.
- I_in and I_out are new events introduced only in the refinement, so they have no abstract M0 versions.
- Refinement is relative: M1 is concrete compared with M0, while M2 will be concrete compared with M1.
Transcript excerpt
0:05 All right. So, your written test number two will be next Wednesday. Uh let's take a look. So, two things uh you can expect to happen most likely tomorrow. If you look at the uh semester calendar right here. Okay. Make a bit larger. All right. So, we are now November 10th >> right here. Okay. So, today we doing uh lecture 16 and then uh next Wednesday uh November 18th, you got your written test number two. At the same time, I'll also release your lab number four, the very last lab. Okay?
0:52 You can also get started later. But but for written test number two, I mean I'm going to give you some guidance and also the practice question as well for you to try it out. But at least what we're going to cover today and also on Thursday will be covered as well in the written test. So it doesn't hurt for you to really get started with the preparation especially uh we haven't test you just yet about the bridge controller case study. So just start from the beginning of the case study but I'm going to confirm the coverage when I release the guide. All right. All right. Okay. So, here lab number four to be released but not yet. Not this week. According to schedule it should be next week but if I can release uh release a few days earlier I'll do so. Okay. But not yet. Okay. Okay. So, uh so let me see. Why do I not
1:43 have Let me just open it again. Okay. There we go. Sorry. All right. Uh I heard that you may have some questions or doubts about a grading for written test number one. I think that maybe the best way to handle that
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.