Clock construction in fully asynchronous parallel systems and PRAM simulation
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 147-156
- https://doi.org/10.1109/sfcs.1992.267777
Abstract
The authors discuss the question of simulating synchronous computations on asynchronous systems. They consider an asynchronous system with very weak, or altogether lacking any, atomicity assumptions. The first contribution of this paper is a novel clock for asynchronous systems. The clock is a basic tool for synchronization in the asynchronous environment. It is a very robust construction and can operate in a system with no atomicity assumptions, and in the presence of a dynamic scheduler. The behavior of the clock is obtained with overwhelming probability (1-2/sup - alpha n/, alpha >0). The authors show how to harness this clock to drive a PRAM simulation on an asynchronous system. The resulting simulation scheme is more efficient than existing ones, while actually relaxing the assumptions on the underlying asynchronous system.Keywords
This publication has 11 references indexed in Scilit:
- Asynchronous PRAMs are (almost) as good as synchronous PRAMsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Efficient parallel algorithms on restartable fail-stop processorsPublished by Association for Computing Machinery (ACM) ,1991
- Combining tentative and definite executions for very fast dependable parallel computingPublished by Association for Computing Machinery (ACM) ,1991
- Impossibility results for asynchronous PRAM (extended abstract)Published by Association for Computing Machinery (ACM) ,1991
- A bridging model for parallel computationCommunications of the ACM, 1990
- Efficient robust parallel computationsPublished by Association for Computing Machinery (ACM) ,1990
- Asynchronous shared memory parallel computationPublished by Association for Computing Machinery (ACM) ,1990
- A more practical PRAM modelPublished by Association for Computing Machinery (ACM) ,1989
- Impossibility and universality results for wait-free synchronizationPublished by Association for Computing Machinery (ACM) ,1988
- On interprocess communicationDistributed Computing, 1986