We consider the distributed framework of swarms of mobile robots. A swarm is a set of computational, anonymous, indistinguishable, homogeneous, and autonomous entities that operate in the Euclidean plane through infinite sequences of Look-Compute-Move cycles. The goal of a swarm is to collaborate to solve a given problem. The ability to solve a problem depends on the swarm features and its setting X^S, where X ∈ {OBLOT, FSTA, FCOM, LUMI} denotes the memory/communication model and S denotes the class of schedulers (e.g., fully-synchronous, sequential, asynchronous) that activate the robots. Given a pool of settings, prior research has characterized the relations (dominance, equivalence, or orthogonality) among their computational powers, recently extending this analysis to the class of sequential schedulers (i.e., activating only one robot per round), and of the restricted ones (i.e., never activating a robot twice consecutively). In this paper, we extend the study on sequential schedulers (SEQ, PERM, and RROBIN) by defining two classes of sequential restricted schedulers R-SEQ and R-PERM. In particular, we analyze how the computational power of each model OBLOT, LUMI, and FCOM is affected by considering both sequential schedulers and their restricted variants; for FSTA, we only provide the relation between RROBIN and R-PERM. We establish both equivalence and dominance results: some settings are computationally equivalent, while others can be separated by problems solvable in one setting but not in the other.

The Dancing problem requires a swarm of n autonomous mobile robots to form a sequence of patterns, i.e., perform a choreography. Existing work has proven that some crucial restrictions on choreographies and initial configurations (e.g., on repetitions of patterns, periodicity, symmetries, contractions/expansions) must hold so that the Dancing problem can be solved under certain robot models. Here, we prove that these necessary constraints can be dropped by considering the $$\mathcal {LUMI}$$ model (i.e., where robots are endowed with a light whose color can be chosen from a constant-size palette) under the quite unexplored sequential scheduler. We formalize the class of Universal Dancing problems which require a swarm of n robots starting from any initial configuration to perform a (periodic or finite) sequence of arbitrary patterns, only provided that each pattern consists of n vertices (including multiplicities). However, we prove that, to be solvable under $$\mathcal {LUMI}$$ , the length of the feasible choreographies is bounded by the compositions of n into the number of colors available to the robots. We provide an algorithm solving Universal Dancing by exploiting the peculiar capability of sequential robots to implement a distributed counter. Even assuming non-rigid movements, our algorithm ensures spatial homogeneity of the performed choreography.

In networked systems supporting mobile agents, a particularly dangerous security threat facing the agents is the presence of a black hole (Bh): a network host that destroys any incoming agent without leaving any trace. The problem, called Black hole search (Bhs), of efficiently determining the location of such a dangerous host has been extensively studied under a variety of different assumptions. In spite of their differences, the existing results share the same assumption that all the searching agents are reliable.In this paper, we start the investigation of the Bhs problem when some of the searching agents are faulty in a malicious way. More precisely, we consider that up to f of the k searching agents are Byzantine: they may behave in an arbitrary manner, actively misleading other agents; furthermore, they are in collusion with the black hole, and immune to its destructive power.We study under what conditions the Bhs problem can be solved in a synchronous network of arbitrary topology in spite of the malicious agents, examining the impact on complexity of two factors: the a-priori topological knowledge held by the agents, and the communication mechanism available to them.We prove that, with prior knowledge about the graph topology (i.e., a network map), Bhs can be solved by k ≥ 2f +2 agents in O(n + f) synchronous rounds both with whiteboards and with just local communication, where n is the number of nodes in the network.Without any knowledge about the topological structure, using whiteboard communication Bhs can be solved by k ≥ (f+1)(∆+ 1) agents in O(m+f) rounds; instead, using local communication, Bhs can be solved by k ≥ (f + 1)(∆ + 1) + 3f + 1 agents in O(m • n + f) rounds, where m is the number of links of the network and ∆ is the maximum degree of the network.In all cases, as we show, the bound on the total number k of agents is asymptotically optimal.

We consider distributed systems of autonomous, punctiform, mobile robots that operate in the Euclidean plane by executing an infinite sequence of Look-Compute-Move cycles. Robots are anonymous, indistinguishable, homogeneous, and disoriented. In literature, four base models have been proposed to study four different memory-communication settings: $$\mathcal {OBLOT}$$ (oblivious and silent), $$\mathcal {FSTA}$$ (finite-state and silent), $$\mathcal {FCOM}$$ (oblivious and finite-communication), and $$\mathcal {LUMI}$$ (finite-state and finite-communication). In particular, the research has investigated how the computational power of these models is affected by considering three main classes of robot schedulers: FSYNCH (fully synchronous), SSYNCH (semi-synchronous), and ASYNCH (asynchronous). This paper focuses on a peculiar type of SSYNCH schedulers, the sequential ones, which activate only one robot at each round. We consider three subclasses: the general sequential scheduler (SEQ), the permutation scheduler (PERM), and the well-known round-robin (RROBIN). For each base model, we investigate how the robots’ computational power changes as the scheduler class varies, thus providing a first overview of the computational landscape of sequential schedulers.

The Dancing problem requires a swarm of n autonomous mobile robots to form a sequence of patterns, aka perform a choreography.Existing work has proven that some crucial restrictions on choreographies and initial configurations (e.g., on repetitions of patterns, periodicity, symmetries, contractions/expansions) must hold so that the Dancing problem can be solved under certain robot models.Here, we prove that these necessary constraints can be dropped by considering the LUMI model (i.e., where robots are endowed with a light whose color can be chosen from a constant-size palette) under the quite unexplored sequential scheduler.We formalize the class of Universal Dancing problems which require a swarm of n robots starting from any initial configuration to perform a (periodic or finite) sequence of arbitrary patterns, only provided that each pattern consists of n vertices (including multiplicities).However, we prove that, to be solvable under LUMI, the length of the feasible choreographies is bounded by the compositions of n into the number of colors available to the robots.We provide an algorithm solving the Universal Dancing problem by exploiting the peculiar capability of sequential robots to implement a distributed counter mechanism.Even assuming non-rigid movements, our algorithm ensures spatial homogeneity of the performed choreography.

In networked environments supporting mobile agents , a pressing problem is the presence of network sites harmful for the agents. In this paper we consider the danger posed by a node that destroys any incoming agent without leaving any trace. Such a dangerous node is known in the literature as a black hole ( Bh ). The problem of a team of system agents determining its location, known as black hole search ( Bhs ), has been extensively studied in the literature under a variety of assumptions, both in synchronous and asynchronous settings. The main complexity parameter of Bhs is the number of system agents (called size ) needed to solve the problem; other parameters are the number of moves (called cost ) performed by the agents, and the time until termination. In the existing literature, with only a couple of exceptions, all results are based on a common assumption that the network is static , i.e. its topology does not change in time. We consider instead the Bhs when the network is dynamic : the link structure of the graph changes over time. While time-varying graphs have been the focus of intense research in the last two decades, very little is known on the problem of locating the Bh in such networks. In this paper, we contribute to fill this research gap by studying Bhs in dynamic ring networks, focusing on the 1-interval connectivity adversarial dynamics. Feasibility and complexity of the problem depend on many factors, specifically on the size n of the ring, whether or not n is known, and the type of inter-agent communication (whiteboards, tokens, face-to-face, visual). In this paper, we provide a complete feasibility characterization presenting size optimal algorithms. Furthermore, we establish lower bounds on the cost and time of size-optimal solutions and show that our algorithms achieve those bounds.

