We consider the well known problem of determining the k'th
vertex reached by chasing pointers in a directed graph of
out-degree 1. The famous "pointer doubling" technique
provides an O(log k) parallel time algorithm on a
Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that
this problem requires Omega(k) steps on an Exclusive-Read
Exclusive-Write (EREW) PRAM, for every k < (c sqrt(log n)),
where n is the number of vertices and c is a constant.

This yields a boolean function which can be computed in
O(log log n) time on a CREW PRAM, but requires
Omega(sqrt (log n)) time on even an `ideal' EREW PRAM. This
is the first separation known for boolean functions between the
power of EREW and CREW PRAMs. Previously, separations between
EREW and CREW PRAMs were only known for functions on `huge'
input domains, or for restricted types of EREW PRAMs.