Fruit flies have solved a computing problem that has vexed computer scientists for decades. Mimicking how some nerve cells in flies pick a leader to make decisions has led scientists to a computer algorithm that could make wireless sensor networks, such as those used for monitoring volcanic activity or controlling swarms of robots, much more efficient.
In such smart networks, some sensors can act as leaders to alert headquarters if, for example, a certain number of them detect rumblings indicating that a volcano might be waking up. The new approach, published in the Jan. 13 Science, achieves the same leader-follower relationships but eliminates a lot of cross-talk among sensors, saving energy and computing power.
A colleague’s presentation on how nerve cells in fruit flies take on different jobs struck computational biologist Ziv Bar-Joseph as being very similar to a distributed computing problem. In distributed computing, many computer processors work together toward a common goal, but with minimal leadership. A handful of processors — typically ones with many neighboring processors — are designated leaders and set up to receive information from the processors around them and pass it on.
“People in computer science made assumptions about what sensors need to know,” says Bar-Joseph, a researcher at Carnegie Mellon University in Pittsburgh who led the new work. But developing cells set up their networks without knowing much about their neighbors, he says. “They work in a much more constrained environment and still come up with solutions.”
When fruit fly larvae are developing, some cells take on particular tasks, such as becoming a precursor of the sensory bristles the flies use to read the air around them. Each bristle ends up surrounded by nonbristle cells. This layout, where there are enough specialized cells, or leaders, but no two are right next to each other, is very similar to how tasks are divvied up in distributed networks, says Bar-Joseph.
For 30 years, computer scientists had thought that to most efficiently designate a handful of processors as leaders that can quickly communicate with the rest of the network, each processor had to take stock of its local neighborhood. Then some processors would identify themselves as leaders, based in part on how many connections they have with other processors.
Young fruit fly nerve cells don’t necessarily know how many cells are in their neighborhood, yet they manage to develop into appropriately distributed sensory bristles. Once a cell elects itself as a bristle, it sends out a protein signal that inhibits neighboring cells from becoming bristles.
The flies’ trick lies in using timing instead of a neighborhood census to determine which cell becomes a bristle, Bar-Joseph and his colleagues report. As time passes, if a cell hasn’t received a don’t-become-a-bristle directive, it becomes a bristle, as simple as that. The new algorithm shows that networks of sensors could do the same, without spending time and energy gathering all that information on how many sensors are nearby, says Bar-Joseph.
“Now you don’t need to know about the neighborhood,” says Bar-Joseph. “Each sensor can be close to five or 500 sensors and it doesn’t need to know anything.”
The approach is “a delight” says Mark Fricker of the University of Oxford in England who is using slime mold behavior to build more efficient networks. “They have taken a very well-established biological developmental system and shown that it can be recast in a computational framework to solve an existing problem efficiently and effectively.”
