Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Distributed exploration of dynamic rings

  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

In the graph exploration problem, a team of mobile computational entities, called agents, arbitrarily positioned at some nodes of a graph, must cooperate so that each node is eventually visited by at least one agent. In the literature, the main focus has been on graphs that are static; that is, the topology is either invariant in time or subject to localized changes. The few studies on exploration of dynamic graphs have been almost all limited to the centralized case (i.e., assuming complete a priori knowledge of the changes and the times of their occurrence). We investigate the decentralized exploration of dynamic graphs (i.e., when the agents are unaware of the location and timing of the changes) focusing, in this paper, on dynamic systems whose underlying graph is a ring. We first consider the fully-synchronous systems traditionally assumed in the literature; i.e., all agents are active at each time step. We then introduce the notion of semi-synchronous systems, where only a subset of agents might be active at each time step (the choice of the subset is made by an adversary); this model is common in the context of mobile agents in continuous spaces but has never been studied before for agents moving in graphs. Our main focus is on the impact that the level of synchrony as well as other factors such as anonymity, knowledge of the size of the ring, and chirality (i.e., common orientation) have on the solvability of the problem, focusing on the minimum number of agents necessary. We draw an extensive map of feasibility, and of complexity in terms of minimum number of agent movements. All our sufficiency proofs are constructive, and almost all our solution protocols are asymptotically optimal.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22

Similar content being viewed by others

