Format

Send to

Choose Destination
Science. 2011 Jan 14;331(6014):183-5. doi: 10.1126/science.1193210.

A biological solution to a fundamental distributed computing problem.

Author information

1
Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel.

Abstract

Computational and biological systems are often distributed so that processors (cells) jointly solve a task, without any of them receiving all inputs or observing all outputs. Maximal independent set (MIS) selection is a fundamental distributed computing procedure that seeks to elect a set of local leaders 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. By studying SOP selection, we 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. Our findings suggest that simple and efficient algorithms can be developed on the basis of biologically derived insights.

Comment in

PMID:
21233379
DOI:
10.1126/science.1193210
[Indexed for MEDLINE]
Free full text

Supplemental Content

Full text links

Icon for HighWire
Loading ...
Support Center