Synchronization and computing capabilities of linear asynchronous structures

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.