# Concurrent vs. Exclusive Reading in Parallel Decoding of LZ-Compressed Files +
## 1 Introduction  
Parallel random access machines (PRAMs) are out of fashion today, but an apology of this model can still be done from the point of view of parallel algorithm design. Indeed, the so-called PRAM model provides the most natural computational tool for a first approach to an algorithmic solution of a problem with parallel computing, and secondly, a distributed memory implementation can be derived from it on a network. The computing techniques involved in the design of parallel and distributed algorithms strictly relate to the computational model on which the parallel or distributed system is based. The efficiency of a technique designed for a specific model can consistently deteriorate when applied to a different system. This is particularly evident when a technique designed for a shared memory parallel random access machine is implemented on a distributed system. Indeed, when the system is scaled up, the communication cost is a bottleneck to linear speed-up. So, we need to limit the interprocessor communication, either involving more local computation or bounding the number of global computation steps in order to obtain a practical algorithm. Local computation might cause a lack of robustness when scalability properties are required. On the other hand, scalability and robustness are generally guaranteed if bounding the number of global computation steps is possible for a specific problem. In this paper, we face the issue of concurrent versus exclusive reading in the design of a parallel algorithm for message passing-based distributed computing with an application to Lempel-Ziv data compression [1; 2; 3]. Broadcasting a message from one to many processors in a network correspondsto concurrent reading on a random access shared memory parallel machine, while exclusive reading implies message passing between disjoint pairs of processors on a distributed system. Basic subroutines for parallel algorithm design are computing the trees of a forest, the level of each node in its tree, and the path between two nodes. These problems can easily be solved with concurrent reading in a time logarithmic in the maximum height of a tree by means of the pointer jumping technique. The well-known Euler tour technique developed in [4] avoids concurrent reading by a linearization of the forest, reducing these problems to list ranking and parallel prefix. Solving such problems with exclusive reading requires a time logarithmic in the number of nodes. Besides avoiding concurrent reading, the Euler tour technique makes the parallel computation of several tree functions possible, as preorder, post-order, and computing the number of descendants of each node in logarithmic time with a linear number of processors. Without such linearization, these functions cannot be computed with such parallel complexity, even if concurrent reading is allowed. On the other hand, allowing concurrent reading to compute the trees of a forest, the level of each node in its tree, and the path between two nodes might be advantageous in parallel algorithm design for distributed computing in practice if such problems are faced on shallow trees with some specific constraints. Indeed, the concurrent reading is caused by the simultaneous access of two or more children to the information stored in a parent node, which increases at each step with the descendants. Therefore, the slow-down of such concurrency would not be so relevant if limited to a constant number of nodes. We evidentiate the properties a tree must have to obtain such limitation, and observe how--in the case of shallow trees--applying the Euler tour technique is not only unnecessary, but even disadvantageous for the running time. We show an application to LZC compressed file decoding [5; 6], whose parallelization employs these computations on such trees for realistic data. The pair compressor/decompressor presents an asymmetry with respect to global parallel computation, since the encoder is not parallelizable [7; 8], while the decoder has a very efficient parallelization [8; 9; 10].