Skip to content
VVS

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
01

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.

Private carSTRAIGHT onlyRobotaxiRIGHT, LEFT, RIGHT…City busLEFT onlyController AlphaSTRAIGHT, RIGHTController BetaLEFT onlySafety monitorasserts every staterequest_alpha [2]request_beta [2]answers on response_type1..3 [2]
Fig. 1Processes and channels. Each vehicle blocks on its response channel until a controller answers.Illustrative· model structure
02

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.

Tool output· SPIN output, as recorded in the report
03

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 = ·
  1. temp = count
  2. temp = temp + 1
  3. count = temp

Vehicle 2

temp = ·
  1. temp = count
  2. temp = temp + 1
  3. count = temp

Shared counter

0

Pick who runs next.

    You are the scheduler here. SPIN explores every order exhaustively, which is how it finds the one that loses an update.Illustrative· example from the report
    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.
    04

    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.