Abstract
We consider the rendezvous problem for identical mobile agents (i.e., running the same deterministic algorithm) with tokens in a synchronous torus with a sense of direction and show that there is a striking computational difference between one and more tokens. More specifically, we show that 1) two agents with a constant number of unmovable tokens, or with one movable token, each cannot rendezvous if they have o(log n) memory, while they can perform rendezvous with detection as long as they have one unmovable token and O(log n) memory; in contrast, 2) when two agents have two movable tokens each then rendezvous (respectively, rendezvous with detection) is possible with constant memory in an arbitrary n × m (respectively, n × n) torus; and finally, 3) two agents with three movable tokens each and constant memory can perform rendezvous with detection in a n × m torus. This is the first publication in the literature that studies tradeoffs between the number of tokens, memory and knowledge the agents need in order to meet in such a network.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alpern, S.: The Rendezvous Search Problem. SIAM Journal of Control and Optimization 33, 673–683 (1995); Earlier version: LSE CDAM Research Report, 53 (1993)
Alpern, S.: Rendezvous Search: A Personal Perspective. Operations Research 50(5), 772–795 (2002)
Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. Kluwer Academic Publishers, Norwell (2003)
Barriere, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Election and Rendezvous of Anonymous Mobile Agents in Anonymous Networks with Sense of Direction. In: Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 17–32 (2003)
Baston, V., Gal, S.: Rendezvous Search When Marks Are Left at the Starting Points. Naval Research Logistics 47(6), 722–731 (2001)
Dessmark, A., Fraigniaud, P., Pelc, A.: Deterministic Rendezvous in Graphs. In: 11th Annual European Symposium on Algorithms (ESA), pp. 184–195 (2003)
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)
Flocchini, P., Kranakis, E., Krizanc, D., Santoro, N., Sawchuk, C.: Multiple Mobile Agent Rendezvous in the Ring. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 599–608. Springer, Heidelberg (2004)
Gasieniec, L., Kranakis, E., Krizanc, D., Zhang, X.: Optimal Memory Rendezvous of Anonymous Mobile Agents in a Uni-directional Ring. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 282–292. Springer, Heidelberg (2006) (to appear)
Kranakis, E., Krizanc, D., Santoro, N., Sawchuk, C.: Mobile Agent Rendezvous Search Problem in the Ring. In: International Conference on Distributed Computing Systems (ICDCS), pp. 592–599 (2003)
Sawchuk, C.: Mobile Agent Rendezvous in the Ring, PhD thesis, Carleton University, School of Computer Science, Ottawa, Canada (2004)
Shannon, C.E.: Presentation of a Maze-Solving Machine. In: 8th Conf. of the Josiah Macy Jr. Found (Cybernetics), pp. 173–180 (1951)
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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kranakis, E., Krizanc, D., Markou, E. (2006). Mobile Agent Rendezvous in a Synchronous Torus. In: Correa, J.R., Hevia, A., Kiwi, M. (eds) LATIN 2006: Theoretical Informatics. LATIN 2006. Lecture Notes in Computer Science, vol 3887. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11682462_60
Download citation
DOI: https://doi.org/10.1007/11682462_60
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32755-4
Online ISBN: 978-3-540-32756-1
eBook Packages: Computer ScienceComputer Science (R0)