On time. Working together, imprecise clocks can keep good time.

Bad Clocks Keep Good Time

Perfection might not be such an elusive goal after all: A pair of physicists has found that groups of imprecise clocks can collaborate to tell time with remarkable accuracy. Their findings might one day help computers tackle tough problems as a team.

Scientists and engineers know the difficulty of extracting accurate information from a collection of imperfect devices, such as a clutch of clocks. Every clock gives a slightly different reading, and the problem is how to combine those readings to get the best estimate of the time. The most obvious solution is to average readings from all the clocks--a strategy once employed by sailors at sea--but the inaccuracy decreases only slowly as the number of clocks increases. For example, to get an estimate 10 times more accurate than that of a single clock, a timekeeper would need about 100 clocks.

A far better way is to read only some of the clocks, report physicists Damien Challet and Neil Johnson of Oxford University. In a computer study, the researchers simulated collections of clocks with readings distributed around the correct value according to a bell curve. They then took the reading of each clock individually, the average reading for each possible pair of clocks, the average reading for each group of three, and so on. By trying every subset, Challet and Johnson found that they could usually identify a combination containing roughly half the clocks whose average reading was far closer to the correct time than the simple average of all the clocks, as they report in the 8 July issue of Physical Review Letters. For example, starting with 20 clocks, they typically found a subset of about 10 whose inaccuracies compensated for one another almost perfectly, so that their average was 100,000 times more accurate than was the average of all the clocks.

Moreover, Challet and Johnson proved mathematically that in certain cases, it is relatively easy to compute the best combination, given the amount that each clock is fast or slow. That implies that a technologist should be able to figure out how to cobble together a nearly perfect machine from a basket of faulty parts after simply checking the inaccuracy of each part.

The work is an important step in the study of "collectives," groups of autonomous agents that conspire to achieve a common goal, says David Wolpert, an expert in complex systems at NASA's Ames Research Center in Moffett Field, California. "Things become really interesting when the agents aren't little clocks but computer chips." Such studies will be crucial, Wolpert says, as computers evolve from machines that perform specific tasks, by following strict rules, to more adaptable entities that can work together and find their own ways to solve larger problems.

Related sites
The abstract for Challet and Johnson's paper
David Wolpert's page on collective intelligence
An upcoming workshop on collectives