Introduction
I was flying back to Boston and looking at small villages in the middle of nowhere from high above, when a puzzle idea came to mind: If people in a village decided to spread some news among them as fast as possible, how would they do it? I would like it to take as few steps as possible for the news to reach everyone, which means that I'd like to avoid having the same villager being contacted twice because that would be wasteful. A slightly more formal version follows.
The puzzle
A vilage is threatened by a fire during the night when everyone is asleep. One of the villagers happens to wake up (for whatever reason people wake up during the night) and spots the fire. She now has to make sure the village gets notified asap, since everyone else is asleep! But how? Let's assume the following:
- Every house has a phone.
- There are N houses in the village.
- The only way to notify someone is by calling them.
- Every phone call takes 1 minute.
- A house can call another house in parallel with other phone calls (of course!).
- A house can only place one phone call at a time.
What algorithm should the villagers devise to make sure that in such an emergency the whole village gets notified as fast as possible? How many minutes would that take?
Now, don't look at the solution just yet!!!
Here 's a naive solution to build upon. It is the first thing that came to mind in the airplane. Say there are 100 houses. The first house finds out, then notifies 9 houses and each of those notifies in turn 10 houses each, for a total of 100 houses. If phone calls could be placed in parallel, this would obviously only take two steps (or minutes) to notify every one. But how do we do it if only one phone call can be placed at a time?
Solution
Assign to each house a number between 0 to N-1 (thanks Scott!).
Let's assume that house 0 spots the fire first.
Each house i (0<=i<N) will contact house 2^(p+j),
where: p = floor( log2(i) ) and 0<j
The process will terminate for house i when 2^(p+j) >= N.
The following figure illustrates the solution. Think about it like you have a piece of paper that is folded in half as many times as there are steps involved in the gossipping process. Every time you unfold the paper, the houses on one of the folded sides notify the corresponding houses on the other folded side, thus doubling the number of houses that are notified with every unfold.
Each yellow line represents an unfold, starting with house 0 which notifies house 1 in the first unfold action. The adjacent yellow line unfolds house 0 into house 2 and house 1 into house 3, thus 4 houses are now notified. In the next step, houses 4,5,6 and 7 will also be notified by houses 0,1,2 and 3 respectively and so on. In the example shown below where N=100, all houses are notified in a total of 7 steps (or unfolds).
I think there are some minor typos in your solution:
ReplyDelete1) there are N houses, so they assigned numbers from 0 to N-1
2) Each house i (0 <= i =0 is the time since the fire was detected (no need for p).
4) Stop calling when i+2^j >= N
I find this solution a bit unsatisfactory, though, since it means the calls that should be made depend on who saw the fire. Ie, each phone call would need to contain the information "there is a fire, it was seen by house H, and it is now time J (and there are N houses in the village)." Then each house would need to adjust its house number to (i-H)%N before proceeding with the algorithm at time step J+1 -- by phoning house ((((i-H)%N) + 2^(J+1)) + H) % N.
What's the most efficient *fixed* network for communicating news of the fire? (Where by fixed, I mean that the identity of the house which first saw the fire shouldn't be a required part of the phone call.)
There's an obvious centralized solution that solves the problem in 3*log_2 N minutes. Structure the houses in a binary tree, assign the chief to be house 0. If you detect a fire, call up in the tree to notify the chief. The chief will know there's a fire in (at most) log_2 N minutes. Then the chief will notify top-down. Notifying the next level takes 2 minutes per level, because there are two phone calls to make, for a total of 2*log_2 N minutes. (Actually one minute less, because the chief only has to make a single phone call, but you get the idea.)
Are there better fixed-network algorithms? (Almost certainly.)
Argh, HTML formatting killed my list of corrections. Here they are again:
ReplyDelete1) there are N houses, so they assigned numbers from 0 to N-1
2) Each house i (0 <= i < N)
3) p = floor(log2(i+2)) - 1, but it doesn't matter because house i should contact house i + 2^j, where j>=0 is the time since the fire was detected (no need for p).
4) Stop calling when i+2^j >= N
....and while we're at it, your original solution can be easily converted into a fixed-network solution. At step j, house i always phones house (i+2^j) unless (i + 2^j) > i OR (2^(j+1) - 1) in which case house i phones house (i - 2^j) instead. Now you just need to communicate j over the phone. (You don't need to communicate N -- just stop calling when no one answers the phone.)
Scott, that's awesome!
ReplyDeleteIndeed, I did not think about the "wrapping" issue if someone other than house 0 spots the fire first.
p ensures that a house doesn't call "backwards" houses that have already been contacted. If you omit p, then each house would have to communicate forward variable j so that consecutive houses don't start from scratch. I like having p better because it's a simple calculation on number i that each house already has (rather than having to communicate critical information in the middle of an emergency).
Also, the suggestion (your 2nd comment) on turning this into a "fixed" network works, but it'd be like a traversing a binary tree and if the node that spotted the fire is a leaf it would have to propagate all the way to the root before trickling back down again. Am I wrong? Isn't calling the root instead directly, like you suggested, easier?
Thanks for the heads-up on the typos!
No, in my second comment the communications pattern is exactly the same as in your original example. The OR should be a bitwise OR. For example, if node 16 spots the fire, it first calls node 17, then 16 calls 18 while 17 calls 19, then 16 calls 20 (etc), then 16 calls 24 (etc), *then 16 calls 0* and from that point on the sequence of calls is exactly the same as if the fire was spotted by 0. But they do need to communicate the time the fire was spotted.
ReplyDeleteReading this after a year. What kind of a geek spends a flight thinking up weird problems like that?
ReplyDelete