On broadcasting time in the model of travelling agents
Section snippets
Introduction and motivation
In this paper, we investigate the problem of broadcasting messages between agents that randomly move on a connected graph . The assumption is that agents start the process at random locations on the graph and then perform a random walk along its vertices. One agent, selected in advance, initially possesses some information. If two agents meet at some point during the process and only one of them possesses the information, it is passed along to the other agent. The broadcasting time
Related problems
The performance of a random walk in a network is a fundamental process that has found applications in many areas of computer science. Since this paper contains theoretical results, let us concentrate on rigorous, theoretical results of related processes. As this is still a very broad topic, we only scratch the surface and focus on multiple random walks performed simultaneously (which has many applications in distributed computing, such as sampling) and processes run on complete graphs. For more
Formulation of the problem and the main result
In this section, we formally define the process we aim to analyse (Section 3.1). We define it for any connected graph but in this paper we focus on complete graphs. As our results are asymptotic in nature, we need to introduce the asymptotic notation that is used throughout the entire paper (Section 3.2). Finally, we state the main result that combines all ranges for the number of agents involved (Section 3.3).
Proofs
This whole section is devoted to proving Theorem 3.1. We investigate the process running on , the complete graph on vertices. Depending on the number of agents involved (parameter ), the proof requires different approaches. We will deal with each subrange of independently. However, before we start, let us state Chernoff’s bound, a well-known concentration inequality that we will use often.
Acknowledgements
This research was funded, in part, through a generous contribution from NXM Labs Inc . NXM’s autonomous security technology enables devices, including connected vehicles, to communicate securely with each other and their surroundings without human intervention while leveraging data at the edge to provide business intelligence and insights. NXM ensures data privacy and integrity by using a novel blockchain-based architecture which enables rapid and regulatory-compliant data monetization.
References (24)
- et al.
Vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communication in a heterogeneous wireless network–performance evaluation
Transp. Res. C
(2016) - et al.
The shortest-path problem for graphs with random arc-lengths
Discrete Appl. Math.
(1985) Tail bounds for sums of geometric and exponential variables
Statist. Probab. Lett.
(2018)- et al.
On the push & pull protocol for rumour spreading
SIAM J. Discrete Math.
(2017) - et al.
Reversible Markov chains and random walks on graphs
(2002) - F. Bai, D.D. Stancil, H. Krishnan, Toward understanding characteristics of dedicated short range communications (DSRC)...
- et al.
Randomized gossip algorithms
IEEE Trans. Inform. Theory
(2006) - et al.
Multiple random walks in random regular graphs
SIAM J. Discrete Math.
(2009) - R. Daknama, K. Panagiotou, S. Reisser, Asymptotics for push on the complete graph, in: 2021 Proceedings of the 14th...
- A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, D. Terry, Epidemic...
Tight analysis of randomized rumor spreading in complete graphs
Connection times in large ad-hoc mobile networks
Bernoulli
Cited by (2)
Broadcasting on paths and cycles
2022, Discrete MathematicsBroadcasting on paths and cycles
2020, arXiv