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 CMU-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 Symp. on Operating System Principles,
`Dec. 1981, 169-177.
`23. Rawson, E.G., and Metcalfe R.M. Fibernet: multimode optical
`fibers for local computer networks. IEEE Trans. on Computer
`Communication COM-26, 7 (July 1978), 983-990.
`24. Saltzer, 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, 0., Bell,
`G., and Newell, A. Computer Structures: Readings and Examples.
`Seconded. 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
`
`Andrew D. Birrell, Roy Levin,
`Roger M. Needham, and 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(cid:173)
`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(cid:173)
`puter-Communication Networks]: Distributed Systems(cid:173)
`distributed applications, distributed databases; C.4 [Per(cid:173)
`formance of Systems]-reliability, availability and ser(cid:173)
`viceability; D.4.7 [Operating Systems]: Organization and
`Design-distributed systems; H.2.4 [Database Manage(cid:173)
`ment]: Systems-distributed systems; H.2.7 [Database
`Management]: Database Administration; H.4.3 [Infor(cid:173)
`mation Systems Applications]: Communications Appli(cid:173)
`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
`theACM
`
`April 1982
`Volume25
`Number 4
`
`PALO ALTO NETWORKS Exhibit 1017 Page 1
`
`

`
`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(cid:173)
`vine involve the use of multiple computers communicat(cid:173)
`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(cid:173)
`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(cid:173)
`ing more than 1500 users. Designing and building
`Grapevine took about three years by a team that aver(cid:173)
`aged two to three persons.
`
`1.1 Environment for Grapevine
`Figure 1' illustrates the kind of computing environ(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`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
`
`Fig. I. An Example of a Small Internet.
`
`attached to any local network in order to send individual
`packets or to establish and use byte streams. The indi(cid:173)
`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(cid:173)
`tocols provide reliable, acknowledged, transmission of
`unlimited amounts of data [ 1].
`
`1.2 Services and Clients
`Our primary consideration when designing and im(cid:173)
`plementing Grapevine was its use as the delivery mech(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`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
`
`Ethernet
`
`telephone line
`
`Ethernet
`
`Ethernet
`
`261
`
`Communications
`of
`the ACM
`
`April 1982
`Volume25
`Number4
`
`PALO ALTO NETWORKS Exhibit 1017 Page 2
`
`

`
`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(cid:173)
`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(cid:173)
`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(cid:173)
`ferent clients. Thus, it should make no assumptions
`about message content. Also, the integrity of these ser(cid:173)
`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(cid:173)
`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
`
`262
`
`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(cid:173)
`pense of delivery time.
`Grapevine should allow decentralized administra(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`ping or content alteration, and control on use and mod(cid:173)
`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(cid:173)
`vices; and is used to configure Grapevine itself. Grape(cid:173)
`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(cid:173)
`work with no structural constraints. Groups are used
`primarily as distribution lists: specifying a group RN arne
`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(cid:173)
`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
`
`Communications
`of
`the ACM
`
`April 1982
`Volume 25
`Number4
`
`PALO ALTO NETWORKS Exhibit 1017 Page 3
`
`

`
`used is discussed in Sec. 4.2. The connect site is an
`internet address for making a connection to the individ(cid:173)
`ual. Thus, an individual entry specifies ways of authen(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`word. If the password authenticates the individual
`then Grapevine returns all messages from the corre(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`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 in box sites
`The first resource 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(cid:173)
`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 hase, and for inspecting
`and changing the associated values.
`
`3.3 Registries
`We use a partitioned naming scheme for RN ames.
`The partitions serve as the basis for dividing the admin(cid:173)
`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(cid:173)
`trary partitions that exist within the user community. A
`two-level hierarchy is appropriate for the size and orga(cid:173)
`nizational complexity of our user community, but a
`larger community or one with more organizational di(cid:173)
`versity would cause us to use a three-level scheme. Using
`more levels would not be a fundamental change to
`Grapevine.
`
`1 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
`of
`theACM
`
`April 1982
`Volume 25
`Number4
`
`PALO ALTO NETWORKS Exhibit 1017 Page 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(cid:173)
`puters are scattered around the internet, their placement
`being dictated by load and topology. Their registration
`servers work together to implement the registration ser(cid:173)
`vice. Their message servers work together to implement
`the delivery service. As we will see in Sees. 4 and 5,
`message and registration services are each clients of the
`other.
`The registration data base is distributed and repli(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`nicating with particular Grapevine servers; and it per(cid:173)
`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(cid:173)
`ment. GrapevineUser thus makes the multiple Grape-
`
`264
`
`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(cid:173)
`mentation of Grapevine, however, includes engineering
`the known behavior of the
`decisions based on
`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 Grapevine User package on
`workstation l. GrapevineUser would contact some reg(cid:173)
`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(cid:173)
`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(cid:173)
`User uses some registration server (such as D) that
`contains the Y registry to locate in box sites for X Y, then
`connects to each of these inbox sites to retrieve his
`messages. Before allowing this retrieval, C uses a regis(cid:173)
`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(cid:173)
`zation, interest, and function. First, if Grapevine per-
`
`Communications
`of
`theACM
`
`April 1982
`Volume 25
`Number4
`
`PALO ALTO NETWORKS Exhibit 1017 Page 5
`
`

`
`Fig. 2. Distribution of Function.
`
`,-
`
`GRAPEVINE
`
`authenticate, membership
`
`Registration
`Server "D"
`.
`//'-.
`locat{'"
`authenticate
`
`forward
`
`Registration
`Server "A"
`/I'-
`//'-.
`locate
`authenticate
`
`/
`I'-
`
`Server "B"
`/f'
`send
`
`locate
`
`Grape vi neUser
`
`File Server" E"
`
`//'-.
`
`FTP
`connection
`
`I
`I
`I
`I
`I
`I
`I
`
`1
`I
`I
`I
`w
`I
`I
`I Message
`I Message
`I
`I
`L - - - ..__ I - - - - - - - -
`
`Server "C"
`
`J
`
`/'-.
`retrieve
`- - - - r - -
`-
`Grapevine User
`
`I
`
`GrapevineUser
`
`Client program
`
`user "P.Q"
`
`Workstation 1
`
`forms all authentications, then users have the same name
`and password everywhere, thus simplifying many admin(cid:173)
`istrative operations. Second, if Grapevine is used every(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`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 returnTo 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
`
`Workstation 2
`
`Client program
`
`user "X.Y"
`
`matches an RName in the registration data base. All
`invalid recipient names are reported back to the client.
`In the infrequent case that 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(cid:173)
`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(cid:173)
`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(cid:173)
`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(cid:173)
`tactically separated as a "header," but this happens
`before Grapevine is involved in the delivery. The prop(cid:173)
`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
`of
`theACM
`
`Aprill982
`Volume25
`Number4
`
`PALO ALTO NETWORKS Exhibit 1017 Page 6
`
`

`
`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(cid:173)
`ing lists, one for each message server to which the mes(cid:173)
`sage should be forwarded and one for local recipients.
`The message server then forwards the message and ap(cid:173)
`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(cid:173)
`viduals in the inco