D. R. Cheriton
Abstract
Naming is an important aspect of distributed system design. A naming system allows users and programs to assign character-string names to objects, and subsequently use the names to refer to those objects. With the interconnection of clusters of computers by wide-area networks and internetworks, the domain over which naming systems must function is growing to encompass the entire world.
In this paper we address the problem of a global naming system, proposing a three-level naming architecture that consists of global, administrational, and managerial naming mechanisms, each optimized to meet the performance, reliability, and security requirements at its own level. We focus in particular on a decentralized approach to the lower levels, in which naming is handled directly by the managers of the named objects. Client-name caching and multicast are exploited to implement name mapping with almost optimum performance and fault tolerance. We also show how the naming system can be made secure. Our conclusions are bolstered by experience with an implementation in the V distributed operating system.
- 1 BIRRELL, A. D., LAMPSON, B. W., NEEDHAM, R. M., AND SCHROEDER, M. D. A global authentication service without global trust. In Proceedings of 1986 IEEE Symposium on Security and Privacy (Oakland, Calif., April 1986) IEEE, New York, 1986, pp. 223-230.]]Google Scholar
- 2 BIRRELL, A. D., LEVIN, R., NEEDHAM, R. M., AND SCHROEDER, M.D. Grapevine: An exercise in distributed computing. Commun. ACM 25, 4 (April 1982), 260-274.]] Google Scholar
- 3 BOGGS, D.R. Internet broadcasting. Tech. Rep. CSL-83-3, Xerox, Oct. 1983.]]Google Scholar
- 4 RROWNBRtDGE, D. R., MARSHALL, L. F., AND RANDELL, B. The Newcastle Connection--or UNIXes of the world unite! So/tw. Pract. Exper. 12, 12 (Dec. 1982), 1147-1162.]]Google Scholar
- 5 CHERITON, D.R. UIO: A uniform I/O system interface for distributed systems. ACM Trans. Comput. Syst. 5, 1 (Feb. 1987), 12-46.]] Google Scholar
- 6 CHERITON, D.R. The V distributed system. Commun. ACM 3I, 3 (Mar. 1988), 105-115.]] Google Scholar
- 7 CHERITON, D. R. VMTP: A transport protocol for the next generation of communication systems. In Proceedings of the SIGCOMM '86 Symposium: Communication Architectures and Protocols (Stowe, Vt., Aug. 1986). ACM, New York, 1986, pp. 406-415. Also in SIGCOMM Comput. Commun. ReG. 16, 3.]] Google Scholar
- 8 CHERITON, D. R., AND DEERING, S. E. Host groups: A multicast extension for datagram internetworks. In Proceedings of the Ninth Data Communications Symposium (Sept. 1985). ACM, New York, 1985, pp. 172-179. Published as Comput. Commun. Rev. 15, 4.]] Google Scholar
- 9 CHERITON, D. R., AND MANN, T.P. Uniform access to distributed name interpretation in the V-System. In Proceedings of the Fourth International Conference on Distributed Computing Systems (San Francisco, May 1984). IEEE, New York, 1984, pp. 290-297.]]Google Scholar
- 10 CHERITON, D. R., AND ZWAENEPOEL, W. Distributed process groups in the V kernel. ACM Trans. Comput. Syst. 3, 2 (May 1985), 77-107.]] Google Scholar
- 11 DEERING, S.E. Host extensions for IP multicasting. Tech. Rep. RFC 988, Network Information Center, SRI International, July 1986.]] Google Scholar
- 12 DEER1NG, S. E., AND CHERITON, D. R. Host groups: A multicast extension to the Internet protocol. Tech. Rep. RFC 966, Network Information Center, SRI International, Dec. 1985.]]Google Scholar
- 13 DEMERS, A., GREENE, D., HAUSER, C., IRISH, W., LARSON, J., SHENKER, S., STURGIS, H., SWINEHART, D., AND TERRY, D. Epidemic algorithms for replicated database maintenance. In Proceedings of the 6th Annual Symposium on Principles of Distributed Computing (Vancouver, B.C., Aug. 1987). ACM, New York, 1987, pp. 12-21.]] Google Scholar
- 14 DIGITAL EQUIPMENT CORPORATION, INTEL CORPORATION, AND XEROX CORPORATION. The Ethernet: A local area network--data link layer and physical layer specifications, Version 1.0. Sept. 1980.]]Google Scholar
- 15 GIFFORD, D.S. Information storage in a decentralized computer system. Ph.D. dissertation, Stanford Univ., June 1981. Also available as Xerox PARC Tech. Rep. CSL-81-8.]] Google Scholar
- 16 LAMPSON, B.W. Designing a global name service, in Proceedings of the 5th Symposium on Principles of Distributed Computing (Calgary, Alb., Aug. 1986). ACM, New York, 1986, pp. 1-10.]] Google Scholar
- 17 LEFFLER, S., KARELS, M., AND McKUSlCK, M. Measuring and improving the performance of 4.2BSD. In I984 USENIX Summer Conference Proceedings (Pittsburgh, Pa., June 1984). USENIX, pp. 237-252.]]Google Scholar
- 18 MANN, T.P. Decentralized naming in distributed computer systems. Ph.D. dissertation, Stanford Univ., May 1987. Available as report STAN-CS-87-1179.]] Google Scholar
- 19 MOCKAPETRIS, P. Domain names: Concepts and facilities. Tech. Rep. RFC 882, Network information Center, SRI International, Sept. 1983.]] Google Scholar
- 20 MOCKAPETRIS, P. Domain names: Implementation and specification. Tech. Rep. RFC 883, Network Information Center, SRI International, Sept. 1983.]] Google Scholar
- 21 MOGUL, J.C. Representing information about files. Ph.D. dissertation, Stanford Univ., March 1986. Available as Computer Science Tech. Rep. STAN-CS-86-1103.]] Google Scholar
- 22 OPPEN, D. C., AND DALAL, Y.K. The clearinghouse: A decentralized agent for locating named objects in a distributed environment. ACM Trans. Office Inf. Syst. 1, 3 (July 1983), 230-253.]] Google Scholar
- 23 RITCHIE, D. M., AND THOMPSON, K. The UNIX timesharing system. Commun. ACM 17, 7 (July 1974), 365-375.]] Google Scholar
- 24 RIPEST, R. L., SHAMIR, A., AND ADLEMAN, L. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 2 (Feb. 1978), 120-126.]] Google Scholar
- 25 RowE, L. A., AND BIRMAN, K.P. A local network based on the UNIX operating system. IEEE Trans. Softw. Eng. SE-8, 2 (March 1982), 137-146.]]Google Scholar
- 26 SANDBERG, R., GOLDBERG, D., KLEIMAN, S., WALSH, D., AND LYON, B. Design and implementation of the Sun network filesystem. Tech. Rep. Sun Microsystems, Inc., 1985.]]Google Scholar
- 27 SCHROEDER, M. D., BIRRELL, A. D., AND NEEDHAM, R.M. Experience with Grapevine: The growth of a distributed system. ACM Trans. Comput. Syst. 2, 1 (Feb. 1984), 3-23.]] Google Scholar
- 28 SHELTZER, A.B. Network transparency in an internetwork environment. Ph.D. dissertation, Univ. of California, Los Angeles, 1985. Available as UCLA Tech. Rep. CSD-850028.]] Google Scholar
- 29 STRONG, H. R., AND DOLEV, D. Byzantine Agreement. Res. Rep. RJ 3714 (42930), IBM Research Division, Dec. 1982.]]Google Scholar
- 30 TERRY, D.B. Distributed name servers: Naming and caching on large distributed computing environments. Ph.D. dissertation, Univ. of California, Berkeley, 1985. Available as UCB/CSD Tech. Rep. 85-228, and as Xerox PARC Tech. Rep. CSL-85-1.]] Google Scholar
- 31 THEIMER, S. M., LANTZ, K. A., AND CHERITON, D.S. Preemptable remote execution facilities for the V System. In Proceedings of the l Oth Symposium on Operating System Principles. ACM, New York, 1985.]] Google Scholar
- 32 WALKER, B., POPEK, G., ENGLISH, R., KLINE, C., AND THIEL, G. The LOCUS distributed operating system. In Proceedings of the 9th Symposium on Operating Systems Principles (Bretton Woods, N.H., Oct. 1983). ACM, New York, 1983, pp. 49-70. Published as Operating Systems Review 17, 5.]] Google Scholar
- 33 WALL, D.W. Mechanisms for broadcast and selective broadcast. Tech. Report 190, Computer Systems Laboratory, Stanford Univ., June 1980.]]Google Scholar
- 34 WELCH, B., AND OUSTERHOUT, J. Prefix tables: A simple mechanism for locating files in a distributed system. Tech. Rep., Computer Science Div., EECS Dept., Univ. of California, Berkeley, Oct. 1985.]] Google Scholar
Index Terms
- Decentralizing a global naming service for improved performance and fault tolerance
Recommendations
CosNamingFT A Fault-Tolerant CORBA Naming Service
SRDS '99: Proceedings of the 18th IEEE Symposium on Reliable Distributed SystemsThis paper describes the design and implementation of a fault-tolerant CORBA naming service - CosNamingFT. Every CORBA object is accessed through its Interoperable Object Reference (IOR), which is registered with the CORBA name service. The name service ...
The profile naming service
Profile is a descriptive naming service used to identify users and organizations. This paper presents a structural overview of Profile's three major components: a confederation of attribute-based name servers, a name space abstraction that unifies the ...
Understanding naming in distributed systems
Naming in distributed systems is modelled as a string translation problem. Viewing names as strings and name resolution mechanisms as syntax directed translators provides a formal handle on the loosely understood concepts associated with naming: we give ...
Reviews
Jerzy J. A. Klaczak
This paper describes a successful attempt to create a unified and fully transparent naming system covering a whole organization. On top of frequently accessed “managerial” directories (stored in individual file servers), the authors superimpose an additional layer of “administrational” directories (implemented by cooperating managers). The multicasts used to communicate with these directories set a current limit of roughly 1000 hosts on the entire system. Further growth, even to worldwide scale, is enabled by connecting independent systems to an additional layer of directories implemented using well-known global naming techniques. The authors show how to make such a system secure. The system has no separate file and name servers, but each manager knows the full global names of its objects. Clients use small caches of directory names to bypass multicasts and to decide where to send the naming request. The hit ratio is well over 99 percent in typical systems. Caches are updated by deleting stale entries on use, allowing the system to achieve optimal fault tolerance, message traffic, and response time. The text is clear, concise, and well written. All the parts necessary to make a good research paper are present here. The authors not only describe the development, analysis, and field tests for theoreticians, they also give many practical guidelines for practitioners of distributed systems. Even beginners can start with the reference list and the discussion of related works. The only lack is a discussion of the direction for further research.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments