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.

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.

Fog computing can play an important role in Vehicular Ad Hoc Networks (VANETs) in enhancing the quality of fog-based services. The idea of partial reliance on fog computing to support the existing infrastructure has been explored in few research papers. Fog computing holds the promise of significant potential benefits to edge users. The capabilities of fog and its position (i.e., the proximity from edge users) give fog the power to play a vital role in employing the most competent node. In other words, fog can reduce the workload that is required to do by the vehicles (e.g., propagating the event’s details, and evaluating the trust of the sender). In this paper, we deploy fog nodes to gather the trust evaluations from the vehicles, which allow fog nodes to rely on their local vehicles to do certain tasks. Also, fog nodes are used in this work to keep the records of its local vehicles to reduce the need to communicate with the cloud. Also, we proposed a scheme using Task-based Experience Reputation (TER), which reflects the vehicle’s reputation in performing certain tasks. Finally, we shed the light on the issue of two commonly used trust updating methods and, we proposed applying the concept of TER to solve this issue. The proposed model reduces the message transmission overhead and workload on the vehicles compared to experience-based trust models.

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.

Vehicular ad hoc networks (VANETs) have drawn a lot of attention in recent years due to their potential in improving traffic safety applications. Evaluating trust between peers in such networks is an essential component that determines whether a received report from a neighboring vehicle should be accepted or refused. For this purpose, many VANET trust management models have been proposed, differing in their architecture, trust establishment process, and flexibility. However, risk estimation has not been taken into consideration in all of these models. In this paper, we propose a risk-based trust evaluation model that overcomes the information oversampling issue in VANETs. The proposed model provides a decision-making process for vehicles receiving conflicting reports regarding an event's occurrence according to the risk estimation for each required action of both reports. The risk is estimated according to the likelihood of taking an incorrect action and its associated impact. Finally, a decision is made corresponding to the action with the lowest risk. We show that a risk-based decision-making scheme may take different actions than a purely trust-based method. Simulation results show that the risk-based trust model outperforms a purely trust-based model.

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.

The temporal component of social networks is often neglected in their analysis, and statistical measures are typically performed on a "static" representation of the network. As a result, measures of importance (like betweenness centrality) cannot reveal any temporal role of the entities involved. Our goal is to start filling this limitation by proposing a form of temporal betweenness measure, and by using it to analyse a knowledge mobilization network. We show that this measure, which takes time explicitly into account, allows us to detect centrality roles that were completely hidden in the classical statistical analysis. In particular, we uncover nodes whose static centrality was considered negligible, but whose temporal role is instead important to accelerate mobilization flow in the network. We also observe the reverse behaviour by detecting nodes with high static centrality, whose role as temporal bridges is instead very low. By revealing important temporal roles, this study is a first step towards a better understanding of the impact of time in social networks, and opens the road to further investigation.

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.

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.

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.

Abstract In this article we consider the decontamination problem in a hypercube network of size n. The nodes of the network are assumed to be contaminated and they have to be decontaminated by a sufficient number of agents. An agent is a mobile entity that asynchronously moves along the network links and decontaminates all the nodes it touches. A decontaminated node that is not occupied by an agent is re‐contaminated if it has a contaminated neighbor. We consider some variations of the model based on the capabilities of mobile agents: locality, where the agents can only access local information; visibility, where they can “see” the state of their neighbors; and cloning, where they can create copies of themselves. We also consider synchronicity as an alternative system requirement. For each model, we design a decontamination strategy and we make several observations. For agents with locality, our strategy is based on the use of a coordinator that leads the other agents. Our strategy results in an optimal number of agents, $\Theta ({n \over \sqrt{\log n}})$ , and requires O(n log n) moves and O(n log n) time steps. For agents with visibility, we assume that the agents can move autonomously. In this setting, our decontamination strategy achieves an optimal time complexity (log n time steps), but the number of agents increases to $ {n \over 2}$ . Finally, we show that when the agents have the capability to clone combined with either visibility or synchronicity, we can reduce the move complexity—which becomes optimal—at the expense of an increase in the number of agents. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

