Real-Time Synchronization of Interprocess Communications

This paper considers a fixed (possibly infinite) set of distributed asynchronous processes, which at various times are willing to communicate with each other. Each process has various ports, each of which is used for communication with a distinct neighbor process. Each process can have at most one port open at any time, and its other ports must be closed. Two processes handshake over a time interval A if their respective ports are open for mutual communication during this interval. Note that the handshake relation is a matching. Successful communication requires a handshake of at least one step of each process; during the one-step overlap a message can be transmitted between processes. The problem is to synchronize processes (via a distributed scheduler) so that they can successfully handshake at their will, given that the means of synchronization is some low-level construct that does not guarantee the handshake property if used in an unsophisticated way. Probabilistic distributed algorithms for synchronizing processes so that they can handshake at will are described. A process is considered to be tame over a time interval A if its speed varies within certain arbitrarily fixed nonzero bounds. Our synchronization algorithms are shown to have real-time response: If a pair of processers are mutually willing to communicate within a time interval A of length at least a given constant and the pair are tame on A, then they establish communication within A with high likelihood (for the worst case behavior of the system), and the expected time for establishment of communication is also constant. Our model and algorithms are applied to solve a large class of real-time resource allocation problems, as well as real-time implementation of the synchronization primitives of Hoare's multiprocessing language CSP. © 1984, ACM. All rights reserved.

Duke Scholars

Author John H. Reif Computer Science