A biological solution to a fundamental distributed computing problem

Yehuda Afek, Noga Alon, Omer Barad, Eran Hornstein, Naama Barkai, Ziv Bar-Joseph

Research output: Contribution to journalArticle

101 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)183-185
Number of pages3
JournalScience
Volume331
Issue number6014
DOIs
StatePublished - Jan 14 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General

Fingerprint Dive into the research topics of 'A biological solution to a fundamental distributed computing problem'. Together they form a unique fingerprint.

  • Cite this

    Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., & Bar-Joseph, Z. (2011). A biological solution to a fundamental distributed computing problem. Science, 331(6014), 183-185. https://doi.org/10.1126/science.1193210