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.
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?
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).