Self-replicating Structures in Dynamical Systems that Perform the Majority Task

Collective dynamics in networks can perform complex tasks. An intensively studied toy example is the ``Majority Task,'' which is a simple model for aspects of emergent coordination and error correction in colonial organisms, social swarms, and communication networks. In the majority task spatially distributed units with two possible states are supposed to collectively evolve from a mixed initial state configuration to a uniform final configuration. When the task is performed correctly the final unit state is the one that was initially in the majority. These networks have no memory or central controllers, so the task is performed solely by unit-unit interactions. How this is accomplished and how it fails is not well understood. In the 2D version examined here, the units interact with only nearest neighbors through the very effective ``2DGKL'' dynamical rule. Rigorous studies of the evolution of 15x15 networks with approximately 50-50 irregular distributions of initial states, have discovered system-spanning, self-replicating structures that form early in the process. Units adjacent to self-replicating structures quickly become part of a larger self-replicating structure until the network reaches its final state. As a result, these structures can be used to predict the outcome of a network. The existence and significance of self-replicating structures is a new insight into the majority task and understanding how they form might be key to decoding and improving how the task is performed.