Naming and Computers

The subject of names arises in many fields of computing.
Most innovations in programming language design revolve around name spaces, for example scoped variable names, encapsulation of variable and function names in classes and objects, inheritance of name spaces of those classes.

Large distributed systems like the Internet and its user communities need names e.g. for

1. Sharing of information (e.g. URLs of documents).
2. Communication about objects (e.g. PGP KeyIDs, Hostnames).
3. Tieing objects to short handles (e.g. magnet: URLs in Gnutella).
4. Proof of access rights aka capabilities (e.g. presenting the url
   http://jsecom8.sun.com:80/servlet/EComActionServlet/\
   ECom.LegalPageInfo;jsessionid=1628%3A3c7f8ef1%3Aaac9f867c28793f
   proves that one toiled through the SUN registration procedure and is now allowed to download free software).

I would like to stimulate discussion about naming in Computer Science. Naming has been a topic in various newsgroups and mailing lists, e.g. the eternity fs mailing list (could not find an archive for that), other distributed global file system lists, e.g. the Bluesky ML, the decentralization ML and the p2p-hackers ML.

However there seems to be no central repository of papers, ideas and implementations concerning the manyfold issues in naming. If you know about articles which contain a more ordered, better commented or more thorough summary of those issues and proposed solutions, please send me an e-mail ( matthiasb (at) acm · οrg )
My take on naming is technical by profession, views from other, say linguistic or philosophical, angles are welcome.

Aside: "What exactly is a name? Can we use and dereference names like variables in logical statements?"

is a question philosophers (and logicians) might ask. So far I found texts by

• Frege (no online version yet)
• Bertrand Russell
• Saul Kripke
• Devitt and Sterelny

Resources on Naming

• In an early paper, Butler W. Lampson et al. suggested how to build a global name space. Their design allows replications and partial updates, but seems to assume a distributed database of shared keys for authorization.
• In Sape Mullender's Distributed Computing, the 12th chapter, by Roger Needham, is about names. He explains the uses of names in distributed computing and a list of problems that follow from that. He discusses Lampson's paper shortly.
• Stuart Haber, Scott Stornetta Secure Names for Bit-Strings. The authors present a scheme were short names can be produced from timestamping certificates. These guarantee the integrity of the named document and can be changed over time. Relies on two central authorities, a timestamping service and a repository to look up the actual location.
• Carl Ellisons SPKI Certificate Theory (RFC 2693) has a section on why we cannot expect globaly unique ids to turn up. It includes a history of naming in the computer age with follies like X.509, as well.
• Ross Anderson's Security Engineering contains eight insightful pages about names, pp. 124-132. He explains a lot about the different functions of naming and the silent assumptions about names that do seldom hold.
• Gordon Irlam wrote a page about naming in 1995.
• A collection of papers related to global, censorproof file systems is at cypherspace. Most of the proposed systems have special naming constructs.
• The eternity-fs people had long discussions about namespaces.
• An interesting post is Ted Anderson's Managing a distributed namespace
• Part of the above design (notably the names including hashes of the server's/author's public key) is implemented in the Self Certifing File System and suggested in Ross Anderson's Eternal Resource Locator paper(.pdf).
• Zooko wrote a good if informal memo about the problems of non-self certifying names, trust and commemorability, titled Names: Decentralized, Secure, Human-Memorizable: Choose Two.
• John Perry Barlow's Accra Manifesto is mainly about ICANN and problems arising from central administration of the DNS.
• Clay Shirky wrote an article with the title DNS Hell: Is there a solution?.
• The draft Host Identity Protocol, by Moskowitz et al., proposes an architecture-independent naming scheme for hosts.
• CircleID has a whole lot of articles about DNS and other naming schemes and their impact. For example, Francis Hwang's Do Domain Names Matter? , or
• What should be the goals when designing a naming system? Brad Tempelton wrote a well-thought-out article on that.
• Adam Back's Auditable Namespace
• An IETF draft on A Survey of Internet Identities explains current usage of identifiers on the net.
• Chains of local names are defined in Rivest and Lampson's SDSI.
• The Pet Markup Language is something like SDSI, it translates memorizable names to keys and allows linking through local namespaces.
• It is possible to overload standard resolvers like libresolv in bind9. It has an api for alternative lookup etc. mechanisms, called sdb.
• Chord and Circle define distributed hash tables for lookups. The Chord people even defined a distributed DNS: Serving DNS using Chord (.pdf) by Russ Cox et al.
• Emil Sit and Robert Morris discuss security aspects of distributed hashes in Security Considerations for Peer-to-Peer Distributed Hash Tables (.pdf).
• handle relies on a central database, but might be interesting anyhow. Larry Stone describes handle and PURL in an evaluation.
• The Unified Resource Name (URN) Working Group set out to define ''persistent, location-independent, resource identifiers``. The Dynamic Delegation Discovery System (rfc 3401 - 3405) trys to implement lazy binding from bitstrings to data. The author suggests to use this for resolution of Uniform Resource Identifiers (URI)". URI are a superset of the URNs.
• The Common Name Resolution Protocol serves requests for loosely ''common`` names.
• The eXtensible Name Service (XNS) standards body has renamed itself to the more lyrical ”eXtensible Data Interchange (XDI)“ standards body. They propose a bundle of XML schemata that express and protect(???) information about identities (personal data, organizational info).
• the Digital Object Identifier system proposes yet another global naming scheme. There even was a partial implementation of it, described in a paper by Andy Powell.