Distributed allocation with pools of servers

ABSTRACT

Distributed systems make possible both a high degree of concurrency and robustness in the face of failure. One approach to achieving these goals is to employ pools of servers implementing major system functions. This paper describes the concept of pools of servers, and presents logically distributed, robust algorithms for one problem arising in this approach: the allocation of servers to clients. Three types of allocation problems are identified: free servers, preferred servers, and retentive servers. Allocation protocols based upon the idea of hash addressing are described and analyzed.

REFERENCES

• 1: Ball, E., Feldman,J., Rashid, R., and Rovner,P. RIG, Rochester's intelligent gateway: System overview. IEEE Trans. on Software Engr., SE-2, 4 (Dec. 1976), 321-328.
• 2: Bartlett, J.F. A "NonStop" operating system. Proc. 11th Hawaii Int. Conf. on System Sciences, vol. III, University of Hawaii, Honolulu, 1978, 103-117.
• 3: Belady, L.A. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal 5, 2(1966), 78-101.
• 4: Chang, E.J. Decentralized algorithms in distributed systems. TRCSRG-103, Department of Computer Science, University of Toronto, Oct 1979.
• 5: Jackson, J.R. Networks of waiting lines. Operations Research 5, 4(Aug 1957), 518-521.
• 6: Anita K. Jones , Robert J. Chansler, Jr. , Ivor Durham , Karsten Schwans , Steven R. Vegdahl, StarOS, a multiprocessor operating system for the support of task forces, Proceedings of the seventh ACM symposium on Operating systems principles, p.117-127, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806579]
• 7: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 8: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 9: 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]
• 10: Lamport, L. The implementation of reliable distributed multiprocess systems. Computer Networks 2 (1978), 95-114.
• 11: Lampson, B.W., and Sturgis, H.E. Crash recovery in a distributed data storage system. Working paper, XeroxPARC, 1980.
• 12: LeLann, G. Algorithms for distributed datasharing systems which use tickets. Proc, 3rd Berkeley Workshop on Distributed Data Management and Computer Networks, Berkeley, Aug. 1978, 259-272.
• 13: LeLann, G. A distributed system for real-time transaction processing. Proc, 14th Hawaii Int. Conf. on System Science, Honolulu, Jan. 1981.
• 14: Barbara Liskov , Robert Scheifler, Guardians and actions: linguistic support for robust, distributed programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.7-19, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582155]
• 15: John K. Ousterhout , Donald A. Scelza , Pradeep S. Sindhu, Medusa: an experiment in distributed operating system structure, Communications of the ACM, v.23 n.2, p.92-105, Feb. 1980 [doi>10.1145/358818.358823]
• 16: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 17: Dennis M. Ritchie , Ken Thompson, The UNIX time-sharing system, Communications of the ACM, v.17 n.7, p.365-375, July 1974 [doi>10.1145/361011.361061]
• 18: Rothnie, J.B. and Goodman, N. An overview of the preliminary design of SDD-1: a system for distributed databases. Proc. 2nd Berkeley Workshop on Distributed Data Base and Computer Networks, May 1977.
• 19: 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]
• 20: Marvin H. Solomon , Raphael A. Finkel, The Roscoe distributed operating system, Proceedings of the seventh ACM symposium on Operating systems principles, p.108-114, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806577]
• 21: Stonebraker, M.R. Concurrency control and consistency of multiple copies of data in distributed INGRES. IEEE Trans. on Software Engr., vol. SE-5, 3(May 1979), 188-194.
• 22: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 23: Maurice V. Wilkes , Roger M. Needham, The Cambridge Model Distributed System, ACM SIGOPS Operating Systems Review, v.14 n.1, p.21-29, January 1980 [doi>10.1145/850693.850695]
• 24: Zimmermann, H. OSI reference model-the ISO model of architecture for open systems interconnection. IEEE Trans. Comm. COM-28, 4 (Apr. 1980), 425-432.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Client/server

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Management, Theory