Will the cat and the dog be in peace?
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?