Fruit fly research could lead to simpler and more robust computer networks
By Grant Banks
January 17, 2011
Over the years science has gleaned an enormous amount of knowledge from the humble fruit fly. Drosophila melanogaster was used to provide the post-Mendelian foundations for our understanding of genetics and has also been used extensively in neuroscience research. The latest fruit fly-inspired innovation could simplify how wireless sensor networks communicate and stands to have wider applications for computing.
This is not the first time computing systems have been compared to biological systems. Learning from a comparison between Linux and E.coli and using fly's eyes to help develop faster visual receivers for robots are just two examples. This time round researchers at Carnegie Mellon University (CMU), Pittsburgh, Pennsylvania, have discovered a highly efficient system of organizing cells in the fruit fly's nervous system develops that stands to have applications in computer networking.
Without communication with surrounding cells or prior knowledge of what these other cells are doing the fly's developing nervous system is able to organize itself so that a small number become leader cells or sensory organ precursor cells (SOP), while the rest become ordinary nerve cells. The SOPs which connect to adjoining nerve cells do not connect with other SOPs, but instead to the ends of the nervous system that are attached to tiny hairs for interacting with the outside world. What is extraordinary about how this hierarchy of cells organizes itself is the fact that the right number and combination of SOP cells and nerve cells form without the need for complicated information exchange.
The fly's nervous system uses a probabilistic method to select the cells that will become SOPs. The cells have no information about how they are connected to each other but 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.
Ziv Bar-Joseph, associate professor of machine learning and computational biology at CMU and author of the report noted that the probability that any cell will self-select increases not as a function of connections, as with a maximal independent set (MIS) algorithm used in computer networking, but as a function of time. The researchers believe that computer networks could be developed using this innovative system creating networks which are much simpler and more robust.
"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 – developed a new distributed computing algorithm using their findings. The resulting network was shown to have qualities that are well suited for networks in which the number and position of the nodes is not completely certain including wireless sensor networks, such as environmental monitoring, or where sensors are dispersed. They also believe this could be used in systems for controlling swarms of robots.
“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," Bar-Joseph said. "This makes the solution applicable to many more applications."
The research was supported in part by grants from the National Institutes of Health and the National Science Foundation.