Tight bounds on parallel list marking

n)-PRAM, when only the location of the head of the list is initially known. Under the assumption that memory cells containing list nodes bear no distinctive tags distinguishing them from other cells, we establish an OHgr (min{ell, n/p}) randomized lower bound for ell-node lists and present a deterministic algorithm whose running time is within a logarithmic additive term of this bound. In the case where list cells are tagged in a way that differentiates them from other cells, we establish a tight theta (min {ell,ell/p + radic(n/p) log n }) bound for randomized algorithms.