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. 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. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1975
Accession Number
ADA039566

Entities

People

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

Organizations

  • Yale University

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Arrays
  • Asynchronous Computation
  • Asynchronous Systems
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Construction
  • Grammars
  • Linear Arrays
  • Machines
  • Parallel Computing
  • Production
  • Recognition
  • Sequences
  • Transitions

Readers

  • Mathematical Modeling and Probability Theory.
  • Parallel and Distributed Computing.