Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHow to Spread a Rumor: Call Your Neighbors or Take a Walk?
161
0
0.0
(
0
)
Added by
Hayk Saribekyan
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the problem of randomized information dissemination in networks. We compare the now standard PUSH-PULL protocol, with agent-based alternatives where information is disseminated by a collection of agents performing independent random walks. In the VISIT-EXCHANGE protocol, both nodes and agents store information, and each time an agent visits a node, the two exchange all the information they have. In the MEET-EXCHANGE protocol, only the agents store information, and exchange their information with each agent they meet. We consider the broadcast time of a single piece of information in an $n$-node graph for the above three protocols, assuming a linear number of agents that start from the stationary distribution. We observe that there are graphs on which the agent-based protocols are significantly faster than PUSH-PULL, and graphs where the converse is true. We attribute the good performance of agent-based algorithms to their inherently fair bandwidth utilization, and conclude that, in certain settings, agent-based information dissemination, separately or in combination with PUSH-PULL, can significantly improve the broadcast time. The graphs considered above are highly non-regular. Our main technical result is that on any regular graph of at least logarithmic degree, PUSH-PULL and VISIT-EXCHANGE have the same asymptotic broadcast time. The proof uses a novel coupling argument which relates the random choices of vertices in PUSH-PULL with the random walks in VISIT-EXCHANGE. Further, we show that the broadcast time of MEET-EXCHANGE is asymptotically at least as large as the other twos on all regular graphs, and strictly larger on some regular graphs. As far as we know, this is the first systematic and thorough comparison of the running times of these very natural information dissemination protocols.
rate research
Read More
In this paper, we study PUSH-PULL style rumor spreading algorithms in the mobile telephone model, a variant of the classical telephone model in which each node can participate in at most one connection per round; i.e., you can no longer have multiple nodes pull information from the same source in a single round. Our model also includes two new parameterized generalizations: (1) the network topology can undergo a bounded rate of change (for a parameterized rate that spans from no changes to changes in every round); and (2) in each round, each node can advertise a bounded amount of information to all of its neighbors before connection decisions are made (for a parameterized number of bits that spans from no advertisement to large advertisements). We prove that in the mobile telephone model with no advertisements and no topology changes, PUSH-PULL style algorithms perform poorly with respect to a graphs vertex expansion and graph conductance as compared to the known tight results in the classical telephone model. We then prove, however, that if nodes are allowed to advertise a single bit in each round, a natural variation of PUSH-PULL terminates in time that matches (within logarithmic factors) this strategys performance in the classical telephone model---even in the presence of frequent topology changes. We also analyze how the performance of this algorithm degrades as the rate of change increases toward the maximum possible amount. We argue that our model matches well the properties of emerging peer-to-peer communication standards for mobile devices, and that our efficient PUSH-PULL variation that leverages small advertisements and adapts well to topology changes is a good choice for rumor spreading in this increasingly important setting.
We give an improved randomized CONGEST algorithm for distance-$2$ coloring that uses $Delta^2+1$ colors and runs in $O(log n)$ rounds, improving the recent $O(log Delta cdot log n)$-round algorithm in [Halldorsson, Kuhn, Maus; PODC 20]. We then improve the time complexity to $O(log Delta) + 2^{O(sqrt{loglog n})}$.
Motivated by storage applications, we study the following data structure problem: An encoder wishes to store a collection of jointly-distributed files $overline{X}:=(X_1,X_2,ldots, X_n) sim mu$ which are emph{correlated} ($H_mu(overline{X}) ll sum_i H_mu(X_i)$), using as little (expected) memory as possible, such that each individual file $X_i$ can be recovered quickly with few (ideally constant) memory accesses. In the case of independent random files, a dramatic result by Pat (FOCS08) and subsequently by Dodis, Pat and Thorup (STOC10) shows that it is possible to store $overline{X}$ using just a emph{constant} number of extra bits beyond the information-theoretic minimum space, while at the same time decoding each $X_i$ in constant time. However, in the (realistic) case where the files are correlated, much weaker results are known, requiring at least $Omega(n/polylg n)$ extra bits for constant decoding time, even for simple joint distributions $mu$. We focus on the natural case of compressingemph{Markov chains}, i.e., storing a length-$n$ random walk on any (possibly directed) graph $G$. Denoting by $kappa(G,n)$ the number of length-$n$ walks on $G$, we show that there is a succinct data structure storing a random walk using $lg_2 kappa(G,n) + O(lg n)$ bits of space, such that any vertex along the walk can be decoded in $O(1)$ time on a word-RAM. For the harder task of matching the emph{point-wise} optimal space of the walk, i.e., the empirical entropy $sum_{i=1}^{n-1} lg (deg(v_i))$, we present a data structure with $O(1)$ extra bits at the price of $O(lg n)$ decoding time, and show that any improvement on this would lead to an improved solution on the long-standing Dictionary problem. All of our data structures support the emph{online} version of the problem with constant update and query time.
We present the first numerical simulations that self-consistently follow the formation of dense molecular clouds in colliding flows. Our calculations include a time-dependent model for the H2 and CO chemistry that runs alongside a detailed treatment of the dominant heating and cooling processes in the ISM. We adopt initial conditions characteristic of the warm neutral medium and study two different flow velocities - a slow flow with v = 6.8 km/s and a fast flow with v = 13.6 km/s. The clouds formed by the collision of these flows form stars, with star formation beginning after 16 Myr in the case of the slower flow, but after only 4.4 Myr in the case of the faster flow. In both flows, the formation of CO-dominated regions occurs only around 2 Myr before the onset of star formation. Prior to this, the clouds produce very little emission in the J = 1 -> 0 transition line of CO, and would probably not be identified as molecular clouds in observational surveys. In contrast, our models show that H2-dominated regions can form much earlier, with the timing depending on the details of the flow. In the case of the slow flow, small pockets of gas become fully molecular around 10 Myr before star formation begins, while in the fast flow, the first H2-dominated regions occur around 3 Myr before the first prestellar cores form. Our results are consistent with models of molecular cloud formation in which the clouds are dominated by dark molecular gas for a considerable proportion of their assembly history.
We consider the effect of introducing a small number of non-aligning agents in a well-formed flock. To this end, we modify a minimal model of active Brownian particles with purely repulsive (excluded volume) forces to introduce an alignment interaction that will be experienced by all the particles except for a small minority of dissenters. We find that even a very small fraction of dissenters disrupts the flocking state. Strikingly, these motile dissenters are much more effective than an equal number of static obstacles in breaking up the flock. For the studied system sizes we obtain clear evidence of scale invariance at the flocking-disorder transition point and the system can be effectively described with a finite-size scaling formalism. We develop a continuum model for the system which reveals that dissenters act like annealed noise on aligners, with a noise strength that grows with the persistence of the dissenters dynamics.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
