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 had a solution, but it turned out to be problematic. They now own a billboard in the yard, on which they can write at most one word.
They set up the following protocol to decide when to let their pets out:
- Alice's Algorithm:
- Raise a red flag on the terrace.
- Write Bob on the billboard.
- Wait while Bob has a blue flag raised on his terrace and the billboard says Bob.
- Let the cat out for an hour.
- Lower the red flag.
- Bob's Algorithm:
- Raise a blue flag on the terrace.
- Write Alice on the billboard.
- Wait while Alice has a red flag raised on her terrace and the billboard says Alice.
- Let the dog out for an hour.
- Lower the blue flag.
This protocol is said to satisfy mutual exclusion if both pets are never out in the field together and said to satisfy starvation-freedom if when an owner wants to let their pet out, they eventually succeed.
Which of these properties does this protocol satisfy?