Fruit fly nervous system biomimicry for faster computer networks

The fruit fly has evolved a method for arranging the tiny, hair-like structures it uses to feel and hear the world. A team of researchers in Israel and at Carnegie Mellon University were inspired by that method and they think it could be used for more effectively deployed wireless sensor networks, such as environmental monitoring, where sensors are dispersed in a lake or waterway, or systems which control swarms of robots.

With a minimum of communication and without advance knowledge of how they are connected with each other, the cells in the fly’s developing nervous system manage to organize themselves in a way in which a small number of cells serve as leaders that provide direct connections with every other nerve cell. The researchers used the insights gained from fruit flies to design a new distributed computing algorithm.

“Computational and mathematical models have long been used by scientists to analyze biological systems”, said one of the researchers Ziv Bar-Joseph, a faculty member of the Lane Center for Computational Biology and the Machine Learning Department 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 potential failures of individual elements.

In the computing world, one step toward creating a 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 it is connected to a leader, and the leaders are not interconnected. A biological analogy is the similar arrangement which 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.

The common solutions to select a MIS use a probabilistic method (similar to rolling a dice) in which some processors identify themselves as leaders, based in part on how many connections they have with other processors. This selection process is rapid, but it requires lots of complicated messages being sent back and forth across the network, and it requires that all of the processors know in advance how they are connected in the network. That can be a problem for applications such as wireless sensor networks, where sensors might be distributed randomly and all might not be within communication range of each other.

During the larval and pupal stages of a fly’s development, the nervous system also uses a probabilistic method to select the cells that will become SOPs. In the fly, however, the cells have no information about how they are connected to each other. As various cells self-select themselves as SOPs, they send out chemical signals to neighboring cells that inhibit those cells from also becoming SOPs. This process continues for three hours, until all of the cells are either SOPs or are neighbors to an SOP, and the fly emerges from the pupal stage.

The researchers noted that the probability that any cell in the fly will self-select increases not as a function of connections (as in the typical MIS algorithm for computer networks) but as a function of time. The method does not require advance knowledge of how the cells are arranged. The communication between cells is as simple as can be. The researchers created a computer algorithm based on the fly’s approach and proved that it provides a fast solution to the MIS problem.

“The run time was slightly greater than current approaches, but the biological approach is efficient and more robust because it doesn’t require so many assumptions”, said Bar-Joseph. “This makes the solution applicable to many more applications.”

For more information, read the results researchers reported in the Jan. 14 edition of the journal Science named: ”A Biological Solution to a Fundamental Distributed Computing Problem”.