We consider a population of @math agents which communicate with each other in a decentralized manner, through random pairwise interactions. One or more agents in the population may act as authoritative sources of information, and the objective of the remaining agents is to obtain information from or about these source agents. We study two basic tasks: broadcasting, in which the agents are to learn the bit-state of an authoritative source which is present in the population, and source detection, in which the agents are required to decide if at least one source agent is present in the population or not.We focus on designing protocols which meet two natural conditions: (1) universality, i.e., independence of population size, and (2) rapid convergence to a correct global state after a reconfiguration, such as a change in the state of a source agent. Our main positive result is to show that both of these constraints can be met. For both the broadcasting problem and the source detection problem, we obtain solutions with a convergence time of @math rounds, w.h.p., from any starting configuration. The solution to broadcasting is exact, which means that all agents reach the state broadcast by the source, while the solution to source detection admits one-sided error on a @math -fraction of the population (which is unavoidable for this problem). Both protocols are easy to implement in practice and have a compact formulation.Our protocols exploit the properties of self-organizing oscillatory dynamics. On the hardness side, our main structural insight is to prove that any protocol which meets the constraints of universality and of rapid convergence after reconfiguration must display a form of non-stationary behavior (of which oscillatory dynamics are an example). We also observe that the periodicity of the oscillatory behavior of the protocol, when present, must necessarily depend on the number @math of source agents present in the population. For instance, our protocols inherently rely on the emergence of a signal passing through the population, whose period is @math rounds for most starting configurations. The design of clocks with tunable frequency may be of independent interest, notably in modeling biological networks.
@cite_15: Rock is wrapped by paper, paper is cut by scissors and scissors are crushed by rock. This simple game is popular among children and adults to decide on trivial disputes that have no obvious winner, but cyclic dominance is also at the heart of predator–prey interactions, the mating strategy of side-blotched lizards, the overgrowth of marine sessile organisms and competition in microbial populations. Cyclical interactions also emerge spontaneously in evolutionary games entailing volunteering, reward, punishment, and in fact are common when the competing strategies are three or more, regardless of the particularities of the game. Here, we review recent advances on the rock–paper–scissors (RPS) and related evolutionary games, focusing, in particular, on pattern formation, the impact of mobility and the spontaneous emergence of cyclic dominance. We also review mean-field and zero-dimensional RPS models and the application of the complex Ginzburg–Landau equation, and we highlight the importance and usefulness of statistical physics for the successful study of large-scale ecological systems. Directions for future research, related, for example, to dynamical effects of coevolutionary rules and invasion reversals owing to multi-point interactions, are also outlined.
@cite_12: We propose a new model of self-organized criticality. A particle is dropped at random on a lattice and moves along directions specified by arrows at each site. As it moves, it changes the direction of the arrows according to fixed rules. On closed graphs these walks generate Euler circuits. On open graphs, the particle eventually leaves the system, and a new particle is then added. The operators corresponding to particle addition generate an Abelian group, same as the group for the Abelian sandpile model on the graph. We determine the critical steady state and some critical exponents exactly, using this equivalence.
We also remark that local interaction dynamics on arbitrary graphs (as opposed to the complete interaction graph) exhibit a much more complex structure of their limit behavior, even if the graph has periodic structure, e.g., that of a grid. Oscillatory behavior may be overlaid with spatial effects @cite_15 , or the system may have an attractor at a critical point, leading to simple dynamic processes displaying self-organized criticality (SOC, @cite_12 ).