P. Panaite, A. Pelc,
Exploring unknown undirected graphs,
Journal of Algorithms 33 (1999), 281-295.
P. Panaite, A. Pelc,
Exploring unknown undirected graphs,
Journal of Algorithms 33 (1999), 281-295.
Preliminary version appeared in: Proc. 9th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'98), San Francisco, USA, January 1998, pp. 316-322.
Abstract:
A robot has to construct a complete map of an unknown environment modeled as an undirected connected graph. The task is to explore all nodes and edges of the graph using the minimum number of edge traversals. The penalty of an exploration algorithm running on a graph G=(V(G),E(G)) is the worst-case number of traversals in excess of the lower bound |E(G)| that it must perform in order to explore the entire graph. We give an exploration algorithm whose penalty is O(|V(G)|) for every graph. We also show that some natural exploration algorithms cannot achieve this efficiency.
K. Diks, A. Lingas, A. Pelc,
An optimal algorithm for
broadcasting multiple messages in trees,
Journal of Parallel and Distributed Computing 59 (1999), 465-474.
Preliminary version appeared as:
K. Diks, A. Lingas, A. Pelc, Broadcasting multiple messages in trees, Proc. 4th Coll. on Structural Information and Communication Complexity, SIROCCO'97, Ascona, Switzerland, July 1997, 69-80.
Abstract:
We consider multiple message broadcasting in tree networks. The source (considered as the root of the tree) has k messages which have to be broadcast to all nodes of the tree. In every time unit each node can send one of already obtained messages to one of its children. A k-message broadcasting scheme prescribes in which time unit a given node should send a message to which child. It is k-optimal if it achieves the smallest possible time for broadcasting k messages from the source to all nodes. We give an algorithm to construct a k-optimal broadcasting scheme for an arbitrary n-node tree. The time complexity of our algorithm is O(nk), i.e., the best possible.
E. Kranakis, A. Pelc, A. Spatharis,
Optimal adaptive fault diagnosis for simple multiprocessor systems,
Networks 34 (1999), 206-214.
Preliminary version appeared in:
Proc. 5th Int. Coll. on Structural Information and Communication Complexity, SIROCCO'98, Amalfi, Italy, June 1998, 82-97.
Abstract:
We study adaptive system-level fault diagnosis for multiprocessor systems. Processors can test each other and future tests can be selected on the basis of previous test results. Fault-free testers give always correct test results, while faulty testers are completely unreliable. The aim of diagnosis is to determine correctly the fault status of all processors. We present adaptive diagnosis algorithms for systems modeled by trees, rings and tori. These algorithms use the smallest possible number of tests in each case. Our results also imply optimal diagnosis for more general systems, assuming a small number of faults. The cost of adaptive diagnosis turns out to be significantly smaller than that of classical ( one-step) diagnosis.
L. Gasieniec, E. Kranakis, D. Krizanc, A. Pelc,
Minimizing congestion of layouts for ATM networks with faulty links,
International Journal of Foundations of Computer Science 10 (1999), 503-512.
Preliminary version appeared in:
Proc. 21st International Symposium on Mathematical Foundations of Computer Science MFCS'96, Cracow, Poland, September 1996, LNCS 1113, pp.372-381.
Abstract:
We consider the problem of constructing virtual path layouts for an ATM network consisting of a complete network K of n processors in which a certain number of links may fail. Our main goal is to construct layouts which tolerate any configuration of up to f faults and have the least possible congestion. First, we study the minimal congestion of 1-hop f-tolerant layouts in K. For any positive integer f we give upper and lower bounds on this minimal congestion and construct f-tolerant layouts with congestion corresponding to the upper bounds. Our results are based on a precise analysis of the diameter of the network which results from K by deleting links from a set of bounded size. Next we study the minimal congestion of h-hop f-tolerant layouts in K, for larger values of the number h of hops. We give upper and lower bounds on the order of magnitude of this congestion, based on results for 1-hop layouts. Finally, we consider a random, rather than worst case, fault distribution where links fail independently with constant probability p<1. Our goal now is to construct layouts with low congestion that tolerate the existing faults with high probability. For any p<1, we show the existence of 1-hop layouts in K, with congestion O(log n).