Scheduling Random Walks

Juggling competing demands in a network of feverishly calculating computers drawing on the same memory resources is like trying to avert collisions among blindfolded, randomly zigzagging ice skaters.

Among networked computers, some sort of software scheduler must act as a referee to regulate data flow. Proving that a given scheduler not only prevents conflicts but also performs its duties efficiently can be surprisingly difficult, however. Computer scientists have found that analyzing even simple data-sharing cases can be troublesome.

One important scheduling problem is equivalent to moving two tokens, each one at the start of a different infinite string of random digits. At each tick of a clock, the scheduler chooses which of the tokens to move one digit to the right, always making sure that the tokens never end up on the same number at the same time. Can the scheduler keep the tokens going forever along their own strings without ever having both tokens simultaneously on, say, 7?

Track 1: 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 . . .

Track 2: 7 1 8 2 8 1 8 2 8 4 5 9 0 4 5 2 3 5 3 . . .

Despite the problem’s apparent simplicity, no one knows the answer yet, says mathematician Peter M. Winkler of Bell Laboratories in Murray Hill, N.J. Nonetheless, recent advances suggest that the answer is probably yes, he remarked at the Joint Mathematics Meetings held last week in New Orleans.

Instead of following tokens along infinite tracks, computer scientists and mathematicians find it convenient to study random walks on a graph–a two-dimensional array of points connected by lines. At each tick of the clock, a token moves randomly from one point to another connected point.

The behavior of random walks by a single token on a graph is well understood, Winkler says. “Much less is known about the behavior of multiple, simultaneous random walks,” he notes.

The scheduling problem takes the following form: If two tokens take random walks on the same array and every step of both walks is known in advance, can the scheduler keep the tokens from ever colliding by choosing, on each clock tick, which token moves? Winkler calls such a scheduler a clairvoyant demon.

In 1990, Winkler conjectured that, on a sufficiently complex graph, a clairvoyant schedule demon can, with positive probability, keep two, randomly walking tokens apart forever. Even now, however, no one can point to a finite graph that is known to have this property.

To obtain clues on how to solve the clairvoyant-demon problem, Winkler looked at a variant that turned out to easier to handle than the original. In the variant, the scheduler doesn’t know the paths in advance but instead has the option of immediately retracting an erroneous move by sending a token backwards along its walk. Winkler terms this scheduler a fickle demon.

The fickle demon has at most four choices at each tick of the clock: Move the first token forward or backward or move the second token forward or backward. It may not make a move that causes a collision or pushes a token back before time 0.

It turns out that both types of demons can be studied in an alternative mathematical setting–as a so-called percolation problem. In this case, a particle starts at the corner (or origin) of a square grid and moves from one vertex of the grid to another. The x coordinate of a vertex represents the location of one token, and the y coordinate represent the location of another token at the same time. Some vertices, corresponding to locations where the tokens would collide, are out of bounds. Can a schedule demon steer such a particle, representing the movements of the two tokens, through this obstacle course? The demon wins if it can push the particle to infinity, avoiding the restricted sites.

It’s easy to see that the clairvoyant demon has no chance to win if it can see only finitely far ahead, Winkler remarks. On the other hand, the fickle demon can never get stuck once it gets started, and even a random strategy will suffice to push the token arbitrarily far, as long as there are infinitely many sites connected to the origin.

For the fickle scheduler, it’s possible to determine precisely what circumstances prevent escape. As a result, Winkler can specify which graphs lend themselves to collision-free navigation by two randomly walking tokens. Using different methods, Bela Bolobas of the University of Memphis in Tennessee and his collaborators have independently obtained similar results.

So far, researchers have failed in their efforts to use the same techniques to prove that a clairvoyant demon who can’t retract a move can promise collision-free navigation on any graph. Recent theoretical work by Peter Gacs of Boston University and computations by John Tromp of the National Research Institute for Mathematics and Computer Science in Amsterdam have provided clues that may yet point to a solution.