Distributed computing models typically assume reliable communication between processors. While such assumptions often hold for engineered networks, e.g., due to underlying error correction protocols, their relevance to biological systems, wherein messages are often distorted before reaching their destination, is quite limited. In this study we aim at bridging this gap by rigorously analyzing a model of communication in large anonymous populations composed of simple agents which interact through short and highly unreliable messages. We focus on the rumor-spreading problem and the majority-consensus problem, two fundamental tasks in distributed computing, and initiate their study under communication noise. Our model for communication is extremely weak and follows the push gossip communication paradigm: In each synchronous round each agent that wishes to send information delivers a message to a random anonymous agent. This communication is further restricted to contain only one bit (essentially representing an opinion). Lastly, the system is assumed to be so noisy that the bit in each message sent is flipped independently with probability 1 2-e, for some small Ae >0. Even in this severely restricted, stochastic and noisy setting we give natural protocols that solve the noisy rumor-spreading and the noisy majority-consensus problems efficiently. Our protocols run in O(log n e2) rounds and use O(n log n e2) messages bits in total, where n is the number of agents. These bounds are asymptotically optimal and, in fact, are as fast and message efficient as if each agent would have been simultaneously informed directly by the source. Our efficient, robust, and simple algorithms suggest balancing between silence and transmission, synchronization, and majority-based decisions as important ingredients towards understanding collective communication schemes in anonymous and noisy populations.
Broadcast related problems were studied in other contexts as well, often with settings where communication noise is inherent. Engineers have studied the related problem of sensor network consensus formation in the presence of communication noise and have demonstrated, for example, tradeoffs between consensus quality and running time @cite_14 . Physicists have studied the spreading of epidemics @cite_16 and the formation of consensus around a zealot in voter models @cite_48 @cite_6 within probabilistic settings that include communication noise. These physically inspired studies often assume very simple algorithms and analyze their performance - this is different from a computer science approach which focuses on identifying the most efficient algorithms. Indeed, broadcast within a noisy voter model setting is expected to yield long convergence times, polynomial in the number of agents.
@cite_48 @cite_14 @cite_6 @cite_16
1969871566 2155723880 1965044289 2030539428
A method for studying the exact properties of a class of inhomogeneous stochastic many-body systems is developed and presented in the framework of a voter model perturbed by the presence of a "zealot," an individual allowed to favor an "opinion." We compute exactly the magnetization of this model and find that in one (1D) and two dimensions (2D) it evolves, algebraically ( t-1 2) in 1D and much slower ( 1 lnt) in 2D, towards the unanimity state chosen by the zealot. In higher dimensions the stationary magnetization is no longer uniform: the zealot cannot influence all the individuals. The implications to other physical problems are also pointed out The paper studies average consensus with random topologies (intermittent links) and noisy channels. Consensus with noise in the network links leads to the bias-variance dilemma-running consensus for long reduces the bias of the final average estimate but increases its variance. We present two different compromises to this tradeoff: the A-ND algorithm modifies conventional consensus by forcing the weights to satisfy a persistence condition (slowly decaying to zero;) and the A-NC algorithm where the weights are constant but consensus is run for a fixed number of iterations [^(iota)], then it is restarted and rerun for a total of [^(p)] runs, and at the end averages the final states of the [^(p)] runs (Monte Carlo averaging). We use controlled Markov processes and stochastic approximation arguments to prove almost sure convergence of A-ND to a finite consensus limit and compute explicitly the mean square error (mse) (variance) of the consensus limit. We show that A-ND represents the best of both worlds-zero bias and low variance-at the cost of a slow convergence rate; rescaling the weights balances the variance versus the rate of bias reduction (convergence rate). In contrast, A-NC, because of its constant weights, converges fast but presents a different bias-variance tradeoff. For the same number of iterations [^(iota)][^(p)] , shorter runs (smaller [^(iota)] ) lead to high bias but smaller variance (larger number [^(p)] of runs to average over.) For a static nonrandom network with Gaussian noise, we compute the optimal gain for A-NC to reach in the shortest number of iterations [^(iota)][^(p)] , with high probability (1-delta), (epsiv, delta)-consensus (epsiv residual bias). Our results hold under fairly general assumptions on the random link failures and communication noise. We study the voter model with a finite density of zealots—voters that never change opinion. For equal numbers of zealots of each species, the distribution of magnetization (opinions) is Gaussian in the mean-field limit, as well as in one and two dimensions, with a width that is proportional to , where Z is the number of zealots, independent of the total number of voters. Thus just a few zealots can prevent consensus or even the formation of a robust majority. The study of social networks, and in particular the spread of disease on networks, has attracted considerable recent attention in the physics community. In this paper, we show that a large class of standard epidemiological models, the so-called susceptible infective removed (SIR) models can be solved exactly on a wide variety of networks. In addition to the standard but unrealistic case of fixed infectiveness time and fixed and uncorrelated probability of transmission between all pairs of individuals, we solve cases in which times and probabilities are nonuniform and correlated. We also consider one simple case of an epidemic in a structured population, that of a sexually transmitted disease in a population divided into men and women. We confirm the correctness of our exact solutions with numerical simulations of SIR epidemics on networks.