Distributed computing has been concerned with the topics of faults and failures from its very beginning (before PODC was born). The consensus problem was at the forefront of the research efforts, and an extensive body of literature on the subject was developed very quickly (e.g., [5, 6, 11, 20]). The beautiful proof of the impossibility of consensus under asynchrony [7] put to rest the unsuccessful attempts to prove otherwise, and gave an even stronger impetus to the focus on synchronous systems.

Abstract A distributed algorithm $${\mathcal {A}}$$ A solves the Point Convergence task if an arbitrarily large collection of entities, starting in an arbitrary configuration, move under the control of $${\mathcal {A}}$$ A to eventually form and thereafter maintain configurations in which the separation between all entities is arbitrarily small. This fundamental task in the standard $$\mathcal {OBLOT}$$ OBLOT model of autonomous mobile entities has been previously studied in a variety of settings, including full visibility, exact measurements (including distances and angles), and synchronous activation of entities. Our study concerns the minimal assumptions under which entities, moving asynchronously with limited and unknown visibility range and subject to limited imprecision in measurements, can be guaranteed to converge in this way. We present an algorithm operating under these constraints that solves Point Convergence, for entities moving in two or three dimensional space, with any bounded degree of asynchrony. We also prove that under similar realistic constraints, but unbounded asynchrony, Point Convergence in the plane is not possible in general, contingent on the natural assumption that algorithms maintain the (visible) connectivity among entities present in the initial configuration. This variant, that we call Cohesive Convergence, serves to distinguish the power of bounded and unbounded asynchrony in the control of autonomous mobile entities, settling a long-standing question whether in the Euclidean plane synchronously scheduled entities are more powerful than asynchronously scheduled entities.

Research on distributed computing by a team of identical mobile computational entities, called robots, operating in a Euclidean space in $\mathit{Look}$-$\mathit{Compute}$-$\mathit{Move}$ ($\mathit{LCM}$) cycles, has recently focused on better understanding how the computational power of robots depends on the interplay between their internal capabilities (i.e., persistent memory, communication), captured by the four standard computational models (OBLOT, LUMI, FSTA, and FCOM) and the conditions imposed by the external environment, controlling the activation of the robots and their synchronization of their activities, perceived and modeled as an adversarial scheduler. We consider a set of adversarial asynchronous schedulers ranging from the classical semi-synchronous (SSYNCH) and fully asynchronous (ASYNCH) settings, including schedulers (emerging when studying the atomicity of the combination of operations in the $\mathit{LCM}$ cycles) whose adversarial power is in between those two. We ask the question: what is the computational relationship between a model $M_1$ under adversarial scheduler $K_1$ ($M_1(K_1)$) and a model $M_2$ under scheduler $K_2$ ($M_2(K_2)$)? For example, are the robots in $M_1(K_1)$ more powerful (i.e., they can solve more problems) than those in $M_2(K_2)$? We answer all these questions by providing, through cross-model analysis, a complete characterization of the computational relationship between the power of the four models of robots under the considered asynchronous schedulers. In this process, we also provide qualified answers to several open questions, including the outstanding one on the proper dominance of SSYNCH over ASYNCH in the case of unrestricted visibility.

In this paper we investigate the computational power of a set of mobile robots with limited visibility. At each iteration, a robot takes a snapshot of its surroundings, uses the snapshot to compute a destination point, and it moves toward its destination. Robots are punctiform and memoryless, they operate in $$\mathbb {R}^m$$ , they have local reference systems independent of each other, and are activated asynchronously by an adversarial scheduler. Moreover, robots are non-rigid, in that they may be stopped by the scheduler at each move before reaching their destination (but are guaranteed to travel at least a fixed unknown distance before being stopped). We show that despite these strong limitations, it is possible to arrange $$3m+3k$$ of these weak entities in $$\mathbb {R}^m$$ to simulate the behavior of a stronger robot that is rigid (i.e., it always reaches its destination) and is endowed with k registers of persistent memory, each of which can store a real number. We call this arrangement a TuringMobile. In its simplest form, a TuringMobile consisting of only three robots can travel in the plane and store and update a single real number. We also prove that this task is impossible with fewer than three robots. Among the applications of the TuringMobile, we focused on Near-Gathering (all robots have to gather in a small-enough disk) and Pattern Formation (of which Gathering is a special case) with limited visibility. Interestingly, our investigation implies that both problems are solvable in Euclidean spaces of any dimension, even if the visibility graph of the robots is initially disconnected, provided that a small amount of these robots are arranged to form a TuringMobile. In the special case of the plane, a basic TuringMobile of only three robots is sufficient.

In this paper, we start the investigation of distributed computing by mobile agents in dangerous dynamic networks. The danger is posed by the presence in the network of a black hole (BH), a harmful site that destroys all incoming agents without leaving any trace. The problem of determining the location of the black hole in a network, known as black hole search (BHS), has been extensively studied in the literature, but always and only assuming that the network is static. At the same time, the existing results on mobile agents computing in dynamic networks never consider the presence of harmful sites. In this paper we start filling this research gap by studying black hole search in temporal rings, specifically focusing on 1-interval connectivity adversarial dynamics. The main complexity parameter of BHS is the number of agents (called size) needed to solve the problem; other parameters are the number of moves (called cost) performed by the agents, and the time until termination. Feasibility and complexity depend on many factors; the size n of the ring, whether or not n is known, and the type of inter-agent communication (whiteboards, tokens, face-to-face, visual). In this paper, we provide a complete feasibility characterization presenting size optimal algorithms. Furthermore, we establish lower bounds on the cost and time of size-optimal solutions and show that our algorithms achieve those bounds.

We consider distributed computations, by identical autonomous mobile entities, that solve the Point Convergence problem: given an arbitrary initial configuration of entities, disposed in the Euclidean plane, move in such a way that, for all ε>0, a configuration is eventually reached and maintained in which the separation between all entities is at most ε. The problem has been previously studied in a variety of settings. Our study concerns the minimal assumptions under which entities, moving asynchronously with limited and unknown visibility range and subject to limited imprecision in measurements, can be guaranteed to converge in this way. We present an algorithm that solves Point Convergence, provided the degree of asynchrony is bounded by some arbitrarily large but fixed constant. This provides a strong positive answer to a decade old open question posed by Katreniak. We also prove that, in an otherwise comparable setting, Point Convergence is impossible with unbounded asynchrony. This serves to distinguish the power of bounded and unbounded asynchrony in the control of autonomous mobile entities, settling at the same time a long-standing question whether in the Euclidean plane synchronous entities are more powerful than asynchronous ones.

The following topics are dealt with: learning (artificial intelligence); security of data; Internet of Things; Internet; resource allocation; data privacy; computer network security; telecommunication security; telecommunication traffic; cellular radio.

