Additional Key Words and Phrases: Connected components, EREW PRAM, minimum spanning trees, parallel algorithms
 have proven that the latter requires [Omega](log n) time on the CREW or EREW PRAM no matter how many processors are used.
 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. The normalization with respect to an ideal machine reflects a focus on the communication structure of the given architecture and an attempt to separate architectural and algorithmic behavior.
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. The asymptotic speedup for the given algorithm and architecture, specified as a function of problem size, is the maximum speedup attainable by any machine of the given architecture, regardless of the number of processors employed.
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.
If k = n and c = O(1), we can conclude that any scheme based on a single hash function requires [Omega](lg n/lg lg n) time to emulate one step of the EREW PRAM. 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.