3 ms·
TLA+'s model checker will verify (NB: this has scaling limits, but that isn't a problem for many practical circumstances) that two concurrent wires (when the sy
by Jtsummers 4y ago
TLA+'s model checker will verify (NB: this has scaling limits, but that isn't a problem for many practical circumstances) that two concurrent wires (when the system is properly specified) won't stomp on each other. Conversely, it will detect when they could stomp on each other.
So take that definition for the wire function and let two processes run it simultaneously:
alice.balance = 100
spawn(wire(alice, bob, 100))
spawn(wire(alice, bob, 100))
Only one of these should succeed, but since the function isn't guaranteed to be atomic we can get to this state:
p1:
if a.balance >= amount: -- true, so continues into the condition body
a.balance -= amount -- process paused here
b.balance += amount
p2:
if a.balance >= amount: -- true, so continues into the condition body
a.balance -= amount -- alice's balance now 0
b.balance += amount -- bob gets 100
When p1 resumes after p2 finishes, Alice will end up with a balance of -100 and Bob will get 200. Assuming overdrafts aren't allowed (per the spec they aren't) then the system has reached an invalid state.
When testing concurrent programs it is a non-trivial thing to force these states, so bugs like this are hard to detect because they may only occur occasionally. And because they occur rarely, even when detected the actual source of the bug can be hard to reliably discern. TLA+'s model checker will check each possible interleaving of the two processes (in this case) and will discover the invalid execution path I showed above. Then you can go back to the spec and address the issue and rerun the checker, if your invariants hold (no sequence of actions lead to overdraft, in this case) then you can have confidence that, at least with regard to the properties you've specified, the system is correct.