title: A biological solution to a fundamental distributed computing problem.
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.
authors.affiliation: Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel.
authors.forename: Yehuda
authors.initials: Y
authors.lastname: Afek
authors.forename: Noga
authors.initials: N
authors.lastname: Alon
authors.forename: Omer
authors.initials: O
authors.lastname: Barad
authors.forename: Eran
authors.initials: E
authors.lastname: Hornstein
authors.forename: Naama
authors.initials: N
authors.lastname: Barkai
authors.forename: Ziv
authors.initials: Z
authors.lastname: Bar-Joseph
mesh_terms: D000465:Algorithms; D000818:Animals; D003195:Computer Communication Networks; D004330:Drosophila / Q000166:cytology* / Q000254:growth & development*; D008432:Mathematical Computing; D008954:Models, Biological; D011336:Probability; D011679:Pupa / Q000166:cytology / Q000254:growth & development; D011984:Sensory Receptor Cells / Q000166:cytology*