David Shaw has returned to an early career. He designed some innovative parallel computers as an associate professor at Columbia University, went off to start a fabulously successful hedge fund and now has decided to simulate molecular dynamics calculations using vast parallelism.
A critical problem in such calculations is called the N-body problem which entails computing the future behavior of a collection of N objects (in our case, atoms) where the objects start with a velocity and position and each object exerts some force on all other objects. One must compute the trajectory of each atom as a function of all nearby atoms and some characterization of far-away atoms. My New York University colleague Leslie Greengard has developed a fundamental method (called "fast multipole") for the far-away atoms. Shaw and his colleagues have worked on how to lay out the near-atom problem on a parallel computer. I provide a reference at the end. The following puzzle, however, will abstract the problem to its essential core.
A bunch of office employees are placed in single-person cubicles along a very long, narrow poorly lit corridor. It is so narrow that only two people can pass one another at a time. The cubicles have numbers on the door starting at 0, so: 0, 1, 2, 3, ... (This numbering system is architecturally unusual but will be convenient mathematically.) We design the protocol of our solution as if we were looking at the hallway from the side, so we'll talk about people moving to the right and to the left.
Each person would like to shake hands with his or her three neighbors in the cubicles on each side (that is, the three to the right and the three to the left). Suppose that each handshake takes 10 seconds and passing from one cubicle to a neighboring one takes no time.
How long would it take if just one worker p wanted to shake hands with all six neighbors?
Just 60 seconds. All the neighbors would come to p.
Of course, while person p meets his six neighbors, person p+7 could meet his six neighbors, so parallelism is possible. But our problem is to make everyone shake hands with his or her three neighbors to the left and his or her three neighbors to the right.
Here is one approach. Suppose that we handle people at locations p, p+4, p+8, etc., with respect to their three neighbors to the right. This can be done in 30 seconds. For example, p+1, p+2, and p+3 shake hands with p at the same time that p+4+1, p+4+2, and p+4+3 shake hands with p+4. In the next 30 seconds people at p+1, p+1+4, p+1+8 shake hands with their right neighbors. Altogether this takes 4 * 30 = 120 seconds.
1. However, 120 seconds is longer than necessary. How much better can we do?
Now, suppose that instead of one dimension, we had two dimensions. We have a large office with freestanding cubicles and each cubicle is surrounded by hallways on all four sides. The cubicles are numbered by their x and y coordinates starting at the lower left at (0,0). Each person wants to shake hands with everyone who is a “Manhattan distance” of two or fewer spaces away (that is, all neighbors two away horizontally and vertically as well as the immediate diagonal neighbors).
2. How can we do this and how much time will it take?
Let’s return to the single-corridor situation but now suppose that walking from cubicle to cubicle takes some time--say, one second per cubicle--but instead of shaking hands, office workers just glance at one another, taking zero time. Because of the bad lighting in the corridor, people will see one another properly only inside cubicles. A cubicle can fit no more than seven people.
3. How long should it take on a single corridor for all people to meet all six nearest neighbors?
Still open is how to solve the problem when participants don't know their cubicle number, and so don't know what their positions are, yet must nevertheless meet their nearest three neighbors.