Fish Switching Schools: Emergence of Consensus in a Boolean Belief Network

Many natural (e.g., insect swarming) and engineered (e.g., cloud computing) networks consist of locally connected units with no central processing unit (CPU). Optimal task-performance by such networks depends on the units achieving consensus, via self-organized dynamics, of what their internal states should be. Experiments using fish that are trained to school toward colored targets yield hints for understanding and designing functional CPU-less networks. One experiment involves two targets of different color and two populations each trained on one of the colors. If one population is in a small majority, the two schools are stable: each member holds an unshakable ``Boolean belief'' of the correct color. Introducing a few untrained fish can cause all of the fish to school toward the color of the initial majority. The undecided fish apparently enable the whole network to perform the ``initial majority task.'' Directed, local, three-fish interactions that harbor ``residual synergy'' somehow make this consensus possible. To investigate the essential aspects of such collective dynamics, we study a binary cellular automaton on a square lattice with nearest neighbor interactions. The update rule is ``if the current state of a cell is 1, then adopt in the next instant the majority state of that cell plus its north and east neighbors, otherwise use the south and west neighbors.'' This rule accurately senses the majority over a wide range of randomly distributed initial states and shows precisely how checkerboard (i.e., undecided) patches propagate through the network switching the Boolean beliefs of cells in their paths.