The coverage provided by a network of battery-powered sensors degrades over time and eventually disappears if energy is not restored. An important approach to energy restoration is to employ k robots that act as mobile battery chargers. These robots decide where to move next according to a predefined algorithm, called energy restoration strategy, whose effectiveness is measured in terms of: i) the number of nodes that it is able to maintain operational at any given time (Coverage Size), and ii) the time a node battery remains depleted before getting recharged (Disconnection Time). In the case of ring networks (e.g., deployed on the border of a closed region), very simple strategies with near-optimal effectiveness exist for k = 1. In this paper we focus on recharging strategies when k > 1 robots are available. We consider two very simple strategies: 1) Sub-segment, where the ring is partitioned into segments and one robot is dedicated to each segment; 2) Overpass, where the robots, initially at equidistant positions, simply move around the ring charging any node in need, overpassing other robots encountered on the way. We study the two strategies running extensive simulations to assess their effectiveness, varying several network parameters. The results show, among others, that Sub-segment is always more effective than Overpass in terms of coverage, while for disconnection time the effectiveness depends also on other factors, like the number of sensors employed and the size of the ring. Most importantly, the results indicate that Sub-segment achieves in almost all networks an optimal effectiveness speed-up: the coverage size increases and the disconnection time decreases by a factor of k with respect to the near optimal strategy for a single robot.

Consider a set of n mobile computational entities, called robots, located and operating on a continuous cycle C (e.g., the perimeter of a closed region of R^2) of arbitrary length l. The robots are identical, can only see their current location, have no location awareness, and cannot communicate at a distance. In this weak setting, we study the classical problems of gathering (GATHER), requiring all robots to meet at a same location; and election (ELECT), requiring all robots to agree on a single one as the "leader". We investigate how to solve the problems depending on the amount of knowledge (exact, upper bound, none) the robots have about their number n and about the length of the cycle l. Cost of the algorithms is analyzed with respect to time and number of random bits. We establish a variety of new results specific to the continuous cycle - a geometric domain never explored before for GATHER and ELECT in a mobile robot setting; compare Monte Carlo and Las Vegas algorithms; and obtain several optimal bounds.

International audience

We investigate the computational power of distributed systems whose autonomous computational entities, called robots, move and operate in the 2-dimensional Euclidean plane in synchronous Look-Compute-Move (LCM) cycles. Specifically, we focus on the power of persistent memory and that of explicit communication, and on their computational relationship. In the most common model, OBLOT, the robots are oblivious (no persistent memory) and silent (no explicit means of communication). In contrast, in the LUMI model, each robot is equipped with a constant-sized persistent memory (called light), visible to all the robots; hence, these luminous robots are capable in each cycle of both remembering and communicating. Since luminous robots are computationally more powerful than the standard oblivious one, immediate important questions are about the individual computational power of persistent memory and of explicit communication. In particular, which of the two capabilities, memory or communication, is more important? in other words, is it better to remember or to communicate ? In this paper we address these questions, focusing on two sub-models of LUMI: FSTA, where the robots have a constant-size persistent memory but are silent; and FCOM, where the robots can communicate a constant number of bits but are oblivious. We analyze the relationship among all these models and provide a complete exhaustive map of their computational relationship. Among other things, we prove that communication is more powerful than persistent memory under the fully synchronous scheduler Fsynch, while they are incomparable under the semi-synchronous scheduler Ssynch.

Temporal graphs (or evolving graphs) are time-varying graphs where time is assumed to be discrete. In this paper, we consider for the first time the problem of exploring temporal graphs of arbitrary unknown topology. We study the feasibility of exploration, under both the Fsync and Ssync schedulers, focusing on the number of agents necessary and sufficient to explore such graphs. We first consider the minimal (i.e., less restrictive) assumption on the dynamics of the graph under which exploration is still feasible: temporal connectivity. Let ℋ be the class of temporally connected graphs; we show that for any temporal graph ? ∈ ℋ the number of agents sufficient to perform exploration is related to the number of its transient edges, a parameter η(?) we call evanescence of the graph. More precisely, any ? ∈ ℋ can be explored by a team of k ≥ 2 η(?) +1 agents; this bound is tight as we prove there are ? ∈ ℋ that cannot be explored by 2 η(?) agents. We then turn our attention to the well-known stronger assumption on the dynamics of the graph, called 1-interval connectivity: the graph is connected at any time step. Let ? ⊂ ℋ be the class of these always-connected temporal graphs. For this class, we prove the existence of a difference between Fsync and Ssync when there is a bound ? on the number of edges missing at each time. In fact, we show a tight bound of 2 ? +1 on the number of agents necessary and sufficient in Ssync, and a smaller tight bound of 2 ? in Fsync. As a corollary, we re-establish two recently published bounds for 1-interval connected rings.

The coverage provided by a sensor network degrades over time as the batteries powering the sensors become exhausted. A common approach to energy restoration in sensor networks powered by batteries is to use a robot acting as a mobile battery charger/changer. The goal is to constantly minimize the number of coverage holes and their duration. In this paper, we focus on decentralized on-line strategies for energy restoration by a robot in linear sensor networks, i.e. whose topology is modelled as a line. We consider a standard On-Demand strategy, where a sensor in need of charge sends a request in the direction of the robot, and the robot moves to serve the requests as they arrive. We examine also a simpler variant of this strategy, Straight, in which the direction of movement of the robot along the line cannot be changed until it reaches the end of the line. We finally consider the simplest possible on-line strategy, Blind, where no requests are sent and the robot automatically and continuously moves from one end of the line to the other, servicing any sensor found needing recharging. We experimentally study the efficiency of these strategies, and we make the counter-intuitive discovery that the simpler the strategy, the better its efficiency. In particular, Blind which does not require any communication nor memory nor computation, is at least as efficient as the other two. We also provide strong analytical support to these experimental findings. In fact we prove that, starting with initially empty batteries, the Blind strategy has better coverage performance that the other two strategies for almost all network sizes. Indeed for some network sizes no other strategy, even if centralized and offline, can do better.

As most existing sensors are powered by batteries, the coverage provided by a sensor network degrades over time and eventually disappears if energy is not restored. A common approach to energy restoration is to use a robot acting as a mobile battery charger/changer. The goal is to maintain the best level of coverage; that is, to constantly minimize the number of coverage holes and their duration. Depending on the strategy employed by the robot, clearly different results can be obtained. In this paper, we focus on sensors arranged in a ring topology and we consider the intuitive online ON-DEMAND strategy where: the robot visits the sensors in clockwise direction when aware of a pending request; a sensor whose battery is about to become depleted originates a recharging request and waits for the robot; the request is forwarded along the ring in counter-clockwise direction until it reaches either the robot or another sensor waiting for the robot. We also consider the simplest possible online strategy, BLIND, where no requests are sent and the robot automatically moves along the ring looking for needing sensors. We experimentally study the efficiency of the two strategies, and we make the counter-intuitive discovery that BLIND, which does not require communication nor computation, is as efficient as On Demand.

