There has been a wide interest in designing distributed algorithms for tiny robots. In particular, it has been shown that the robots can complete certain tasks even in the presence of faulty robots. In this paper, we focus on gathering of all non-faulty robots at a single point in presence of faulty robots. We propose a wait-free algorithm (i.e., no robot waits for other robot and algorithm instructs each robot to move in every step, unless it is already at the gathering location), that gathers all non-faulty robots in semi-synchronous model without any agreement in the coordinate system and with weak multiplicity detection (i.e., a robot can only detect that either there is one or more robot at a location) in the presence of at most @math faulty robots for @math . We show that the required capability for gathering robots is minimal in the above model, since relaxing it further makes gathering impossible to solve. Also, we introduce an intermediate scheduling model between the asynchronous ( i.e., no instantaneous movement or computation) and the semi-synchronous (i.e., both instantaneous movement and computation) as the asynchronous model with instantaneous computation. Then we propose another algorithm in model for gathering all non-faulty robots with weak multiplicity detection without any agreement on the coordinate system in the presence of at most @math faulty robots for @math .
Given a set of n autonomous mobile robots that can freely move on a two dimensional plane, they are required to gather in a position on the plane not fixed in advance (Gathering Problem). The main research question we address in this paper is: Under which conditions can this task be accomplished by the robots? The studied robots are quite simple: they are anonymous, totally asynchronous, they do not have any memory of past computations, they cannot explicitly communicate between each other. We show that this simple task cannot be in general accomplished by the considered system of robots. Consider a set of @math identical mobile computational entities in the plane, called robots, operating in Look-Compute-Move cycles, without any means of direct communication. The Gathering Problem is the primitive task of all entities gathering in finite time at a point not fixed in advance, without any external control. The problem has been extensively studied in the literature under a variety of strong assumptions (e.g., synchronicity of the cycles, instantaneous movements, complete memory of the past, common coordinate system, etc.). In this paper we consider the setting without those assumptions, that is, when the entities are oblivious (i.e., they do not remember results and observations from previous cycles), disoriented (i.e., have no common coordinate system), and fully asynchronous (i.e., no assumptions exist on timing of cycles and activities within a cycle). The existing algorithmic contributions for such robots are limited to solutions for @math or for restricted sets of initial configura... A leader election algorithm based on the performance and the operation rate of nodes and links as proposed. The performance of the existing leader election algorithms should be improved because a distributed system pauses until a node becomes a unique leader among all nodes in the system. The pre-election algorithm that elects a provisional leader while the leader is executing is also introduced. The common theoretical model adopted in recent studies on algorithms for systems of autonomous mobile robots assumes that the positional input of the robots is obtained by perfectly accurate visual sensors, that robot movements are accurate, and that internal calculations performed by the robots on (real) coordinates are perfectly accurate as well. The current paper concentrates on the effect of weakening this rather strong set of assumptions, and replacing it with the more realistic assumption that the robot sensors, movement and internal calculations may have slight inaccuracies. Specifically, the paper concentrates on the ability of robot systems with inaccurate sensors, movements and calculations to carry out the task of convergence. The paper presents several impossibility results, limiting the inaccuracy allowing convergence. The main positive result is an algorithm for convergence under bounded measurement, movement and calculation errors. This paper considers the convergence problem in autonomous mobile robot systems. A natural algorithm for the problem requires the robots to move towards their center of gravity. This paper proves the correctness of the gravitational algorithm in the fully asynchronous model. It also analyzes its convergence rate and establishes its convergence in the presence of crash faults. In a previous paper, Garcia-Molina specifies the leader election problem for synchronous and asynchronous distributed systems with crash and link failures and gives an elegant algorithm for each type of system. This paper points out a flaw in Garcia-Molina's specification of leader election in asynchronous systems and proposes a new specification. In this note we make a minor correction to a scheme for robots to broadcast their private information. All major results of the paper [I. Suzuki and M. Yamashita, SIAM J. Comput., 28 (1999), pp. 1347-1363] hold with this correction.  