Partially effective randomization in simulations between ARBITRARY and COMMON PRAMs

It is known that $\text{Θ(}\text{log}\text{n}\text{log}\text{log}\text{n}\text{)}$ steps are needed to simulate one step of ARBITRARY CRCW PRAMs by COMMON CRCW PRAMs, but it was open whether there is a faster simulation when randomization is allowed. This paper gives both positive and negative answers. (i) It is shown that one step of ARBITRARY can be simulated by $\text{O(}\text{log}\text{m}\text{k(}\text{log}\text{log}\text{m−}\text{log}\text{k)}\text{+}\text{log}\text{log}\text{n)}$ steps on randomized COMMON with error-rate n^−c, where m=n/k is the number of different memory cells into which at least one processor of the simulated PRAM attempts to write. The deterministic $\text{Θ(}\text{log}\text{n}\text{log}\text{log}\text{n}\text{)}$-step simulation does not become faster for smaller m, while our randomized simulation becomes $\text{O(}\text{log}\text{log}\text{n)}$ when $\text{m⩽}\text{n}\text{log}\text{log}\text{n}\text{log}\text{n}$. (ii) It is shown that when $\text{m=n,}\text{Ω(}\text{log}\text{n}\text{log}\text{log}\text{n}\text{)}$ steps are needed to simulate one step of ARBITRARY by COMMON even if randomization is allowed. This lower-bound result needs some assumption on processor communication but it strongly suggests randomization does not help when m is small.