ON THE COMPLEXITY OF CERTIFIED WRITE-ALL ALGORITHMS

An asynchronous PRAM allows processors to run at different and unpredi ctable speeds. Thus a fundamental problem in designing asynchronous PR AM algorithms is constructing a synchronization primitive which determ ines that a set of tasks has been completed. The certified write-all p roblem (CWA) is: given an array A[1..n] and a flag f which are both in itialized to zero, set all elements of A to one, and then set f to one . A solution to the certified Write-all problem can be used as a synch ronization primitive in a wide variety of settings. This paper investi gates the complexity of CWA algorithms by presenting several new algor ithms and lower bound proofs. We present a new randomized CWA algorith m which uses expected O(n) work using up to n/log n processors. We sho w that this algorithm is optimal in both work and processor utilizatio n by proving an OMEGA(n + p log n) lower bound on the expected work do ne by a p processor randomized CWA algorithm. Our CWA algorithm uses c oncurrent reads and concurrent writes. We show that this is necessary by proving that no concurrent read exclusive write (CREW) asynchronous PRAM can solve the CWA problem. However, for a fail-stop PRAM, where processors operate synchronously until they fail, we present a randomi zed CREW CWA algorithm. This algorithm also uses O(n) expected work us ing up to n/log n CREW fail-stop processors. (C) 1994 Academic Press, Inc.