In this paper we investigate the computational power of a set of mobile robots with limited visibility. At each iteration, a robot takes a snapshot of its surroundings, uses the snapshot to compute a destination point, and it moves toward its destination. Each robot is punctiform and memoryless, it operates in R m , it has a local reference system independent of the other robots’ ones, and is activated asynchronously by an adversarial scheduler. Moreover, the robots are nonrigid, in that they may be stopped by the scheduler at each move before reaching their destination (but are guaranteed to travel at least a fixed unknown distance before being stopped). We show that despite these strong limitations, it is possible to arrange 3m+3k of these weak entities in R m to simulate the behavior of a stronger robot that is rigid (i.e., it always reaches its destination) and is endowed with k registers of persistent memory, each of which can store a real number. We call this arrangement a TuringMobile. In its simplest form, a TuringMobile consisting of only three robots can travel in the plane and store and update a single real number. We also prove that this task is impossible with fewer than three robots. Among the applications of the TuringMobile, we focused on Near-Gathering (all robots have to gather in a small-enough disk) and Pattern Formation (of which Gathering is a special case) with limited visibility. Interestingly, our investigation implies that both problems are solvable in Euclidean spaces of any dimension, even if the visibility graph of the robots is initially disconnected, provided that a small amount of these robots are arranged to form a TuringMobile. In the special case of the plane, a basic TuringMobile of only three robots is sufficient. © Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, and Giovanni Viglietta.

In this paper we investigate the computational power of population protocols under some unreliable or weaker interaction models. More precisely, we focus on two features related to the power of interactions: omission failures and one-way communications. We start our investigation by providing a complete classification of all the possible models arising from the aforementioned weaknesses, and establishing the computational hierarchy of these models. We then address for each model the fundamental question of what additional power is necessary and sufficient to completely overcome the model's weakness and make it able to simulate faultless two-way protocols. We answer this question by presenting simulators that work under certain assumptions and by proving that simulation is impossible without such assumptions.

Shape formation (or pattern formation) is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been investigated in the realm of programmable matter, where entities are assumed to be small and with severely limited capabilities. Namely, it has been studied in the geometric Amoebot model, where the anonymous entities, called particles, operate on a hexagonal tessellation of the plane and have limited computational power (they have constant memory), strictly local interaction and communication capabilities (only with particles in neighboring nodes of the grid), and limited motorial capabilities (from a grid node to an empty neighboring node); their activation is controlled by an adversarial scheduler. Recent investigations have shown how, starting from a well-structured configuration in which the particles form a (not necessarily complete) triangle, the particles can form a large class of shapes. This result has been established under several assumptions: agreement on the clockwise direction (i.e., chirality), a sequential activation schedule, and randomization (i.e., particles can flip coins to elect a leader). In this paper we provide a characterization of which shapes can be formed deterministically starting from any simply connected initial configuration of n particles. The characterization is constructive: we provide a universal shape formation algorithm that, for each feasible pair of shapes (S0, SF), allows the particles to form the final shape SF (given in input) starting from the initial shape S0, unknown to the particles. The final configuration will be an appropriate scaled-up copy of SF depending on n. If randomization is allowed, then any input shape can be formed from any initial (simply connected) shape by our algorithm, provided that there are enough particles. Our algorithm works without chirality, proving that chirality is computationally irrelevant for shape formation. Furthermore, it works under a strong adversarial scheduler, not necessarily sequential. We also consider the complexity of shape formation both in terms of the number of rounds and the total number of moves performed by the particles executing a universal shape formation algorithm. We prove that our solution has a complexity of O(n2) rounds and moves: this number of moves is also asymptotically worst-case optimal.

The Meeting problem for k>=2 searchers in a polygon P (possibly with holes) consists in making the searchers move within P, according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of P, we minimize the number of searchers k for which the Meeting problem is solvable. Specifically, if P has a rotational symmetry of order sigma (where sigma=1 corresponds to no rotational symmetry), we prove that k=sigma+1 searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with k=2 searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look-Compute-Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations (provided that the coordinates of the polygon's vertices are algebraic real numbers in some global coordinate system), and each searcher can geometrically construct its own destination point at each cycle using only a compass. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self-stabilizing map construction subroutine which is of independent interest.

Shape formation is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been investigated in the realm of programmable matter. Namely, it has been studied in the geometric Amoebot model, where the anonymous entities, called particles, operate on a hexagonal tessellation of the plane, have constant memory, can only communicate with neighboring particles, and can only move from a grid node to an empty neighboring node; their activation is controlled by an adversarial scheduler. Recent investigations have shown how, starting from a well-structured configuration in which the particles form a (not necessarily complete) triangle, the particles can form a large class of shapes. This result has been established under several assumptions: agreement on the clockwise direction (i.e., chirality), a sequential activation schedule, and randomization. In this paper we provide a characterization of which shapes can be formed deterministically starting from any simply connected initial configuration of n particles. As a byproduct, if randomization is allowed, then any input shape can be formed from any initial (simply connected) shape by our algorithm, provided that n is large enough. Our algorithm works without chirality, proving that chirality is computationally irrelevant for shape formation. Furthermore, it works under a strong adversarial scheduler, not necessarily sequential. We also consider the complexity of shape formation both in terms of the number of rounds and the total number of moves performed by the particles executing a universal shape formation algorithm. We prove that our solution has a complexity of O(n^2) rounds and moves: this number of moves is also asymptotically optimal.

Almost all the vast literature on graph exploration assumes that the graph is static: its topology does not change during the exploration, except for occasional faults. To date, very little is known on exploration of dynamic graphs, where the topology is continously changing. The few studies have been limited to the centralized (or post-mortem) case, assuming complete a priori knowledge of the changes and the times of their occurrence, and have only considered fully synchronous systems. In this paper, we start the study of the decentralized (or live) exploration of dynamic graphs, i.e. when the agents operate in the graph unaware of the location and timing of the changes. We consider dynamic rings under the standard 1-interval-connected restriction, and investigate the feasibility of their exploration, in both the fully synchronous and semi-synchronous cases. When exploration is possible we examine at what cost, focusing on the minimum number of agents capable of exploring the ring. We establish several results highlighting the impact that anonymity and structural knowledge have on the feasibility and complexity of the problem.

In highly dynamic networks, topological changes are not anomalies but rather integral part of their nature. Such networks are becoming quite ubiquitous. They include systems where the entities are mobile and communicate without infrastructure (e.g. vehicles, satellites, robots, or pedestrian smartphones): the topology changes as the entities move. They also include systems, such as peer-to-peer networks, where the changes are caused by entities entering and leaving the system, They even include systems where there is no physical mobility at all, such as social networks. A vast literature on these dynamic networks has been produced in many different fields, including distributed computing. The several efforts to survey the status of the research and attempts to clarify and classify models and assumptions, have so far brought more valuable bibliographic data than order and clarity. Goal of this note is to ask questions that might bring author and readers to start to clarify some important research aspects and put some order in a sometimes confusing field. The focus here is entirely on distributed computing, specifically on its deterministic aspects.

When deploying a wireless sensor network in an unknown environment, commonly referred to as Region of Interest (ROI), the main goal is for the entire region to be covered by the sensing ranges of the deployed sensors. While this goal of full coverage is easily achieved in presence of human intervention, it becomes problematic if the region is dangerous or inaccessible to human. An approach recently proposed to solve the problem is to use a robot to deploy the sensors; the main advantages respect to the alternative of employing mobile sensors are the reduced costs (due to manufacture and maintenance cost of common static sensors vs. mobile ones) and the reduced complexity of the coordination and control algorithms. Indeed several solution algorithms to achieve deployment of sensors by a robot in an unknown region have been proposed in the literature. Unfortunately, even when restricted to orthogonal regions (e.g., city maps, building plans, etc), all the existing algorithms fail to achieve full coverage of the ROI. Specifically, following the existing protocols, the robot would leave uncovered areas near either the boundaries or critical areas (e.g. areas that are linked to the rest of the region by a narrow corridor). In this paper we present an algorithm that overcomes these problems and guarantees that the deployment of the sensors by the robot achieves full coverage in any simply connected orthogonal ROI, whose topology is unknown to the robot. The proposed algorithm has minimal requirements: it does not need GPS but only local orientation by the robot; the communication range of a deployed sensor is limited to its deployed neighbours, and the robot has a similar range; the total number of sensors used is minimal. Also minimal are the robot's memory requirements, the total amount of robots movements and of communication between robot and sensors.

Delay-tolerant networks (DTNs) are characterized by a possible absence of end-to-end communication routes at any instant. Yet, connectivity can be achieved over time and space, leading to evaluate a given route both in terms of topological length or temporal length. The problem of measuring temporal distances in a social network was recently addressed through postprocessing contact traces like email data sets, in which all contacts are punctual in time (i.e., they have no duration). We focus on the distributed version of this problem and address the more general case that contacts can have arbitrary durations (i.e., be nonpunctual). Precisely, we ask whether each node in a network can track in real time how "out-of-dateâ it is with respect to every other. Although relatively straightforward with punctual contacts, this problem is substantially more complex with arbitrarily long contacts: consecutive hops of an optimal route may either be disconnected (intermittent connectedness of DTNs) or connected (i.e., the presence of links overlaps in time, implying a continuum of path opportunities). The problem is further complicated (and yet, more realistic) by the fact that we address continuous-time systems and nonnegligible message latencies (time to propagate a single message over a single link); however, this latency is assumed fixed and known. We demonstrate the problem is solvable in this general context by generalizing a time-measurement vector clock construct to the case of "nonpunctualâ causality, which results in a tool we call T-Clocks, of independent interest. The remainder of the paper shows how T-Clocks can be leveraged to solve concrete problems such as learning foremost broadcast trees (BTs), network backbones, or fastest broadcast trees in periodic DTNs.

In this paper we study the power of using lights, i.e. visible external memory, for distributed computation by autonomous robots moving in Look-Compute-Move (LCM) cycles. With respect to the LCM cycles, the most common models studied in the literature are the fully-synchronous (FSYNC), the semi-synchronous (SSYNC), and the asynchronous (ASYNC). In this paper we introduce in the ASYNC model, the weakest of the three, the availability of visible external memory: each robot is equipped with a light bulb that is visible to all other robots, and that can display a constant numbers of different colors, the colors are persistent, that is they are not automatically reset at the end of each cycle. We first study the relationship between ASYNC with visible bits and SSYNC. We prove hat asynchronous robots, when equipped with a constant number of colors, are strictly more powerful than traditional semi-synchronous robots. We also show that, when enhanced with visible lights, the difference between asynchrony and semi-synchrony disappears, this result must be contrasted with the strict dominance ASYNC

We consider infrastructure-less highly dynamic networks, where connectivity does not necessarily hold, and the network may actually be disconnected at every time instant. These networks are naturally modeled as time-varying graphs. Clearly the task of designing protocols for these networks is less difficult if the environment allows waiting (i.e., it provides the nodes with store-carry-forward-like mechanisms such as local buffering) than if waiting is not feasible. We provide a quantitative corroboration of this fact in terms of the expressivity of the corresponding time-varying graph; that is in terms of the language generated by the feasible journeys in the graph. We prove that the set of languages Lnowait when no waiting is allowed contains all computable languages. On the other end, we prove that Lwait is just the family of regular languages. This gap is a measure of the computational power of waiting. We also study bounded waiting; that is when waiting is allowed at a node only for at most d time units. We prove the negative result that L wait[d] = Lnowait.

Consider a set of $n>2$ 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 $n \leq 4$ or for restricted sets of initial configurations of the robots; the question of whether such weak robots could deterministically gather has remained open. In this paper, we prove that indeed the Gathering Problem is solvable, for any $n>2$ and any initial configuration, even under such restrictive conditions.

In many network applications, the computation takes place on the minimum-cost spanning tree (MST) of the network G; unfortunately, a single link or node failure disconnects the tree. The ALL NODES REPLACEMENT (ANR) problem is the problem of precomputing, for each node u in G, the new MST should u fail. This problem has been extensively investigated for serial and parallel settings, and efficient solutions have been designed for those environments. The situation is surprisingly different in distributed settings. In fact, no distributed solution exists to date which performs better than the brute-force repeated application of MST construction. In this paper, we consider for the first time the problem of computing all the replacement minimum-cost spanning trees distributively. We design a solution protocol, and we prove that the total amount of communication exchanges taking place is O(n), each exchange using at most O(n) data items. Hence, the total amount of data items communicated during the computation (the data complexity) is O(n^2). We also show how the simpler problem ALL EDGES REPLACEMENT (AER) dealing with single edge failures, which can be solved with the same costs using some existing techniques. Also for the AER problem, efficient solutions exist in the serial and parallel setting but, prior to this work, no distributed solution other than brute force was known.

Delay-tolerant networks (DTNs) are characterized by a possible absence of end-to-end communication routes at any instant. In most cases, however, a form of connectivity can be established over time and space. This particularity leads to consider the relevance of a given route not only in terms of hops (topological length), but also in terms of time (temporal length). The problem of measuring temporal distances between individuals in a social network was recently addressed, based on a posteriori analysis of interaction traces. This paper focuses on the distributed version of this problem, asking whether every node in a network can know precisely and in real time how out-of-date it is with respect to every other. Answering affirmatively is simple when contacts between the nodes are punctual, using the temporal adaptation of vector clocks provided in (Kossinets et al., 2008). It becomes more difficult when contacts have a duration and can overlap in time with each other. We demonstrate that the problem remains solvable with arbitrarily long contacts and non-instantaneous (though invariant and known) propagation delays on edges. This is done constructively by extending the temporal adaptation of vector clocks to non-punctual causality. The second part of the paper discusses how the knowledge of temporal lags could be used as a building block to solve more concrete problems, such as the construction of foremost broadcast trees or network backbones in periodically-varying DTNs.

The capability to query the topology of spatial regions is fundamental to today's centralized spatial computing systems, like spatial databases and GIS. By contrast, this paper explores decentralized algorithms for computing the topology of spatial regions in wireless sensor networks. The approach generates global topological information about regions, using only the local knowledge of nodes and their immediate network neighbors aggregated up through spatial boundary structures. Using three basic boundary structures (boundary nodes, boundary cycles, and boundary orientation), a family of decentralized algorithms is defined that can respond efficiently to snapshot queries about the topology of spatial regions, including containment and adjacency queries. The communication complexity of the algorithm is O(n) for realistic inputs. Empirical investigation of the performance of the approach, using simulation, also confirms the efficiency, scalability, and robustness of this approach.

Communication in networks suffers if a link fails. When the links are edges of a tree that has been chosen from an underlying graph of all possible links, a broken link even disconnects the network. Most often, the link is restored rapidly. A good policy to deal with this sort of transient link failures is swap rerouting, where the temporarily broken link is replaced by a single swap link from the underlying graph. A rapid replacement of a broken link by a swap link is only possible if all swap links have been precomputed. The selection of high-quality swap links is essential; it must follow the same objective as the originally chosen communication subnetwork. We are interested in a minimum-diameter tree in a graph with edge weights (so as to minimize the maximum travel time of messages). Hence, each swap link must minimize (among all possible swaps) the diameter of the tree that results from swapping. We propose a distributed algorithm that efficiently computes all of these swap links, and we explain how to route messages across swap edges with a compact routing scheme. Finally, we consider the computation of swap edges in an arbitrary spanning tree, where swap edges are chosen to minimize the time required to adapt routing in case of a failure, and give efficient distributed algorithms for two variants of this problem.

We consider sensor self-deployment problem, constructing FOCUSED coverage (F-coverage) around a Point of Interest (POI), with novel evaluation metric, coverage radius. We propose to deploy sensors in polygon layers over a locally computable equilateral triangle tessellation (TT) for optimal F-coverage formation, and introduce two types of deployment polygon, H-polygon and C-polygon. We propose two strictly localized solution algorithms, Greedy Advance (GA), and Greedy-Rotation-Greedy (GRG). The two algorithms drive sensors to move along the TT graph to surround POI. In GA, nodes greedily proceed as close to POI as they can; in GRG, when their greedy advance is blocked, nodes rotate around POI along locally computed H- or C-polygon to a vertex where greedy advance can resume. We prove that they both yield a connected network with maximized hole-free area coverage. To our knowledge, they are the first localized sensor self-deployment algorithms that provide such coverage guarantee. We further analyze their coverage radius property. Our study shows that GRG guarantees optimal or near optimal coverage radius. Through extensive simulation we as well evaluate their performance on convergence time, energy consumption, and node collision.

Energy management has become one of the main hurdles in the quest for autonomous and reliable Wireless Sensor Networks (WSN). This paper examines the emerging problem of increasing network availability by recharging, replacing or redeploying depleted sensors with the help of mobile entities. When mobility becomes a sensor's attribute and service stations are static, we propose passive vs. pro-active approaches to energy redistribution and restoration. In particular, for pro-active approaches, we study the mobility strategies and underlying topologies that guarantee a successful sensor recharge. The experimental results so far show that taking our novel pro-active approach to energy redistribution and network fatigue outperforms passive strategies. The proposed closest-first swapping-based mobility strategy provides the best overall performance among all the pro-active approaches studied and the proposed Compass Directed Unit Graph provides an efficient and flexible underlying topology to achieve energy equilibrium.

We study the computational power of a distributed system consisting of simple autonomous robots moving on the plane. The robots are endowed with visual perception but do not have any means of explicit communication with each other, and have no memory of the past. In the extensive literature it has been shown how such simple robots can form a single geometric pattern (e.g., a line, a circle, etc), however arbitrary, in spite of their obliviousness. This brings to the front the natural research question: what are the real computational limits imposed by the robots being oblivious? In particular, since obliviousness limits what can be remembered, under what conditions can oblivious robots form a series of geometric patterns? Notice that a series of patterns would create some form of memory in an otherwise memory-less system. In this paper we examine and answer this question showing that, under particular conditions, oblivious robot systems can indeed form series of geometric patterns starting from any arbitrary configuration. More precisely, we study the series of patterns that can be formed by robot systems under various restrictions such as anonymity, asynchrony and lack of common orientation. These results are the first strong indication that oblivious solutions may be obtained also for tasks that intuitively seem to require memory.

Focused coverage is defined as the coverage of a wireless sensor network surrounding a point of interest (POI), and is measured by coverage radius, i.e., minimum distance from POI to uncovered areas. Sensor self-deployment algorithm GRG is designed for autonomous focused coverage formation. It however does not always produce optimal (i.e., maximized) coverage radius. In this paper, we propose optimized GRG, referred to as OGRG, for guaranteed coverage radius maximization, and evaluate its performance in comparison with GRG.

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.

We consider the map construction problem in a simple, connected graph by a set of mobile computation entities or agents that start from scattered locations throughout the graph. The problem is further complicated by dangerous elements, nodes and links, in the graph that eliminate agents traversing or arriving at them. The agents working in the graph communicate using a limited amount of storage at each node and work asynchronously. We present a deterministic algorithm that solves the exploration and map construction problems. The end result is also a rooted spanning tree and the election of a leader. The total cost of the algorithm is O(nsm) total number of moves, where m is the number of links in the network and nsis the number of safe nodes, improving the existing O(m2) bound.

We pinpoint a new sensor self-deployment problem, constructing focused coverage around a point of interest (POI), and introduce an evaluation metric, coverage radius. We propose two solutions, greedy advance (GA) and greedy-rotation-greedy (GRG), which are to our knowledge the first sensor self-deployment algorithms that operate in a purely localized manner and yet provide coverage guarantee. The two algorithms drive sensors to move along a locally-computed equilateral triangle tessellation (TT) to surround POI. In GA, nodes greedily proceed as close to POI as they can; in GRG, when their greedy advance is blocked, nodes rotate around POI to a TT vertex where greedy advance can resume. They both yield a connected network of TT layout with hole-free coverage; GRG furthermore assures a hexagon coverage shape centered at POI. We prove their correctness and analyze their coverage radius property. Our study shows that GRG guarantees optimal hexagonal coverage radius and near optimal circular coverage radius. Through extensive simulation we as well evaluate their performance on convergence time, energy consumption, and node collision.

The continuous growth of wireless sensor networks demands new approaches to efficiently manage and service them. We present an approximation solution to the facility location problem for sensor network maintenance based on static sensors and mobile facilities. The main goal is to increase the network lifetime by recharging or redeploying sensors with the help of mobile multi-purpose maintenance facilities. Our problem is a variant of the facility location problem (FLP). In our case, we need to find a suitable deployment of the facilities where their workload is balanced and the movement of the facilities in their areas is minimized. This should be accomplished keeping the number of sensor communications at minimum. While finding the optimal placement of the maintenance facilities is a NP-hard problem, we show a simple and efficient solution, totally distributed and localized, which starting with a balanced deployment, progresses to a final partition of remarkable quality. Such final partition satisfies the load balancing requirement and minimizes the facility travel times. The experimental analysis of our distributed and localized solution shows that sensor message cost remains low as the size of the network increases. The experiments also show a load distribution similar and sometimes better than centralized deployment solutions.

We formalize the distance-sensitive service discovery problem in wireless sensor and actor networks, and propose a novel localized algorithm, iMesh. Unlike existing solutions, iMesh uses no global computation and generates constant per-node storage load. In iMesh, new service providers (i.e., actors) publish their location information in four directions, updating an information mesh. Information propagation for relatively remote services is restricted by a blocking rule, which also updates the mesh structure. Based on an extension rule, nodes along mesh edges may further advertise newly arrived relatively near service by backward distance-limited transmissions, replacing previously closer service location. The final information mesh is a planar structure constituted by the information propagation paths. It stores locations of all the service providers and serves as service directory. Service consumers (i.e., sensors) conduct a lookup process restricted within their home mesh cells to discover nearby services. We analytically study the properties of iMesh including construction cost and distance sensitivity over a static network model. We evaluate its performance in static/dynamic network scenarios through extensive simulation. Simulation results verify our theoretical findings and show that iMesh guarantees nearby (closest) service selection with very high probability, Gt99 percent (respectively, Gt95 percent).

A black hole is a highly harmful host that disposes of visiting agents upon their arrival without any observable trace of the destruction. The problem of locating the black hole in asynchronous ring network is known to be solvable by a team of mobile agents if each node is equipped with a whiteboard. A simpler and less expensive inter-communication and synchronization mechanism is provided by tokens: each agent has available a bounded number of tokens that can be carried, placed in a node or/and on a port of the node, or removed. All tokens are identical and no other form of communication or coordination is available to the agents. It is known that locating the black hole in an anonymous ring network using tokens is feasible when the team of agents is initially collocated (i.e. they all start from the same host). Recently, the more difficult case when the agents are scattered (i.e., when the agents do not start from the same host) has also been examined and solutions requiring only O(1) tokens per agent but using a total of O(n2) moves have been presented. The number of moves can be reduced to O(kn + n log n) if the number k of agents is known. In this paper, we study the impact of orientation and knowledge of team size on the cost of black hole location by scattered agents with tokens. We prove that, in oriented rings, the number of moves can be reduced from O(n2) to the optimal Theta(nlogn) using only O(1) tokens per agent, without any knowledge of the team size. This result holds even if both agents and nodes are anonymous. Interestingly, the proposed algorithm solves, with the same cost, also the leader election problem and the rendezvous problem for the scattered agents despite the presence of a BH.

In this paper we consider a dangerous process located at a node of a network (called Black Hole ) and a team of mobile agents deployed to locate that node. The nature of the danger is such that when an agent enters the dangerous node, it is trapped there leaving no trace of its destruction. The goal is to deploy as few agents as possible and to locate the black hole in as few moves as possible. We present a simple algorithm that works on any topology (a-priori known by the agents). Our algorithm, based on the pre-computation of an open vertex cover by cycles of the network, uses the optimal number of agents (two); its cost (number of moves) depends on the choice of the cover and it is optimal for several classes of networks.

We consider the problem of decontaminating a network infected by a mobile virus. The goal is to perform the task using as small a team of antiviral agents, avoiding any recontamination of disinfected areas, and minimizing the amount of agents' movements across the network. In all the existing literature, it is assumed that the immunity level of a disinfected site is nil. In this paper we consider the network decontamination problem under a new model of immunity to recontamination: we consider the case when a disinfected vertex, after the cleaning agent has gone, will become recontaminated only if a weak majority of its neighbours are infected. We study the effects of this level of immunity on the number of antiviral agents necessary to decontaminate the entire network. We focus on tori and on trees, and establish lower-bounds on the team size; we also establish lower bounds on the number of moves performed by an optimal-size time of cleaners. We design and present strategies for disinfecting tori and trees; we prove that these strategies are optimal in terms of both team size and number of moves. In particular, the upper and lower bounds are tight for tree networks and for synchronous tori; the bounds are within a constant factor of each other in the case of asynchronous tori.

In mobile sensor networks, self-deployment and relocation are two different research issues, both of which involve autonomous sensor movement. They share in most cases a common goal, that is, to improve overall network sensing coverage. Under this circumstance, some self-deployment algorithms may be applied to solving relocation problem without modification. However, considering efficiency, they will not be a good option in the scenario with high sensor failure rate. Existing sensor relocation protocols are not quite practical because they rely on strong assumptions and/or have weakness in maintaining network topology. In this paper, we propose a distributed zone-based sensor relocation protocol, ZONER, for mobile sensor networks on the basis of a restricted flooding technique, i.e., ZFlooding. Requiring zero-knowledge about sensor field, the ZONER is able to effectively discover previously-deployed redundant sensors without being concerned with obstacles or network ununiformity, and it relocates them in a shifting way to replace failed non-redundant ones without changing network topology. At the end of the paper, we prove the correctness of the ZONER and point out our future work

Abstract Mobile agents operating in networked environments face threats from other agents as well as from the hosts (i.e., network sites) they visit. A black hole is a harmful host that destroys incoming agents without leaving any trace. To determine the location of such a harmful host is a dangerous but crucial task, called black hole search. The most important parameter for a solution strategy is the number of agents it requires (the size); the other parameter of interest is the total number of moves performed by the agents (the cost). It is known that at least two agents are needed; furthermore, with full topological knowledge, Ω(n log n) moves are required in arbitrary networks. The natural question is whether, in specific networks, it is possible to obtain (topology‐dependent but) more cost efficient solutions. It is known that this is not the case for rings. In this article, we show that this negative result does not generalizes. In fact, we present a general strategy that allows two agents to locate the black hole with O(n) moves in common interconnection networks: hypercubes, cube‐connected cycles, star graphs, wrapped butterflies, chordal rings, as well as in multidimensional meshes and tori of restricted diameter. These results hold even if the networks are anonymous. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(2), 61–71 2006

In the rendezvous search problem, two mobile agents must move along the n nodes of a network so as to minimize the time required to meet or rendezvous. When the mobile agents are identical and the network is anonymous, however, the resulting symmetry can make the problem impossible to solve. Symmetry is typically broken by having the mobile agents run either a randomized algorithm or different deterministic algorithms. We investigate the use of identical tokens to break symmetry so that the two mobile agents can run the same deterministic algorithm. After deriving the explicit conditions under which identical tokens can be used to break symmetry on the n node ring, we derive the lower and upper bounds for the time and memory complexity of the rendezvous search problem with various parameter sets. While these results suggest a possible tradeoff between the mobile agents' memory and the time complexity of the rendezvous search problem, we prove that this tradeoff is limited.

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.

Studies on the relationship between label consistency, computability, and complexity assume the existence of local orientation; this assumption is in fact at the basis of the point-to-point model and is realistic for systems where a communication link can connect only two entities. However, in systems which use more advanced communication and interconnection technology, such as buses, optical networks, and wireless communication media, and more importantly, in heterogeneous systems (such as the Internet) which include any combination of the above, local orientation cannot be assumed. This implies that the entire established body of results on the relationship between label consistency (e.g., sense of direction}) and computability and complexity does not hold for systems with advanced communication technology. In this paper we consider a new type of consistency which we shall call backward consistency and which, unlike sense of direction, can exist even without local orientation. Thus, unlike all previous forms of consistency, it can be found (or designed) in advanced distributed systems. We study backward consistency both in terms of its relationship with the traditional properties of local orientation and (weak) sense of direction, and with respect to symmetries of the edge labelings and of the naming functions. We show that backward consistency is computationally equivalent to sense of direction; in other words, it is possible to take advantage of the computational power of sense of direction even in the absence of local orientation.

