Synchronization and computing capabilities of linear asynchronous structures
- 1 October 1975
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 19-28
- https://doi.org/10.1109/sfcs.1975.27
Abstract
A model is defined in which questions concerning delay bounded asynchronous parallel systems may be investigated. Persistence and determinacy are introduced for this model. These two conditions are shown to be sufficient to guarantee that a synchronous execution policy can be relaxed to an asynchronous execution policy with no change to the result of the computation. In addition, the asynchronous execution time is only (D+1) times the synchronous execution time, where D is the delay bound. A wide class of recognition problems is identified which can be solved by linear asynchronous structures. Also, it is shown that synchronization problems, similar to the "firing squad synchronization problem," cannot be solved by delay bounded asynchronous systems.Keywords
This publication has 2 references indexed in Scilit:
- Real-time language recognition by one-dimensional cellular automataJournal of Computer and System Sciences, 1972
- Generation of Primes by a One-Dimensional Real-Time Iterative ArrayJournal of the ACM, 1965