By J. H. Saltzer, 29 March 1999 (Minor update, 28 March 2000 11:30 a.m.).

This may be a good opportunity to point out (or remind your class) that in systems, before you can talk about any topic you first need to have talked about all of the other topics. Grapevine involves networks, naming, protection, consistency in distributed systems, modularity, scaling, file systems, hierarchy...

This is a good example of a paper that might well be read several times, each time focusing on one aspect, largely ignoring the aspects we haven't come to yet, and reviewing those aspects we covered previously, but in the new light of the current topic. The discussion suggestions here are focused primarily on the naming aspects of Grapevine.

• Do we recognize any names in the authors, citations, and acknowledgments? (We are beginning to see some names coming up frequently, e.g. Andrew Birrell, Bob Metcalfe, Butler Lampson, etc. One reason is that there are only a few places where systems research is regularly undertaken.)

• What does Grapevine name?
  (People--both as mailboxes and as principals [a chapter six concept]
  services
  computers
  messages [at a different level--every message has a postmark] )

• In Grapevine, do the names Schroeder.PaloAlto and Schroeder.RedondoBeach refer to the same person with two inboxes or different persons? (Normally two different persons. That is the whole point of having multiple registries, to allow decentralization of name administration without any need to coordinate. A person with redundant inboxes has all the inboxes associated with one name.)

• Why are there

  secondary inboxes? (Fault tolerance [a chapter seven concept])

  Multiple post offices?(

  1. Fault isolation. One disk failure doesn't lose all mail.
  2. support for fault tolerance--secondary inboxes.
  3. scale--to handle many users
  4. performance--want a P.O. that isn't on the other side of the continent or the other side of a slow link.)

  Multiple registries? (Decentralized administration.)

  Multiple registration servers? (Fault tolerance--a registry is replicated at several registration servers.)

• What happens when P.X says "deliver this message to Q.Y? (At the surface level,

  P.X --> Y "Where is Q's inbox?"
Y --> P.X "Q's inbox is at PO6"
P.X --> PO6 "here's a message for Q.Y"

  And Q picks it up...
  Q.Y --> Y "Where is Q.Y's inbox?"
Y --> Q.Y ""Q.Y's inbox is at PO6"
Q.Y --> PO6 "What's new for Q.Y?"
PO6 --> Q.Y "This message from P.X..."

  But note that the first message, sent to registry Y, requires that P know the network attachment point of some registration server that holds a copy of registry Y. There is an additional, fairly elaborate, ceremony involved in discovering that fact.)

• in that example, shouldn't PO6 be something like "PO6.PaloAlto"? (This is a question of naming level in our discourse. PO6 is a symbol that was intended to stand for the binary address of the network attachment point, not as its literal Rname. This is confusing, but important to understand, because the paper uses this same form of discourse. Some names are Rnames, while others are symbols standing for binary addresses.)

• On page 263, top of column 2, "membership", what is "membership in its closure" referring to? (The authors are talking about transitive closure, the set of all the non-list objects contained in a list and all of its sublists. Since there is nothing in Grapevine that prevents a name from appearing in two lists, or prevents list A from containing among its descendents list B and list B containing among its descendents list A, a moderately careful algorithm is needed to construct the transitive closure.)

• What is "resource location"? (This is the DNS-like function of Grapevine. Given a name, tell me the network attachment point identifier that goes with it.)

• How does Grapevine differ with the Internet systems that do the same functions? (
  1. It integrates mail delivery with domain name service.
  2. It provides some protection features.
  3. The naming hierarchy is exactly two-level. (Is this fundamental?)
  4. It allows for multiple inboxes.
  5. It provides a user-identification/mail-list/user-group management system.)

• What is the "internet" this paper talks about? (A Xerox internal forwarding network that uses a non-IP protocol named "PUP".)

