You are now in the main content area

On broadcasting time in the model of travelling agents

Theorem 3.1.

Figure: The main results summarized in one theorem (3.1.)

Summary

Consider the following broadcasting process run on a connected graph G = (V,E). Suppose that k ≥ 2 agents start on vertices selected from V uniformly and independently at random. One of the agents has a message that she wants to communicate to the other agents. All agents perform independent random walks on G, with the message being passed when an agent that knows the message meets an agent that does not know the message. The broadcasting time ξ(G,k) is the time it takes to spread the message to all agents.

Our ultimate goal is to gain a better understanding of the broadcasting process run on real-world networks of roads of large cities that might shed some light on the behaviour of future autonomous and connected vehicles. Due to the complexity of road networks, such phenomena have to be studied using simulation in practical applications. In this paper, we study the process on the simplest scenario, i.e., the family of complete graphs, as in this case the problem is analytically tractable. We provide tight bounds for ξ(Kn,k) that hold asymptotically almost surely for the whole range of the parameter k. These theoretical results reveal interesting relationships and, at the same time, are also helpful to understand and explain the behaviour we observe in more realistic networks.

Keywords

Broadcasting, Talkative particles, Random walk

2021 Journal Impact Factor: 1.254

Publication date: March 11, 2021

Links

References

APA Huq, R., Kamiński, B., Mashatan, A., Prałat, P., & Szufel, P. (2021). On broadcasting time in the model of travelling agents. Discrete Applied Mathematics, 291, 246-263.
BibTeX @article{HUQ2021BrAG,
title = {On broadcasting time in the model of travelling agents},
author = {Huq, Reaz and Kami{\'n}ski, Bogumi{\l} and Mashatan, Atefeh and Pra{\l}at, Pawe{\l} and Szufel, Przemys{\l}aw},
journal = {Discrete Applied Mathematics},
year = {2021},
volume = {291},
pages = {246--263},
doi={10.1016/j.dam.2020.12.022}
}
DOI https://doi.org/10.1016/j.dam.2020.12.022
IEEE R. Huq, B. Kamiński, A. Mashatan, P. Prałat, and P. Szufel, "On broadcasting time in the model of travelling agents," Discrete Applied Mathematics, vol. 291, pp. 246-263, Mar. 2021.
ISSN 0166-218X

Funding

This research was funded, in part, through a generous contribution from NXM Labs Inc (external link, opens in new window) .