Fruit fly brains for wireless deployments

A newly developed algorithm could improve distributed computer networks using principles behind the biological development of a fruit fly.

Described in the journal Science this week, the algorithm could allow engineers to effectively deploy distributed systems in a wider range of situations.

Current distributed networks typically communicate via a so-called 'maximal independent set' (MIS) of 'leader' nodes that connect to non-leader elements, but not each other.

Network elements self-select to join the MIS using an iterative, probabilistic method that is based, in part, on how many connections each element has with others.

According to machine learning researcher Ziv Bar-Joseph, the self-selection method is 'rapid' but requires a great deal of communication and advance knowledge of how components are connected to each other.

That requirement was energy-intensive and could be an issue for randomly distributed sensors, he said, highlighting ad hoc sensor networks and swarms of nanorobots as examples.

Bar-Joseph and his colleagues in Israel and the US studied the development of fruit flies, taking particular interest in how flies' brain cells organised themselves.

During larva and pupa stages, some cells self-selected to become sensory organ precursors (SOPs) that controlled sensory bristles on flies' bodies - like MIS nodes in a sensor network.

"MIS for sensor networks is similar [to SOPs] in some ways," said Bar-Joseph, of Carnegie Mellon University.

"[In distributed electronic networks], we are trying to obtain some globally smart behaviour from a collection of relatively cheap and weak processors.

"Similarly, each cell in our brain is pretty limited in terms of what it can do, but collectively they can do wonderful things."

Digital fly brains

While the researchers did not yet know how exactly fruit fly brains developed, Bar-Joseph expected their observations to be sufficient for an MIS selection algorithm.

"People have been looking at this for decades," he told iTnews. "It's not completely figured out yet [but] we don't care how the fly got to the solution."

The team closely observed two clusters of approximately 20 brain cells in each of 10 fruit fly pupae for three hours.

Unlike current MIS selection methods, the SOP selection process did not require cells to know the number of non-selected cells they neighboured.

MIS selection algorithm by Y Afek, N Alon, O Barad, E Hornstein, N Barkai, and Z Bar-Joseph. Courtesy of Science/AAAS.

Cells that became SOPs would emit a protein that inhibited their neighbours from self-selecting later, and the probability that a cell would self-select to become an SOP appeared to increase as time progressed.

Bar-Joseph said that few cells tended to self-select initially, so there was a small chance that neighbouring cells would "collide" by simultaneously self-selecting to become SOPs.

Such collisions occurred in fruit flies less than one percent of the time, he said, noting that flies that developed with conflicting SOP signals suffered an evolutionary disadvantage.

To avoid collisions in the digital model, the researchers determined that collisions would lead to the inhibition of all future communications between the two would-be leaders.

Their resultant algorithm was found to solve the MIS problem in a quick, robust manner, although it was slightly slower than current methods for networks with a large number of components.

Bar-Joseph expected the 15-line algorithm to be easily implemented in research projects and the industry, although the researchers had not yet spoken to industry members about their findings and had no commercial plans.

"We devised a solution to a longstanding distributed computing problem," the researchers wrote in Science.

"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."