Consider the Ants Nearby Treasure Search (ANTS) problem introduced by Feinerman, Korman, Lotker, and Sereni (PODC 2012), where @math mobile agents, initially placed at the origin of an infinite grid, collaboratively search for an adversarially hidden treasure. In this paper, the model of is adapted such that the agents are controlled by a (randomized) finite state machine: they possess a constant-size memory and are able to communicate with each other through constant-size messages. Despite the restriction to constant-size memory, we show that their collaborative performance remains the same by presenting a distributed algorithm that matches a lower bound established by on the run-time of any ANTS algorithm.
Distributed computing by finite state machines has been studied in several different contexts including @cite_15 @cite_1 and the recent work of Emek and Wattenhofer @cite_3 from which we borrowed the agents communication model (see ). In that regard, the line of work closest to our paper is probably the one studying graph exploration by FSM controlled agents, see, e.g., @cite_8 .
@cite_15 @cite_1 @cite_3 @cite_8
2098579316 1501097462 2052474723 2039936247
We explore the computational power of networks of small resource-limited mobile agents. We define two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size. With a fairness condition on interactions, we define the concept of stable computation of a function or predicate, and give protocols that stably compute functions in a class including Boolean combinations of threshold-k, parity, majority, and simple arithmetic. We prove that all stably computable predicates are in NL. With uniform random sampling of pairs to interact, we define the model of conjugating automata and show that any counter machine with O(1) counters of capacity O(n) can be simulated with high probability by a protocol in a population of size n. We prove that all predicates computable with high probability in this model are in P ∩ RL. Several open problems and promising future directions are discussed. Population protocols are used as a theoretical model for a collection (or population) of tiny mobile agents that interact with one another to carry out a computation. The agents are identically programmed finite state machines. Input values are initially distributed to the agents, and pairs of agents can exchange state information with other agents when they are close together. The movement pattern of the agents is unpredictable, but subject to some fairness constraints, and computations must eventually converge to the correct output value in any schedule that results from that movement. This framework can be used to model mobile ad hoc networks of tiny devices or collections of molecules undergoing chemical reactions. This chapter surveys results that describe what can be computed in various versions of the population protocol model. A new model that depicts a network of randomized finite state machines operating in an asynchronous environment is introduced. This model, that can be viewed as a hybrid of the message passing model and cellular automata is suitable for applying the distributed computing lens to the study of networks of sub-microprocessor devices, e.g., biological cellular networks and man-made nano-networks. Although the computation and communication capabilities of each individual device in the new model are, by design, much weaker than those of an abstract computer, we show that some of the most important and extensively studied distributed computing problems can still be solved efficiently. A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K-state robot and any d ≥ 3, there exists a planar graph of maximum degree d with at most K + 1 nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs Ω(D log d) memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS up to depth D + 1 enables a robot to explore any graph of diameter D and maximum degree d using a memory of size O(D log d) bits. We thus prove that the worst case space complexity of graph exploration is Θ(D log d) bits.