Happier Pets

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:
    1. Raise a red flag on the terrace.
    2. Write Bob on the billboard.
    3. Wait while Bob has a blue flag raised on his terrace and the billboard says Bob.
    4. Let the cat out for an hour.
    5. Lower the red flag.
  • Bob's Algorithm:
    1. Raise a blue flag on the terrace.
    2. Write Alice on the billboard.
    3. Wait while Alice has a red flag raised on her terrace and the billboard says Alice.
    4. Let the dog out for an hour.
    5. 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?

×

Problem Loading...

Note Loading...

Set Loading...