Search

We consider the problem of scattering n robots in a two dimensional continuous space. As this problem is impossible to solve in a deterministic manner, all solutions must be probabilistic. We investigate the amount of randomness (that is, the number of random bits used by the robots) that is required to achieve scattering. We first prove that n log n random bits are necessary to scatter n robots in any setting. Also, we give a sufficient condition for a scattering algorithm to be random bit optimal. As it turns out that previous solutions for scattering satisfy our condition, they are hence proved random bit optimal for the scattering problem. Then, we investigate the time complexity of scattering when strong multiplicity detection is not available. We prove that such algorithms cannot converge in constant time in the general case and in o(log log n) rounds for random bits optimal scattering algorithms. However, we present a family of scattering algorithms that converge as fast as needed without using multiplicity detection. Also, we put forward a specific protocol of this family that is random bit optimal ( O( n log n) random bits are used) and time optimal ( O(log log n) rounds are used). This improves the time complexity of previous results in the same setting by a log n factor. Aside from characterizing the random bit complexity of mobile robot scattering, our study also closes the time complexity gap with and without strong multiplicity detection (that is, O(1) time complexity is only achievable when strong multiplicity detection is available, and it is possible to approach a constant value as desired otherwise). [ABSTRACT FROM AUTHOR]

We investigate self-stabilizing algorithms for anonymous and oblivious robots in uniform ring networks, that is, we focus on algorithms that can start from any initial configuration (including those with multiplicity points). First, we show that no probabilistic self-stabilizing gathering algorithm exists in the asynchronous (ASYNC) model or if only global-weak and local-strong multiplicity detection is available. This impossibility result implies that a common assumption about initial configurations (no two robots share a node initially) is a very strong one. On the positive side, we give a probabilistic self-stabilizing algorithm for the gathering and orientation problems in the semi-synchronous (SSYNC) model with global-strong multiplicity detection. With respect to impossibility results, those are the weakest system hypotheses. In addition, as an application of the previous algorithm, we provide a self-stabilizing algorithm for the set formation problem. Our results imply that any static set formation can be realized in a self-stabilizing manner in this model. [ABSTRACT FROM AUTHOR]

We present fault detectors for transient faults, (i.e., corruptions of the memory of the processors, but not of the code of the processors). We distinguish fault detectors for tasks (i.e., the problem to be solved) from failure detectors for implementations (i.e., the algorithm that solves the problem). The aim of our fault detectors is to detect a memory corruption as soon as possible. We study the amount of memory needed by the fault detectors for some specific tasks, and give bounds for each task. The amount of memory is related to the size and the number of views that a processor has to maintain to ensure a quick detection. This work may give the implementation designer hints concerning the techniques and resources that are required for implementing a task. [ABSTRACT FROM AUTHOR]

Most distributed solutions for swarms of oblivious mobile robots consider that individual robots are represented by points that can overlap, which is physically impossible. A recent trend is to consider “fat” robots, i.e. robots that are represented by unit discs and cannot overlap, but still assume that robots can be seen if there exists a point in the unit disc that has a line of sight with the target robot. Again, this does not match practical sensing devices implementations. We propose a new model for sensing devices that originates from embedded omnidirectional cameras, sonars, or lasers found on real robots. This model opens new algorithmic issues since the visibility relation becomes asymmetric. As a case study, we consider the gathering problem for four volumic robots and provide an algorithm to solve the problem in the fully asynchronous setting in our extended model. [ABSTRACT FROM AUTHOR]

Abstract A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced. [ABSTRACT FROM AUTHOR]

We study theoretical and practical aspects of five of the most well-known self-stabilizing dining philosophers algorithms. We theoretically prove that three of them are incorrect. For practical evaluation, we simulate these five algorithms as well as two classic non-self-stabilizing algorithms and evaluate their fault-tolerance, latency and throughput of critical section access. We present a new combined algorithm that achieves the best throughput of the two remaining correct self-stabilizing algorithms by determining the system load and switching between these basic algorithms. We prove the combined algorithm correct, simulate it and study its performance characteristics. [ABSTRACT FROM AUTHOR]

Abstract: We explore asynchronous unison in the presence of systemic transient and permanent Byzantine faults in shared memory. We observe that the problem is not solvable under a less than strongly fair scheduler or for system topologies with maximum node degree greater than two. We present then a self-stabilizing Byzantine-tolerant solution to asynchronous unison for chain and ring topologies under the central strongly fair daemon. Our algorithm has minimum possible containment radius and optimal stabilization time. [Copyright &y& Elsevier]

Abstract: The matching problem asks for a large set of disjoint edges in a graph. It is a problem that has received considerable attention in both the sequential and the self-stabilizing literature. Previous work has resulted in self-stabilizing algorithms for computing a maximal (-approximation) matching in a general graph, as well as computing a -approximation on more specific graph types. In this paper, we present the first self-stabilizing algorithm for finding a -approximation to the maximum matching problem in a general graph. We show that our new algorithm, when run under a distributed adversarial daemon, stabilizes after at most rounds. However, it might still use an exponential number of time steps. [Copyright &y& Elsevier]

Abstract: The maximal matching problem has received considerable attention in the self-stabilizing community. Previous work has given several self-stabilizing algorithms that solve the problem for both the adversarial and the fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon. In the following we present a single self-stabilizing algorithm for this problem that unites all of these algorithms in that it has the same time complexity as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. In addition, the algorithm improves the previous best time complexities for the distributed adversarial daemon from and to where is the number of processes, is the number of edges, and is the maximum degree in the graph. [Copyright &y& Elsevier]