Distributed Information Processing in Biological and Computational systems

Navlakha, S. & Bar-Joseph, Z., 2014. Distributed information processing in biological and computational systems. Communications of the ACM, 58(1), pp.94—102.

Introduction

This article discusses how distributed biological systems solve problems such as routing and navigation, decision making, and leader election. The motivation for this kind of research is that understanding how computational problems are being solved by biological problems can lead to algorithms which are particularly beneficial, if robustness and adaptivity are of high importance. Therefore, bidirectional studies in the biological and computer science domain have been conducted, applying ideas and principles from one of these domains to the other.

Communication models

Communication in biological systems typically involves very small message sizes (e.g. the presence or absence of one bit). Typical models are

1. beeping (i.e. a message can be either present or not), or
2. communications based on finite state machines which are only able to count up to a certain number (e.g. up to ten messages and all other messages are handled as >10).

It has been shown that both models are able to handle certain problems such as interval coloring (i.e. distribute resources such that neighboring nodes have disjoint resources), although a higher runtime complexity is required.

Population models facilitate communication by direct communication between a pair of agents. This type of communication is able to solve problems such as OR computations, majority, summation, leader election and consensus. Ants, for instance use the number of antena contacts as to decide whether to increase the number of outgoing ants from the nest (high number of contacts -> many ants -> a lot of food -> increase the number of outgoing ants).

Shared memory models are facilitated by proteins which were shown to modify DNA as a mean to regulate the expression and activity of genes.

Robustness of biological communication models

Biological communication models focus on robustness rather than speed, which is especially important in noisy environments. Many proteins (approximately 40% of the human proteins have at least one paralog), for instance, often have structural similar paralogs which originated from the same ancestral protein. These paralogs act as backups in case the original protein is altered.

Biological systems also optimize their topology to increase the robustness of their information processing. Therefore, weakly linked modules that are robust against single-point attacks and cascading failures are preferred over densely connected cliques which offer higher performance. The human brain overproduces synapses by 50-60% during its development and only stabilizes its circuitry in late adolescence. In addition, several lifeforms have the ability to adjust their structure (e.g. the wirering of neurons) to the challenges faced in the decision making process.