We consider the uniform scattering problem for a set of autonomous mobile robots deployed in a grid network: starting from an arbitrary placement in the grid, using purely localized computations, the robots must move so to reach in finite time a state of static equilibrium in which they cover uniformly the grid. The theoretical quest is on determining the minimal capabilities needed by the robots to solve the problem. We prove that uniform scattering is indeed possible even for very weak robots. The proof is constructive. We present a provably correct protocol for uniform self-deployment in a grid. The protocol is fully localized, collision-free, and it makes minimal assumptions; in particular: (1) it does not require any direct or explicit communication between robots; (2) it makes no assumption on robots synchronization or timing, hence the robots can be fully asynchronous in all their actions; (3) it requires only a limited visibility range; (4) it uses at each robot only a constant size memory, hence computationally the robots can be simple Finite-State Machines; (5) it does not need a global localization system but only orientation in the grid (e.g., a compass); (6) it does not require identifiers, hence the robots can be anonymous and totally identical.

The aim of this paper is to study the computational power of the qualitative model, where entities are given distinct labels which are however mutually incomparable; this model is opposed to the quantitative model, where labels are integers. The qualitative model captures, for example,the case when the labels are written in different alphabets (e.g., Cyrillic, Latin) and there is no a priori agreement on a common encoding. We investigate the qualitative model through the problem of leader election in a distributed mobile environment. All known leader election protocols assume that the initial input values are distinct and pairwise comparable. While distinctness of the input values is clearly required, the comparability assumption is questionable. Our concern is whether it is possible to remove this comparability assumption. To focus solely on this concern, we consider theproblem in its weakest setting: anonymous highly symmetric networks (i.e.,Cayley graphs). In this way, to break the symmetry (and thus elect a leader) among the incomparable mobile agents, we can not rely on the existence of distinguished node labels nor on any topological asymmetry of the network. We describe a generic election protocol which is effective for all anonymous Cayley graphs; i.e., it solves the election problem if the problem is solvable, otherwise it determines that the problem is not solvable. For arbitrary networks, our protocol is conditionally effective; that is, it performs election of one agent among any set of agents in any network, under some weak conditions on the network and on the initial positions of the agents. Our work is a first step toward a better understanding of the inherent differences between "quantitative computing" where parameters are taken from a total order, and "qualitative computing" where parameters are taken from a partial order.

Abstract Several papers considered the problem of routing inad hocwireless networks using the positions of the mobile hosts. Perimeter routing 1 , 2 gives an algorithm that guarantees delivery of messages in such networks without the use of flooding of control packets. However, this protocol is likely to fail if the transmission ranges of the mobile hosts vary because of natural or man‐made obstacles. It may fail because either some connections are not considered, which effectively results in a disconnection of the network, or because some crossing connections are used, which could misdirect the message. In this paper, we describe a robust routing protocol, a variant of perimeter routing, which tolerates up to 40% of variation in the transmission ranges of the mobile hosts. More precisely, our protocol guarantees message delivery in a connected ad hoc wireless network without the use of message flooding whenever the ratio of the maximum transmission range to the minimum transmission range is at most √2. Copyright © 2003 John Wiley & Sons, Ltd.

Consider a team of mobile software agents deployed to capture a (possibly hostile) intruder in a network. All agents, including the intruder move along the network links; the intruder could be arbitrarily fast, and aware of the positions of all the agents. The problem is to design the agents' strategy for capturing the intruder. The main efficiency parameter is the size of the team. This is an instance of the well known graph-searching problem whose many variants have been extensively studied in the literature. In all existing solutions, and in all the variants of the problem, it is assumed that agents can be removed from their current location and placed in another network site arbitrarily and at any time. As a consequence, the existing optimal strategies cannot be employed in situations for which agents cannot access the network at any point, or cannot "jump" across the network, or cannot reach an arbitrary point of the network via an internal travel through insecure zones. This motivates the contiguous search problem in which agents cannot be removed from the network, and clear links must form a connected sub-network at any time, providing safety of movements. This new problem is NP-complete in general. We study it for tree networks, and we consider its more general version, the weighted case, which arises naturally when considering networks whose nodes and links are of different nature and thus require a different number of agents to be explored. We give a linear-time algorithm that computes, for any tree $T$, the minimum number of agents to capture the intruder, and the corresponding search strategy. Beside its optimality in time, our algorithm is naturally distributed: if $T$ is a processor-network, then the minimal search strategy for $T$ can be computed by $T$ in a decentralized manner, using a linear number of messages.

This paper studies routing vulnerability in networks modeled by chordal ring graphs. In a chordal ring graph, the vertices are labeled in ℤ2n and each even vertex i is adjacent to the vertices i + a, i + b, i, + c, where a, b, and c are different odd integers. Our study is based on a geometrical representation that associates to the graph a tile which periodically tessellates the plane. Using this approach, we present some previous results on triple-loop graphs, including an algorithm to calculate the coordinates of a given vertex in the tile. Then, an optimal consistent fault-tolerant routing of shortest paths is defined for a chordal ring graph with odd diameter and maximum order. This is accomplished by associating to the chordal ring graph a triple-loop one. When some faulty elements are present in the network, we give a method to obtain central vertices, which are vertices that can be used to reroute any communication affected by the faulty elements. This implies that the diameter of the corresponding surviving route graph is optimum. © 2000 John Wiley & Sons, Inc.