References

  1. Albers, S., Henzinger, M.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164–1188 (2000)

    Article  MathSciNet  Google Scholar 

  2. Arantes, L., Greve, F., Sens, P., Simon, V.: Eventual leader election in evolving mobile networks. In: Proceedings of the 17th International Conference on Principles of Distributed Systems (OPODIS), pp. 23–37 (2013)

    Google Scholar 

  3. Augustine, J., Pandurangan, G., Robinson, P.: Fast byzantine agreement in dynamic networks. In: Proceedings of the 32th Symposium on Principles of Distributed Computing (PODC), pp. 74–83 (2013)

  4. Avin, C., Koucky, M., Lotker, Z.: How to explore a fast-changing world. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), pp. 121–132 (2008)

    Chapter  Google Scholar 

  5. Awerbuch, B., Even, S.: Efficient and reliable broadcast is achievable in an eventually connected network. In: Proceedings of the 3th Symposium on Principles of Distributed Computing (PODC), pp. 278–281 (1984)

  6. Balamohan, B., Dobrev, S., Flocchini, P., Santoro, N.: Exploring an unknown dangerous graph with a constant number of tokens. Theor. Comput. Sci. 610, 169–181 (2016)

    Article  MathSciNet  Google Scholar 

  7. Baumann, H., Crescenzi, P., Fraigniaud, P.: Parsimonious flooding in dynamic graphs. Distrib. Comput. 24(1), 31–44 (2011)

    Article  Google Scholar 

  8. Biely, M., Robinson, P., Schmid, U.: Agreement in directed dynamic networks. In: Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 73–84 (2012)

    Chapter  Google Scholar 

  9. Brejova, B., Dobrev, S., Kralovic, R., Vinar, T.: Efficient routing in carrier-based mobile networks. Theor. Comput. Sci. 509, 113–121 (2013)

    Article  MathSciNet  Google Scholar 

  10. Bui-Xuan, B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(2), 267–285 (2003)

    Article  MathSciNet  Google Scholar 

  11. Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Measuring temporal lags in delay-tolerant networks. IEEE Trans. Comput. 63(2), 397–410 (2014)

    Article  MathSciNet  Google Scholar 

  12. Casteigts, A., Flocchini, P., Mans, B., Santoro, N.: Shortest, fastest, and foremost broadcast in dynamic networks. Int. J. Found. Comput. Sci. 25(4), 499–522 (2015)

    Article  MathSciNet  Google Scholar 

  13. Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emerg. Distrib. Syst. 27(5), 387–408 (2012)

    Article  Google Scholar 

  14. Chalopin, J.: Election and rendezvous with incomparable labels. Theor. Comput. Sci. 399(1), 54–70 (2008)

    Article  MathSciNet  Google Scholar 

  15. Clementi, A., Monti, A., Pasquale, F., Silvestri, R.: Information spreading in stationary Markovian evolving graphs. IEEE Trans. Parallel Distrib. Syst. 22(9), 1425–1432 (2011)

    Article  Google Scholar 

  16. Cooper, C., Klasing, R., Radzi, T.: Searching for black-hole faults in a network using multiple agents. In: Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS), pp. 320–332 (2006)

    Google Scholar 

  17. Das, S., Flocchini, P., Kutten, S., Nayak, A., Santoro, N.: Map construction of unknown graphs by multiple agents. Theor. Comput. Sci. 385(1–3), 34–48 (2007)

    Article  MathSciNet  Google Scholar 

  18. Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32(3), 265–297 (1999)

    Article  MathSciNet  Google Scholar 

  19. Di Luna, G., Baldoni, R.: Brief announcement: investigating the cost of anonymity on dynamic networks. In: Proceedings of the 34th Symposium on Principles of Distributed Computing (PODC), pp. 339–341 (2015)

  20. Di Luna, G., Baldoni, R., Bonomi, S., Chatzigiannakis, I.: Conscious and unconscious counting on anonymous dynamic networks. In: Proceedings of the 15th International Conference on Distributed Computing and Networking (ICDCN), pp. 257–271 (2014)

  21. Di Luna, G., Dobrev, S., Flocchini, P., Santoro, N.: Live exploration of dynamic rings. In: Proceedings of the 36th IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 570–579 (2016)

  22. Di Luna, G., Flocchini, P., Pagli, L., Prencipe, G., Santoro, N., Viglietta, G.: Gathering in dynamic rings. In: Proceedings of the 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 339–355 (2017)

  23. Dieudonn, Y., Pelc, A.: Deterministic network exploration by anonymous silent agents with local traffic reports. ACM Trans. Algorithms 11(2), 10:1–10:29 (2014)

    MathSciNet  MATH  Google Scholar 

  24. Dobrev, S., Flocchini, P., Kralovic, R., Santoro, N.: Exploring a dangerous unknown graph using tokens. Theor. Comput. Sci. 472, 28–45 (2013)

    Article  Google Scholar 

  25. Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Searching for a black hole in arbitrary networks: optimal mobile agents protocolss. Distrib. Comput. 19(1), 1–19 (2006)

    Article  Google Scholar 

  26. Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. In: Proceedings of 42th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 444–455 (2015)

    Chapter  Google Scholar 

  27. Ferreira, A.: Building a reference combinatorial model for MANETs. IEEE Netw. 18(5), 24–29 (2004)

    Article  Google Scholar 

  28. Flocchini, P., Kellett, M., Mason, P., Santoro, N.: Map construction and exploration by mobile agents scattered in a dangerous network. In: Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1–10 (2009)

  29. Flocchini, P., Kellett, M., Mason, P., Santoro, N.: Searching for black holes in subways. Theory Comput. Syst. 50(1), 158–184 (2012)

    Article  MathSciNet  Google Scholar 

  30. Flocchini, P., Mans, B., Santoro, N.: On the exploration of time-varying networks. Theor. Comput. Sci. 469, 53–68 (2013)

    Article  MathSciNet  Google Scholar 

  31. Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Morgan & Claypool, San Rafael (2012)

    Book  Google Scholar 

  32. Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theor. Comput. Sci. 345(2–3), 331–344 (2005)

    Article  MathSciNet  Google Scholar 

  33. Godard, E., Mazauric, D.: Computing the dynamic diameter of non-deterministic dynamic networks is hard. In: Proceedings of the 10th Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGSENSORS), pp. 88–102 (2014)

    Google Scholar 

  34. Harary, F., Gupta, G.: Dynamic graph models. Math. Comput. Model. 25(7), 79–88 (1997)

    Article  MathSciNet  Google Scholar 

  35. Ilcinkas, D., Klasing, R., Wade, A.: Exploration of constantly connected dynamic graphs based on cactuses. In: Proceedings of the 21st International Colloquium Structural Information and Communication Complexity (SIROCCO), pp. 250–262 (2014)

    Chapter  Google Scholar 

  36. Ilcinkas, D., Wade, A.: On the power of waiting when exploring public transportation systems. In: Proceedings of the 15th International Conference on Principles of Distributed Systems (OPODIS), pp. 451–464 (2011)

    Google Scholar 

  37. Ilcinkas, D., Wade, A.: Exploration of the t-interval-connected dynamic graphs: the case of the ring. In: Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 13–23 (2013)

    Chapter  Google Scholar 

  38. Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42th Symposium on Theory of Computing (STOC), pp. 513–522 (2010)

  39. Kuhn, F., Moses, Y., Oshman, R.: Coordinated consensus in dynamic networks. In: Proceedings 30th Symposium on Principles of Distributed Computing (PODC), pp. 1–10 (2011)

  40. Liu, C., Wu, J.: Scalable routing in cyclic mobile networks. IEEE Trans. Parallel Distrib. Syst. 20(9), 1325–1338 (2009)

    Article  Google Scholar 

  41. Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. Theor. Comput. Sci. 634, 1–23 (2016)

    Article  MathSciNet  Google Scholar 

  42. O’Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Proceedings of the Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 104–110 (2005)

  43. Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33, 281–295 (1999)

    Article  MathSciNet  Google Scholar 

  44. Shannon, C.: Presentation of a maze-solving machine. In: Proceedings of the 8th Conference of the Josiah Macy Jr. Foundation (Cybernetics), pp. 173–180 (1951)

Download references

Acknowledgements

We would like to thank the anonymous reviewers for the comments and suggestions. Especially, for suggesting the improved bounds discussed in Sect. 3.1 and a correction of Theorem 5. This research has been supported in part by NSERC under the Discovery Grant program, by Dr. Flocchini’s University Research Chair, and by the VEGA 2/0165/16 Grant.

Author information

Authors and Affiliations

  1. School of Electrical Engineering and Computer Science, University of Ottawa, 800 King Edward Avenue, Ottawa, ON, Canada

    G. Di Luna & P. Flocchini

  2. Slovak Academy of Sciences, Dúbravská cesta 9, 811 04, Bratislava, Slovakia

    S. Dobrev

  3. School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, ON, Canada

    N. Santoro

Authors
  1. G. Di Luna
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. Dobrev
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. P. Flocchini
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. N. Santoro
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to G. Di Luna.

Additional information

Some of these results have been presented at the 37th International Conference on Distributed Computing Systems (ICDCS) [21].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Di Luna, G., Dobrev, S., Flocchini, P. et al. Distributed exploration of dynamic rings. Distrib. Comput. 33, 41–67 (2020). https://doi.org/10.1007/s00446-018-0339-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-018-0339-1

Keywords

Search

Navigation