Use of information, memory and randomization in asynchronous gathering
作者:
Highlights:
• 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.
摘要
•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.
论文关键词:Gathering,Grid,State machine,Deterministic,Randomized,Memory,Input,Mobile agent
论文评审过程:Received 28 December 2016, Revised 4 October 2017, Accepted 27 October 2017, Available online 8 November 2017, Version of Record 14 March 2018.
论文官网地址:https://doi.org/10.1016/j.jcss.2017.10.005