Report

A Biological Solution to a Fundamental Distributed Computing Problem

Science  14 Jan 2011:
Vol. 331, Issue 6014, pp. 183-185
DOI: 10.1126/science.1193210

You are currently viewing the abstract.

View Full Text

Via your Institution

Log in through your institution

Log in through your institution


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.

View Full Text