Deadlocked Cats And Dogs

Alice and Bob are best friends living in houses separated by a field. However, they have a problem. Alice owns a cat and Bob owns a dog, and their pets do not get along. 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:
  1. Raise a red flag on the terrace.
  2. Wait while Bob has a blue flag raised on his terrace.
  3. Let the cat out for an hour.
  4. Lower the red flag.
• Bob's Algorithm:
  1. Raise a blue flag on the terrace.
  2. Wait while Alice has a red flag raised on her terrace.
  3. Let the dog out for an hour.
  4. Lower the blue flag.

Provided that Alice and Bob strictly follow the protocol, is it guaranteed that whenever either owner wants to let their pet out, they will eventually be able to do so?

Low Level Concurrency by Olena Syrota.