Search

We consider mobile robotic entities that have to cooperate to solve assigned tasks. In the literature, two models have been used to model their visibility sensors: the full visibility model, where all robots can see all other robots, and the limited visibility model, where there exists a limit λ > 0 such that all robots closer than λ are seen and all robots further than λ are not seen. We introduce the uncertain visibility model, which generalizes both models by considering that a subset of the robots further than λ cannot be seen. An empty subset corresponds to the full visibility model, and a subset containing every such robot corresponds to the limited visibility model. Then, we explore the impact of this new visibility model on the feasibility of benchmarking tasks in mobile robots computing: gathering, uniform circle formation, luminous rendezvous, and leader election. For each task, we determine the weakest visibility adversary that prevents task solvability, and the strongest adversary that allows task solvability. Our work sheds new light on the impact of visibility sensors in the context of mobile robot computing, and paves the way for more realistic algorithms that can cope with uncertain visibility sensors. [ABSTRACT FROM AUTHOR]

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]

Self-stabilization is a strong property, which guarantees that a distributed system always resumes a correct behavior starting from an arbitrary initial state. Since it is a strong property, some problems cannot have self-stabilizing solutions. Weaker guarantees hence have been later introduced to cope with impossibility results, e.g., probabilistic self-stabilization only guarantees probabilistic convergence to a correct behavior, and weak stabilization only guarantees the possibility of convergence. In this paper, we investigate the relative power of self, probabilistic, and weak stabilization, with respect to the set of problems that can be solved. Weak stabilization is by definition stronger than self-stabilization and probabilistic self-stabilization in that precise sense. We first show that weak stabilization allows to solve problems having no self-stabilizing solution. We then show that any finite state deterministic weak stabilizing algorithm to solve a problem under the strongly fair scheduler is always a probabilistic self-stabilizing algorithm to solve the same problem under the randomized scheduler. Unfortunately, this good property does not hold in general for infinite state algorithms. We however show that for some classes of infinite state algorithms, this property holds. These results hint at more practical use of weak stabilizing algorithms, as they are easier to design and prove their correctness than their self-stabilizing and probabilistic self-stabilizing counterparts. [ABSTRACT FROM AUTHOR]

We propose a snap-stabilizing synchronization technique, called the Neighborhood Synchronizer (NS) that synchronizes nodes with their neighbors in a tree network. The NS scheme has optimal memory requirement — only one bit per processor. NS is snap-stabilizing, meaning that it always behaves according to its specification. The proposed synchronizer being snap-stabilizing is optimal in terms of stabilization time. We show an application of the synchronizer by designing an efficient broadcast algorithm (BA) in tree networks. B4 is also snap-stabilizing and needs only 2h + 2ra - 1 rounds to broadcast m messages, where h is the height of the tree. [ABSTRACT FROM AUTHOR]

Hierarchical routing provides a less expensive algorithm compared to the traditional all-pairs routing algorithms. We present an algorithm in this paper which benefits from the lower memory requirement, faster routing table lookup, and less costly broadcast exemplified by hierarchical routing, and yet maintains routing capability of all pairs of connected nodes even in the presence of faults, such as link/node failures and repairs, and corruption of program variables. Additionally, this algorithm solves the problem of cluster partitioning where nodes that are supposed to be in the same subset of the network, become isolated due to link or node failures. Being self-stabilizing, starting from an arbitrary state (with possibly corrupted routing tables), the protocol is guaranteed to reach a configuration with routing tables containing valid entries in a finite time. The protocol automatically updates the shortest paths in the face of dynamically changing link weights. The proposed protocol also dynamically allocates/deallocates storage for the routing information as the network size changes. The algorithm works on an arbitrary topology and under a distributed daemon model. [ABSTRACT FROM AUTHOR]

This paper describes a parameterized protocol applicable to directed acyclic graph (DAG) topologies. The function parameter of the protocol is instantiated twice to design two specific protocols: (i) the topological sorting of the successor list at every node, and (ii) a shortest path routing table construction. Both protocols are self-stabilizing and thus they are resilient to transient failures and guarantee system recovery in a finite time linear in the network diameter. From the fact that a DAG topology can be imposed on a more general topology through graph labeling protocols, the solutions presented in this paper are expected to be quite useful for a large class of distributed systems, where an optimal routing along with the robustness and fault tolerance are key factors. [ABSTRACT FROM AUTHOR]