# Concurrent vs. Exclusive Reading in Parallel Decoding of LZ-Compressed Files +
## 2 Concurrent versus Exclusive Reading  
If we use a parent array as data structure to represent a forest, computing the trees, the level of each node in its tree, and the path between two nodes are problems which can easily be solved on a CREW (concurrent read, exclusive write) PRAM by running in parallel the pointer jumping operation \(parent[i]=parent[parent[i]]\). The procedure takes a number of processors linear in the number of nodes and a time logarithmic in the maximum height of a tree. Generally speaking, implementing such a procedure causes a slow-down logarithmic in the number of nodes if we solve the reading conflicts by standard broadcasting techniques. Therefore, the total running time increases to square-logarithmic in the worst case, since the maximum height of a tree can reach the order of magnitude of the number of nodes. To keep the time logarithmic, we need to assume some constraints on the structure of each tree of the forest. Indeed, there must be a constant \(c>0\) such that for each tree of the forest, the number of nodes with more than one child distant more than \(c\) from the root is less than \(c\), and none of the nodesmore distant than \(c\) from the root has more than \(c\) children. It is easy to see that this is a necessary and sufficient condition to solve the reading conflicts by standard broadcasting with no slow-down on the total running time in terms of asymptotic behavior of the parallel complexity. If such a constant does not exist, the well-known Euler tour technique developed in [4] avoids the concurrent reading of the children.  
The Euler tour technique reduces the problems to list ranking on the EREW (exclusive read, exclusive write) PRAM with a number of processors and a time, respectively, linear and logarithmic both in the number of nodes. Let \(F\) be a forest of rooted trees with every node having a parent pointer along with a doubly-linked list of children. To begin, we replace every node \(v\) of \(F\) by an array \(V[1\cdots d(v)+1]\) of copies of \(v\), where \(d(v)\) is the number of children of \(v\). Let \(w_{1}\cdots w_{d(v)}\) be the children of \(v\) and \(W_{1}[1\cdots d(w_{1})+1],\cdots W_{d(v)}[1\cdots d(w_{d(v)}+1)]\) the corresponding arrays. We link \(W_{i}[1]\) to \(V[i]\) and \(V[i+1]\) to \(W_{i}[d(w_{i})+1]\), and obtain for each tree \(T\) of \(F\) a linked list starting at \(R[1]\) and ending at \(R[d(r)+1]\), where \(r\) is the root of \(T\) and \(R\) the corresponding array. Then, it is clear that we find the trees in the forest by applying list ranking. Moreover, for each list associated with a tree, we assign to the first entry in every array a weight \(+1\), and to all the others \(-1\). Then, the level of each node in its tree is obtained with prefix computation by computing the partial sums of these values in the list. Partial sums corresponding to positions of components of the array associated with \(v\) in the list are equal to the level of \(v\) in its tree. Since we assumed to have children doubly linked with their parent, the realization of the list takes constant time with a linear number of processors or logarithmic time with O(\(n/\log n\)) processors. List ranking and prefix computation require logarithmic time with O(\(n/\log n\)) processors as well. If children are not doubly linked to their parent, adding the links from a parent to its children generally takes logarithmic time with a linear number of processors employing parallel sorting procedures. However, there are cases where the bound to the number of children is known and constant.  
To conclude this section, we wish to point out that even if there is a constant bounding the nodes with more children and the children of a node too distant from the root, the Euler tour technique might still be advantageous when the tree is not shallow enough. However, this is not the case for the application to LZC-compressed file decoding that we present in this paper.