Peer-to-peer systems can share the computing resources and services by directly communicating within a widely distributed network. It is important that these systems can efficiently locate, in as few hops as possible, the node storing the desired data in a large system. Thus, it is worth consuming some extra storage to obtain better routing performance. In this paper, we propose redundant strategies to improve the routing performance and data availability on Chord and De Bruijn topologies. Hybrid-Chord combines multiple chord rings and successors, and Redundant D2B maintains successors, to improve the routing performance. The proposed systems can reduce the number of lookup hops significantly (by as much as 50%) compared to the original ones, and have better fault tolerance capabilities, with a small storage overhead.

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.

In this paper we consider the map construction problem in the case of an anonymous, unoriented torus of unknown size. An agent that can move from node to neighbouring node in the torus is initially placed in an arbitrary node and has to construct an edge-labeled map. In other words, it has to draw in its local memory an edge-labeled torus isomorphic to the one it is moving on. The agent has enough local memory to represent the torus and one or two tokens that can be dropped on and picked up from nodes. Efficiency is measured in terms of number of moves performed by the agent. When the agent has no token available, the problem is clearly unsolvable. In the paper we show that, when the agent has one token available there exists an optimal algorithm for constructing the map of the torus; the agent, in fact, performs /spl Theta/(N) moves (where N is the number of nodes of the torus). Before showing the optimal solution with the optimal number of tokens, we describe a simpler solution that works when two tokens are available, we then modify it to obtain the same bound when the agent has only one token available.

In this paper, we consider the problem of decontaminating a network, i.e., protecting it from unwanted and dangerous intrusions. Initially all nodes are contaminated and a team of agents is deployed to clean the entire network. When an agent transits on a node, it can clean it, when the node is left unguarded, however, it will be recontaminated as soon as at least one of its neighbour is contaminated. We study the problem in asynchronous chordal ring networks with n nodes and chord lengths d/sub 1/ = 1, d/sub 2/, ..., d/sub k/, and in tori. We consider two variations of the model: one where an agent has only local knowledge, the other in which it has "visibility", i.e., it can "see" the state of its neighbouring nodes. We first show that, when the largest chord d/sub k/ is not too large (d/sub k/ /spl les/ /spl radic/n), the number of agents necessary to perform the task in chordal rings does not depend on the size of the network but only on the length of the longest chord. We also show a lower bound on the number of agents for the torus topology. We then propose tight strategies for decontamination. We analyse the number of moves and the time complexity of the decontamination algorithms showing that the visibility assumption allows us to decrease substantially both complexity measures. Another advantage of the "visibility model" is that agents move independently and autonomously without requiring any coordination.

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

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.

The next-generation (NG) wireless systems are envisioned to integrate the current communication systems into a seamless infrastructure, capable of allowing mobile users (MU) to access a wide range of high bandwidth wireless services. This integration of heterogeneous networks makes it difficult to locate MU as these MU move across networks using different access technologies and protocols. In this context, global roaming management constitutes a challenging problem. This paper presents an efficient approach which facilitates interoperability between heterogeneous networks during global roaming situations. Preliminary results reveal that such an approach significantly improves the performance of the NG wireless systems in terms of generated signaling traffic and response time during the global roaming process.

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

We consider the problem of routing messages on Series Parallel Graphs (SPGs) and we introduce a new technique called Distance Routing. This technique is based on the idea of encoding in the label of each node x some information about a shortest path from the source of the SPG to x, and from x to the terminal node of the SPG. We first compare shortest path Distance Routing and I-interval Routing Schemes on directed SPGs. We then show that Distance Routing can be used to route on bidirectional SPGs, where no general shortest path I-interval Routing Scheme can be applied. We also show the relevance of the study of the time complexity in the choice of a Compact Routing method.

This paper describes a system able to recognize human faces from different perspectives, and which have different expressions. It possibly presents some kind of noise in their representation. The problem of face recognition has been approached using a complex architecture based on a hierarchy of neural networks, with a particular self-referencing structure. The system, in fact, is structured as a tree in which nodes correspond to neural networks, each one having different tasks. Each leaf is a recognition module composed by some networks with different characteristics depending on the different preprocessing operators used. These networks are coordinated by a supervisor in a self-referencing structure. During the training phase, the supervisor, called Meta-Net, observes the behaviour of recognition nets and learns which net is more able in which task, while during the test phase it decides, given an input image, which weights to assign to each network and modifies their output in order to obtain the final result. This architecture shows a high generalization capability and allows the recognition of images with different kinds of noise better than what each single network can do, as confirmed by a preliminary experimental evaluation.