Accession Number:

ADA094650

Title:

Distributed Algorithms for Synchronizing Interprocess Communication Within Real Time,

Descriptive Note:

Corporate Author:

HARVARD UNIV CAMBRIDGE MASS AIKEN COMPUTATION LAB

Personal Author(s):

Report Date:

1980-01-01

Pagination or Media Count:

26.0

Abstract:

This paper considers a fixed possibly infinite set, pi, of distributed asynchronous processes which at various times are willing to communicate with each other. We describe probabilistic algorithms for synchronizing this communication with boolean flag variables, each of which can be written by only one process and read by at most one other process. With very few assumptions the speeds of processes may vary in time within fixed arbitrary bounds, and the processes may be willing to communicate with a time varying set of processes but bounded in number, and no probability assumptions about system behavior we show our synchronization algorithms have real time response if at any time a pair of processes are mutually willing to communicate, they establish communication within a constant time interval, with high likelihood for the worst case behavior of the system. Our communication model and synchronization algorithms are quite robust and can be applied to solve a large class of resource synchronization problems, as well as implement Dijkstras CSP in real time. Author

Subject Categories:

  • Computer Hardware
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE