Uniting With Only a Few Random Links

Information about highly complex systems, such as the spread of diseases, the rise and fall of financial markets, or cell-phone communication networks, benefits from large-scale networked computer simulation.

These simulations are frequently implemented using large networks of computers that break down the problem into many parts. Tackling weighty problems, bit by byte, allows the simulation process to run faster — sometimes.

The problem comes when the computers have to compare notes, says Gyorgy Korniss, assistant professor of physics at Rensselaer. Korniss’ solution is to use “small-world” networking — which links a computer to its nearest neighbor, and also a few other random computers in the group. Korniss’ findings were published in the Jan. 31 issue of the journal Science.

Korniss’s research could lead to better parallel-computing techniques for simulation. Parallel computing divides a task among many smaller computers instead of one large one to do the job faster and more efficiently.

Typically, each computer in a network is connected to its closest “neighbor.” But getting information from the machine next door doesn’t allow each computer to get the whole picture of what the entire neighborhood is doing. When one system is collecting data at a greater pace than another, the result is a data traffic jam, causing a major slowdown in the simulation process.

“Enormous amounts of additional time or memory are required for computers to keep track of information they need from each other to create accurate simulations,” Korniss says.

The solution, according to Korniss, lies with creating a “small world”-like communication network in which the individual computers randomly “check in” with each other to make sure they are in sync.