Brief Announcement: Broadcast via Mobile Agents in a Dynamic Network: Interplay of Graph Properties & Agents

In this paper, we study the specific problem of Broadcast in the context of mobile agents on a dynamic graph. This can be used to model situations in which actual robots are trying to move through constrained spaces (e.g., a building with rooms and corridors connecting those rooms). It can also be used to model situations on networks where each agent is a virtual agent that moves from computer to computer in order to spread some information or perform some task on a subset of computers. Considering mobile agents on dynamic graphs allows for broader applications in modeling the real world (e.g., earthquakes/fires changing the connectivity between rooms in a building) or a virtual one (e.g., two computers in a network become connected/disconnected because a cable is added/cut between them).

Within this paradigm, many problems have been studied, modeling an array of real world issues: gathering [3], scattering [2], pattern formation [6], dispersion [1], and convergence [4]. Here, we study the problem of Broadcast as introduced in Das, Giachoudis, Luccio, and Markou [5]. In it, there is initially one agent with a message that is to be transmitted to a number of other agents located on the nodes of the graph.

The problem of Broadcast, as studied in this paper, acts as an interesting bridge between agent-specific problems and traditional distributed computing. In traditional distributed computing, Broadcast requires all nodes to participate in the broadcast of a message originating at one node. However, here, the number of agents is independent of the number of nodes and furthermore the agents can move around on the nodes. By studying such “bridge” problems, we may develop a deeper understanding of the links between the mobile agents on a graph model and standard distributed computing.

In the paper that introduced Broadcast in this context, the focus was on the question of the minimum number of agents that allow the problem to be solvable. A number of graph classes of varying density were presented with lower and upper bounds on the necessary number of agents. Based on this, [5] observes the number of agents “apparently depends on the density of the underlying graph $G$ or, the number of redundant edges in $G$”.

However, this is not the case! Here we give infinite classes of graphs in which edge density and number of agents are unrelated. We further investigate edge connectivity, vertex connectivity, and other graph properties and analyze their potential relationships with Broadcast.

In this paper, we focus on a fine-grained analysis of the edge density of a graph with $n$ nodes and its relationship to the number of agents needed to solve Broadcast on that graph. The work of Das, Giachoudis, Luccio, and Markou [5] used edge density to divide the classes of graphs into sparse and dense graphs and showed that there exist sparse graphs (rings) for which Broadcast can be solved using $o(n)$ agents and more dense graphs (grids) for which Broadcast requires at least $\mathrm{\Omega }(n)$ agents. In particular, they show that for rings, with edge density $1$, $k=2$ ignorant agents suffice to solve Broadcast and for $2\times L$ grids, including a $2\times 3$ grid with edge density $1.1\overline{6}$, $k\ge L=\mathrm{\Omega }(n)$ ignorant agents are required to solve Broadcast.

One might naturally assume that for graphs with edge density greater than $1.1\overline{6}$, $k=\mathrm{\Omega }(n)$ agents are required to solve Broadcast. However, this is not the case. We show that there exists a class of graphs, commonly known as generalized theta graphs, that may have edge density larger than $1.1\overline{6}$ that in fact require only $k=o(n)$ ignorant agents to solve Broadcast. This surprising result shows that edge density, by itself, may not be the dividing line between graphs that require $k=o(n)$ and $k=\mathrm{\Omega }(n)$ ignorant agents. An example of such a construction is as follows. Consider a generalized theta graph with $\mathrm{\ell }$ paths between two nodes, such that each path is of length $d$. The number of nodes $n$ is $\mathrm{\ell }d+2$ and the edge density is $1+(\mathrm{\ell }-2)/(\mathrm{\ell }d+2)$, which can be rewritten as $1+(n-2-2d)/(nd)$. The number of ignorant agents needed to solve Broadcast is $\mathrm{\ell }$. When $d=\omega (1)$, we see that $\mathrm{\ell }=o(n)$. Let $n=100$ and $d={\log }^{\ast }n=4$. Then the given graph requires $o(n)$ ignorant agents and has edge density $1.225>1.1\overline{6}$.

A complementary question one might then ask is, whether in the range of edge density $\rho \in (1,1.1\overline{6})$, do graphs require very few agents, i.e., $k\ll n$? We answer this question in the negative by constructing, for any arbitrary $f(n)\to \mathrm{\infty }$, a family of graphs with edge density tending to $1$ from above (and therefore in particular ) requiring $\mathrm{\Omega }(n/f(n))$ agents. For example, taking $f(n)=\log n$ gives a graph with edge density tending to $1$ but agents tending to $\mathrm{\infty }$.

One might then wonder if there is any relationship between the exact edge density of a graph and the exact number of ignorant agents needed to solve for that edge density. From [5], we see that for trees, that have edge density , $k=1$ suffices. For rings, that have edge density exactly $1$, $k=2$ suffices. For a complete graph, that has edge density $(n-1)/2$, $k\ge n-2$ ignorant agents are needed. The question then becomes: are there specific values $\rho$ and $k$ such that any graph with edge density requires ignorant agents for some constant $k$? We answer this in the negative. For any $k>0$ and any $\rho >1$, we construct an infinite family of graphs with edge density requiring exactly $k$ ignorant agents to solve Broadcast. In other words, there is no threshold $\rho$ and number of ignorant agents $k$ for which the statement “any graph whose edge density is below $\rho$ requires ignorant agents” is correct.

A natural next line of inquiry is to look towards other graph properties and ask about their relationship with the number of ignorant agents needed to solve Broadcast. We begin with edge connectivity, that is the defining constraint on the adversary. We show that it is possible for a graph to have low (constant) edge connectivity but require high (linear) number of agents to achieve Broadcast. (Contrast this, for example, with the ring, which has edge connectivity $2$ and also requires $2$ agents.) In fact, for arbitrary $\lambda$, we construct a family of graphs on $n$ vertices with edge connectivity $(n-1)/\lambda$ but requiring exactly $n-2\lambda +1$ ignorant agents for Broadcast.

As edge connectivity is thus irrelevant, we next investigate vertex connectivity. In this context we develop an adversary strategy for any graph with vertex-connectivity at least 3. In particular, for all $\beta \ge 3$, all graphs with vertex connectivity $\beta$ and minimum degree $\delta$ require at least $k\ge \delta -1$ ignorant agents to solve Broadcast. (Note that for specific classes of graphs we have improved on this bound using earlier arguments; however, this is a more broadly-applicable lower bound.)

We also develop an adversary strategy for any graph which has a specific type of bond with $m$ edges, showing Broadcast is unsolvable for $k\le m-2$ ignorant agents.