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:
Post a Comment