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?

×

Problem Loading...

Note Loading...

Set Loading...