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 .
@cite_21 @cite_24 the authors study the time it takes to broadcast information from one of @math mobile agents to all others. The agents move on a square grid of @math nodes and in each time step, an agent can (a) exchange information with all agents at distance at most @math from it, and (b) move to any random node at distance at most @math from its current position. The results in these papers only apply to a very dense scenario where the number of agents is linear in the number of grid nodes (i.e., @math ). They show that the broadcast time is @math w.h.p., when @math and @math @cite_21 , and it is @math w.h.p., when @math @cite_24 . These results crucially rely on @math , which implies that the range of agents' communications or movements at each step defines a connected graph.
@cite_24 @cite_21
1981696935 2087097376 1984466682 2153529758
We consider broadcasting in radio networks, modeled as undirected graphs, whose nodes know only their own label and labels of their neighbors. In every step every node acts either as a transmitter or as a receiver. A node acting as a transmitter sends a message which can potentially reach all of its neighbors. A node acting as a receiver in a given step gets a message if and only if exactly one of its neighbors transmits in this step. Bar-Yehuda, Goldreich, and Itai [J. Comput. System Sci., 45 (1992), pp. 104--126] considered broadcasting in this model. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks of diameter 3. This claim turns out to be incorrect in this model (although it is valid in a more pessimistic model [R. Bar-Yehuda, O. Goldreich, and A. Itai, Errata Regarding "On the time complexity of broadcast in radio networks: An exponential gap between determinism and randomization," http: www.wisdom.weizmann.ac.il mathusers oded p .html, 2002]). We construct an algorithm that broadcasts in logarithmic time on all graphs from the Bar-Yehuda, Goldreich, and Itai paper (BGI). Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter @math . On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time @math on these graphs. In view of the randomized algorithm from BGI, running in expected time @math on all @math -node graphs of diameter D (cf. also a recent @math -time algorithm from [D. Kowalski and A. Pelc, Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing, Boston, 2003, pp. 73--82; A. Czumaj and W. Rytter, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, MA, 2003, pp. 492--501]), our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting, under the considered model of radio communication. Consider a team of mobile software agents deployed to capture a (possibly hostile) intruder in a network. All agents, including the intruder move along the network links; the intruder could be arbitrarily fast, and aware of the positions of all the agents. The problem is to design the agents' strategy for capturing the intruder. The main efficiency parameter is the size of the team. This is an instance of the well known graph-searching problem whose many variants have been extensively studied in the literature. In all existing solutions, and in all the variants of the problem, it is assumed that agents can be removed from their current location and placed in another network site arbitrarily and at any time. As a consequence, the existing optimal strategies cannot be employed in situations for which agents cannot access the network at any point, or cannot "jump" across the network, or cannot reach an arbitrary point of the network via an internal travel through insecure zones. This motivates the contiguous search problem in which agents cannot be removed from the network, and clear links must form a connected sub-network at any time, providing safety of movements. This new problem is NP-complete in general. We study it for tree networks, and we consider its more general version, the weighted case, which arises naturally when considering networks whose nodes and links are of different nature and thus require a different number of agents to be explored. We give a linear-time algorithm that computes, for any tree @math , the minimum number of agents to capture the intruder, and the corresponding search strategy. Beside its optimality in time, our algorithm is naturally distributed: if @math is a processor-network, then the minimal search strategy for @math can be computed by @math in a decentralized manner, using a linear number of messages. The paper studies broadcasting in radio networks whose stations are represented by points in the Euclidean plane. In any given time step, a station can either receive or transmit. A message transmitted from station (v) is delivered to every station (u) at distance at most (1) from (v), but (u) successfully hears the message if and only if (v) is the only station at distance at most (1) from (u) that transmitted in this time step. A designated source station has a message that should be disseminated throughout the network. All stations other than the source are initially idle and wake up upon the first time they hear the source message. It is shown in [11] that the time complexity of broadcasting depends on two parameters of the network, namely, its diameter (in hops) (D) and a lower bound (d) on the Euclidean distance between any two stations. The inverse of (d) is called the granularity of the network, denoted by (g). Specifically, the authors of [11] present a broadcasting algorithm that works in time (O (D g)) and prove that every broadcasting algorithm requires Ω (D √g) time. In this paper, we distinguish between the arbitrary deployment setting, originally studied in [11], in which stations can be placed everywhere in the plane, and the new grid deployment setting, in which stations are only allowed to be placed on a (d)-spaced grid. Does the latter (more restricted) setting provides any speedup in broadcasting time complexity? Although the (O (D g)) broadcasting algorithm of [11] works under the (original) arbitrary deployment setting, it turns out that the Ω (D √g) lower bound remains valid under the grid deployment setting. Still, the above question is left unanswered. The current paper answers this question affirmatively by presenting a provable separation between the two deployment settings. We establish a tight lower bound on the time complexity of broadcasting under the arbitrary deployment setting proving that broadcasting cannot be completed in less than Ω ( D √g) time. For the grid deployment setting, we develop a broadcasting algorithm that runs in time O ( D g5 6 log g), thus breaking the linear dependency on (g). In a seminal paper, Bar- (1992) considered broadcasting in radio networks whose nodes know only their own label and labels of their neighbors. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks, by constructing a class of graphs of diameter 3, with the property that every broadcasting algorithm requires linear time on one of these graphs. Due to a subtle error in the argument, this result is incorrect. We construct an algorithm that broadcasts in logarithmic time on all graphs from the work of Bar- Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter o(log log n). On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time spl Omega (4 spl radic n) on one of these graphs. In view of the randomized algorithm, running in expected time O(D log n + log sup 2 n) on all n-node graphs of diameter D, our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting.