Designing a Global Name Service
Butler W. Lampson


Name service maps a name to a set of properties.  It is the basis for
resource location (such as mail addressing, authentication, etc.). Name
service is not a general database (slower changes, looser integrity
constraints), not a file system (much larger, more available).

Name Service Requirements:

  * Large size
  * Long life
  * High Availability
  * Fault isolation
  * Tolerance of mistrust

This implies hierarchical system.

At the Client Level:

  * Hierarchical Names and their values. Facilities for updating,
    and reading.
	Directory structure.  Edges in the tree are named with the
        directory name. Nodes in the tree are labeled with a timestamp.

  * Protection and Authentication of system.
        Access control is based on an "entity" named in the system.
        Entities password, etc., is stored as a property.  You can use
	your initial access to get access to a directory with a second
	identity, a second password, and also more access.  Can chain this
	authentications	together to extend your abilities

Administrative Level:

  * distributed, replicated copies
	There are a number of distributed copies of each directory.

  * locating copies
		
  * keeping copies synchronized
        Copies are kept approximately the same. Updates are spread via
        "sweeps" or via unstructured message passing between copies.
	Sweep obtains a circular linked list of copies.  Traverses copies,
        collecting a set of all updates. Then applies these updates to
        each copy.

        "Epochs" are used to create new rings (if a server fails
        permanently, for example). Epoch is identified by its starting
        time stamp.

Name Space:

  * names are divided into two parts: 1) Full name of a directory, 2) name
    of entity within the directory. Entity name is expected to be short.
    Directory name is long.

  * hierarchical structure of name space is the basic mechanism for
    growth.  

  * directory can be restructured, using forwarding links to redirect old
    names to their new names.

Caching: Values have expiration times.  They can be cached until then by
    clients.

Values and Updates:

  * value is a tree with labeled arcs and timestamped nodes

  * updates are operations with name a node (via the path to the node and 
    the node's timestamp) and say whether to create the node or remove it.

  * Updates are total (you can always apply them).

  * Updates are commutative: order of two updates does not affect result

  * Updates are idempotent: can apply the same update twice.

Directory Copies:

  * there is always at least one complete ring in set of DCs.

  * there are never two complete non-intersecting rings.

Comments:

  I didn't like this paper.  I thought it was poorly organized and hard to
read.  For example, in the overview section, the first sentence says there
are "6 major abstractions," and then 

Questions:

  Why exactly is a hierarchical system required?  It seems like Lampson
thinks its obvious, but he doesn't justify his statement.

  Admin does static partitioning of data.  In a large name service, is
this enough? 

  Is the assumption that names change slowly valid? (e.g., Akamai DNS
  tricks).  Or, the "location" property of a person?