Motivated by the growing interest in mobile systems, we study the dynamics of information dissemination between agents moving independently on a plane. Formally, we consider @math mobile agents performing independent random walks on an @math -node grid. At time @math , each agent is located at a random node of the grid and one agent has a rumor. The spread of the rumor is governed by a dynamic communication graph process @math , where two agents are connected by an edge in @math iff their distance at time @math is within their transmission radius @math . Modeling the physical reality that the speed of radio transmission is much faster than the motion of the agents, we assume that the rumor can travel throughout a connected component of @math before the graph is altered by the motion. We study the broadcast time @math of the system, which is the time it takes for all agents to know the rumor. We focus on the sparse case (below the percolation point @math ) where, with high probability, no connected component in @math has more than a logarithmic number of agents and the broadcast time is dominated by the time it takes for many independent random walks to meet each other. Quite surprisingly, we show that for a system below the percolation point the broadcast time does not depend on the relation between the mobility speed and the transmission radius. In fact, we prove that @math for any @math , even when the transmission range is significantly larger than the mobility range in one step, giving a tight characterization up to logarithmic factors. Our result complements a recent result of (SODA 2011) who showed that above the percolation point the broadcast time is polylogarithmic in @math .
A prolific line of research has addressed broadcasting and gossiping in static graphs, where the nodes of the graph represent active entities which exchange messages along incident edges according to specific protocols (e.g., , , ). The most recent results in this area relate the performance of the protocols to expansion properties of the underlying topology, with particular attention to the case of social networks, where broadcasting is often referred to as @cite_2 . (For a relatively recent, comprehensive survey on this subject, see @cite_8 .)
@cite_8 @cite_2
2010682628 1990476939 2110100895 2132612558
In this paper we study gossip based information spreading with bounded message sizes. We use algebraic gossip to disseminate k distinct messages to all n nodes in a network. For arbitrary networks we provide a new upper bound for uniform algebraic gossip of O((k + log n + D)Δ) rounds with high probability, where D and Δ are the diameter and the maximum degree in the network, respectively. For many topologies and selections of k this bound improves previous results, in particular, for graphs with a constant maximum degree it implies that uniform gossip is order optimal and the stopping time is Θ(k + D). To eliminate the factor of Δ from the upper bound we propose a non-uniform gossip protocol, TAG, which is based on algebraic gossip and an arbitrary spanning tree protocol S. The stopping time of TAG is O(k+ log n + d(S) + t(S)), where t(S) is the stopping time of the spanning tree protocol, and d(S) is the diameter of the spanning tree. We provide two general cases in which this bound leads to an order optimal protocol. The first is for k=Ω(n), where, using a simple gossip broadcast protocol that creates a spanning tree in at most linear time, we show that TAG finishes after Θ(n) rounds for any graph. The second uses a sophisticated, recent gossip protocol to build a fast spanning tree on graphs with large weak conductance. In turn, this leads to the optimally of TAG on these graphs for k=Ω(polylog(n)). The technique used in our proofs relies on queuing theory, which is an interesting approach that can be useful in future gossip analysis. The dynamic behavior of a network in which information is changing continuously over time requires robust and efficient mechanisms for keeping nodes updated about new information. Gossip protocols are mechanisms for this task in which nodes communicate with one another according to some underlying deterministic or randomized algorithm, exchanging information in each communication step. In a variety of contexts, the use of randomization to propagate information has been found to provide better reliability and scalability than more regimented deterministic approaches.In many settings, such as a cluster of distributed computing hosts, new information is generated at individual nodes, and is most "interesting" to nodes that are nearby. Thus, we propose distance-based propagation bounds as a performance measure for gossip mechanisms: a node at distance d from the origin of a new piece of information should be able to learn about this information with a delay that grows slowly with d, and is independent of the size of the network.For nodes arranged with uniform density in Euclidean space, we present natural gossip mechanisms, called spatial gossip, that satisfy such a guarantee: new information is spread to nodes at distance d, with high probability, in O(log1 + e d) time steps. Such a bound combines the desirable qualitative features of uniform gossip, in which information is spread with a delay that is logarithmic in the full network size, and deterministic flooding, in which information is spread with a delay that is linear in the distance and independent of the network size. Our mechanisms and their analysis resolve a conjecture of [1987].We further show an application of our gossip mechanisms to a basic resource location problem, in which nodes seek to rapidly learn the location of the nearest copy of a resource in a network. This problem, which is of considerable practical importance, can be solved by a very simple protocol using Spatial Gossip, whereas we can show that no protocol built on top of uniform gossip can inform nodes of their approximately nearest resource within poly-logarithmic time. The analysis relies on an additional useful property of spatial gossip, namely that information travels from its source to sinks along short paths not visiting points of the network far from the two nodes. Over the last decade, we have seen a revolution in connectivity between computers, and a resulting paradigm shift from centralized to highly distributed systems. With massive scale also comes massive instability, as node and link failures become the norm rather than the exception. For such highly volatile systems, decentralized gossip-based protocols are emerging as an approach to maintaining simplicity and scalability while achieving fault-tolerant information dissemination. In this paper, we study the problem of computing aggregates with gossip-style protocols. Our first contribution is an analysis of simple gossip-based protocols for the computation of sums, averages, random samples, quantiles, and other aggregate functions, and we show that our protocols converge exponentially fast to the true answer when using uniform gossip. Our second contribution is the definition of a precise notion of the speed with which a node's data diffuses through the network. We show that this diffusion speed is at the heart of the approximation guarantees for all of the above problems. We analyze the diffusion speed of uniform gossip in the presence of node and link failures, as well as for flooding-based mechanisms. The latter expose interesting connections to random walks on graphs. In this paper, we study two related iterative randomized algorithms for distributed computation of averages. The first algorithm is the Broadcast Gossip Algorithm, in which at each iteration one randomly selected node broadcasts its own state to its neighbors. The second algorithm is a novel variation of the former, in which at each iteration every node is allowed to broadcast: hence, this algorithm, which we call Collision Broadcast Gossip Algorithm (CBGA), is affected by interference among messages. The performance of both algorithms is evaluated in terms of rate of convergence and asymptotical error: focusing on large Abelian Cayley networks, we highlight the role of topology and of design parameters. We show that on fully connected graphs the rate of convergence is bounded away from one, whereas the asymptotical error is bounded away from zero. On the contrary, on sparse graphs the rate of convergence goes to one and the asymptotical error goes to zero, as the size of the network grows larger. Our results also show that the performance of the CBGA is close to the performance of the BGA: this indicates the robustness of broadcast gossip algorithms to interferences.