Partially effective randomization in simulations between ARBITRARY and COMMON PRAMs

摘要

It is known that Θ((log n)/(log log n)) 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. (ⅰ) It is shown that one step of ARBITRARY can be simulated by O((log m)/(k log log m-log k)) + log log 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 Θ((log n)/(log log n))-step simulation does not become faster for smaller m, while our randomized simulation becomes O(log log n) when m ≤ ((n log log n)/(log n)). (ⅱ) It is shown that when m = n, Ω((log n)/(log log n)) 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.