L.M. Kirousis, E. Kranakis, D. Krizanc, A. Pelc, Power consumption in packet radio networks,
Theoretical Computer Science 243 (2000), 289-305.
L.M. Kirousis, E. Kranakis, D. Krizanc, A. Pelc, Power consumption in packet radio networks,
Theoretical Computer Science 243 (2000), 289-305.
Preliminary version appeared in: Proc. 14th Symposium on Theoretical Aspects of Computer Science, STACS'97, Lubeck, Germany, February/March 1997, LNCS 1200, pp. 363-374.
Abstract:
In this paper we study the problem of assigning transmission ranges to the nodes of a multi-hop packet radio network so as to minimize the total power consumed under the constraint that adequate power is provided to the nodes to ensure that the network is strongly connected (i.e., each node can communicate along some path in the network to every other node). Such assignment of transmission ranges is called complete. We also consider the problem of achieving strongly connected bounded diameter networks. For the case of n+1 colinear points at unit distance apart (the unit chain) we give a tight asymptotic bound for the minimum cost of a range assignment of diameter h when h is a fixed constant and when h < (1+e) log n, for some constant e >0. When the distances between the colinear points are arbitrary, we give an O(n4) time dynamic programming algorithm for finding a minimum cost complete range assignment.
K. Diks, A. Pelc,
Optimal adaptive broadcasting with a bounded fraction of faulty nodes,
Algorithmica 28 (2000), 37-50..
Preliminary version appeared in:
Proc. Fifth Annual European Symposium on Algorithms, ESA'97, Graz, Austria, September 1997, LNCS 1284, pp. 118-129.
Abstract:
We consider broadcasting among n processors, f of which can be faulty. A fault-free processor, called the source, holds a piece of information which has to be transmitted to all other fault-free processors. We assume that the fraction f/n of faulty processors is bounded by a constant \gamma<1. Transmissions are fault free. Faults are assumed of crash type: faulty processors do not send or receive messages. We use the {\em whispering} model: pairs of processors communicating in one round must form a matching. A fault-free processor sending a message to another processor becomes aware of whether this processor is faulty or fault free and can adapt future transmissions accordingly. The main result of the paper is a broadcasting algorithm working in O(log n) rounds and using O(n) messages of logarithmic size, in the worst case. Our method also gives the first algorithm for adaptive distributed fault diagnosis in O(log n) rounds.
P. Panaite, A. Pelc,
Optimal broadcasting in faulty trees,
Journal of Parallel and Distributed Computing 60 (2000), 566-584.
Preliminary version appeared as:
P. Panaite, A. Pelc, Optimal fault-tolerant broadcasting in trees, Proc. 8th Annual International Symposium on Algorithms and Computation, ISAAC'97, Singapore, December 1997, LNCS 1350, pp. 143-152.
and
P. Panaite, A. Pelc, Universally fault-tolerant broadcasting in trees, Proc. International Conference on Parallel and Distributed Systems, ICPADS'97, Seoul, Korea, December 1997, pp. 724-729.
Abstract:
We consider broadcasting a message from one node of a tree to all other nodes. In the presence of up to k link failures the tree becomes disconnected, and only nodes in the connected component C containing the source can be informed. The maximum ratio between the time used by a broadcasting scheme B to inform C and the optimal time to inform C, taken over all components C yielded by configurations of at most k faults, is the k-vulnerability of B. This is the maximum slowdown incurred by B due to the lack of a priori knowledge of fault location, for at most k faults. This measure of fault-tolerance is similar to the competitive factor of on-line algorithms: in both cases, the performance of an algorithm lacking some crucial information is compared to the performance of an ``off-line'' algorithm, one that is given this information as input. It is also the first known tool to measure and compare fault-tolerance of broadcasting schemes in trees. We seek broadcasting schemes with low vulnerability, working for tree networks. It turns out that schemes that give the best broadcasting time in a fault-free environment may have very high vulnerability, i.e., poor fault-tolerance, for some trees. The main result of this paper is an algorithm that, given an arbitrary tree T and an integer k, computes a broadcasting scheme B with lowest possible k-vulnerability among all schemes working for T. Our algorithm has running time O(kn2+n2log n), where n is the size of the tree. We also give an algorithm to find a ``universally fault-tolerant'' broadcasting scheme in a tree T: one that approximates the lowest possible k-vulnerability, for all $k$ simultaneously.
P. Denejko, K. Diks, A. Pelc, M. Piotrow,
Reliable minimum finding comparator networks,
Fundamenta Informaticae 42 (2000), 235-249.
Preliminary version appeared in:
Proc. 19th Int. Symp. Mathematical Foundations of Computer Science MFCS-94, Kosice, Slovakia, August 1994, LNCS 841, pp. 306-315.
Abstract:
we consider the problem of constructing reliable minimum finding networks built from unreliable comparators. In case of a faulty comparator inputs are directly output without comparison. Our main result is the first nontrivial lower bound on depths of networks computing minimum among n>2 items in the presence of k>0 comparators.
E. Kranakis, A. Pelc,
Better adaptive diagnosis of hypercubes,
IEEE Transactions on Computers 49 (2000), 1013-1020.
Abstract:
We consider the problem of adaptive fault diagnosis in hypercube multiprocessor systems. Processors perform tests on one another 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 the hypercube dimension. We propose an adaptive diagnosis algorithm whose efficiency is drastically better than that of any previously known strategies. While the worst-case number of tests for any of them exceeds 2n log n for an n-dimensional hypercube, our method uses at most 2n + 2n tests in the worst case. We can also modify our algorithm to improve the number of testing rounds. By slightly increasing the number of tests to 2n + (n+1)2 (still a much better performance than 2n log n), we can carry out diagnosis in at most 11 rounds in the worst case (as opposed to over n rounds in the best previously known strategy).
P. Panaite, A. Pelc,
Impact of topographic information on graph exploration efficiency,
Networks, 36 (2000), 96-103.
Abstract:
A robot has to explore an undirected connected graph by visiting all its nodes and traversing all edges. It may either have a complete a priori knowledge of the graph, or only have an unoriented map of it, or finally, lack any knowledge of the graph. We study the impact of this varying amount of knowledge on exploration performance. It is shown that the best exploration algorithm lacking any knowledge of the graph uses twice as many edge traversals in the worst case as the best algorithm which has an unoriented map of the graph. On the other hand, the latter uses twice as many edge traversals in the worst case as the best algorithm having a complete knowledge of the graph. Similar results for the restricted case of exploration algorithms working only for trees are also established.