• How does Grapevine convert a receive-and-forward network into a store-and-forward network? (
  1. (It employs a reliable byte-stream protocol.
  2. It places message buffers on disk.)

• Why is duplicate elimination done at mailbox buffering time rather than when recursively enumerating the distribution list? (Duplicate elimination could be done at either recursive resolution time or at delivery time. The paper explains their rationale for doing it at delivery in the first full paragraph on page 266: comparing postmarks at delivery takes less computation than sorting the original list of recipients.

  This seems a little odd, but it is probably explained by two unstated environmental concerns:

  1. The computing environment at the time: this system was implemented on Xerox Alto computers, which had about the horsepower, RAM, and disk space of the original IBM PC with an 8086.
  2. They were worried about messages addressed to several long mailing lists. (everyone in Palo Alto, all engineers in the company, everyone working on product X, etc.)
  So it appears they were trying to avoid the need to apply cleverness in doing sorting of large lists in a small space. And since duplicates would be added to a mailbox adjacent to one another, it is very easy to check at delivery time. Sort of like having your mailman weed out duplicate junk mail, rather than having the bulk mailer clean up his address lists.)

• Is there any other use of hierarchy beyond two-part names?
  (Yes. grapevine registries are organized hierarchically, starting with the "gv.gv" group, which contains all registration servers.

  -------------------
  Sample GV registry with four registration servers and four registries (including itself)...The GV registry is replicated on every registration server:
  
  rname  type     value
  r1.gv     i     (pup address of server 1)
  r2.gv     i     (pup address of server 2)
  r3.gv     i     (pup address of server 3)
  r4.gv     i     (pup address of server 4)
  reg1.gv   g      r1.gv r2.gv r3.gv
  reg2.gv   g      r3.gv r4.gv
  reg3.gv   g      r1.gv r4.gv
  gv.gv     g      r1.gv r2.gv r3.gv r4.gv
  -------------------
  

• page 265, col. 2, on accepting mail: "In the infrequent case that no regisration server for a registry is accessible, all RNames in that registry are presumed for the time being to be valid." What is the consequence of this design decision? (Some user errors are reported back to the client at the instant of mailing, while others are delayed.)

• In the same paragraph it says that the server constructs a "property list" for the message, with the sender name, returnTo name, reqcipient list, and postmark. Chapter 5 uses a term of art for this kind of information. What is it? ("metadata".)

• Where is the metadata in Internet mail? (Internet e-mail attaches a header to the front of each message. In addition, there is a little bit more metadata hiding outside the header and text, known as the "envelope address". It is passed from mail server to mail server along with the message header and text.)

• page 267, col. 2, near middle. What is the difference between "not found" and "wrong server"? (The first response means that you have asked the right registry and it can authoritatively say that this name does not exist. There is no better answer to be found anywhere else. The second means that this isn't the right registry to be asking, look elswhere.)

• Compare "wrong server" with DNS non-recursive lookup. (Similar idea: ask nearest server, even though it may not know. If it does (common case) you win. If it doesn't, it will tell you and then you go through the big-deal search.)

• Where does name discovery terminate in Grapevine? (Page 267, column 3, last paragraph. There are two ways. Either you must know an internet address for "GrapevineRServer", or if you are lucky enough to have a registration server within broadcast range, you can broadcast a plea for help getting started: "Does anyone on this net know an RServer?".

  There is another, higher-level form of name discovery: Grapevine apparently also makes use of well-known Rnames. For example, the server name "Maildrop.ms" is the thing you contact to send a message. This name apparently has to be configured into the sending mailer program.)

• Does Grapevine use caching? Where?

• How is a hint different from a cache? (there is a whole sidebar on this subject.)

• Could we apply Grapevine to the modern Internet? (Retrofitting would be a major overhaul, because it cuts across so many existing systems, mail, identification, DNS, etc. Getting it to scale up to the size of the Internet could also be a problem.)

• This sounds like a great system. What happened to it? (This was an internal, trial prototype. Xerox designed a successor named Clearinghouse as a product, but Xerox dropped the ball and nothing ever came out of that product laboratory. See D. K. Smith and R. C. Alexander, "Fumbling the Future," Morrow & Company, 1988.
  In addition, the centralized control of registries didn't appeal to the decentralized sensibilities of the people developing the Internet.)

• Here are two questions that were proposed but not used for one-page reading reports. They bring in later topics, consistency and authentication. But they can be useful triggers for discussion when those topics are reached.

  The Grapevine system employs a "loose" definition of consistency of its distributed registration database. Although "convergence" is guaranteed, administrative updates of database entries are not atomic across all servers. This property can lead to surprises for an administrator who is accustomed to thinking of Grapevine as a single server. Describe at least one sequence of actions that a single administrator can perform to the registration database that can produce unexpected results or errors.

  The Grapevine design team acknowledge their password-based authentication scheme as intrinsically weak, but they quickly skim over the fact that authentication is only one-way. Discuss the problems that a lack of server authentication can cause and how they affect the design goals stated on page 262 of the paper.

• If you are ambitious, there was a followup paper on experience with Grapevine published two years later:
  Michael D. Schroeder, Andrew D. Birrell, and Roger M. Needham. Experience with Grapevine: the growth of a distributed system. ACM Trans. on Computer Systems 2, 1 (February, 1984) pages 3-23.

  ---

  Comments and suggestions: Saltzer@mit.edu