A. Pelc, Activating anonymous ad hoc radio networks,
Distributed Computing 19 (2007), 361-371.
A. Pelc, Activating anonymous ad hoc radio networks,
Distributed Computing 19 (2007), 361-371.
Preliminary version appeared as:
A. Pelc, Waking up anonymous ad hoc radio networks, Proc. 19th International Symposium on Distributed Computing (DISC 2005), September 2005, Cracow, Poland, LNCS 3724, 260-272.
Abstract:
We consider the task of activating an anonymous ad hoc radio network from a single source, by a deterministic algorithm. In the beginning only the source is active and has to activate other nodes by disseminating messages throughout the network. Nodes of the network do not know its topology and they do not have distinct labels. In such networks some nodes are impossible to reach. A node in a network is accessible if it can be activated by some (possibly network-dependent) deterministic algorithm. We show that the problem of recognizing whether a given node of an anonymous radio network is accessible, can be solved in polynomial time for the synchronous scenario. A deterministic wakeup algorithm for ad hoc networks is universal if it activates all accessible nodes in all networks. We study the question of the existence of such a universal activating algorithm. For synchronous communication we design a universal activating algorithm, and for asynchronous communication we show that no such algorithm exists.
A. Pelc, D. Peleg, Feasibility and complexity of broadcasting with random transmission failures,
Theoretical Computer Science 370 (2007), 279-292.
Preliminary version appeared in:
Proc. 24th Ann. ACM Symposium on Principles of Distributed Computing (PODC'2005), July 2005, Las Vegas, U.S.A., 334-341.
Abstract:
Fault-tolerant broadcasting in the message passing and radio models is considered under a probabilistic failure model. At each step, the transmitter of each node may fail with fixed constant probability p<1, and failures are independent. Both node-omission and malicious transmission failures are studied. Our goal is to establish conditions on feasibility and to estimate the (synchronous) time complexity of almost-safe broadcasting (i.e., broadcasting which is correct with probability at least 1-1/n for n-node graphs and for sufficiently large n) under these scenarios.
D. Kowalski, A. Pelc, Optimal deterministic broadcasting in known topology radio networks,
Distributed Computing 19 (2007), 185-195.
Abstract:
We consider deterministic broadcasting in radio networks whose nodes have full topological information about the network. The aim is to design a polynomial algorithm, which, given a graph G with source s, produces a fast broadcast scheme in the radio network represented by G. The problem of finding a fastest broadcast scheme for a given graph is NP-hard, hence it is only possible to get an approximation algorithm. We give a deterministic polynomial algorithm which produces a broadcast scheme of length O(D + log 2 n), for every n-node graph of diameter D.
J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc,
Searching for a black hole in synchronous tree networks,
Combinatorics, Probability & Computing 16 (2007), 595-619.
Preliminary version appeared as:
J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc, Searching for a black hole in tree networks, Proc. 8th International Conference on Principles of Distributed Systems (OPODIS'2004), December 2004, Grenoble, France, LNCS 3544, 67-80.
Abstract:
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 tree network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable of identifying a black hole is two. For a given tree and given starting node we are interested in the fastest possible black hole search by two agents. For arbitrary trees we give a 5/3-approximation algorithm for this problem. We give optimal black hole search algorithms for two ``extreme'' classes of trees: the class of lines and the class of trees in which any internal node (including the root which is the starting node) has at least 2 children.
A. Dessmark, A. Pelc, Broadcasting in geometric radio networks,
Journal of Discrete Algorithms 5 (2007), 187-201.
Preliminary version appeared as:
A. Dessmark, A. Pelc, Tradeoffs between knowledge and time of communication in geometric radio networks, Proc. 13th Ann. ACM Symposium on Parallel Algorithms and Architectures (SPAA 2001), Crete, Greece, 59-66.
Abstract:
We consider deterministic broadcasting in geometric radio networks (GRN) whose nodes know only a limited part of the network. Nodes of a GRN are situated in the plane and each of them is equipped with a transmitter of some range r. A signal from this node can reach all nodes at distance at most r from it but if a node u is situated within the range of two nodes transmitting simultaneously, then a collision occurs at u and u cannot get any message. Each node knows the part of the network within knowledge radius s from it, i.e., it knows the positions, labels and ranges of all nodes at distance at most s. The aim of this paper is to study the impact of knowledge radius s on the time of deterministic broadcasting in a GRN with n nodes and eccentricity D of the source. Our results show sharp contrasts between the efficiency of broadcasting in geometric radio networks as compared to broadcasting in arbitrary graphs. They also show quantitatively the impact of various types of knowledge available to nodes on broadcasting time in GRN. Efficiency of broadcasting is influenced by knowledge radius, knowledge of individual positions when knowledge radius is zero, and awareness of collisions.
J. Czyzowicz, E. Kranakis, D. Krizanc, A. Pelc, M. Vargas Martin,
Assigning bookmarks in perfect binary trees,
Ars Combinatoria 82 (2007), 165-179.
Abstract:
Consider a web domain consisting of a collection V={v_1,...,v_n} of web pages connected by hyperlinks. Assume that there exists a directed path of hyperlinks from the home page r to any other page of the collection. Let p_i be the probability that a user wants to access page v_i. A bookmark is an additional hyperlink from the home page r to any other page. We want to add k bookmarks to this web page collection, so as to minimize the expected access time from r, measured by the length of the shortest path of hyperlinks. We show that this optimization problem is NP-hard in general, even for uniform probability distribution, and solve it polynomially in two cases: when the web domain is a line with arbitrary probability distribution, and when the domain is a complete binary tree with uniform distribution and k < sqrt{n+1}.
E. Markou, A. Pelc, Efficient exploration of faulty trees,
Theory of Computing Systems 40 (2007), 225-247.
Preliminary version appeared in:
Proc. 15th Australasian Workshop on Combinatorial Algorithms (AWOCA'2004), July 2004, Ballina Beach Resort, New South Wales, Australia, 52-63.
Abstract:
We consider the problem of exploration of trees, some of whose edges are faulty. A robot, situated in a starting node and unaware of the location of faults, has to explore the connected fault-free component of this node by visiting all its nodes. The cost of the exploration is the number of edge traversals. For a given tree and given starting node, the overhead of an exploration algorithm is the worst-case ratio (taken over all fault configurations) of its cost to the cost of an optimal algorithm which knows where faults are situated. An algorithm, for a given tree and given starting node, is called perfectly competitive if its overhead is the smallest among all exploration algorithms not knowing the location of faults. We design a perfectly competitive exploration algorithm for any line, and an exploration algorithm for any tree, whose overhead is at most 9/8 larger than that of a perfectly competitive algorithm. Both our algorithms are fairly natural and the total time of local computations used during exploration is linear in the size of the explored tree. Our main contribution is the analysis of performance of these algorithms, showing that natural exploration strategies perform well in faulty trees.
S. Guilbault, A. Pelc, Fast adaptive diagnosis with a minimum number of tests,
Proc. 18th International Symposium on Algorithms and Computation (ISAAC 2007), December 2007, Sendai, Japan, LNCS 4835, 415-426.
Abstract:
We study adaptive system-level fault diagnosis for multiprocessor systems. Processors can test each other and later tests can be scheduled on the basis of previous test results. Fault-free testers correctly identify the fault status of tested processors, while faulty testers can give arbitrary test results. The goal is to identify correctly the status of all processors, assuming that the number of faults does not exceed a given upper bound t, where n is the number of processors. Tests involving disjoint pairs of processors can be performed simultaneously in one round. Two most important measures of quality of a diagnosis algorithm are its worst-case cost (the number of tests used) and time (the number of rounds used). It is known that the optimal worst-case cost of a diagnosis algorithm is n+t-1. However, the known algorithms of this cost use time Theta (n). We present an algorithm with optimal cost n+t-1 using time O(log t), provided that the upper bound t on the number of faults satisfies t(t+1) < n+1. Hence, for moderate numbers of faults which we assume, our algorithm achieves exponential speed-up, compared to the previously known diagnosis algorithms of optimal cost.