We address the perpetual grid exploration (PGE) by a swarm of autonomous, asynchronous, myopic, and luminous robots. We first show that it is impossible for the robots to explore the grid regardless of their number and the number of colors they can take if their visibility range is one. We also show that PGE is impossible with three oblivious robots that have a visibility range of two hops. We then present three optimal algorithms solving the problem. The first algorithm uses four oblivious robots with a visibility range of two, but assumes they agree on a common chirality. For the two other algorithms, no common chirality is assumed. The former uses three robots that have a visibility range of two and a two-color light. The latter uses three oblivious robots under visibility range three.

Gathering is a key task in distributed and mobile systems, which becomes significantly harder if some agents are subject to Byzantine faults, known as being the worst ones. We propose here to study the task of Byzantine gathering in an arbitrary graph: despite the presence of Byzantine agents, the goal is to ensure that all the other (good) agents, executing the same algorithm, eventually meet at the same node and stop. Initially, each agent gets as input a different label and some global knowledge that is common to all agents. The agents move in synchronous rounds and communicate with each other only when located at the same node. There are f Byzantine agents. These agents act in an unpredictable way, e.g., they may convey arbitrary informations or forge any label. In the literature, the gathering algorithms working in such a context all have an exponential time complexity in the number n of nodes and the labels of the good agents. In this paper, we design a deterministic algorithm to solve Byzantine gathering in time polynomial in n and the logarithm $$\ell $$ of the smallest label of a good agent, provided the agents are a strong team i.e., a team where the number of good agents is at least some quadratic polynomial in f. Our algorithm requires global knowledge that can be coded in $$O(\log \log \log n)$$ bits: we prove this size is of optimal order of magnitude to obtain a polynomial time complexity in n and $$\ell $$ with strong teams.

We consider the gathering problem for asynchronous and oblivious robots that cannot communicate explicitly with each other but are endowed with visibility sensors that allow them to see the positions of the other robots. Most investigations on the gathering problem on the discrete universe are done on ring shaped networks due to the number of symmetric configurations. We extend in this paper the study of the gathering problem on torus shaped networks assuming robots endowed with local weak multiplicity detection. That is, robots cannot make the difference between nodes occupied by only one robot from those occupied by more than one robot unless it is their current node. Consequently, solutions based on creating a single multiplicity node as a landmark for the gathering cannot be used. We present in this paper a deterministic algorithm that solves the gathering problem starting from any rigid configuration on an asymmetric unoriented torus shaped network.

Abstract We consider swarms of asynchronous oblivious robots evolving into an anonymous grid-shaped network. In this context, we investigate optimal (w.r.t. the number of robots) deterministic solutions for the terminating exploration problem. We first show lower bounds in the semi-synchronous model. Precisely, we show that at least three robots are required to explore any grid of at least three nodes, even in the probabilistic case. Then, we show that at least four (resp. five) robots are necessary to deterministically explore a $\bf(2,2)$-Grid (resp. a $\bf(3,3)$-Grid). We then propose deterministic algorithms in the asynchronous model. This latter being strictly weakest than the semi-synchronous model, all the aforementioned bounds still hold in that context. Our algorithms actually exhibit the optimal number of robots that is necessary to explore a given grid. Overall, our results show that except in two particular cases, three robots are necessary and sufficient to deterministically explore a grid of at least three nodes and then terminate. The optimal number of robots for the two remaining cases is four for the $\bf(2,2)$-Grid and five for the $\bf(3,3)$-Grid, respectively.

We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: $M_{init}$, which denotes the number of nodes between two border nodes, and $O_{init}$, which denotes the number of nodes hosting robots between two border nodes. In both cases, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if $M_{init}$ or $O_{init}$ is odd, gathering is always feasible with three or four colors. The proposed algorithms do not require additional assumptions, such as knowledge of the number of robots, multiplicity detection capabilities, or the assumption of towerless initial configurations. These results demonstrate the power of lights to achieve gathering of robots with limited visibility.

The problem of exploring a discrete environment by identical oblivious asynchronous agents (or robots) devoid of direct means of communication has been well investigated so far. The (terminating) exploration requires that starting from a configuration where no two agents occupy the same node, every node needs to be visited by at least one agent, with the additional constraint that all agents eventually stop moving. Agents have sensors that allow them to see their environment and move accordingly. The previous works on this problem assume agents having an unlimited visibility, that is, they can sense the agents on every node of the ring, whatever the ring size. In this paper, we address deterministic exploration in an anonymous, unoriented ring using oblivious, and myopic agents. By myopic, we mean that their visibility is limited in terms of sensing distance. We consider the strongest possible myopia that is, an agent can only sense agents located at its own and at its immediate neighboring nodes. Our contribution is threefold. We first prove that within such settings, no deterministic exploration is possible in the semi-synchronous model. The result is also valid for the (fully) asynchronous model and holds for any k 6. Finally, we provide optimal (in terms of number of agents) deterministic algorithms in the fully synchronous model for both cases 3 6.

Spades aims at offering a solution to deal with distributed, volatile and heterogeneous computing resources. The targeted platform is a large one with potentially huge number of resources. In a seamless way, our proposal includes i) an abstraction of the resources in a computing overlay; ii) a P2P distributed resource/service discovery; iii) an user job scheduling workflow; iv) an auto-stabilizing solution and v) optimized algorithms for Petascale architecture. In order to orchestrate Spades platform, we have designed and implemented Sbam middleware.