Synchronization and Computing Capabilities of Linear Asynchronous Structures

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.

Authors

• Richard J. Lipton
• Raymond E. Miller
• Lawrence Snyder 0001

Keywords

• Synchronization
• Concurrent computing
• Physics computing
• Delay effects
• Delay systems
• Computational modeling
• Clocks
• Integrated circuit interconnections
• Context
• Production
• Deterministic
• Less Than Or Equal
• Number Of Steps
• Parallelization
• Linear Array
• State Machine
• Calculation Steps
• Normal Form
• Cellular Automata
• Synchronization Problem
• Asynchronous System