Atomic acquisition with two processesComplete reachable interleaving graph
The problem
Check mutual exclusion over all one-shot lock-acquisition interleavings.
The checked result
Mutual exclusion holds: yes.
An atomic acquisition prevents simultaneous entry. A split acquisition can let both processes remember a free lock before either marks it occupied.
Why the checker accepts it
- Start all processes outside the critical section with a free lock.
- Explore every enabled interleaving to a complete reachable closure.
- Check the number of processes in the critical section at each state.
- For a failure, replay the provided schedule to the unsafe state.
Formal specification
{
"processes": 2,
"mode": "atomic",
"state_encoding": "process PCs, lock bit, process saved-free bits; PC 0=start, 1=checked, 2=critical, 3=done",
"atomicity": "Atomic mode tests and acquires together; split mode tests then acquires in separate steps."
}Claim and evidence
{
"claim": {
"mutual_exclusion": true
},
"witness": {
"method": "reachable-state enumeration"
}
}Dataset construction
Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 8 checker units for this record; the unit type is stated in its verification scope.
Complexity and limits
The finite state space is exponential in the number of processes; this family uses two or three one-shot processes.
This is a shared-memory mutual-exclusion model. It does not verify a network protocol, message loss, liveness, or fairness.
A boundary to investigate
Separating a lock check from acquisition allows another process to observe the same free lock. Extend from shared-memory concurrency to bounded message queues and explicit network faults.