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:
- 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?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The protocol satisfies mutual exclusion: first note that Alice only lets the cat out if her flag is up, while Bob only lets the dog out if his flag is up. If either flag is down, at most one pet can be outside. If both flags are up, then the person whose name is on the board lets his or her pet out.
Is there any way that Bob will let his dog out if Alice's cat is already outside? No. Before letting his dog out, he writes "Alice" on the board and raises his flag. If the cat is outside, then Alice's flag will be up, and Bob will have to wait.
Let A i , B j be when the event "Alice is at step i " and "Bob is at step j ", respectively. Let "<" represent one event happening before another. Let's say Bob has already passed B 1 and B 2 and is at B 3 . There is only a problem if A 3 < B 3 . Let''s consider sequences:
A 2 < B 2 < A 3 < B 3 or A 2 < A 3 < B 2 < B 3 In this case Bob has written "Alice" on the board after Alice wrote "Bob". So "Alice" will be on the board and Bob will wait until Alice's flag drops before letting the dog out.
B 2 < A 2 < A 3 < B 3 . In this case Alice has written "Bob" on the board after he wrote "Alice". So she will wait until Bob's flag drops before letting her cat out. Thus there is no way both pets will be outside at the same time:
The protocol satisfies starvation-freedom: Since the individual algorithms are symmetric, it suffices to prove that Alice will be eventually able to let her cat out. Suppose she wants to let the cat out. She will only need to wait if the blue flag is up and "Bob" is on the board. But if the blue flag is up and "Bob" is on the board, there is nothing to keep Bob from letting his dog out (which he either does after "Bob" appears on the board or before the red flag is raised). Once Bob's dog is out, he'll eventually come in, and the blue flag will drop at that point. The Alice can let her cat out.