Title: Universal Protocols for Information Dissemination Using Emergent Signals,
Abstract: We consider a population of $n$ 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 $O(\log^2 n)$ 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 $\varepsilon$-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 $^\\# X$ 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 $\Theta(\log \frac{n}{^\\# X})$ rounds for most starting configurations. The
design of clocks with tunable frequency may be of independent interest, notably
in modeling biological networks.