Fruit Flies Inspire Scientists to Optimize Computer Networks
The fruit fly has evolved a method for positioning its tiny, hair-like structures used to feel and hear the world that’s so efficient, that a team of scientists in Israel and at Carnegie Mellon University says it could be copied to more effectively deploy wireless sensor networks and other distributed computing applications.
With a minimum of communication and without advanced knowledge of how they are connected with each other, the cells in the fly’s developing nervous system manage to organize themselves so that a small number of cells serve as leaders that provide direct connections with every other nerve cell, said author Ziv Bar-Joseph, associate professor of machine learning at Carnegie Mellon University.
The result, the researchers report in the Jan. 14 edition of the journal Science, is the same sort of scheme used to manage the distributed computer networks that perform such everyday tasks as searching the Web or controlling an airplane in flight. But the method used by the fly’s nervous system to organize itself is much simpler and more robust than anything humans have concocted.
“It is such a simple and intuitive solution, I can’t believe we did not think of this 25 years ago,” said co-author Noga Alon, a mathematician and computer scientist at Tel Aviv University and the Institute for Advanced Study in Princeton, N.J.
Bar-Joseph, Alon and their co-authors — Yehuda Afek of Tel Aviv University and Naama Barkai, Eran Hornstein and Omer Barad of the Weizmann Institute of Science in Rehovot, Israel — used the insights gained from fruit flies to design a new distributed computing algorithm. They found it has qualities that make it particularly well suited for networks in which the number and position of the nodes is not completely certain. These include wireless sensor networks, such as environmental monitoring, where sensors are dispersed in a lake or waterway, or systems for controlling swarms of robots.
“Computational and mathematical models have long been used by scientists to analyze biological systems,” said Bar-Joseph, a member of the Lane Center for Computational Biology in Carnegie Mellon’s School of Computer Science. “Here we’ve reversed the strategy, studying a biological system to solve a long-standing computer science problem.”
Today’s large-scale computer systems and the nervous system of a fly both take a distributive approach to performing tasks. Though the thousands or even millions of processors in a computing system and the millions of cells in a fly’s nervous system must work together to complete a task, none of the elements need to have complete knowledge of what’s going on, and the systems must function despite failures by individual elements.
In the computing world, one step toward creating this distributive system is to find a small set of processors that can be used to rapidly communicate with the rest of the processors in the network — what graph theorists call a maximal independent set (MIS). Every processor in such a network is either a leader (a member of the MIS) or is connected to a leader, but the leaders are not interconnected.
A similar arrangement occurs in the fruit fly, which uses tiny bristles to sense the outside world. Each bristle develops from a nerve cell, called a sensory organ precursor (SOP), which connects to adjoining nerve cells, but does not connect with other SOPs.