We study the standard communication problem of broadcast for mobile agents moving in a network.The agents move autonomously in the network and can communicate with other agents only whenthey meet at a node. In this model, broadcast is a communication primitive for information transferfrom one agent, the source, to all other agents. Previous studies of this problem were restrictedto static networks while, in this paper, we consider the problem in dynamic networks modelledas an evolving graph. The dynamicity of the graph is unknown to the agents; in each round anadversary selects which edges of the graph are available, and an agent can choose to traverse one ofthe available edges adjacent to its current location. The only restriction on the adversary is thatthe subgraph of available edges in each round must span all nodes; in other words the evolvinggraph is constantly connected. The agents have global visibility allowing them to see the locationof other agents in the graph and move accordingly. Depending on the topology of the underlyinggraph, we determine how many agents are necessary and sufficient to solve the broadcast problem indynamic networks. While two agents plus the source are sufficient for ring networks, much largerteams of agents are necessary for denser graphs such as grid graphs and hypercubes, and finallyfor complete graphs ofnnodes at leastn−2agents plus the source are necessary and sufficient.We show lower bounds on the number of agents and provide some algorithms for solving broadcastusing the minimum number of agents, for various topologies.

We study the standard communication problem of broadcast for mobile agents moving in a network. The agents move autonomously in the network and can communicate with other agents only when they meet at a node. In this model, broadcast is a communication primitive for information transfer from one agent, the source, to all other agents. Previous studies of this problem were restricted to static networks while, in this paper, we consider the problem in dynamic networks modelled as an evolving graph. The dynamicity of the graph is unknown to the agents; in each round an adversary selects which edges of the graph are available, and an agent can choose to traverse one of the available edges adjacent to its current location. The only restriction on the adversary is that the subgraph of available edges in each round must span all nodes; in other words the evolving graph is constantly connected. The agents have global visibility allowing them to see the location of other agents in the graph and move accordingly. Depending on the topology of the underlying graph, we determine how many agents are necessary and sufficient to solve the broadcast problem in dynamic networks. While two agents plus the source are sufficient for ring networks, much larger teams of agents are necessary for denser graphs such as grid graphs and hypercubes, and finally for complete graphs of n nodes at least n ? 2 agents plus the source are necessary and sufficient. We show lower bounds on the number of agents and provide some algorithms for solving broadcast using the minimum number of agents, for various topologies.

Broadcasting with Mobile Agents in Dynamic Networks

Flaminia L. Luccio;
2021-01-01

Abstract

We study the standard communication problem of broadcast for mobile agents moving in a network. The agents move autonomously in the network and can communicate with other agents only when they meet at a node. In this model, broadcast is a communication primitive for information transfer from one agent, the source, to all other agents. Previous studies of this problem were restricted to static networks while, in this paper, we consider the problem in dynamic networks modelled as an evolving graph. The dynamicity of the graph is unknown to the agents; in each round an adversary selects which edges of the graph are available, and an agent can choose to traverse one of the available edges adjacent to its current location. The only restriction on the adversary is that the subgraph of available edges in each round must span all nodes; in other words the evolving graph is constantly connected. The agents have global visibility allowing them to see the location of other agents in the graph and move accordingly. Depending on the topology of the underlying graph, we determine how many agents are necessary and sufficient to solve the broadcast problem in dynamic networks. While two agents plus the source are sufficient for ring networks, much larger teams of agents are necessary for denser graphs such as grid graphs and hypercubes, and finally for complete graphs of n nodes at least n ? 2 agents plus the source are necessary and sufficient. We show lower bounds on the number of agents and provide some algorithms for solving broadcast using the minimum number of agents, for various topologies.
2021
24th International Conference on Principles of Distributed Systems (OPODIS 2020)
File in questo prodotto:
File Dimensione Formato  
LIPIcs-OPODIS-2020-24.pdf

non disponibili

Tipologia: Versione dell'editore
Licenza: Accesso chiuso-personale
Dimensione 500.6 kB
Formato Adobe PDF
500.6 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/3735648
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact