TIGHT BOUNDS ON PARALLEL LIST MARKING

The list marking problem involves marking the nodes of an L-node linke d list stored in the memory of a (p, n)-PRAM, when only the position o f the head of the list is initially known, while the remaining list no des are stored in arbitrary memory locations. Under the assumption tha t cells containing list nodes bear no distinctive tags distinguishing them from other cells, we establish an Omega(min{l, n/p}) randomized l ower bound for l-node lists and present a deterministic algorithm whos e running time is within a logarithmic additive term of this bound. Su ch a result implies that randomization cannot be exploited in any sign ificant way in this setting. For the case where list cells are tagged in a way that differentiates them from other cells, the above lower bo und still applies to deterministic algorithms, while we establish a ti ght Theta(min {l, l/p + root(n/p) log n }) bound for randomized algori thms. Therefore, in the latter case, randomization yields a better per formance for a wide range of parameter values. (C) 1998 Academic Press .