Elsevier

Discrete Applied Mathematics

Volume 291, 11 March 2021, Pages 246-263
Discrete Applied Mathematics

On broadcasting time in the model of travelling agents

https://doi.org/10.1016/j.dam.2020.12.022Get rights and content

Abstract

Consider the following broadcasting process run on a connected graph G=(V,E). Suppose that k2 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.

Section snippets

Introduction and motivation

In this paper, we investigate the problem of broadcasting messages between agents that randomly move on a connected graph G=(V,E). The assumption is that k2 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 Kn, the complete graph on n vertices. Depending on the number of agents involved (parameter k=k(n)), the proof requires different approaches. We will deal with each subrange of k 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)

  • DoerrB. et al.

    Tight analysis of randomized rumor spreading in complete graphs

  • DöringH. et al.

    Connection times in large ad-hoc mobile networks

    Bernoulli

    (2016)
  • Cited by (2)

    • Broadcasting on paths and cycles

      2022, Discrete Mathematics
    View full text