Use of information, memory and randomization in asynchronous gathering

DOI10.1016/J.JCSS.2017.10.005MaRDI QIDQ1745729zbMATH OpenOpenAlexFDO

Authors Andrzej Pelc

Publication date 18 April 2018

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.05869

zbMATH Keywords

gridmemorygatheringmobile agentdeterministicrandomizedstate machineinput

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14)

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.

Recommendations

• Randomized gathering of asynchronous mobile robots
• Gathering Asynchronous Oblivious Mobile Robots in a Ring
• Gathering asynchronous oblivious mobile robots in a ring
• Distributed computing by mobile robots: gathering
• Linear time and space gathering of anonymous mobile agents in asynchronous trees

Cites work

• scientific article; zbMATH DE number 2102782 (Why is no real title available?)
• scientific article; zbMATH DE number 6784996 (Why is no real title available?)
• A distributed algorithm for gathering many fat mobile robots in the plane
• Almost optimal asynchronous rendezvous in infinite multidimensional grids
• Anonymous meeting in networks
• Asynchronous deterministic rendezvous in graphs
• Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems
• Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements
• Delays induce an exponential memory gap for rendezvous in trees
• Deterministic rendezvous in graphs
• Deterministic rendezvous, treasure hunts and strongly universal exploration sequences
• Distributed computing by mobile robots: gathering
• Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots
• Finding Your Kids When They Are Lost
• Gathering despite mischief
• Gathering of asynchronous robots with limited visibility
• How many ants does it take to find the food?
• How to meet asynchronously (almost) everywhere
• How to meet when you forget: log-space rendezvous in arbitrary graphs
• LATIN 2004: Theoretical Informatics
• Minimax Rendezvous on the Line
• Randomized Rendez-Vous with Limited Memory
• Rendezvous Search on the Line
• Rendezvous on the Line when the Players' Initial Distance is Given by an Unknown Probability Distribution
• Rendezvous search on labeled networks
• Rendezvous search when marks are left at the starting points
• The Rendezvous Search Problem
• The rendezvous problem on discrete locations
• Two Dimensional Rendezvous Search

Cited in

(1)

• Retrieval of scattered information by EREW, CREW and CRCW PRAMs

This page was built for publication: Use of information, memory and randomization in asynchronous gathering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1745729)