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. We describe probabilistic distributed algorithms for synchronizing processes so that they can handshake at will. The means of synchronization are 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 real time response: If a pair of processes are mutually willing to communicate within a time interval delta of length at least a given constant and the pair are tame on delta, then they establish communication within delta with high likelihood (for the worst case behavior of the system and the expected time for establishment of communication is also constant. We feel the term real time is merited, for the actual time needed for establishment of communication is upper bounded by a constant with overwhelming probability; furthermore, violations of this property occur with vanishingly low likelihood. We have very few assumptions: (1) Tameness is required of a process only during the interval it is willing to communicate; and (2) the processes may be willing to communicate with a time varying set of processes which are only bounded in number.