16. Lampson, B, and Sturgis, H.K. Crash Recovery in a Distributed
`System. (unpublished), Xerox Palo Alto Research Center, 1979.
`17. Liskov, Barbara. Linguistic support for distributed programs: a
`status report. Laboratory for Computer Science Computation
`Structures Group Memo 201, MIT, Cambridge, 1980.
`18. Metcalfe, R.M., and Boggs, D.R. Ethernet: distributed packet
`switching for local computer networks. Comm. A CM 19, 7 (July
`1976) 395-404.
`19. Nelson, Bruce Jay. Remote Procedure Call. Ph.D. Dissertation,
`Report CM U-CS-81-119, Carnegie-Mellon University, Pittsburgh,
`PA, 1981.
`20. Ousterhout, John K., Scelza, Donald, A., and Sindhu, Pradeep.
`Medusa: an experiment in distributed operating system structure.
`Comm. ACM 23, 2 (Feb. 1980), 92-105.
`21. Peterson, James L. Notes on a workshop on distributed
`computing. Operating Systems Review 13, 3 (July 1979), 18-27.
`22. Popek, G., et al. Locus: A network transparent, high reliability
`distributed system. Proc. 8th Syrup. on Operating System Principles,
`Dec. 1981, 169-177.
`23. Rawson, E.G., and Metcalfe R.M. Fibernet: muhimode optical
`fibers for local computer networks. IEEE Trans. on Computer
`Communication COM-26, 7 (July 1978), 983-990.
`24. Sahzer, J.H. End-to-end arguments in system design. Proc. 2nd
`Int. Conf. on Operating Systems. Paris (April 1981).
`25. Saltzer, J.H., Clark, D., and Reed, D. Version Two Ring
`Network. Laboratory for Computer Science Report, MIT,
`Cambridge, 1981.
`26. Spector, Alfred Z. Multiprocessing Architectures for Local
`Computer Networks. Ph.D. Dissertation, Report STAN-CS-81-874,
`Stanford University, 1981.
`27. Swan, R.J., Fuller, S.H., and Siewiorek, D.P. Cm* A modular
`multi-microprocessor. Proc. of the National Computer Conference.
`June 1977, 636-644.
`28. Thacker, C.P., McCreight, E.M., Lampson B.W., Sproull, R.F.,
`and Boggs, D.R. Alto: A personal computer. In Siewiorek, O., Bell,
`G., and Newell, A. Computer Structures: Readings and Examples.
`Second ed. McGraw Hill, New York, 1981.
`29. Wilkes, M.V., and Wheeler, D.J. The Cambridge digital
`communication ring. Proc. Local Area Communication Network
`Symposium. Boston, May 1979.
`30. ALTO: A Personal Computer System Hardware Manual. Xerox
`Palo Alto Research Center, 1979.
`31. Zimmerman, H. OSI reference model--the ISO model of
`architecture for open systems interconnection. IEEE Trans. on
`Communication COM-28, 4 (Apr. 1980), 425-432.
`
`260
`
`Operating Systems
`Grapevine: An Exercise in
`Distributed Computing
`
`Anita K. Jones
`Editor
`
`A n d r e w D. Birrell, R o y Levin,
`R o g e r M. N e e d h a m , a n d Michael D. Schroeder
`
`Xerox Palo Alto Research Center
`
`Grapevine is a multicomputer system on the Xerox
`research internet. It provides facilities for the delivery of
`digital messages such as computer mail; for naming
`people, machines, and services; for authenticating people
`and machines; and for locating services on the internet.
`This paper has two goals: to describe the system itself
`and to serve as a case study of a real application of
`distributed computing. Part I describes the set of services
`provided by Grapevine and how its data and function are
`divided among computers on the internet. Part II pre-
`sents in more detail selected aspects of Grapevine that
`illustrate novel facilities or implementation techniques,
`or that provide insight into the structure of a distributed
`system. Part III summarizes the current state of the
`system and the lessons learned from it so far.
`
`CR Categories and Subject Descriptors: C.2.4 [Com-
`puter-Communication Networks]: Distributed Systems--
`distributed applications, distributed databases; C.4 [Per-
`formance of Systems]--reliability, availability and ser-
`viceabifity; D.4.7 [Operating Systems]: Organization and
`Design--distributed systems; H.2.4 [Database Manage-
`ment]: Systems--distributed systems; H.2.7 [Database
`Management]: Database Administration; H.4.3 [Infor-
`mation Systems Applications]: Communications Appli-
`cations-electronic mail
`General Terms: Design, Experimentation, Reliability
`
`Part I. Description of Grapevine
`
`1. Introduction
`
`Grapevine is a system that provides message delivery,
`resource location, authentication, and access control ser-
`
`Authors' Present Addresses: Andrew D. Birrell, Roy Levin, and
`Michael D. Schroeder, Xerox Palo Alto Research Center, Computer
`Science Laboratory, 3333 Coyote Hill Road, Palo Alto, CA 94304;
`Roger M. Needham, University of Cambridge Computer Laboratory,
`Corn Exchange Street, Cambridge, CB2 3QG, United Kingdom.
`Permission to copy without fee all or part of this material is
`granted provided that the copies are not made or distributed for direct
`commercial advantage, the ACM copyright notice and the title of the
`publication and its date appear, and notice is given that copying is by
`permission of the Association for Computing Machinery. To copy
`otherwise, or to republish, requires a fee and/or specific permission.
`© 1982 ACM 0001-0782/82/0400-0260 $00.75.
`
`Communications
`of
`the ACM
`
`April 1982
`Volume 25
`Number 4
`
`Google Inc.
`GOOG 1027
`IPR of U.S. Patent No. 6,286,045
`
`

`
`vices in a computer internet. The implementation of Grapevine is distributed and replicated. By distributed we mean that some of the services provided by Grape- vine involve the use of multiple computers communicat- ing through an internet; by replicated we mean that some of the services are provided equally well by any of several distinct computers. The primary use of Grapevine is delivering computer mail, but Grapevine is used in many other ways as well. The Grapevine project was motivated by our desire to do research into the structure of distrib- uted systems and to provide our community with better computer mail service. Plans for the system were presented in an earlier paper 5. This paper describes the completed system. The mechanisms discussed below are in service support- ing more than 1500 users. Designing and building Grapevine took about three years by a team that aver- aged two to three persons. 1.1 Environment for Grapevine Figure l'illustrates the kind of computing environ- ment in which Grapevine was constructed and operates. A large internet of this style exists within the Xerox Corporation research and development community. This internet extends from coast-to-coast in the U.S.A. to Canada, and to England. It contains over 1500 computers on more than 50 local networks. Most computing is done in personal workstation com- puters 12; typically each workstation has a modest amount of local disk storage. These workstations may be used at different times for different tasks, although gen- erally each is used only by a single individual. The internet connecting these workstations is a collection of Ethernet local networks 6, gateways, and long distance links (typically telephone lines at data rates of 9.6 to 56 Kbps). Also connected to the internet are server com- puters that provide shared services to the community, such as file storage or printing. Protocols already exist for communicating between computers attached to the internet 11 . These protocols provide a uniform means for addressing any computer attached to any local network in order to send individual packets or to establish and use byte streams. The indi- vidual packets are typically small (up to 532 bytes), and are sent unreliably (though with high probability of success) with no acknowledgment. The byte stream pro- tocols provide reliable, acknowledged, transmission of unlimited amounts of data 1 . 1.2 Services and Clients Our primary consideration when designing and im- plementing Grapevine was its use as the delivery mech- anism for a large, dispersed computer mail system. A computer mail system allows a group of human users to exchange messages of digital text. The sender prepares a message using some sort of text editing facility and names a set of recipients. He then presents the message to a delivery mechanism. The delivery mechanism moves the message from the sender to an internal buffer for each recipient, where it is stored along with other mes- sages for that recipient until he wants to receive them. We call the buffer for a recipient's messages an inbox. When ready, the recipient can read and process the messages in his inbox with an appropriate text display program. The recipient names supplied by the sender may identify distribution lists: named sets of recipients, each of whom is to receive the message. We feel that computer mail is both an important application of dis- tributed computing and a good test bed for ideas about how to structure distributed systems. Buffered delivery of a digital message from a sender to one or more recipients is a mechanism that is useful in many contexts: it may be thought of as a general communication protocol, with the distinctive property that the recipient of the data need not be available at the time the sender wishes to transmit the data. Grapevine separates this message delivery function from message creation and interpretation, and makes the delivery func- tion available for a wider range of uses. Grapevine does not interpret the contents of the messages it transports. Interpretation is up to the various message manipulation programs that are software clients of Grapevine. A client Fig. 1. An Example of a Small Internet. r Wo,-kstation r I Workstat,oo I I ) ~ ~ Ethernet I ~ ~ Gateway ~ telephone line Ethernet J Workstation Workstation Server Workstation Gateway I I Server I I Ethernet Workstation 261 Communications of the ACM April 1982 Volume 25 Number 4
`
`

`
`program implementing a computer mail user interface will interpret messages as interpersonal, textual memos. Other clients might interpret messages as print files, digital audio, software, capabilities, or data base updates. Grapevine also offers authentication, access control, and resource location services to clients. For example, a document preparation system might use Grapevine's resource location service to find a suitable printing server attached to the internet (and then the message delivery service to transfer a document there for printing) or a file server might use Grapevine's authentication and access control services to decide if a read request for a particular file should be honored. Grapevine's clients run on various workstations and server computers attached to the internet. Grapevine itself is implemented as programs running on server computers dedicated to Grapevine. A client accesses the services provided by Grapevine through the mediation of a software package running on the client's computer. The Grapevine computers cooperate to provide services that are distributed and replicated. 2. Design Goals We view distributed implementation of Grapevine both as a design goal and as the implementation tech- nique that best meets the other design goals. A primary motivation for the Grapevine project was implementing a useful distributed system in order to understand some system structures that met a real set of requirements. Once we chose message delivery as the functional do- main for the project, the following specific design goals played a significant role in determining system structure. Grapevine makes its services available to many dif- ferent clients. Thus, it should make no assumptions about message content. Also, the integrity of these ser- vices should not in any way depend on correctness of the clients. Though the use of an unsatisfactory client program will affect the service given to its user, it should not affect the service given to others. These two goals help determine the distribution of function between Grapevine and its clients. Two goals relate to Grapevine's reliability properties. First, a user or client implementor should feel confident that if a message is accepted for delivery then it will either be made available to its intended recipients or returned with an indication of what went wrong. The delivery mechanism should meet this goal in the face of user errors (such as invalid names), client errors (such as protocol violations), server problems (such as disk space congestion or hardware failures), or communication dif- ficulties (such as internet link severance or gateway crashes). Second, failure of a single Grapevine server computer should not mean the unavailability of the Grapevine services to any client. The typical interval from sending a message to its arrival in a recipient's inbox should be a few minutes at most. The typical interactive delay perceived by a client program when delivering or receiving a message should be a few seconds at most. Since small additions to delivery times are not likely to be noticed by users, it is permissible to improve interactive behavior at the ex- pense of delivery time. Grapevine should allow decentralized administra- tion. The users of a widespread internet naturally belong to different organizations. Such activities as admission of users, control of the names by which they are known, and their inclusion in distribution lists should not require an unnatural degree of cooperation and shared conven- tions among administrations. An administrator should be able to implement his decisions by interacting directly with Grapevine rather than by sending requests to a central agency. Grapevine should work well in a large size range of user communities. Administrators should be able to im- plement decentralized decisions to adjust storage and computing resources in convenient increments when the shape, size, or load patterns of the internet change. Grapevine should provide authentication of senders and recipients, message delivery secure from eavesdrop- ping or content alteration, and control on use and mod- ification of its data bases. 3. Overview 3.1 Registration Data Base Grapevine maintains a registration data base that maps names to information about the users, machines, services, distribution lists, and access control lists that those names signify. This data base is used in controlling the message delivery service; is accessed directly for the resource location, access control, and authentication ser- vices; and is used to configure Grapevine itself. Grape- vine also makes the values in the data base available to clients to apply their own semantics. There are two types of entries in the registration data base: individual and group. We call the name of an entry in the registration data base an RName. A group entry contains a set of RNames of other data base entries, as well as additional information that will be discussed later. Groups are a way of naming collections of RNames. The groups form a naming net- work with no structural constraints. Groups are used primarily as distribution lists: specifying a group RName as a recipient for a message causes that message to be sent to all RNames in that group, and in contained groups. Groups also are used to represent access control lists and collections of like resources. An individual entry contains an authenticator (a pass- word), a list of inbox sites, and a connect site, as well as additional information that will be discussed later. The inbox site list indicates, in order of preference, the Grapevine computers where the individual's messages may be buffered. The way these multiple inboxes are 262 Communications April 1982 of Volume 25 the ACM Number 4
`
`

`
`used is discussed in Sec. 4.2. The connect site is an internet address for making a connection to the individ- ual. Thus, an individual entry specifies ways of authen- ticating the identity of and communicating with--by message delivery or internet connection--the named entity. Individuals are used to represent human users and servers, in particular the servers that implement Grapevine. Usually the connect site is used only for individuals that represent servers. Specifying an individ- ual RName (either a human or a server) as a recipient of a message causes the message to be forwarded to and buffered in an inbox for that RName. 3.2 Functions Following is a list of the functions that Grapevine makes available to its clients. Responses to error condi- tions are omitted from this description. The first three functions constitute Grapevine's delivery service. Accept message: sender, password, recipients, message-body ~ ok The client presents a message body from the sender for delivery to the recipients. The sender must be RName of an individual and the password must au- thenticate that individual (see below). The recipients are individual and group RNames. The individuals correspond directly to message recipients while the groups name distribution lists. After Grapevine ac- knowledges acceptance of the message the client can go about its other business. Grapevine then expands any groups specified as recipients to produce the com- plete set of individuals that are to receive the message and delivers the message to an inbox for each. Message polling: individual ~ (empty, nonempty} Message polling is used to determine whether an individual's inboxes contain messages that can be retrieved. We chose not to authenticate this function so it would respond faster and load the Grapevine computers less. Retrieve messages: name, password ~ sequence of messages ~ ok The client presents an individual's name and pass- word. If the password authenticates the individual then Grapevine returns all messages from the corre- sponding inboxes. When the client indicates "ok," Grapevine erases these messages from those inboxes. Grapevine's authentication, access control, and resource location services are implemented by the remaining func- tions. These are called the registration service, because they are all based on the registration data base. Authenticate: individual, password ~ (authentic, bogus} The authentication function allows any client to determine the authenticity of an individual. An indi- 263 vidual/password combination is authentic if the pass- word matches the one in the individual's registration data base entry. 1 Membership: name, group ~ (in, out} Grapevine returns an indication of whether the name is included in the group. Usually the client is interpreting the group as an access control list. There are two forms of the membership function. One indi- cates direct membership in the named group; the other indicates membership in its closure. Resource location: group --~ members individual ~ connect site individual ~ ordered list of inbox sites The first resoucce location function returns a group's membership set. if the group is interpreted as a distribution list, this function yields the individual recipients of a message sent to the distribution list; if the group is interpreted as the name of some service, this function yields the names of the servers that offer the service. For a group representing a service, com- bining the first function with the second enables a client to discover the internet addresses of machines offering the service, as described in Sec. 5. The third function is used for message delivery and retrieval as described in Sec. 4. Registration data base update and inquiry: There are various functions for adding and deleting names in the registration data base, and for inspecting and changing the associated values. 3.3 Registries We use a partitioned naming scheme for RNames. The partitions serve as the basis for dividing the admin- istrative responsibility, and for distributing the data base among the Grapevine computers. We structure the name space of RNames as a two-level hierarchy. An RName is a character string of the form F.R where R is a registry name and F is a name within that registry. Registries can correspond to organizational, geographic, or other arbi- trary partitions that exist within the user community. A two-level hierarchy is appropriate for the size and orga- nizational complexity of our user community, but a larger community or one with more organizational di- versity would cause us to use a three-level scheme. Using more levels would not be a fundamental change to Grapevine. This password-based authentication scheme is intrinsically weak. Passwords are transmitted over the internet as clear-text and clients of the authentication service see individuals' passwords. It also does not provide two-way authentication: clients cannot authenticate servers. The Grapevine design includes proper encryption-based authentication and security facilities that use Needham and Schroeder's protocols 9 and the Federal Data Encryption Standard 8. These better facilities, however, are not implemented yet. Communications April 1982 of Volume 25 the ACM Number 4
`
`

`
`3.4 Distribution of Function As indicated earlier, Grapevine is implemented by code that runs in dedicated Grapevine computers, and by code that runs in clients' computers. The code running in a Grapevine computer is partitioned into two parts, called the registration server and the message server. Although one registration server and one message server cohabit each Grapevine computer, they should be thought of as separate entities. (Message servers and registration servers communicate with one another purely by internet protocols.) Several Grapevine com- puters are scattered around the internet, their placement being dictated by load and topology. Their registration servers work together to implement the registration ser- vice. Their message servers work together to implement the delivery service. As we will see in Secs. 4 and 5, message and registration services are each clients of the other. The registration data base is distributed and repli- cated. Distribution is at the grain of a registry; that is, each registration server contains either entries for all RNames in a registry or no entries for that registry. Typically no registration server contains all registries. Also, each registry is replicated in several different reg- istration servers. Each registration server supports, by publicly available internet protocols, the registration functions described above for names in the registries that it contains. Any server that contains the data for a registry can accept a change to that registry. That server takes the responsibility for propagating the change to the other relevant servers. Any message server is willing to accept any message for delivery, thus providing a replicated mail submission service. Each message server will accept message polling and retrieval requests for inboxes on that server. An individual may have inboxes on several message servers, thus replicating the delivery path for the individual. If an increase in Grapevine's capacity is required to meet expanding load, then another Grapevine computer can be added easily without disrupting the operation of existing servers or clients. If usage patterns change, then the distribution of function among the Grapevine com- puters can be changed for a particular individual, or for an entire registry. As we shall see later this redistribution is facilitated by using the registration data base to de- scribe the configuration of Grapevine itself. The code that runs in clients' machines is called the Grapevine User package. There are several versions of the GrapevineUser package: one for each language or op- erating environment. Their function and characteristics are sufficiently similar, however, that they may be thought of as a single package. This package has two roles: it implements the internet protocols for commu- nicating with particular Grapevine servers; and it per- forms the resource location required to choose which server to contact for a particular function, given the data distribution and server availability situation of the mo- ment. GrapevineUser thus makes the multiple Grape- vine servers look like a single service. A client using the GrapevineUser package never has to mention the name or internet address of a particular Grapevine server. The GrapevineUser package is not trusted by the rest of Grapevine. Although an incorrect package could affect the services provided to any client that uses it, it cannot affect the use of Grapevine by other clients. The imple- mentation of Grapevine, however, includes engineering decisions based on the known behavior of the GrapevineUser package, on the assumption that most clients will use it or equivalent packages. 3.5 Examples of How Grapevine Works With Fig. 2 we consider examples of how Grapevine works. If a user named P. Q were using workstation 1 to send a message to X.Y., then events would proceed as follows. After the user had prepared the message using a suitable client program, the client program would call the delivery function of the GrapevineUser package on workstation I. GrapevineUser would contact some reg- istration server such as A and use the Grapevine resource location functions to locate any message server such as B; it would then submit the message to B. For each recipient, B would use the resource location facilities, and suitable registration servers (such as A ) to determine that recipient's best inbox site. For the recipient X. Y, this might be message server C, in which case B would forward the message to C. C would buffer this message locally in the inbox for X.Y. If the message had more recipients, the message server B might consult other registration servers and forward the message to multiple message servers. If some of the recipients were distribu- tion lists, B would use the registration servers to obtain the members of the appropriate groups. When X. Y wishes to use workstation 2 to read his mail, his client program calls the retrieval function of the GrapevineUser package in workstation 2. Grapevine- User uses some registration server (such as D) that contains the Y registry to locate inbox sites for X. Y, then connects to each of these inbox sites to retrieve his messages. Before allowing this retrieval, C uses a regis- tration server to authenticate X. Y. If X. Y wanted to access a file on the file server E through some file transfer program (FTP) the file server might authenticate his identity and check access control lists by communicating with some registration server (such as A ). 3.6 Choice of Functions The particular facilities provided by Grapevine were chosen because they are required to support computer mail. The functions were generalized and separated so other applications also could make use of them. If they want to, the designers of other systems are invited to use the Grapevine facilities. Two important benefits occur, however, if Grapevine becomes the only mechanism for authentication and for grouping individuals by organi- zation, interest, and function. First, if Grapevine per- 264 Communications April 1982 of Volume 25 the ACM Number 4
`
`

`
`Fig. 2. Distribution of Function. GRAPEVINE Registration Server "A" /\ authenticate, membership Registration Server "D" a°ut~tee ti clte Message Server "B" locate .~.../~sen d I I GrapevineUser Client program user "P.Q" forward Workstation 1 authenticate/~ locate" \ + ! Message 1 Server "C" retrieve' ~ GrapevineUser Client program user "X.Y" GrapevineUser File Server "E" /x FTP connection Workstation 2 forms all authentications, then users have the same name and password everywhere, thus simplifying many admin- istrative operations. Second, if Grapevine is used every- where for grouping, then the same group structure can be used for many different purposes. For example, a single group can be an access control list for several different file servers and also be a distribution list for message delivery. The groups in the registration data base can capture the structure of the user community in one place to be used in many ways. 4. Message Delivery We now consider the message delivery service in more detail. 4.1 Acceptance To submit a message for delivery a client must estab- lish an internet connection to a message server; any operational server will do. This resource location step, done by the GrapevineUser package, is described in Sec. 5. Once such a connection is established, the GrapevineUser package simply translates client proce- dure calls into the corresponding server protocol actions. If that particular message server crashes or otherwise becomes inaccessible during the message submission, then the GrapevineUser package locates another mes- sage server (if possible) and allows the client to restart the message submission. The client next presents the RName and password of the sender, a return To RName, and a list of recipient RNames. The message server authenticates the sender by using the registration service. If the authentication fails, the server refuses to accept the message for delivery. Each recipient RName is then checked to see if it 265 matches an RName in the registration data base. All invalid recipient names are reported back to the client. In the infrequent case thai no registration server for a registry is accessible, all RNames in that registry are presumed for the time being to be valid. The server constructs a property list for the message containing the sender name, returnTo name, recipient list, and a post- mark. The postmark is a unique identification of the message, and consists of the server's clock reading at the time the message was presented for delivery together with the server's internet address. Next, the client ma- chine presents the message body to the server. The server puts the property list and message body in reliable storage, indicates that the message is accepted for deliv- ery, and closes the connection. The client may cancel delivery anytime prior to sending the final packet of the message body, for example, after being informed of invalid recipients. Only the property list is used to direct delivery. A client might obtain the property values by parsing a text message body and require that the parsed text be syn- tactically separated as a "header," but this happens before Grapevine is involved in the delivery. The prop- erty list stays with the message body throughout the delivery process and is available to the receiving client. Grapevine guarantees that the recipient names in the property list were used to control the delivery of the message, and that the sender RName and postmark are accurate. 4.2 Transport and Buffering Once a message is accepted for delivery, the client may go about its other business. The message server, however, has more to do. It first determines the complete list of individuals that should receive the message by Communications April 1982 of Volume 25 the ACM Number 4
`
`

`
`recursively enumerating groups in the property list. It obtains from the registration service each individual's inbox site list. It chooses a destination message server for each on the basis of the inbox site list ordering and its opinion of the present accessibility of the other message servers. The individual names are accumulated in steer- ing lists, one for each message server to which the mes- sage should be forwarded and one for local recipients. The message server then forwards the message and ap- propriate steering list to each of the other servers, and places the message in the inboxes for local recipients. Upon receiving a forwarded message from another server, the same algorithm is performed using the indi- viduals in the incoming steering list as the recipients, all of which will have local inboxes unless the registration data base has changed. The message server stores the property list and body just once on its local disk and places references to the disk object in the individual's inboxes. This sharing of messages that appear in more that one local inbox saves a considerable amount of storage in the server. 2 With this delivery algorithm, messages for an indi- vidual tend to accumulate at the server that is first on the inbox site list. Duplicate elimination, required be- cause distribution lists can overlap, is achieved while adding the message into the inboxes by being sure never to add a message if that same message, as identified by its postmark, was the one previously added to that inbox. This duplicate elimination mechanism fails under certain unusual circumstances such as servers crashing or the data base changing during the delivery process, but requires less computation than the alternative of sorting the list of recipient individuals. In some circumstances delivery must be delayed, for example, all of an individual's inbox sites or a registry's registration servers may be inaccessible. In such cases the message is queued for later delivery. In some circumstances delivery will be impossible: for example, a recipient RName may be removed from the registration data base betwe