Real-Time Synchronization of Interprocess Comunication
Abstract
This paper considers a fixed (possibly infinite) set 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. The use of flag variables seems as to require the fewest assumptions possible without considering specific systems. A process is considered to be tame over a time interval delta if its speed varies within certain arbitrarily fixed nonzero bounds. We show our synchronization algorithms have realtime response: If a pair of processes are mutually willing to communicate within a time interval delta and the pair are tame on delta, then they establish communication within delta with high likelihood (for the worst case behavior of the system). Our communication model and synchronization algorithms are quite robust. They are applied to solve a large class of real time resource synchronization problems, as well as real time implementation of the synchronization primitives of Hoare's multiprocessing language CSP.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1980
- Accession Number
- ADA108825
Entities
People
- John Reif
- Paul G. Spirakis
Organizations
- Harvard University