Search

We study properties of multiple random walks on a graph under various assumptions of interaction between the particles. To give precise results, we make our analysis for random regular graphs. The cover time of a random walk on a random r-regular graph was studied in [6], where it was shown with high probability (whp), that for r ≥ 3 the cover time is asymptotic to θrn ln n, where θr = (r − 1)/(r − 2). In this paper we prove the following (whp) results. For k independent walks on a random regular graph G, the cover time CG(k) is asymptotic to CG/k, where CG is the cover time of a single walk. For most starting positions, the expected number of steps before any of the walks meet is ]> . If the walks can communicate when meeting at a vertex, we show that, for most starting positions, the expected time for k walks to broadcast a single piece of information to each other is asymptotic to 2θrn (ln k)/k, as k,n → ∞. We also establish properties of walks where there are two types of particles, predator and prey, or where particles interact when they meet at a vertex by coalescing, or by annihilating each other. For example, the expected extinction time of k explosive particles (k even) tends to (2ln 2) θrn as k→ ∞. The case of n coalescing particles, where one particle is initially located at each vertex, corresponds to a voter model defined as follows: Initially each vertex has a distinct opinion, and at each step each vertex changes its opinion to that of a random neighbour. The expected time for a unique opinion to emerge is the expected time for all the particles to coalesce, which is asymptotic to 2 θrn. Combining results from the predator-prey and multiple random walk models allows us to compare expected detection time in the following cops and robbers scenarios: both the predator and the prey move randomly, the prey moves randomly and the predators stay fixed, the predators move randomly and the prey stays fixed. In all cases, with k predators and ℓ prey the expected detection time is θrHℓn/k, where Hℓ is the ℓ-th harmonic number. [ABSTRACT FROM AUTHOR]

We consider the model of exploration of an undirected graph G by a single agent which is called the rotor-router mechanism or the Propp machine (among other names). Let Πv indicate the edge adjacent to a node v which the agent took on its last exit from v. The next time when the agent enters node v, first a ˵rotor″ at node v advances pointer Πv to the edge ]> which is next after the edge Πv in a fixed cyclic order of the edges adjacent to v. Then the agent is directed onto edge Πv to move to the next node. It was shown before that after initial O(mD) steps, the agent periodically follows one established Eulerian cycle, that is, in each period of 2m consecutive steps the agent traverses each edge exactly twice, once in each direction. The parameters m and D are the number of edges in G and the diameter of G. We investigate robustness of such exploration in presence of faults in the pointers Πv or dynamic changes in the graph. We show that after the exploration establishes an Eulerian cycle, if at some step the values of k pointers Πv are arbitrarily changed, then a new Eulerian cycle is established within O(km) steps; if at some step k edges are added to the graph, then a new Eulerian cycle is established within O(km) steps; if at some step an edge is deleted from the graph, then a new Eulerian cycle is established within O(νm) steps, where ν is the smallest number of edges in a cycle in graph G containing the deleted edge. Our proofs are based on the relation between Eulerian cycles and spanning trees known as the ˵BEST″ Theorem (after de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte). [ABSTRACT FROM AUTHOR]

We consider a fixed, undirected, known network and a number of ˵mobile agents″ which can traverse the network in synchronized steps. Some nodes in the network may be faulty and the agents are to find the faults and repair them. The agents could be software agents, if the underlying network represents a computer network, or robots, if the underlying network represents some potentially hazardous physical terrain. Assuming that the first agent encountering a faulty node can immediately repair it, it is easy to see that the number of steps necessary and sufficient to complete this task is Θ(n/k + D), where n is the number of nodes in the network, D is the diameter of the network, and k is the number of agents. We consider the case where one agent can repair only one faulty node. After repairing the fault, the agent dies. We show that a simple deterministic algorithm for this problem terminates within O(n/k + Dlogf/loglogf) steps, where f =  min {n/k, n/D}, assuming that the number of faulty nodes is at most k/2. We also demonstrate the worst-case asymptotic optimality of this algorithm by showing a network such that for any deterministic algorithm, there is a placement of k/2 faults forcing the algorithm to work for Ώ(n/k + Dlogf/loglogf) steps. [ABSTRACT FROM AUTHOR]

Efficient exploration of unknown or unmapped environments has become one of the fundamental problem domains in algorithm design. Its applications range from robot navigation in hazardous environments to rigorous searching, indexing and analysing digital data available on the Internet. A large number of exploration algorithms has been proposed under various assumptions about the capability of mobile (exploring) entities and various characteristics of the environment which are to be explored. This paper considers the graph model, where the environment is represented by a graph of connections in which discrete moves are permitted only along its edges. Designing efficient exploration algorithms in this model has been extensively studied under a diverse set of assumptions, e.g., directed vs undirected graphs, anonymous nodes vs nodes with distinct identities, deterministic vs probabilistic solutions, single vs multiple agent exploration, as well as in the context of different complexity measures including the time complexity, the memory consumption, and the use of other computational resources such as tokens and messages. In this work the emphasis is on memory efficient exploration of anonymous graphs. We discuss in more detail three approaches: random walk, Propp machine and basic walk, reviewing major relevant results, presenting recent developments, and commenting on directions for further research. [ABSTRACT FROM AUTHOR]

