We study the problem of fast leaders election on TOLERANT, a CRCW PRAM
model which tolerates concurrent write but does not support symmetry
breaking. The leaders election problem is related to the problem of si
mulating stronger CRCW models, which support leaders election by prede
fined conflict resolution rules. We give a randomized simulation of MA
XIMUM-a very strong CRCW PRAM-on TOLERANT. The simulation is optimal,
is reliable, and runs in nearly doubly logarithmic time and linear spa
ce. This is the first simulation which is fast, optimal, and space-eff
icient, and therefore grants true comparison of algorithms running on
different CRCW PRAMs. Moreover, it implies that the memory to which co
ncurrent read or concurrent write is allowed should never be more than
linear-the rest of the memory can always be addressed under the EREW
convention. The techniques presented in this paper tackle fundamental
difficulties in the design of fast parallel algorithms. (C) 1994 Acade
mic Press, Inc.