Search

In this paper we consider a network where an intruder is moving "contaminating" the nodes it passes by, and we focus on the problem of decontaminating such a network by a team of mobile agents. The contamination/decontamination process has the following asynchronous dynamics: when the team is deployed all nodes are assumed to be contaminated, when an agent transits on a node, it will clean the node, when the node is left with no agent, the node will be recontaminated as soon as at least one of its neighbours is contaminated. We study the problem in asynchronous chordal ring networks and in tori. We consider two variations of the model: one where agents have only local knowledge, the other in which they have "visibility", i.e., they can "see" the state of their neighbouring nodes. We first derive lower bounds on the minimum number of agents necessary for the decontamination. In the case of chordal rings we show that the number of agents necessary to perform the cleaning does not depend on the size of the network; in fact it is linear in the length of the longest chord (provided that it is not too long). In the case of a torus, the minimum number of agents is equal to 2 · h, where h is the smallest dimension. We then propose optimal strategies for decontamination and 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 FROM AUTHOR]

Sprouts is a two players game that was first introduced by M.S. Patterson and J.H. Conway in 1967. There are two players A and B that, starting from a set of x0 vertices, build a graph by alternatively connecting any two vertices with degree less than three with an edge, and by drawing a new vertex on this new edge. A move is allowed only if the new connection maintains the planarity of the graph. The player that executes the last possible move is the winner. We study some new topological properties of this game and we show their effectiveness by giving a complete analysis of the case x0=7 for which, to the best of our knowledge, no formal proof has been previously given. [Copyright &y& Elsevier]

We consider the problem of routing in an asynchronous dynamically changing ring of processors using schemes that minimize the storage space for the routing information. In general, applying static techniques to a dynamic network would require significant re-computation. Moreover, the known dynamic techniques applied to the ring lead to inefficient schemes. In this paper we introduce a new technique, Dynamic Interval Routing, and we show tradeoffs between the stretch factor, the adaptation cost, and the size of the update messages used by routing schemes based upon it. We give three algorithms for rings of maximum size N: the first two are deterministic, one with adaptation cost zero but worst case stretch factor (N/2) the other with worst case adaptation cost O(N) update messages of O(log N) bits and stretch factor 1. The third algorithm is randomized, uses update messages of size O(k log N), has adaptation cost O(k), and expected stretch factor 1 + 1/k, for any integer k ≥ 3. All schemes require O(log N) bits per node for the routing information and all messages headers are of O(log N) bits. [ABSTRACT FROM AUTHOR]

Abstract This paper studies the well-known problem of gathering multiple mobile agents moving in a graph, but unlike previous results, we consider the problem in the presence of an adversarial mobile entity which we call the malicious agent. The malicious entity can occupy any empty node and prevent honest mobile agents from entering this node. This new adversarial model is interesting as it models transient mobile faults that can appear anywhere in a network. Moreover, our model lies between the less powerful delay-fault model , where the adversary can block an agent for only a finite time, and the more powerful but static fault model of black holes that can even destroy the agents. We study the problem for ring networks and we provide a complete characterization of the solvability of gathering, depending on the size n of the ring and the number of agents k. We consider both oriented or unoriented rings with either synchronous or asynchronous agents. We prove that in an unoriented ring network with asynchronous agents the problem is not solvable when k is even, while for synchronous agents the problem is unsolvable when both n is odd and k is even. We then present algorithms that solve gathering for all the remaining cases, thus completely solving the problem. Finally, we provide a proof-of-concept implementation of the synchronous algorithms using programmable Lego Mindstorms EV3 robots. [ABSTRACT FROM AUTHOR]

A new algorithm is introduced for analyzing possible nestings in mobile ambient calculus. It improves both time and space complexities of the technique proposed by Nielson and Seidl. The improvements are achieved by enhancing the data structure representations, and by reducing the computation to the control flow analysis constraints that are effectively necessary to get to the least solution. These theoretical results are also supported by experimental tests run on a Java-based tool that implements a suite of algorithms for nesting analysis of mobile ambients. [Copyright &y& Elsevier]