Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.
Subscribe

Logo for

Science 331 (6014): 183-185

Copyright © 2011 by the American Association for the Advancement of Science

A Biological Solution to a Fundamental Distributed Computing Problem

Yehuda Afek,1,* Noga Alon,1,2,* Omer Barad,3,* Eran Hornstein,3 Naama Barkai,3,{dagger} Ziv Bar-Joseph4,{dagger}

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.

1 Blavatnik School of Computer Science and Sackler School of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel.
2 Institute for Advanced Study, Princeton, NJ 08544, USA.
3 Department of Molecular Genetics, Weizmann Institute of Science, Rehovot 76100, Israel.
4 School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA.

* These authors contributed equally to this work.

{dagger} To whom correspondence should be addressed. E-mail: naama.barkai{at}weizmann.ac.il (N.B.); zivbj{at}cs.cmu.edu (Z.B.-J.)

THIS ARTICLE HAS BEEN CITED BY OTHER ARTICLES:
The stubborn roots of metabolic cycles.
E. Reznik, A. Watson, and O. Chaudhary (2013)
J R Soc Interface 10, 20130087
   Abstract »    Full Text »    PDF »
Distributed algorithms for sensor networks.
C. Lenzen and R. Wattenhofer (2012)
Phil Trans R Soc A 370, 11-26
   Abstract »    Full Text »    PDF »
Learning from Nature.
J. O. Kephart (2011)
Science 331, 682-683
   Abstract »    Full Text »    PDF »

To Advertise     Find Products

Science Signaling. ISSN 1937-9145 (online), 1945-0877 (print). Pre-2008: Science's STKE. ISSN 1525-8882