Distributed algorithms for synchronizing interprocess communication within real time

ABSTRACT

This paper considers a fixed (possibly infinite) set &pgr; 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 a pair of processes are mutually willing to communicate within a constant time interval, they establish communication in that interval, 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.

REFERENCES

• 1: Dana Angluin, Local and global properties in networks of processors (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.82-93, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804655]
• 2: Eshrat Arjomandi , Michael J. Fischer , Nancy A. Lynch, A difference in efficiency between synchronous and asynchronous systems, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.128-132, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802466]
• 3: Arthur Bernstein, Output Guards and Nondeterminism in “Communicating Sequential Processes”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.234-238, April 1980 [doi>10.1145/357094.357101]
• 4: Francez, N. and Rodeh, "A Distributed Data Type Implemented by a Probabilistic Communication Scheme," 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, Oct. 1980, pp. 373-379.
• 5: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 6: Daniel Lehmann , Michael O. Rabin, On the advantages of free choice: a symmetric and fully distributed solution to the dining philosophers problem, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-138, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567547]
• 7: Lipton, R. and F.G. Sayward, "Response Time of Parallel Programs," Research Report #108, Dept. Computer Science, Yale Univ., June 1977.
• 8: Nancy A. Lynch, Fast allocation of nearby resources in a distributed system, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.70-81, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804654]
• 9: Rabin, M., "N-Process Synchronization by a 4 log2N-valued Shared Variable," 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, Oct. 1980, pp. 407-410.
• 10: Rabin, M., "The Choice Coordination Problem," Mem. No. UCB/ERL M80/38, Electronics Research Lab., Univ. of California, Berkeley, Aug. 1980.
• 11: Schwartz, J., "Distributed Synchronization of Communicating Sequential Processes," DAI Research Report No. 56, Univ. of Edinburg, 1980.
• 12: Sam Toueg, Deadlock- and livelock-free packet switching networks, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.94-99, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804656]
• 13: Valiant, L.G., "A Scheme for Fast Parallel Communication," Technical Report, Computer Science Dept., Edinburg Univ., Edinburg, Scotland, July 1980.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Asynchronous/synchronous operation

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity measures

General Terms:
Algorithms, Measurement, Theory