Fruit Flies Do Distributed Computing

First the ants jump on the bandwagon, and now the fruit flies.  This is from a fairly recent article published in Science (link). 

A common problem in distributed computing is to determine a local set of master/leader nodes in a group of nodes.  Such is called the maximal independent set, or MIS.  The goal is to have all non-master nodes connected to a master, and to not have masters connect to each other.  Although it sounds simple from a top to bottom approach, one is not afforded this luxury; after all, this is distributed.  Looking at it from the bottom up, it's a much more difficult problem.  A given node can only see a very limited amount around it.  From this standpoint, the problem is so difficult that constructing a MIS deterministically is impossible (assuming all nodes are equal). 

For a moment, let's leave the realm of computer science and enter the realm of biology.  In biological systems, there is often a need to be very precise, all without any central guiding intelligence.  This is especially true of embryonic development.  Cells must differentiate from a somewhat generic mass to more specialized, highly ordered structures.  The paper notes the notum of a fly, where there are many neat rows of small bristles, with a few scattered (yet evenly spaced) rows of long bristles.  The structure shows a high degree of organization, which all came about via simple cell to cell communication.  There was no signal for "put this row here", but instead a passing of short chemical messages to one another.  It's truly amazing that such order can come from relative chaos with so little intervention.

The researchers first looked at exactly how this chemical communication occurred.  For one, the bristles were found to have properties like masters.  The cells that they were derived from acted in a different manner than their surrounding cells.  Upon further examination, they found that these cells expressed large amounts of a cell-membrane protein called "Delta".  Surrounding cells had a membrane protein called "Notch", which could recognize Delta.  It was found that Delta would inhibit surrounding cells with the Notch receptor from becoming bristle cells.  Essentially, the message is "I'm already forming a bristle, so don't form one yourself," although the actual message is much shorter than that (connected/not connected). 

This phenomenon is very similar to the MIS problem.  The only difference is that the biological system is able to do it perfectly almost every time, and that such systems have been doing this for a very long time.  As such, the researchers applied the method used by the biological system to form an actual MIS algorithm.  The algorithm works in a multi-pass way.  Without getting too involved in the details, there are two exchanges that occur during each pass.  In the first exchange, with a certain probability empirically determined from the fruit flies, a message is passed to all neighbors.  If we don't receive any message back, then the given node becomes a master, and terminates the algorithm.  If we do receive a message back, then the algorithm continues for a set number of passes, repeating these steps. 

They found that the algorithm was very effective, and could provably generate a proper MIS every time.  With a high probability, all nodes would fall into place, although, on occasion, a node failed to be connected to anything.  The authors acknowledge this, and claim that such events are rare and can easily be corrected by means outside of the algorithm.  As for the performance of the algorithm, it runs in O(log(n)^2), where n is the number of nodes in the network, and messages passed need only be one bit in size.  Pretty impressive, especially when one considers the difficulty of the problem.  I guess fruit flies are smarter than we think.