Paradigms for process interaction in distributed programs

ABSTRACT

Distributed computations are concurrent programs in which processes communicate by message passing. Such programs typically execute on network architectures such as networks of workstations or distributed memory parallel machines (i.e., multicomputers such as hypercubes). Several paradigms—examples or models—for process interaction in distributed computations are described. These include networks of filters, clients, and servers, heartbeat algorithms, probe/echo algorithms, broadcast algorithms, token-passing algorithms, decentralized servers, and bags of tasks. These paradigms are appliable to numerous practical problems. They are illustrated by solving problems, including parallel sorting, file servers, computing the topology of a network, distributed termination detection, replicated databases, and parallel adaptive quadrature. Solutions to all problems are derived in a step-wise fashion from a general specification of the problem to a concrete solution. The derivations illustrate techniques for developing distributed algorithms.

REFERENCES

• 1: AFEK, Y., AWERBUCH, B, AND GAFNI, E. 1987. Applying static network protocols to dynamic networks. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science IEEE Computer Society (Los Angeles, Oct.), pp. 358-370.
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Selim G. Akl, Parallel Sorting Algorithms, Academic Press, Inc., Orlando, FL, 1990
• 4: Frances Allen , Michael Burke , Philippe Charles , Ron Cytron , Jeanne Ferreant, An overview for the PTRAN analysis system for multiprocessing, Journal of Parallel and Distributed Computing, v.5 n.5, p.617-640, October 1988 [doi>10.1016/0743-7315(88)90015-9]
• 5: Gregory R. Andrews, Concurrent programming: principles and practice, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1991
• 6: Gregory R. Andrews , Fred B. Schneider, Concepts and Notations for Concurrent Programming, ACM Computing Surveys (CSUR), v.15 n.1, p.3-43, March 1983 [doi>10.1145/356901.356903]
• 7: Gregory R. Andrews , Michael Coffin , Irving Elshoff , Kelvin Nilson , Gregg Townsend , Ronald A. Olsson , Titus Purdin, An overview of the SR language and implementation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.1, p.51-86, Jan. 1988 [doi>10.1145/42192.42324]
• 8: M. Annaratone , E. Arnould , T. Gross , H. T. Kung , M. S. Lam, Warp architecture and implementation, Proceedings of the 13th annual international symposium on Computer architecture, p.346-356, June 02-05, 1986, Tokyo, Japan
• 9: M. Stella Athins , Ronald A. Olsson, Performance of multi-tasking and synchronization mechanisms in the programming language SR, Software—Practice & Experience, v.18 n.9, p.879-895, September 1988 [doi>10.1002/spe.4380180906]
• 10: Henri E. Bal , Jennifer G. Steiner , Andrew S. Tanenbaum, Programming languages for distributed computing systems, ACM Computing Surveys (CSUR), v.21 n.3, p.261-322, Sep. 1989 [doi>10.1145/72551.72552]
• 11: 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]
• 12: Kenneth P. Birman , Thomas A. Joseph, Reliable communication in the presence of failures, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.47-76, Feb. 1987 [doi>10.1145/7351.7478]
• 13: Nicholas Carriero , David Gelernter , Jerrold Leichter, Distributed data structures in Linda, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.236-242, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512666]
• 14: S. Chandrasekaran , S. Venkatesan, A message-optimal algorithm for distributed termination detection, Journal of Parallel and Distributed Computing, v.8 n.3, p.245-252, Mar. 1990 [doi>10.1016/0743-7315(90)90099-B]
• 15: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 16: K. M. Chandy , J. Misra, The drinking philosophers problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.632-646, Oct. 1984 [doi>10.1145/1780.1804]
• 17: Ernest Jen-Hao Chang, Decentralized algorithms in distributed systems, 1979
• 18: CHANG, E. J. H. 1982. Echo algomthms: Depth parallel operations on general graphs. IEEE Trans Softw. Eng. 8, 4 (Jul.), 391-401.
• 19: David D. Clark, The structuring of systems using upcalls, Proceedings of the tenth ACM symposium on Operating systems principles, p.171-180, December 1985, Orcas Island, Washington, United States
• 20: P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with “readers” and “writers”, Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971 [doi>10.1145/362759.362813]
• 21: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 22: D~JKSTRA, E. W., AND SCHOLTEN, C. S. 1980. Termination detection in diffusing computations. Inf. Process. Lett. 11, 1 (Aug.), 1 4.
• 23: DIJKSTRA, E. W., FEIJEN, W. H. J., AND VAN GASTEREN, A. J. M. 1983. Derivation of a termination detection algorithm for distributed computation. Inf. Process. Lett. 16, 5 (JunO, 217-219.
• 24: ELSHOFF, I. J. P., AND ANDREWS, G. R. 1988. The development of two distributed algorithms for network topology. Tech. Rep. TR 88-13. Dept. of Computer Science, Univ. of Arizona.
• 25: Raphael Finkel , Udi Manber, DIB—a distributed implementation of backtracking, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.2, p.235-256, April 1987 [doi>10.1145/22719.24067]
• 26: Geoffrey C. Fox , Mark A. Johnson , Gregory A. Lyzenga , Steve W. Otto , John K. Salmon , David W. Walker, Solving problems on concurrent processors. Vol. 1: General techniques and regular problems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 27: Nissim Francez, Distributed Termination, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.1, p.42-55, Jan. 1980 [doi>10.1145/357084.357087]
• 28: GARCIA-MOLINA, H. 1982. Elections in a distributed computing system. IEEE Trans. Comput. C-31, 1 (Jan.), 48-59.
• 29: N H Gehani , W D Roome, Concurrent C, Software—Practice & Experience, v.16 n.9, p.821-844, Sept. 1986
• 30: David Gelernter, Generative communication in Linda, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.80-112, Jan. 1985 [doi>10.1145/2363.2433]
• 31: GENTLEMAN, W. M. 1981. Message passing between sequential processes: The reply primitive and the administrator concept. Softw. Pract. Exper. 11,435-466.
• 32: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 33: GRIT, D. H., AND McGRAw, J. R. 1985. Programming divide and conquer on a MIMD machine. Softw. Pract. Exper. 15, 1 (Jan.), 41-53.
• 34: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 35: W D Hillis, The connection machine, MIT Press, Cambridge, MA, 1985
• 36: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 37: 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]
• 38: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 39: LAMPORT, L. 1982. An assertional correctness proof of a distributed algorithm. Sci. Comput. Program. 2, 3 (Dec.), 175-206.
• 40: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 41: Hugh C. Lauer , Roger M. Needham, On the duality of operating system structures, ACM SIGOPS Operating Systems Review, v.13 n.2, p.3-19, April 1979 [doi>10.1145/850657.850658]
• 42: LELANN, G. 1977. Distributed systems: Towards a formal approach. In Proceedings of Information Processing 77. North-Holland Publishing Co., Amsterdam, pp. 155-160.
• 43: Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
• 44: Mamoru Maekawa , Arthur E Oldehoeft , Rodney R Oldehoeft, Operation systems: advanced concepts, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1986
• 45: Keith Marzullo , Susan Owicki, Maintaining the time in a distributed system, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.295-305, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806730]
• 46: R McCurley , F B Schneider, Derivation of a distributed algorithm for finding paths in directed networks, Science of Computer Programming, v.6 n.1, p.1-9, Jan. 1986
• 47: Jayadev Misra, Detecting termination of distributed computations using markers, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.290-294, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806729]
• 48: Jayadev Misra , K. M. Chandy, Termination Detection of Diffusing Computations in Communicating Sequential Processes, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.37-43, Jan. 1982 [doi>10.1145/357153.357156]
• 49: MITCHELL, J. G., MAYBURY, W., AND SWEET, R. 1979. Mesa language manual, version 5.0. Report CSL-79-3, Xerox Palo Alto Research Center, Palo Alto, Calif.
• 50: MORGAN, C. 1985. Global and logical time in distributed algorithms. Inf Process. Lett. 20, 4 (May), 189-194.
• 51: OWlCK~, S. ANU GRIES, D. 1976. An axiomatic proof technique for parallel programs. Acta Inf. 6, 319-340.
• 52: James L. Peterson , Abraham Silberschatz, Operating system concepts (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 53: RANA, S. P. 1983. A distributed solution of the distributed termination problem. Inf. Process. Lett. 17, 1 (Jul.), 43-46.
• 54: M. Raynal , D. Beeson, Algorithms for mutual exclusion, MIT Press, Cambridge, MA, 1986
• 55: Michel Raynal, Networks and distributed computation: concepts, tools, and algorithms, MIT Press, Cambridge, MA, 1988
• 56: Michel Raynal, Distributed algorithms and protocols, John Wiley & Sons, Inc., New York, NY, 1988
• 57: Glenn Ricart , Ashok K. Agrawala, An optimal algorithm for mutual exclusion in computer networks, Communications of the ACM, v.24 n.1, p.9-17, Jan. 1981 [doi>10.1145/358527.358537]
• 58: SANDBERG, e., GOLDBERG, D. KLEIMAN, S., WALSH, D., AND LYON, B. 1985. Design and implementation of the Sun network filesystem. In Proceedings of the Usenix Conference. (Jun~). pp. 119-130.
• 59: Richard D. Schlichting , Fred B. Schneider, Fail-stop processors: an approach to designing fault-tolerant computing systems, ACM Transactions on Computer Systems (TOCS), v.1 n.3, p.222-238, August 1983 [doi>10.1145/357369.357371]
• 60: SCHNEIDER, F. B. 1980. Ensuring consistency in a distributed database system by use of distributed semaphores. In Proceedings of International Symposium on Distributed Databases. (Versailles, France, Mar.), pp. 183-189.
• 61: Fred B. Schneider, Synchronization in Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.125-148, April 1982 [doi>10.1145/357162.357163]
• 62: M. W. Alford , J. P. Ansart , G. Hommel , L. Lamport , B. Liskov , G. P. Mullery , F. B. Schneider, Distributed systems: methods and tools for specification. An advanced course, Springer-Verlag New York, Inc., New York, NY, 1985
• 63: Fred B. Schneider , David Gries , Richard D. Schlichting, Fault-tolerant broadcasts, Science of Computer Programming, v.4 n.1, p.1-15, April 1984 [doi>10.1016/0167-6423(84)90009-1]
• 64: SmSERSCHATZ, A 1979. Communication and synchronization m distributed systems. IEEE Trarzs. Softw. Engr. SE 5, 6 (Nov.), 542-546.
• 65: Ichiro Suzuki , Tadao Kasami, A distributed mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.3 n.4, p.344-349, Nov. 1985 [doi>10.1145/6110.214406]
• 66: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 67: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• 68: THOMAS, R. H., AND CROW~HER, W. 1988. The uniform system: An approach to runtime support for large scale shared memory parallel processors. In Proceedings of the 1988 International Conference on Parallel Processing. IEEE Computer Society (St. Charles, Illinois, Aug.), pp. 245-254.
• 69: THOMPSON, K. 1978. UNIX implementation. Bell Syst. Tech. J. 57, 6, part 2 (Jul.-Aug.), 1931-1946

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency
      D.4.4 Communications Management
          Subjects: Message sending

General Terms:
Algorithms, Design

Keywords:
clients and servers, distributed and parallel algorithms, distributed programming, distributed programming methods, heartbeat algorithms, networks of filters, patterns for interprocess communication, probe/echo algorithms, replicated servers, token-passing algorithms