The Power of Tokens: Rendezvous and Symmetry Detection for Two Mobile Agents in a Ring | SpringerLink
Skip to main content
Springer Nature Link
Log in

The Power of Tokens: Rendezvous and Symmetry Detection for Two Mobile Agents in a Ring

  • Conference paper
SOFSEM 2008: Theory and Practice of Computer Science (SOFSEM 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4910))

  • 1329 Accesses

Abstract

Rendezvous with detection differs from the usual rendezvous problem in that two mobile agents not only accomplish rendezvous whenever this is possible, but can also detect the impossibility of rendezvous (e.g., due to symmetrical initial positions of the agents) in which case they are able to halt. We study the problem of rendezvous with and without detection of two anonymous mobile agents in a synchronous ring. The agents have constant memory and each of them possess one or more tokens which may be left at some nodes of the ring and noticed later. We derive sharp bounds for the case of at most two tokens per agent and also explore trade-offs between the number of tokens available to the agents and the time needed to accomplish rendezvous with detection.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alpern, S.: Rendezvous search: A personal perspective. Operations Research 50(5), 772–795 (2002)

    Article  MathSciNet  Google Scholar 

  2. Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. Kluwer Academic Publishers, Norwell, Massachusetts (2003)

    MATH  Google Scholar 

  3. Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Multiple agents rendezvous in a ring in spite of a black hole. In: Papatriantafilou, M., Hunel, P. (eds.) OPODIS 2003. LNCS, vol. 3144, pp. 34–46. Springer, Heidelberg (2004)

    Google Scholar 

  4. Knuth, D.: The Art of Computer Programming, Fundamental Algorithms, 3rd edn., vol. 1. Addison-Wesley, Reading (1997)

    Google Scholar 

  5. Kranakis, E., Krizanc, D.: An algorithmic theory of mobile agents. In: Roddick, J.F., Hornsby, K. (eds.)TGC 2006. LNCS, vol. 4661, Springer, Heidelberg (2007)

    Google Scholar 

  6. Kranakis, E., Krizanc, D., Markou, E.: Mobile agent rendezvous in a synchronous torus. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  7. Kranakis, E., Krizanc, D., Santoro, N., Sawchuk, C.: Mobile agent rendezvous search problem in the ring. In: ICDCS. International Conference on Distributed Computing Systems, pp. 592–599 (2003)

    Google Scholar 

  8. Sawchuk, C.: Mobile Agent Rendezvous in the Ring. PhD thesis, Carleton University, School of Computer Science, Ottawa, Canada (2004)

    Google Scholar 

  9. Weiss, G.: Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. Wiley, Chichester (2002)

    Google Scholar 

  10. Yu, X., Yung, M.: Agent rendezvous: A dynamic symmetry-breaking problem. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 610–621. Springer, Heidelberg (1996)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Département d’informatique, Université du Québec en Outaouais, Gatineau, Québec J8X 3X7, Canada. Research supported in part by NSERC,  

    Jurek Czyzowicz

  2. School of Information Technology and Engineering, University of Ottawa, Ottawa, Canada, on leave from Slovak Academy of Sciences, Bratislava, Slovakia., Research supported in part by NSERC,  

    Stefan Dobrev

  3. School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6, Canada. Research supported in part by NSERC and MITACS,  

    Evangelos Kranakis

  4. Department of Mathematics, Wesleyan University, Middletown, Connecticut 06459, USA

    Danny Krizanc

Authors
  1. Jurek Czyzowicz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stefan Dobrev
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Evangelos Kranakis
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Danny Krizanc
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Viliam Geffert Juhani Karhumäki Alberto Bertoni Bart Preneel Pavol Návrat Mária Bieliková

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Czyzowicz, J., Dobrev, S., Kranakis, E., Krizanc, D. (2008). The Power of Tokens: Rendezvous and Symmetry Detection for Two Mobile Agents in a Ring. In: Geffert, V., Karhumäki, J., Bertoni, A., Preneel, B., Návrat, P., Bieliková, M. (eds) SOFSEM 2008: Theory and Practice of Computer Science. SOFSEM 2008. Lecture Notes in Computer Science, vol 4910. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77566-9_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-77566-9_20

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-77565-2

  • Online ISBN: 978-3-540-77566-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation