Synchronization and computing capabilities of linear asynchronous structures

A model is defined in which questions concerning delay bounded asynchronous parallel systems may be investigated. It is shown that synchronization problems, similar to the "firing squad synchronization problem", cannot be solved by delay bounded asynchronous systems. Three conditions called persistence, determinacy, and single change are introduced. These 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. This is a Church-Rosser type theorem, but in addition, the asynchronous execution time is shown to be only (D+1) times the synchronous execution time where D is the delay bound. Finally, a wide class of recognition problems is identified which can be solved by linear asynchronous structures. © 1977 Academic Press, Inc.