This paper considers the problem of element distinctness on CRCW PRAMs with unbounded memory. A complete proof of the op-timal lower bound of H (nlogn/ (plog(|logn+ 1))) steps for n ele-ments problem on p processor COMMON PRAM is presented. This lower bound has been previously correctly stated by Boppana, but his proof was not complete. Its correction requires some additional observations and some not straightforward changes.
展开▼
