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:
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?