Spreading a Confirmed Rumor: A Case for Oscillatory Dynamics
Résumé
We consider an information spreading problem in which a population of $n$ agents is to determine, through random pairwise interactions, whether an authoritative rumor source $X$ is present in the population or not. The studied problem is a generalization of the rumor spreading problem, in which we additionally impose that the rumor should disappear when the rumor source no longer exists. It is also a generalization of the self-stabilizing broadcasting problem and has direct application to amplifying trace concentrations in chemical reaction networks.
We show that there exists a protocol such that, starting from any possible initial state configuration, in the absence of a rumor source all agents reach a designated ``uninformed'' state after $O(\log^2 n)$ rounds w.h.p., whereas in the presence of the rumor source, at any time after at least $O(\log n)$ rounds from the moment $X$ appears, at least $(1 -\varepsilon)n$ agents are in an ``informed'' state with probability $1 - O(1/n)$, where $\varepsilon>0$ may be arbitrarily fixed. The protocol uses a constant number of states and its operation relies on an underlying oscillatory dynamics with a closed limit orbit. On the negative side, we show that any system which has such an ability to ``suppress false rumors'' in sub-polynomial time must either exhibit significant and perpetual variations of opinion over time in the presence of the rumor source, or use a super-constant number of states.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...