Robots in a line

I was given this interesting puzzle or thought experiment by a friend.

Consider a line of n identical robots with constant memory, all running the same program (except for the first and last robots). Each robot can communicate (send messages) to the robots adjacent to it, taking one second to do so.

To start, the first robot is active, and all the other robots idle. By a series of messages, how can you make it so that all the robots say “yay” at the same time?

First attempt: Counting downwards

My first intuition was making the robots count downwards. Pick any large integer k, for example 1000000.

What the first robot does is send the number k-1 to the next robot, wait for k seconds, and say “yay“. The next robot does the same, sending k-2 to the third robot and starting its own timer. This continues all the way down.

So if there are 20 robots, 19 seconds after the experiment begins the last robot receives a message, and begins to count down from 999981. At this time, the counter for every other robot is the same.

Therefore, 999981 seconds later, all robots should say “yay” at the same time, and we are done.

The problem with this approach is we don’t know what n is; we don’t know how many robots there are. If we choose a sufficiently large n so that n > k, the approach will obviously fail.

While it works for certain values of n, we need something that would work no matter how large n is. It is obvious that this first approach fails.

Second attempt: Counting upwards

Obviously we can’t count downwards if we don’t know how many robots there are! We can invent a scheme that allows us to count the number of robots.

From now I will drop the explicit message sending and describe the message sending procedure explicitly.

Let the first robot start at 1. Then the next robot would be 2, and so on until the last robot is n.

Now the last robot knows how many robots there are in the line. Now we can use what we had in the first attempt, by picking a number k that is greater than n. So once the number of robots is known, we use the timer and counting down method to make all the robots say “yay” at the same time.

However, there is still a fundamental flaw with this solution. Suppose that the robots have m bits of memory. Then the counter can only go up to 2^m, otherwise it will overflow.

If the number of robots is greater than 2^m, this solution will not work.

Solution: Breaking apart the problem

The trick is to break up the problem into smaller pieces. To do so, we have to have a way of reliably breaking apart the problem.

There is a simple way of finding the middle of the line of robots. We can send two signals. The green one goes at the regular speed, that is, one robot per second. It reaches the last robot in n seconds, then bounces back and goes the opposite direction.

The other signal, the yellow signal, goes at a third of the regular speed: that is, one robot every three seconds.

By the time the yellow signal has reached the middle, the green signal would have gone to the opposite end and back. Therefore, any robot receiving both the green and yellow signals knows that it is the middle robot.

Once the middle has been found, we can split the problem into two equal subproblems. Ignoring the multitude of possible off-by-one errors, two middle robots may act like the new end and start robot respectively. The two subproblems now execute at the same time.

The procedure is repeated several times. Each time the number of robots in a chain is halfed. The subdivision is continued until the chain is divided into sections of length 1. At this moment every robot says “yay” at the same time, so we are done.

This problem is often referred to as the Firing squad synchronization problem.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s