On building very large naming systems

ABSTRACT

This position paper draws attention to the construction of very large scale distributed naming systems. Some existing systems of this kind include the Domain Name System (DNS) and the DEC Distributed Name Service (DEC DNS) [10,11]. One of the most important requirements for the system is high availability. Replication is therefore of particular interest in structuring such a system.It is difficult to implement replication for a large and still growing distributed system. Although replication promises attractive properties such as high availability and enhanced reliability, the cost for maintaining consistency is substantial. Many replication control methods have been developed and studied, but few keep a good balance between high availability and reliability. Although replication has been used for large naming and authentication systems [1,10], it is only successful in situations in which the application can handle stale naming data. If an application must keep close track of some key naming data, it may be badly interrupted if the naming data is out of date. In such situations, the standard replication process is not adequate. In the following sections, I will explain the problem in further detail and describe a solution to it based on the experience of designing a global naming system - the Universal Name Service at Cambridge University Computer Laboratory [9].

REFERENCES

• 1: Andrew D. Birrell , Roy Levin , Michael D. Schroeder , Roger M. Needham, Grapevine: an exercise in distributed computing, Communications of the ACM, v.25 n.4, p.260-274, April 1982 [doi>10.1145/358468.358487]
• 2: A. Birrell et al. A simple and efficient implementation for small database. Technical Report, DEC SRC RR24, Jan. 1985.
• 3: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 4: 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]
• 5: S.Kille. The design of QUIPU. Technical Report, UCL, England, RN/89/19,1989.
• 6: Rivka Ladin , Barbara Liskov , Liuba Shrira, Lazy replication: exploiting the semantics of distributed services, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.43-57, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93399]
• 7: L. Lamport. The part-time parliament. Technical report, DEC SRC RR 49, 1989.
• 8: Butler W Lampson, Designing a global name service, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.1-10, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10591]
• 9: C. Ma. Designing a Universal Name Service. Ph.D. thesis submitted, Computer Lab. Cambridge University, 1992.
• 10: S. Martin et al. Development of the VAX distributed name service. Digital Technical Journal, (9):9-15, Jun. 1989.
• 11: P. Mockapetris , K. J. Dunlap, Development of the domain name system, Symposium proceedings on Communications architectures and protocols, p.123-133, August 16-18, 1988, Stanford, California, United States
• 12: R. Needham. Naming and Protection. In Distributed Systems (Edited by S. Mullender), Addison-Wesley, 1989
• 13: Sushil N. Pandhi, The universal data connection, IEEE Spectrum, v.24 n.7, p.31-37, July 1987