Improved complex distributed computing systems

Edit Hook

Abstract from paper:"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 SOPselection, 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." (Yehuda A; 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.)

Biomimicry Story

By looking at how cells in fruit flies, during larvae and pupae development, select the precursors to fly sensory bristles (called sensory organ precursors of SOPs), the researchers created a new algorithm that "does not require knowledge of the degree of individual processors, uses one-bit messages, and has optimal message complexity. These features are useful for many applications, including wireless communication systems and ad hoc sensor networks." (Yehuda et al. 2011:185).

Challenges Solved

According to the paper, a long-standing computational problem is that of electing a set of local leaders, called the maximal independent set or MIS, in a network of connected processors. Distributively electing a MIS has been considered a challenge for the last 30 years. Despite efforts to solve some of the challenges, no method was able to efficiently reduce message complexity without assuming knowledge of the number of neighbors.

Edit Summary