Search

Consider n identical relocatable sensors , with sensing range r and visibility range 2 r , initially placed at arbitrary positions on a line segment barrier; each sensor can detect the presence of an intruder in its sensing range, and is said to cover the portion of the barrier that intersects with its sensing range. Sensors operate in Look-Compute-Move cycles: in a cycle a sensor determines the positions of sensors in its visibility range, it computes its next position (within its visibility range), and then moves to the calculated position. The barrier coverage problem we consider is for the sensors to independently make decisions and movements so to reach final positions whereby they collectively cover the barrier; in particular we are interested in oblivious (or memoryless) sensors, and focus on the impact that the level of synchrony and the presence/absence of orientation (i.e., global notion of "left-right") have on the solvability of the problem. It is known that without orientation, oblivious sensors can solve the problem if they are fully synchronous (i.e., they operate in synchronous rounds and are all active at every round). In this paper, we prove that orientation is critical to being able to solve the problem if we relax the assumption of full synchronization. We first show that if sensors are unoriented, then barrier coverage is unsolvable even in the semi-synchronous setting. In contrast, if sensors agree on a global orientation, then we give an algorithm for barrier coverage, even in the completely asynchronous setting. Finally, we extend the existing result of Cohen and Peleg and show that convergence to barrier coverage by unoriented sensors in the semi-synchronous model is possible with bounded visibility range 2 r + ρ (for arbitrarily small ρ > 0) and bounded mobility range r. [ABSTRACT FROM AUTHOR]

The gathering (or multi-agent rendezvous) problem requires a set of mobile agents, arbitrarily positioned at different nodes of a network to group within finite time at the same location, not fixed in advanced. The extensive existing literature on this problem shares the same fundamental assumption: the topological structure does not change during the rendezvous or the gathering; this is true also for those investigations that consider faulty nodes. In other words, they only consider static graphs. In this paper we start the investigation of gathering in dynamic graphs , that is networks where the topology changes continuously and at unpredictable locations. We study the feasibility of gathering mobile agents, identical and without explicit communication capabilities, in a dynamic ring of anonymous nodes; the class of dynamics we consider is the classic 1-interval-connectivity ; i.e., dynamic graphs that are however connected at any point in time. We focus on the impact that factors such as chirality (i.e., a common sense of orientation) and cross detection (i.e., the ability to detect, when traversing an edge, whether some agent is traversing it in the other direction), have on the solvability of the problem; and we establish several results. We provide a complete characterization of the classes of initial configurations from which the gathering problem is solvable in presence and in absence of cross detection and of chirality. The feasibility results of the characterization are all constructive: we provide distributed algorithms that allow the agents to gather within low polynomial time. In particular, the algorithms for gathering with cross detection are time optimal. We also show that cross detection is a powerful computational element. Indeed, we prove that, without chirality, knowledge of the ring size n is strictly more powerful than knowledge of the number k of agents; on the other hand, with chirality, knowledge of n can be substituted by knowledge of k , yielding the same classes of feasible initial configurations. From our investigation it follows that, for the gathering problem, the computational obstacles created by the dynamic nature of the ring can be overcome by the presence of chirality or of cross-detection. [ABSTRACT FROM AUTHOR]

Abstract We consider the problem of simulating traditional population protocols under weaker models of communication, which include one-way interactions (as opposed to two-way interactions) and omission faults (i.e., failure by an agent to read its partner's state during an interaction), which in turn may be detectable or undetectable. We focus on the impact of a leader, and we give a complete characterization of the models in which the presence of a unique leader in the system allows the construction of simulators: when simulations are possible, we give explicit protocols; when they are not, we give proofs of impossibility. Specifically, if each agent has only a finite amount of memory, the simulation is possible only if there are no omission faults. If agents have an unbounded amount of memory, the simulation is possible as long as interactions are detectable. If an upper bound on the number of omissions involving the leader is known, the simulation is possible in all omissive models. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph where every node is colored either black or white. Consider now the following repetitive process on G: each node recolors itself, at each local time step, with the color held by the majority of its neighbors. Depending on the initial assignment of colors to the nodes and on the definition of majority, different dynamics can occur. We are interested in dynamos; i.e., initial assignments of colors which lead the system to a monochromatic configuration in a finite number of steps. In the context of distributed computing and communication networks, this repetitive process is particularly important in that it describes the impact that a set of initial faults can have in majority-based systems (where black nodes correspond to faulty elements and white to non-faulty ones). In this paper, we study two particular forms of dynamos (irreversible and monotone) in tori, focusing on the minimum number of initial black elements needed to reach the fixed point. We derive lower and upper bounds on the size of dynamos for three types of tori, under different assumptions on the majority rule (simple and strong). These bounds are tight within an additive constant. The upper bounds are constructive: for each topology and each majority rule, we exhibit a dynamo of the claimed size. [Copyright &y& Elsevier]

We consider a well-known distributed colouring game played on a simple connected graph: initially, each vertex is coloured black or white; at each round, each vertex simultaneously recolours itself by the colour of the simple (strong) majority of its neighbours. A set of vertices M is said to be a dynamo, if starting the game with only the vertices of M coloured black, the computation eventually reaches an all-black configuration.The importance of this game follows from the fact that it models the spread of faults in point-to-point systems with majority-based voting; in particular, dynamos correspond to those sets of initial failures which will lead the entire system to fail. Investigations on dynamos have been extensive but restricted to establishing tight bounds on the size (i.e., how small a dynamic monopoly might be).In this paper we start to study dynamos systematically with respect to both the size and the time (i.e., how many rounds are needed to reach all-black configuration) in various models and topologies.We derive tight tradeoffs between the size and the time for a number of regular graphs, including rings, complete d-ary trees, tori, wrapped butterflies, cube connected cycles and hypercubes. In addition, we determine optimal size bounds of irreversible dynamos for butterflies and shuffle-exchange using simple majority and for DeBruijn using strong majority rules. Finally, we make some observations concerning irreversible versus reversible monotone models and slow complete computations from minimal dynamos. [Copyright &y& Elsevier]