CLOCK CONSTRUCTION IN FULLY ASYNCHRONOUS PARALLEL SYSTEMS AND PRAM SIMULATION

We consider the problem of simulating synchronous computations on asyn chronous shared memory systems. The systems we consider allow for arbi trary asynchronous behavior of the processors. In addition, we make ve ry limited (and in some cases no) assumptions about the atomicity of r ead and write operations to shared memory. We provide detailed definit ions of these asynchronous systems and their atomicity properties. The first construction in this paper is a novel clock for asynchronous sy stems. The clock is a basic tool for synchronization in the asynchrono us environment. The construction we give is extremely robust, and can be implemented in a system with no atomicity assumptions, and in the p resence of an adaptive adversary scheduler The correct behavior of the clock is obtained with overwhelming probability (> 1-2-alphan, alpha > 0). We then show how to harness this clock to drive an efficient PRA M simulation on an asynchronous system. The simulation requires an O(l og2 n) work, and O(log n) space, overhead. This improves by a log n fa ctor on the efficiency of previously obtained simulation results, whil e relaxing the assumptions on the underlying asynchronous system.