Document Open Access Logo

Broadcasting with Mobile Agents in Dynamic Networks

Authors Shantanu Das , Nikos Giachoudis, Flaminia L. Luccio , Euripides Markou

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.24.pdf
  • Filesize: 0.48 MB
  • 16 pages

Document Identifiers

Author Details

Shantanu Das
  • Aix-Marseille Université, CNRS, Université de Toulon, LIS, Marseille, France
Nikos Giachoudis
  • DCSBI, University of Thessaly, Lamia, Greece
Flaminia L. Luccio
  • DAIS, Università Ca' Foscari Venezia, Italy
Euripides Markou
  • DCSBI, University of Thessaly, Lamia, Greece

Funding

Partially supported by DAIS - Ca’ Foscari University of Venice (IRIDE program). Most of this work was done when Shantanu Das and Euripides Markou visited Ca’ Foscari University.

Cite AsGet BibTex

Shantanu Das, Nikos Giachoudis, Flaminia L. Luccio, and Euripides Markou. Broadcasting with Mobile Agents in Dynamic Networks. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.OPODIS.2020.24

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.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
  • Theory of computation → Distributed algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Distributed Algorithm
  • Dynamic Networks
  • Mobile Agents
  • Broadcast
  • Constantly Connected
  • Global visibility

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. J. Anaya, J. Chalopin, J. Czyzowicz, A. Labourel, A. Pelc, and Y. Vaxès. Convergecast and broadcast by power-aware mobile agents. Algorithmica, 74(1):117-155, 2016. Google Scholar
  2. B. Awerbuch and S. Even. Efficient and reliable broadcast is achievable in an eventually connected network. In Proceedings of the 3th Symposium on Principles of Distributed Computing (PODC), pages 278-281, 1984. Google Scholar
  3. S. Balev, J. J. Laredo, I. Lamprou, Y. Pigné, and E. Sanlaville. Cops and robbers on dynamic graphs: Offline and online case. In Proc. Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, volume 12156 of LNCS, pages 203-219. Springer, 2020. Google Scholar
  4. A. Casteigts, P. Flocchini, B. Mans, and N. Santoro. Shortest, fastest, and foremost broadcast in dynamic networks. International Journal of Foundations of Computer Science, 25(4):499-522, 2015. Google Scholar
  5. A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387-408, 2012. Google Scholar
  6. M. Chrobak, L. Gasieniec, and W. Rytter. Fast broadcasting and gossiping in radio networks. J. Algorithms, 43(2):177-189, 2002. Google Scholar
  7. A. Clementi, A. Monti, F. Pasquale, and R. Silvestri. Information spreading in stationary markovian evolving graphs. IEEE Transactions on Parallel and Distributed Systems, 22(9):1425-1432, 2011. Google Scholar
  8. J. Czyzowicz, K. Diks, J. Moussi, and W. Rytter. Broadcast with energy-exchanging mobile agents distributed on a tree. In Structural Information and Communication Complexity - 25th International Colloquium (SIROCCO), pages 209-225, 2018. Google Scholar
  9. J. Czyzowicz, K. Diks, J. Moussi, and W. Rytter. Energy-optimal broadcast and exploration in a tree using mobile agents. Theoretical Computer Science, 795:362-374, 2019. Google Scholar
  10. J. Czyzowicz, L. Gasieniec, A. Kosowski, E. Kranakis, D. Krizanc, and N. Taleb. When patrolmen become corrupted: Monitoring a graph using faulty mobile robots. Algorithmica, 79(3):925-940, 2017. Google Scholar
  11. S. Das, R. Focardi, F. L. Luccio, E. Markou, and M. Squarcina. Gathering of robots in a ring with mobile faults. Theoretical Computer Science, 764:42-60, 2019. Google Scholar
  12. S. Das, N. Giachoudis, F. L. Luccio, and E. Markou. Gathering of robots in a grid with mobile faults. In 45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2019), volume 11376 of LNCS, pages 164-178. Springer, 2019. Google Scholar
  13. S. Das, G. A. Di Luna, and L. A. Gasieniec. Patrolling on dynamic ring networks. In Proc. 45th Int. Conf. on Current Trends in Theory and Practice of Computer Science (SOFSEM), volume 11376 of LNCS, pages 150-163. Springer, 2019. Google Scholar
  14. G.A. Di Luna, S. Dobrev, P. Flocchini, and N. Santoro. Live exploration of dynamic rings. In Proocedings of the 36th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 570-579, 2016. Google Scholar
  15. G.A. Di Luna, P. Flocchini, L. Pagli, G. Prencipe, N. Santoro, and G. Viglietta. Gathering in dynamic rings. In Proocedings of the 24th International Colloquium Structural Information and Communication Complexity (SIROCCO), pages 339-355, 2017. Google Scholar
  16. T. Erlebach, M. Hoffmann, and F. Kammer. On temporal graph exploration. In Proceedings of 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 444-455, 2015. Google Scholar
  17. A. Ferreira. Building a reference combinatorial model for manets. IEEE Network, 18(5):24-29, 2004. Google Scholar
  18. P. Flocchini, B. Mans, and N. Santoro. On the exploration of time-varying networks. Theoretical Computer Science, 469:53-68, January 2013. URL: https://doi.org/10.1016/j.tcs.2012.10.029.
  19. L. Gasieniec. Deterministic Broadcasting in Radio Networks, pages 233-235. Springer US, Boston, MA, 2008. URL: https://doi.org/10.1007/978-0-387-30162-4_105.
  20. L. Gasieniec and A. Pelc. Adaptive broadcasting with faulty nodes. Parallel Computing, 22(6):903-912, 1996. Google Scholar
  21. L. Gasieniec and A. Pelc. Broadcasting with linearly bounded transmission faults. Discrete Applied Mathematics, 83(1-3):121-133, 1998. Google Scholar
  22. T. Gotoh, Y. Sudo, F. Ooshita, H. Kakugawa, and T. Masuzawa. Group exploration of dynamic tori. In 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), pages 775-785, July 2018. Google Scholar
  23. F. Harary and G. Gupta. Dynamic graph models. Mathematical and Computer Modelling, 25(7):79-88, 1997. Google Scholar
  24. D. Ilcinkas, R. Klasing, and A.M. Wade. Exploration of constantly connected dynamic graphs based on cactuses. In Proceedings 21st International Colloquium Structural Information and Communication Complexity (SIROCCO), pages 250-262, 2014. Google Scholar
  25. D. Ilcinkas and A.M. Wade. On the power of waiting when exploring public transportation systems. In Proceedings of the 15th International Conference on Principles of Distributed Systems (OPODIS), pages 451-464, 2011. Google Scholar
  26. D. Ilcinkas and A.M. Wade. Exploration of the t-interval-connected dynamic graphs: the case of the ring. Theory of Computing Systems, 62(5):1144-1160, 2018. Google Scholar
  27. F. Kuhn, N. Lynch, and R. Oshman. Distributed computation in dynamic networks. In Proceedings of the 42nd Symposium on Theory of Computing (STOC), pages 513-522, 2010. Google Scholar
  28. F. Kuhn and R. Oshman. Dynamic networks: Models and algorithms. SIGACT News, 42(1):82-96, 2011. Google Scholar
  29. G. A. Di Luna. Mobile agents on dynamic graphs. In Distributed Computing by Mobile Entities, Current Research in Moving and Computing, pages 549-584. Springer, 2019. Google Scholar
  30. O. Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12(4):239-280, 2016. Google Scholar
  31. O. Michail and P.G. Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634:1-23, 2016. URL: https://doi.org/10.1007/978-3-662-44465-8_47.
  32. R. O'Dell and R. Wattenhofer. Information dissemination in highly dynamic graphs. In Proceedings of the Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pages 104-110, 2005. Google Scholar
  33. D. Peleg and A. A. Schäffer. Time bounds on fault-tolerant broadcasting. Networks, 19(7):803-822, 1989. URL: https://doi.org/10.1002/net.3230190706.
  34. Y. Yamauchi, T. Izumi, and S. Kamei. Mobile agent rendezvous on a probabilistic edge evolving ring. In 2012 Third International Conference on Networking and Computing, pages 103-112, December 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact