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 two 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, a 7?
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 find it convenient to study random walks on 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 such an array is well understood, Winkler says. “Much less is known about the behavior of multiple, simultaneous random walks,” he notes.
The scheduling question takes the following form: If two tokens take random walks on the same array and every step of each walk is known in advance, can the scheduler keep the tokens from ever colliding by choosing, on each tick of the clock, which token moves?
Winkler has solved a variant of the problem that turns out to be 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.
For this fickle scheduler, Winkler can specify precisely which arrays of points and connections lend themselves to collision-free navigation by two randomly walking tokens.
Using different methods, Bela Bollob’s 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 these techniques to prove that a clairvoyant scheduler who can’t retract a move can promise collision-free navigation on any array, Winkler says. Recent theoretical work by Peter Göcs 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, he adds.
