Use of information, memory and randomization in asynchronous gathering
Pages 193 - 205
Abstract
We investigate initial information, unbounded memory and randomization in gathering mobile agents on a grid. We construct a state machine, such that it is possible to gather, with probability 1, all configurations of its copies. This machine has initial input, unbounded memory, and is randomized. We show that no machine having any two of these capabilities but not the third, can be used to gather, with high probability, all configurations. We construct deterministic Turing Machines that are used to gather all connected configurations, and we construct deterministic finite automata that are used to gather all contractible connected configurations. We construct a state machine, whose copies can be gathered with probability 1.This machine has initial input, unbounded memory, and is randomized.We show that no two of these capabilities allow gathering.We show a deterministic Turing Machine to gather all connected configurations.We show a deterministic automaton to gather all contractible connected configurations.
References
[1]
C. Agathangelou, C. Georgiou, M. Mavronicolas, A distributed algorithm for gathering many fat mobile robots in the plane, in: Proc. 32nd Annual ACM Symposium on Principles of Distributed Computing, PODC 2013, pp. 250259.
[2]
N. Agmon, D. Peleg, Fault-tolerant gathering algorithms for autonomous mobile robots, SIAM J. Comput., 36 (2006) 56-82.
[3]
S. Alpern, The rendezvous search problem, SIAM J. Control Optim., 33 (1995) 673-683.
[4]
S. Alpern, Rendezvous search on labelled networks, Nav. Res. Logist., 49 (2002) 256-274.
[5]
S. Alpern, S. Gal, The Theory of Search Games and Rendezvous, Kluwer Academic Publisher, 2002.
[6]
E. Anderson, R. Weber, The rendezvous problem on discrete locations, J. Appl. Probab., 28 (1990) 839-851.
[7]
E. Anderson, S. Fekete, Asymmetric rendezvous on the plane, in: Proc. 14th Annual ACM Symp. on Computational Geometry, 1998, pp. 365-373.
[8]
E. Anderson, S. Fekete, Two-dimensional rendezvous search, Oper. Res., 49 (2001) 107-118.
[9]
E. Bampas, J. Czyzowicz, L. Gasieniec, D. Ilcinkas, A. Labourel, Almost optimal asynchronous rendezvous in infinite multidimensional grids, in: Proc. 24th International Symposium on Distributed Computing, DISC 2010, pp. 297311.
[10]
V. Baston, S. Gal, Rendezvous on the line when the players' initial distance is given by an unknown probability distribution, SIAM J. Control Optim., 36 (1998) 1880-1889.
[11]
V. Baston, S. Gal, Rendezvous search when marks are left at the starting points, Nav. Res. Logist., 48 (2001) 722-731.
[12]
M. Cieliebak, P. Flocchini, G. Prencipe, N. Santoro, Distributed computing by mobile robots: gathering, SIAM J. Comput., 41 (2012) 829-879.
[13]
R. Cohen, D. Peleg, Convergence properties of the gravitational algorithm in asynchronous robot systems, SIAM J. Comput., 34 (2005) 1516-1528.
[14]
R. Cohen, D. Peleg, Convergence of autonomous mobile robots with inaccurate sensors and movements, SIAM J. Comput., 38 (2008) 276-302.
[15]
J. Czyzowicz, A. Kosowski, A. Pelc, How to meet when you forget: log-space rendezvous in arbitrary graphs, Distrib. Comput., 25 (2012) 165-178.
[16]
J. Czyzowicz, A. Labourel, A. Pelc, How to meet asynchronously (almost) everywhere, ACM Trans. Algorithms, 8 (2012).
[17]
G. De Marco, L. Gargano, E. Kranakis, D. Krizanc, A. Pelc, U. Vaccaro, Asynchronous deterministic rendezvous in graphs, Theor. Comput. Sci., 355 (2006) 315-326.
[18]
A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc, Deterministic rendezvous in graphs, Algorithmica, 46 (2006) 69-96.
[19]
Y. Dieudonn, A. Pelc, Anonymous meeting in networks, Algorithmica, 74 (2016) 908-946.
[20]
Y. Dieudonn, A. Pelc, D. Peleg, Gathering despite mischief, ACM Trans. Algorithms, 11 (2014).
[21]
Y. Emek, T. Langner, D. Stolz, J. Uitto, R. Wattenhofer, How many ants does it take to find the food?, Theor. Comput. Sci., 608 (2015) 255-267.
[22]
P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, Gathering of asynchronous oblivious robots with limited visibility, Theor. Comput. Sci., 337 (2005) 147-168.
[23]
P. Fraigniaud, A. Pelc, Delays induce an exponential memory gap for rendezvous in trees, ACM Trans. Algorithms, 9 (2013).
[24]
S. Gal, Rendezvous search on the line, Oper. Res., 47 (1999) 974-976.
[25]
N. Gordon, I.A. Wagner, A.M. Bruckstein, Gathering multiple robotic agents with limited sensing capabilities, in: Proc. ANTS Workshop, 2004, pp. 142-153.
[26]
S. Guilbault, A. Pelc, Asynchronous rendezvous of anonymous agents in arbitrary graphs, in: LNCS, vol. 7109, 2011, pp. 162-173.
[27]
A. Israeli, M. Jalfon, Token management schemes and random walks yield self stabilizing mutual exclusion, in: Proc. 9th Annual ACM Symposium on Principles of Distributed Computing, PODC 1990, pp. 119131.
[28]
B. Keller, T. Langner, J. Uitto, R. Wattenhofer, Overcoming obstacles with ants, in: Proc. 19th International Conference on Principles of Distributed Systems, OPODIS 2015, pp. 117.
[29]
E. Kranakis, D. Krizanc, P. Morin, Randomized rendez-vous with limited memory, in: LNCS, vol. 4957, Springer, 2008, pp. 605-616.
[30]
E. Kranakis, D. Krizanc, N. Santoro, C. Sawchuk, Mobile agent rendezvous in a ring, in: Proc. 23rd Int. Conference on Distributed Computing Systems, IEEE, 2003, pp. 592-599.
[31]
W. Lim, S. Alpern, Minimax rendezvous on the line, SIAM J. Control Optim., 34 (1996) 1650-1665.
[32]
A. Pelc, Deterministic rendezvous in networks: a comprehensive survey, Networks, 59 (2012) 331-347.
[33]
A. Ta-Shma, U. Zwick, Deterministic rendezvous, treasure hunts and strongly universal exploration sequences, in: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 599608.
[34]
L. Thomas, Finding your kids when they are lost, J. Oper. Res. Soc., 43 (1992) 637-639.
[35]
X. Yu, M. Yung, Agent rendezvous: a dynamic symmetry-breaking problem, in: LNCS, vol. 1099, Springer, 1996, pp. 610-621.
Recommendations
Broadcasting in undirected ad hoc radio networks
Special issue: PODC 02We consider distributed broadcasting in radio networks, modeled as undirected graphs, whose nodes have no information on the topology of the network, nor even on their immediate neighborhood. For randomized broadcasting, we give an algorithm working in ...
Byzantine gathering in polynomial time
AbstractGathering is a key task in distributed and mobile systems, which becomes significantly harder if some agents are subject to Byzantine faults, known as being the worst ones. We propose here to study the task of Byzantine gathering in an arbitrary ...
On bounded symport/antiport P systems
DNA'05: Proceedings of the 11th international conference on DNA ComputingWe introduce a restricted model of a one-membrane symport/antiport system, called bounded S/A system. We show the following:
1. A language $L \subseteq a_1^* ... a_k^*$ is accepted by a bounded S/A system if and only if it is accepted by a log n space-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier Inc.
Publisher
Academic Press, Inc.
United States
Publication History
Published: 01 June 2018
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in