Protecting agents from host attacks is a pressing security concern in networked environments supporting mobile agents. In this paper, we consider a black hole: a highly harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The task to identify the location of the harmful host is clearly dangerous for the searching agents. We study under what conditions and at what cost a team of autonomous asynchronous mobile agents can successfully accomplish this task; we are concerned with solutions that are generic (i.e., topology-independent). We study the size of the optimal solution (i.e., the minimum number of agents needed to locate the black hole), and the cost of the minimal solution (i.e., the number of moves performed by the agents executing a size-optimal solution protocol). We establish tight bounds on size and cost depending on the a priori knowledge the agents have about the network, and on the consistency of the local labellings. In particular, we prove that: with topological ignorance Δ + 1 agents are needed and suffice, and the cost is Θ(n2), where Δ is the maximal degree of a node and n is the number of the nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is Θ(n2); and with complete topological knowledge only two agents suffice and the cost is Θ(n log n). All the upper-bound proofs are constructive.

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.

An anonymous ring network is a ring where all processors (vertices) are totally indistinguishable except for their input value. Initially, to each vertex of the ring is associated a value from a totally ordered set; thus, forming a multiset. In this paper we consider the problem of sorting such a distributed multiset and we investigate its relationship with the election problem. We focus on the computability and the complexity of these problems, as well as on their interrelationship, providing strong characterizations, showing lower bounds, and establishing efficient upper bounds.

