Simulations among concurrent-write PRAMs (Q1104097)

The paper is concerned with the relative power of the two most popular concurrent-write models of parallel computation, the PRIORITY PRAM [\textit{L. M. Goldschlager}, J. Assoc. Comput. Mach. 29, 1073-1086 (1982; Zbl 0489.68042)], and the COMMON PRAM [\textit{L. Kučera}, Inf. Process. Lett. 14, 93-96 (1982; Zbl 0498.68029)]. Improving the trivial and seemingly optimal O(log n) simulation, we show that one step of a PRIORITY machine can be simulated by O(log n/(log log n)) steps of a COMMON machine with the same number of processors (8C25 A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the first n/log n processor, O(log n)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.