Radio networks model wireless data communication when bandwidth is limited to one wave frequency. The key restriction of such networks is mutual interference of packets arriving simultaneously to a node. The many-to-many (m2m) communication primitive involves p participant nodes of a distance at most d between any pair of them, from among n nodes in the network, and the task is to have all participants get to know all input messages. We consider three cases of the m2m communication problem. In the ad-hoc case, each participant knows only its name and the values of n, p and d. In the partially centralized case, each participant knows the topology of the network and the values of p and d, but does not know the names of other participants. In the centralized case each participant knows the topology of the network and the names of all the participants. For the centralized m2m problem, we give deterministic protocols, for both undirected and directed networks, working in O(d+p) time, which is provably optimal. For the partially centralized m2m problem, we give a randomized protocol for undirected networks working in O((d+p +log2n)log p) time with high probability (whp), and we show that any deterministic protocol requires Ώ(plogn/pn+d) time. For the ad-hoc m2m problem, we develop a randomized protocol for undirected networks that works in O((d+log p)log2n +plog p) time whp. We show two lower bounds for the ad-hoc m2m problem. One states that any m2m deterministic protocol requires Ώ(nlogn/d + 1n) time when n–p=Ώ(n) and d>1; Ώ(n) time when n–p=o(n); and Ώ(plogn/pn) time when d=1. The other lower bound states that any m2m randomized protocol requires Ώ(p+dlog(n/d+1)+log2n) expected time. [ABSTRACT FROM AUTHOR]

We consider a fixed communication network where (software) agents can move freely from node to node along the edges. A black hole is a faulty or malicious node in the network such that if an agent enters this node, then it immediately ˵dies.″ We are interested in designing an efficient communication algorithm for the agents to identify all black holes. We assume that we have k agents starting from the same node s and knowing the topology of the whole network. The agents move through the network in synchronous steps and can communicate only when they meet in a node. At the end of the exploration of the network, at least one agent must survive and must know the exact locations of the black holes. If the network has n nodes and b black holes, then any exploration algorithm needs Ώ(n/k + Db) steps in the worst-case, where Db is the worst case diameter of the network with at most b nodes deleted. We give a general algorithm which completes exploration in O((n/k)logn/loglogn + bDb) steps for arbitrary networks, if b≤k/2. In the case when b≤k/2, ]> and ]> , we give a refined algorithm which completes exploration in asymptotically optimal O(n/k) steps. [ABSTRACT FROM AUTHOR]

A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of locating all black holes in a network, through the exploration of its nodes by a set of mobile agents. In this paper we consider the problem of designing the fastest Black Hole Search, given the map of the network, the starting node and, possibly, a subset of nodes of the network initially known to be safe. We study the version of this problem that assumes that there is at most one black hole in the network and there are two agents, which move in synchronized steps. We prove that this problem is not polynomial-time approximable within $\frac{389}{388}$ (unless P=NP). We give a 6-approximation algorithm, thus improving on the 9.3-approximation algorithm from [3]. We also prove APX-hardness for a restricted version of the problem, in which only the starting node is initially known to be safe. Keywords: approximation algorithm, black hole search, graph exploration, mobile agent, inapproximability. [ABSTRACT FROM AUTHOR]

Numerous studies have shown that packet reordering is common, especially in satellite networks. Reordering of packets decreases the TCP performance of a network, mainly because it leads to overestimation of the congestion of the network. We consider satellite networks and analyze the performance of such networks when reordering of packets occurs. We propose a solution that could significantly improve the performance of the network when reordering of packets occurs in the satellite network. We report results of our simulation experiments, which support this claim. Our solution is based on enabling the senders to distinguish between dropped packets and reordered packets. [ABSTRACT FROM AUTHOR]

Radio networks model wireless communication when processing units communicate using one wave frequency. This is captured by the property that multiple messages arriving simultaneously to a node interfere with one another and none of them can be read reliably. We present improved solutions to the problem of waking up such a network. This requires activating all nodes in a scenario when some nodes start to be active spontaneously, while every sleeping node needs to be awaken by receiving successfully a message from a neighbor. Our contributions concern the existence and efficient construction of universal radio synchronizers, which are combinatorial structures introduced in [6] as building blocks of efficient wake-up algorithms. First we show by counting that there are (n,g)-universal synchronizers for . Next we show an explicit construction of (n,g)-universal-synchronizers for . By way of applications, we obtain an existential wake-up algorithm which works in time and an explicitly instantiated algorithm that works in time , where n is the number of nodes and Δ is the maximum in-degree in the network. Algorithms for leader-election and synchronization can be developed on top of wake-up ones, as shown in [7], such that they work in time slower by a factor of than the underlying wake-up ones. [ABSTRACT FROM AUTHOR]

A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous arbitrary network, assuming an upper bound on the time of any edge traversal by an agent. For a given graph and a given starting node we are interested in finding the fastest possible Black Hole Search by two agents (the minimum number of agents capable to identify a black hole). We prove that this problem is NP-hard in arbitrary graphs, thus solving an open problem stated in [2]. We also give a 7/2-approximation algorithm, thus improving on the 4-approximation scheme observed in [2]. Our approach is to explore the given input graph via some spanning tree. Even if it represents a very natural technique, we prove that this approach cannot achieve an approximation ratio better than 3/2. Keywords: approximation algorithm, black hole search, graph exploration, mobile agent, NP-hardness. [ABSTRACT FROM AUTHOR]