G. De Marco, A. Pelc,
Deterministic broadcasting time with partial knowledge of the network,
Theoretical Computer Science 290 (2003), 2009-2020.
G. De Marco, A. Pelc,
Deterministic broadcasting time with partial knowledge of the network,
Theoretical Computer Science 290 (2003), 2009-2020.
Preliminary version appeared in:
Proc. 11th Annual International Symposium on Algorithms And Computation (ISAAC 2000), Taipei, Taiwan, December 2000, LNCS 1969, 374-385.
Abstract:
We consider the time of deterministic broadcasting in networks whose nodes have limited knowledge of network topology. Each node v knows only the part of the network within knowledge radius r from it, i.e., it knows the graph induced by all nodes at distance at most r from v. Apart from that, each node knows the maximum degree D of the network. One node of the network, called the source, has a message which has to reach all other nodes. We adopt the widely studied communication model called the one-way model in which, in every round, each node can communicate with at most one neighbor, and in each pair of nodes communicating in a given round, one can only send a message while the other can only receive it. This is the weakest of all store-and-forward models for point-to-point networks, and hence our algorithms work for other models as well, in at most the same time. We show trade-offs between knowledge radius and time of deterministic broadcasting, when the knowledge radius is small, i.e., when nodes are only aware of their close vicinity. While for knowledge radius 0, minimum broadcasting time is Theta (e), where e is the number of edges in the network, broadcasting can be usually completed faster for positive knowledge radius. Our main results concern knowledge radius 1. We develop fast broadcasting algorithms and analyze their execution time. We also prove lower bounds on broadcasting time, showing that our algorithms are close to optimal.
A. Dessmark, A. Lingas, A. Pelc,
Tradeoffs between load and degree in virtual path layouts,
Parallel Processing Letters 13 (2003), 485-496.
Abstract:
We study virtual path layouts in ATM networks. Packets are routed along virtual paths in the network by maintaining a routing field whose subfields determine intermediate destinations of the packet, i.e., the endpoints of virtual paths on its way to the final destination. Most of the research on virtual path layouts has focused on tradeoffs between load (i.e., the maximum number of virtual paths passing through a link) and the hop number of the layout (i.e., the maximum number of virtual paths needed to travel between any two nodes). There is however another important limitation on construction of layouts, resulting from technological properties of switches situated at nodes. This bound is the degree of the layout (i.e., the maximum number of virtual paths with a common endpoint). In this paper we study relations between these three parameters of virtual path layouts, for the all-to-all problem. For any integer h, we show tradeoffs between load and degree of h-hop layouts in the ring and in the mesh by establishing upper and lower bounds on these parameters. Our bounds on the degree of an h-hop layout of given load are asymptotically tight and the bounds on the load of an h-hop layout of given degree are asymptotically tight for constant h.
J. Czyzowicz, W. Fraczak, A. Pelc, W. Rytter,
Linear time prime decomposition of regular prefix codes,
International Journal of Foundations of Computer Science 14 (2003), 1019-1031.
Preliminary version appeared as:
J. Czyzowicz, W. Fraczak, A. Pelc, W. Rytter, Prime decompositions of regular prefix codes, Proc. 7th International Conference on Implementation and Application of Automata (CIAA'2002), July 2002, Tours, France, LNCS 2608, 85-94.
Abstract:
One of the new approaches to data classification uses prefix codes and finite state automata as representations of prefix codes. A prefix code is a (possibly infinite) set of strings such that no string is a prefix of another one. An important task driven by the need for the efficient storage of such automata in memory is the decomposition (in the sense of formal languages concatenation) of prefix codes into prime factors. We investigate properties of such prefix code decompositions. A prime decomposition is a decomposition of a prefix code into a concatenation of nontrivial prime prefix codes. A prefix code is prime if it cannot be decomposed into at least two nontrivial prefix codes. In the paper a linear time algorithm is designed which finds the prime decomposition F_1F_2 ... F_k of a regular prefix code F given by its minimal deterministic automaton. Our results are especially interesting for infinite regular prefix codes.
J.Czyzowicz, E.Kranakis, D. Krizanc, M.V.Martin, A. Pelc,
Enhancing hyperlink structure for improving Web performance,
Journal of Web Engineering 1 (2003), 93-127.
Abstract:
In a Web site, each page v has a certain probability p(v) of being requested by a user. The access cost of a Web site is the sum of p(v)c(r,v), over all pages v, where c(r,v) is the cost of the shortest path between the home page r and page v. This research concerns the problem of minimizing the access cost of a Web site by adding hotlinks over its underlying structure. We propose an improvement of Web site access by making the most popular pages more accessible to the users. We present heuristic algorithms for the hotlink assignment problem. These algorithms are tested and compared by simulation on real and random Web sites. We develop the Hotlink Optimizer (HotOpt), a new software tool that finds an assignment of hotlinks reducing the access cost of a Web site. HotOpt is empowered by one of the algorithms presented in the paper.
B.S.Chlebus, L.Gasieniec, A. Pelc,
Deterministic computations on a PRAM with static processor and memory faults,
Fundamenta Informaticae 55 (2003), 285-306.
Preliminary version appeared as:
B.S.Chlebus, L.Gasieniec, A. Pelc, Fast deterministic simulation of computations on faulty parallel machines, Proc. Third Annual European Symposium on Algorithms ESA'95, Corfu, Greece, September 1995, LNCS 979, p. 89-101.
Abstract:
We consider Parallel Random Access Machine (PRAM) which has some processors and memory cells faulty. The faults considered are static, i.e., once the machine starts to operate, the operational/faulty status of PRAM components does not change. We develop a deterministic simulation of a fully operational PRAM on a similar faulty machine which has constant fractions of faults among processors and memory cells. The simulating PRAM has n processors and m memory cells, and simulates a PRAM with n processors and a constant fraction of m memory cells. The simulation is in two phases: it starts with preprocessing, which is followed by the simulation proper performed in a step-by-step fashion. Preprocessing is performed in time O((m/n+ log n)log n). The slowdown of a step-by-step part of the simulation is O(log m).