An intersection, checked exhaustively
Autonomous vehicles ask two controllers for permission to move. A model checker explores every interleaving of their messages to show that no vehicle is ever given a movement it is not allowed, and that no request waits forever.
- Context
- MSc coursework (F21RS), individual
- Date
- Dec 2025
- Size
- 407-line Promela model, six processes
- Stack
- Promela, SPIN, LTL
The model
Three kinds of vehicle have different rights. A private car may only go straight, a city bus may only turn left, and a robotaxi alternates right and left turns. Controller Alpha serves straight and right; Controller Beta serves left and cannot grant right turns. Vehicles send requests over bounded channels of capacity two and wait on their own response channel. A separate monitor process asserts the permission rules and the channel bounds in every state.
What SPIN checked
- safety_type1
[] (last_response_type1 != LEFT && last_response_type1 != RIGHT)A private car is only ever told to go straight. - safety_type2
[] (last_response_type2 != STRAIGHT && last_response_type2 != RIGHT)A bus is only ever told to turn left. - safety_type3
[] (last_response_type3 != STRAIGHT)A robotaxi is never told to go straight. - liveness_typeN
[] (typeN_request_pending -> <> !typeN_request_pending)Every pending request is eventually answered, for each of the three types.
The report records zero errors for the monitor's assertions, the three safety properties and the three liveness properties. The search stored 3,291 states with 9,382 transitions and reached depth 627. Progress labels on each vehicle loop support checking under weak fairness, so an unscheduled process is not mistaken for starvation.
How an update gets lost
The second half of the report studies a shared counter of vehicles inside the intersection. An increment written as read, add, write can interleave so that two vehicles enter and the counter shows one. Try both schedules, then switch to the atomic version.
Vehicle 1
temp = ·- temp = count
- temp = temp + 1
- count = temp
Vehicle 2
temp = ·- temp = count
- temp = temp + 1
- count = temp
Shared counter
0
Pick who runs next.
- Atomic sections
- Wrapping the increment in atomic { } makes it one indivisible step for the model checker, so no interleaving can split it.
- A channel as a lock
- A rendezvous channel of capacity zero forces a handshake before the critical section, which behaves like a mutex. It works, but adds states, so atomic sections are the simpler choice in a model.
Looking back
Re-reading the report, the safety and liveness runs show identical search statistics. A liveness property needs SPIN's acceptance-cycle search with weak fairness (pan -a -f), which explores differently from a plain safety search, so I would now re-run the liveness checks explicitly in that mode and report their numbers separately. It is a small thing, and exactly the kind of thing I check first today.