1 Tahrcountry Musings: Solution to a fundamental distributed computing problem from biologically derived insights

Friday, January 14, 2011

Solution to a fundamental distributed computing problem from biologically derived insights

Here is yet another example of benefits derived from nature. Scientists  from Blavatnik School of Computer Science and Sackler School of Mathematics, Tel Aviv University , Institute for Advanced Study, Princeton, USA, Department of Molecular Genetics, Weizmann Institute of Science,  Israel and School of Computer Science, Carnegie Mellon UniversityUSA have successfully developed     a solution to fundamental distributed computing problem from biologically derived insights in to fruit flies. It also emphasizes the need for biodiversity conservation. We have only scratched the surface. The vast cornucopia is yet to be fully explored for its multifaceted benefits.

Computational and biological systems are often distributed so that processors (cells) jointly solve a task. None of the cells receive all inputs or observe all outputs. Maximal independent set (MIS) selection is a fundamental distributed computing procedure where a set of local leaders are elected in a network. A variant of this problem is solved during the development of the fly’s nervous system, when sensory organ precursor (SOP) cells are chosen. 

Scientist studied SOP selection in fruit flies and derived a fast algorithm for MIS selection that combines two attractive features. First, processors do not need to know their degree; second, it has an optimal message complexity while only using one-bit messages.

The research amply demonstrated that simple and efficient algorithms can be developed on the basis of biologically derived insights.

No comments: