Additional Key Words and Phrases: Connected components, EREW PRAM, minimum spanning trees, parallel algorithms
1986] have proven that the latter requires [Omega](log n) time on the CREW or EREW PRAM no matter how many processors are used.
1997] showed that an EREW PRAM algorithm can be simulated on the QSM model with a slow down by a factor of g, where g is the bandwidth parameter of the QSM model.
In Section 6, we adapt algorithm to run on the EREW PRAM and reduce the processor bound to linear.
For a given algorithm, and architecture's scalability is the ratio of the algorithm's asymptotic speedup when run on the architecture in question to its corresponding asymptotic speedup when run on an EREW PRAM, as a function of problem size.
We define the scalability [PSI](s) of a machine for a given algorithm to be the ratio of the asymptotic speedups on the real machine and on the ideal realization of an EREW PRAM.
We choose the EREW PRAM as our ideal architecture since its behavior resembles that of a real system when ignorign the effects of interconnection networks and caches.
We define scalability [Psi](s) of an architecture for a given algorithm with problem size s as the ratio of the algorithm's asymptotic speedup on the architecture in question and its corresponding asymptotic speedup on an EREW PRAM.
To make our discussion of contention resolution protocols more concrete, we will focus our attention primarily on a single application, namely that of efficiently emulating an EREW PRAM on a c-collision crossbar network.
We now return to the question of efficiently emulating an EREW PRAM on a c-collision crossbar.
On the other hand, Dietzfelbinger and Meyer auf der Heide  have recently shown that a bound of O(lg lg n) time per EREW PRAM step is attainable for the same settings of k and c.
If k = n lg n and c = O(1), the second "balls in bins" claim made at the outset of the paper shows that the emulation of a single EREW PRAM step will correspond to a [Theta](lg n)-relation routing problem wvhp.