Name
Abstract | ||
|---|---|---|
We consider the problem of simulating synchronous computations on asynchronous shared memory systems. The systems we consider allow for arbitrary asynchronous behavior of the processors. In addition, we make very limited (and in some cases no) assumptions about the atomicity of read and write operations to shared memory. We provide detailed definitions of these asynchronous systems and their atomicity properties. The first construction in this paper is a novel clock for asynchronous systems. The clock is a basic tool for synchronization in the asynchronous environment. The constructiion we give is extremely robust, and can be implemented in a system with no atomicity assumptions, and in the presence of an adaptive adversary scheduler The correct behavior of the clock is obtained with overwhelming probability (>1−2 − αn , α >0). We then show how to harness this clock to drive an efficient PRAM simulation on an asynchronous system. The simulation requires an O ( log 2 n ) work, and O ( log n ) space, overhead. This improves by a log n factor on the efficiency of previously obtained simulation results, while relaxing the assumptions on the underlying asynchronous system. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0304-3975(94)90162-7 | SFCS '92 Proceedings of the 33rd Annual Symposium on Foundations of Computer Science |
Keywords | Field | DocType |
clock construction,asynchronous parallel system,pram simulation,synchronization,parallel systems,atomicity,mathematics,asynchronous system,computational modeling,computational complexity,robustness,computer science,dynamic scheduling,concurrent computing,parallel algorithms,probability | Atomicity,Asynchronous communication,Synchronization,Asynchronous system,Parallel algorithm,Computer science,Parallel computing,Clock synchronization,Asynchronous circuit,Computational complexity theory,Distributed computing | Journal |
Volume | Issue | ISSN |
128 | 1-2 | Theoretical Computer Science |
ISBN | Citations | PageRank |
0-8186-2900-2 | 27 | 1.72 |
References | Authors | |
7 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yonatan Aumann | 1 | 1127 | 102.90 |
| Michael O. Rabin | 2 | 3471 | 3060.62 |