K. Diks, E. Kranakis, A. Pelc, Perfect broadcasting in unlabeled networks,
Discrete Applied Mathematics 87 (1998), 33-47.
K. Diks, E. Kranakis, A. Pelc, Perfect broadcasting in unlabeled networks,
Discrete Applied Mathematics 87 (1998), 33-47.
Abstract:
We consider broadcasting a message from one node to all other nodes of an asynchronous totally unlabeled network: neither nodes nor links of the network have a priori assigned labels but all nodes know the topology of the network. Nodes can send messages of arbitrary size and we are interested in minimizing the total number of messages. Broadcasting in an n-node unlabeled network is perfect if it uses n-1 messages (the minimum even in the labeled network). We show that the problem of deciding whether an arbitrary network admits perfect broadcasting from a given source, is NP-hard. We characterize regular networks in which perfect broadcasting from every node is possible, and give such broadcasting algorithms.
A. Pelc, Optimal diagnosis of heterogeneous systems with random faults,
IEEE Transactions on Computers 47 (1998), 298-304.
Abstract:
We consider the problem of fault diagnosis in multiprocessor systems. Processors perform tests on one another; fault-free testers correctly identify the fault status of tested processors, while faulty testers can give arbitrary test results. Processors fail with arbitrary probabilities and all failures are independent. The goal is to identify correctly the status of all processors, based on the set of test results. A diagnosis algorithm is optimal if it has the highest probability of correctness (reliability) among all (deterministic) diagnosis algorithms. We give a fast diagnosis algorithm and prove its optimality for arbitrary values of failure probabilities. This is for the first time that optimal diagnosis is given for systems without any assumptions on the behavior of faulty processors or on the values of failure probabilities.
We also investigate locally optimal diagnosis algorithms: for any set of test results they return the most probable configuration of faulty and fault-free processors that could yield it. We show a fast diagnosis which is always locally optimal. If all processors have failure probabilities smaller than 1/2, a locally optimal diagnosis is proved to be optimal. However, if some processors have failure probabilities exceeding 1/2, a locally optimal diagnosis need not have the highest reliability. We even show examples that it may have arbitrarily small reliability, when the number of processors increases, while optimal reliability remains constant.
A. Pelc, E. Upfal, Reliable fault diagnosis with few tests,
Combinatorics, Probability & Computing 7 (1998), 323-333.
Abstract:
We consider the problem of fault diagnosis in multiprocessor systems. Processors perform tests on one another; fault-free testers correctly identify the fault status of tested processors, while faulty testers can give arbitrary test results. Processors fail independently with constant probability p<1/2 and the goal is to identify correctly the status of all processors, based on the set of test results. For 0 < q < 1, q-diagnosis is a fault diagnosis algorithm whose probability of error does not exceed q. We show that the minimum number of tests to perform q-diagnosis for n processors is of order Theta(n log (1/q)) in the nonadaptive case and of order n +Theta(log (1/q)) in the adaptive case. We also investigate q-diagnosis algorithms that minimize the maximum number of tests performed by, and performed on, processors in the system, constructing testing schemes in which each processor is involved in very few tests. Our results demonstrate that the flexibility yielded by adaptive testing permits a significant saving in the number of tests for the same reliability of diagnosis.
A. Czumaj, L. Gasieniec, A. Pelc, Time and cost trade-offs in gossiping,
SIAM Journal on Discrete Mathematics 11 (1998), 400-413.
Abstract:
Each of n processors has a value which should be transmitted to all other processors. This fundamental communication task is called gossiping. In a unit of time every processor can communicate with at most one other processor and during such a transmission each member of a communicating pair learns all values currently known to the other. Two important criteria of efficiency of a gossiping algorithm are its running time and the total number of transmissions. Another measure of quality of a gossiping algorithm is the total number of links used for transmissions. This is the minimum cost of a network which can support the gossiping algorithm. We establish trade-offs between the time T of gossiping and the number C of transmissions and between the time of gossiping and the number L of links used by the algorithm. For a given T we construct gossiping algorithms working in time T, with parameters C and L close to optimal.
K. Diks, A. Pelc, System diagnosis with smallest risk of error,
Theoretical Computer Science 203 (1998), 163-173.
Preliminary version appeared in: Proc. 22nd International Workshop on Graph Theoretic Concepts in Computer Science WG'96, Cadenabbia, Italy, June 1996, LNCS 1197, p. 141-150.
Abstract:
We consider the problem of fault diagnosis in multiprocessor systems. Every processor can test its neighbors; fault-free processors correctly identify the fault status of tested neighbors, while faulty testers can give arbitrary test results. Processors fail independently with constant probability p<1/2 and the goal is to identify correctly the status of all processors, based on the set of test results. We give fast diagnosis algorithms with the highest possible probability of correctness for systems represented by complete bipartite graphs and by simple paths. This is for the first time that the most reliable fault diagnosis is given for these systems in a probabilistic model without any assumptions on the behavior of faulty processors.
E. Kranakis, D. Krizanc, A. Pelc, D.Peleg,
Approximate maxima finding of continuous functions under restricted budget,
Theoretical Computer Science 203 (1998), 151-162.
A preliminary version appeared in: Proc. 22nd International Workshop on Graph-Theoretic Concepts in Computer Science WG '96, Cadenabbia, Italy, June 1996, LNCS 1197, p. 268-278.
and the results were announced in: E. Kranakis, D. Krizanc, A. Pelc, D. Peleg, The complexity of data mining on the Web, Proc. 15th ACM Symp. on Principles of Distributed Computing PODC'96, Philadelphia, Pennsylvania, USA, (short abstract), p. 153.
Abstract:
A function is distributed among nodes of a graph in a ``continuous'' (or ``slowly changing'') way, i.e., such that the difference between values stored at adjacent nodes is small. The goal is to find a node of maximum value by probing some nodes under a restricted budget. Every node has an associated cost which has to be paid for probing it and a probe reveals the value of the node. If the total budget is too small to allow probing every node, it is impossible to find the maximum value in the worst case. Hence we seek an Approximate Maxima Finding (AMF) algorithm that offers the best worst-case guarantee g, i.e., for any continuous distribution of values it finds a node whose value differs from the maximum value by at most g.
Approximate Maxima Finding in graphs is related to a generalization of the multicenter problem and we get new results for this problem as well. For example, we give a polynomial algorithm to find a minimum cost solution for the multicenter problem on a tree, with arbitrary node costs.
K. Diks, E. Kranakis, A. Pelc, Broadcasting in unlabeled tori,
Parallel Processing Letters 8 (1998), 177-188.
Abstract:
We consider broadcasting a message from one node to all other nodes of an asynchronous totally unlabeled torus: neither nodes nor links have a priori assigned labels but they know the topology and the size of the torus. Nodes can send messages of arbitrary size and we are interested in minimizing the total number of messages. A naive broadcasting algorithm in a n x n totally unlabeled torus uses 3n2 +1 messages, while the obvious lower bound is n2 -1. The main result of this paper is a broadcasting algorithm using 2n2 + O(n) messages. We also give a lower bound of 1.04n2-O(n) messages. This is the first result on message complexity of broadcasting in totally unlabeled networks.
K. Diks, S. Dobrev, E. Kranakis, A. Pelc and P. Ruzicka,
Broadcasting in unlabeled hypercubes with linear number of messages,
Information Processing Letters 66 (1998), 181-186.
Abstract:
We consider broadcasting a message from one node to all other nodes of an asynchronous totally unlabeled n-node hypercube. Neither nodes nor links have a priori assigned labels. We show a broadcasting algorithm which uses only O(n) messages. This answers affirmatively an open question of G. Tel.
A.Farley, A. Pelc, A.Proskurowski, Minimum-time multidrop broadcast,
Discrete Applied Mathematics 82 (1998), 59-75.
Abstract:
The multidrop communication model assumes that a message originated by a sender is sent along a path in a network and is communicated to each site along that path. In the presence of several concurrent senders, we require that the transmission paths be vertex-disjoint. The time analysis of such communication includes both start-up time and drop-off time terms. We determine the minimum time required to broadcast a message under this communication model in several classes of graphs.
L. Gasieniec, A. Pelc, Broadcasting with linearly
bounded transmission faults,
Discrete Applied Mathematics 83 (1998), 121-133.
Abstract:
We consider broadcasting with a linearly bounded number of transmission failures. For a constant parameter a < 1 we assume that at most ai faulty transmissions can occur during the first i time units of the communication process, for every natural number i. Every informed node can transmit information to at most one neighbor in a unit of time. Faulty transmissions have no effect. We investigate worst-case optimal non-adaptive broadcasting time under this fault model, for several communication networks. We show, for example, that for the n-node line network this time is linear in n, if a < 1/2, and exponential otherwise. For the hypercube and the complete graph, broadcasting in the linearly bounded fault model can be performed in time logarithmic in the number of nodes.