The studies on the relationship between label consistency, computability and complexity assume the existence of local orientation; this assumption is in fact at the basis of the point-to-point model and is realistic for systems where a communication link can connect only two entities.However, in systems which use more advanced communication and interconnection technology such as buses, optical networks, wireless communication media, etc., and more importantly, heterogeneous systems (such as internet) which include any combination of the above, local orientation can not be assumed.In this paper we consider a new type of consistency which we shall call backward consistency and which, unlike sense of direction, can exist even without local orientation.Thus, unlike all previous forms of consistency, it can be found (or designed) in advanced distributed systems.We study backward consistency both in terms of its relationship with the traditional properties of local orientation and (weak) sense of direction, and with respect to symmetries of the edge labelings and of the naming functions.We prove that backward consistency is computationally equivalent to sense of direction; in other words, it is possible to take advantage of the computational power of sense of direction even in absence of local orientation.'Research supported in part by F.C.A.R and N3.E.R.C permission to make digital or hard copies of all

An extensive body of evidence exists of the impact that specific edge labelings have on the communication complexity of distributed problems. It has been long suspected that these very different labelings share a common property, named sense of direction. In spite of the large number of investigations, and of the obvious practical importance, a formal characterization of this property did not exist. In this paper, we finally provide a formal definition of sense of direction, making explicit the very specific relationship between three factors: the labeling, the topological structure, and the local view that an entity has of the system. In a way, sense of direction is the capability of a node in the system to use the labeling to translate the local view of its neighbors into its own. Using the formal definition as an observational platform, we describe several properties which allow the translation process to be possible beyond the immediate neighborhood. Finally, we identify four general classes of labelings and analyze their properties; these classes include all the labelings used in the literature. © 1998 John Wiley & Sons, Inc. Networks 32: 165–180, 1998

