Will the cat and the dog be in peace?
Source: Low Level Concurrency by Olena Syrota
Alice and Bob are best friends living in two houses across a field. However, they have a problem. Alice owns a cat and Bob a dog and their pets do not get along. So, as a result they can never let both their pets loose in the field together.
They set up the following protocol to decide when to let their pets out:
-
Alice's Algorithm:
- Raise a red flag on the terrace.
- Wait while Bob has a blue flag raised on his terrace.
- Let the cat out for sometime.
- Lower the red flag.
-
Bob's Algorithm:
- Raise a blue flag on the terrace.
- Wait while Alice has a red flag on her terrace.
- Let the dog out for sometime.
- Lower the blue flag.
Provided that Alice and Bob strictly follow the protocol, is it guaranteed that the dog and the cat can never be in the field in the same time?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
As long as Alice has her cat out, her flag is raised. She only lowers the flag after she takes the cat in. Bob will not let his dog out as long as Alice's flag is raised, meaning he will not let his dog out until Alice's cat is inside. By the same logic, since their algorithm is the same, Alice will not let her cat out as long as Bob's dog is in his yard.