How Networks of Biological Cells Solve Distributed Computing Problems

Distributed computing is all the rage these days. The idea is to break down computational tasks into convenient chunks and distribute them across a network to a number of computers. The benefits are clear, such as easy, on-demand access to huge computing resources. 

The conventional way to think about these systems is as independent Turing machines connected by a network that allows them to exchange large messages. This so-called ‘message passing model’ certainly applies to much of the distributed computing that takes place on the internet; projects such as the SETI@home and the Einstein @home programs.

But there is a growing awareness that many networks are much more limited, both in the size of the messages they can transmit and receive and also in the processing capacity at each node. 

A biological cell, for example, can transmit and receive only limited amounts of information and can perform only rudimentary processing tasks.  It’s easy to imagine that a network of cells can perform only very simple distributed computing tasks. On the other hand, perhaps they can make up for their individual deficiencies by working as a group and so are just as capable as other networks.   

So an important question is how these limitations influence the classes of distributed computing tasks that groups of cells can perform. 

Today we have an answer thanks to the work of Yuval Emek, Jasmin Smula and Roger Wattenhofer at the Swiss Federal Institute of Technology in Zurich. “We believe that there is a need for a network model, where nodes are by design below the computation and communication capabilities of Turing machines,” they say. 

These guys have modelled the computing behaviour of a network of these sub-Turing machines, which they call finite state machines. They show that far from being critically handicapped, a network of finite state machines is capable of solving many of the standard problems in conventional distributed computing, such as the 3-colouring of undirected trees . 

What’s more, these networks can do the job just as efficiently–in a time that is poly-logarithmic with the number of cells.

That could turn out to have far reaching consequences. It may be a stretch to imagine a network of cells joining the SETI@home project. But it provides a framework in which to study how networks of cells might solve other common problems in biological systems such as forward planning, trajectory calculations and so on.

The new model can also be applied in more prosaic ways, such as predicting the performance of networks of sensors which are strongly constricted by power limitations.

Emek and co ask the question: “do tiny bio/nano nodes “compute” and/or “communicate” essentially [in] the same [way] as a computer?”

The answer, it would seem, is yes, which means it is an exciting time to be a distributed computing specialist working in biology. 

Ref: arxiv.org/abs/1202.1186: Stone Age Distributed Computing