Loop networks (or Hamiltonian circulant graphs) are a popular class of fault-tolerant network topologies which include rings and complete graphs. For this class, the fundamental problem of leader election has been extensively studied, assuming either a fault-free system or an upper-bound on the number of link failures. We consider loop networks where an arbitrary number of links have failed and a processor can only detect the status of its incident links. We show that a leader election protocol In a faulty loop network requires only O(n log n) messages in the worst-case, where n is the number of processors. Moreover, we show that this is optimal. The proposed algorithm also detects network partitions. We also show that it provides an optimal solution for arbitrary nonfaulty networks with sense of direction.

We consider the problem of selecting the Kth smallest element of a set distributed among the sites of a communication network when the size of messages is bounded; that is, each message is a packet which contains at most c bits, where c/spl ges/1 is a constant. A general selection algorithm using packets is presented and its packet complexity is analyzed. Its complexity is shown to be a significant improvement for a large range of packet sizes over the existing bounds. The proposed technique is then instanciated for specific classes of network topologies; the resulting bounds either match or improve the ones of existing solutions for a large range of values of the packet size. Furthermore, it is bit optimal in star networks.

In this paper we deal with the efficiency oftoken-based strategies for the basic problem of controlling the allocation of a shared resource in a ring of n processing entities. We propose new protocols that allow a bounded number of exchanged messages per access request to the resource, while this amount is unbounded for classical solutions. We also guarantee all the requests to be served within a maximum delay. The new proposed protocols are request-message-based strategies, in that a process entity sends a message to “inform” the token of the access request.

We study the positive impact that the availability of Sense of Direction has on the message complexity of the election problem in arbitrary networks of processors. We present a /spl Theta/(n log n) solution; without sense of direction, this problem requires /spl Omega/(e+nlogn) messages where e is the number of communication links. This result confirms and extends the evidence on the impact of sense of direction which, up to now, was established only for specific classes of topologies. >

Given two geometric sets A and B, it is said that A is containable in B provided A is isometric to a subset of B. Containability induces a partial order on any set of geometric figures, such as rectangles in the plane. A recent result states that for the set of rectangles in the plane, the containability partial order is of countably infinite dimension. In this paper the rectangle result is extended to other families of geometric figures and to a partial order obtained from quadratic polynomials.

The problem of selecting the Kth smallest element of a set of N elements distributed among d sites of a communication network is examined. A reduction technique is a distributed algorithm that transforms this problem to an equivalent one where either K or N (or both) are reduced. A collection of distributed reduction techniques is presented; the combined use of the algorithms offers new solutions for the selection problem in shout-echo networks and in a class of point-to-point networks. The communication complexity of these solutions is analyzed and shown to represent an improvement on the multiplicative constant of existing bounds for those networks.>

A parallel algorithm is described for merging two sorted vectors of total length N. The algorithm runs on a shared-memory model of parallel computation that disallows more than one processor to simultaneously read from or write into the same memory location. It uses k processors where l ≤ k ≤ N and requires O(N/k + log k × log N) time. The proposed approach for merging leads to a parallel sorting algorithm that sorts a vector of length N in O(log2k + N/k) log N) time. Because they modify their behavior and hence their running time according to the number of available processors, the two new algorithms are said to be self-reconfiguring. In addition, both algorithms are optimal, for k ≤ N/log2N, in view of the Ω(N) and Ω(N log N) lower bounds on merging and sorting, respectively.

Abstract An algorithm for selecting the kth smallest element of a distributed file using shout‐echo communication primitives is presented. It is shown that, for large values of k (e. g., the median), the proposed algorithm improves the existing upperbound.

The problem of assigningncarrier frequencies so as to avoid certain types (third and fifth order) of intermodulation interference is discussed. For the third-order case, close upper and lower bounds on the optimal solution are established; and close to optimal solutions are given forn < 100(previously, suboptimal solutions were known only forn \leq 23). For the fifth-order case, it is shown that some existing results can be applied to this problem, and suboptimal solutions obtained by this construction are given forn \leq 17(no solutions were known previously).

The problem of sorting a file distributed over a number of sites of a communication network is examined. Two versions of this problem are investigated; distributed solution algorithms are presented; and their communication complexity analyzed both in the worst and in the average case. The worst case bounds are shown to be sharp, with respect to order of magnitude, for large files.

The problem of determining in a distributed fashion the centers and the medians of a network is considered.Lower bounds on the time needed to solve these problems are proved.Algorithms that achieve those bounds for tree networks are presented; the number of exchanged messages is linear in the number of nodes.These techniques are extended to work on general networks in O(n) time units exchanging O(n.e) messages, where n is the number of nodes and e the number of edges in the network.In addition, a comparison with a simple heuristic approach is included.