The Grapevine Interfaceby Andrew BirrellEdition 2January 1982Abstract: Grapevine is a multi-computer system on the Xerox research internet. It providesfacilities 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 onthe internet.This document describes the semantics of the services provided by Grapevine, and theprotocols that allow access to these services over the internet, in sufficient detail for a readerto program software that will use Grapevine.Note: Grapevine is the outcome of a research project. The services and protocols describedhere are not part of a Xerox product, and are not related to the Xerox Network Systemsprotocols.XEROXPALO ALTO RESEARCH CENTERCOMPUTER SCIENCE LABORATORY3333 Coyote Hill Road / Palo Alto / California 94304 W;p REqX MrF LX >Jq s$- <; 9 O 7 3(, 120 /h, +qs> )W1% '# 't'qX'x' rF4d >QLX{THE GRAPEVINE INTERFACE11.IntroductionGrapevine is a distributed system spanning multiple computers, providing distributed and replicatedservices to clients on the Xerox research internet. (We use the term client to mean software makinguse of some facility, and user to mean human users of software.) The services provided includemessage delivery, resource location, authentication and access controls.The Grapevine system was designed and implemented by Andrew Birrell, Roy Levin, RogerNeedham and Michael Schroeder, with considerable help from several other members of theComputer Science Laboratory in the Xerox Palo Alto Research Center.A general description of Grapevine is given in the paper "Grapevine: an Exercise in DistributedComputing", which was presented at the 8th Symposium on Operating System Principles inDecember 1981, and which is to be published in CACM (April 1981). Read that paper thoroughlybefore attempting to read this document. Before proceeding with this document, you should alsohave some familiarity with the PUP internet environment.This document specifies the client interfaces to the Grapevine system: it treats the Grapevine systemas a "black box", and defines the semantics that a client of the black box can observe and how aclient may interact with the black box. The intention is to define the semantics and the relevantcommunication protocols in sufficient detail that a suitably skilled reader could proceed to programpackages and systems that use Grapevine. There is no attempt here to explain how the inside ofthe black box is constructed or operates. The communication protocols allow a client to interactwith particular Grapevine computers, but to take full advantage of Grapevine the client must alsounderstand how the services provided by Grapevine are distributed and replicated. This documentdoes not attempt to provide a global view of the Xerox internet message facilities, nor is it intendedas a guide for those who administer Grapevine or other parts of the message system. TheGrapevine system does not include the IFS mail servers, nor user interface programs such as Laurel.We distinguish between a service and a server which provides an instance of that service. Grapevineprovides several services; various computers within Grapevine provide instances of these services, orof part of these services. For example, accepting mail for subsequent delivery is a service; eachGrapevine Mail Server provides an instance of that service. Accepting mail for delivery is thus areplicated service: it is provided by multiple computers, and any of these computers is adequate forproviding the service. A client wishing to submit mail may submit it equally well to any of theGrapevine mail servers. A more complicated example is the Grapevine Name Registration Service,which is provided by the Grapevine Registration Servers. As will be seen, no one of the registrationservers provides the entirety of this service, because each registration server knows about only somesubset of the registered names. On the other hand, multiple registration servers know about eachname. Thus the Grapevine name registration service is distributed as well as being replicated.The services provided by Grapevine come in three major groups. Firstly, the Registration serversprovide a naming database. This database is distributed and replicated. It is organized to allow fordistributed administration of the names. The database provides its clients with a name-to-valuemapping, and the ability to make changes to that mapping. This naming database is intended to beused for many purposes, including resource location and authentication in connection with the useof the Grapevine communication protocols. Secondly, the Mail Servers provide a message system.The facilities provided are the submission of a message together with a list of intended recipients.The mail servers will forward the message to a site convenient for each recipient, where the messageis buffered until the recipient cares to retrieve the message. Thirdly, the software provided with theGrapevine servers provides various administrative facilities which are useful in connection with!fuvuXvuvGu aw2 ^u30 ] xu-$ [:xuA YoH VgO TS RC O"= M(NvMu " L5vu* JjZ Hvu Ee CF B<& @731 >mU <a :H 9 N 7BV 5xX 3S 0xuxuxu .b -x&u +E x u8 ){x u%6 '\ %+xu $#xu. "PU I (x u "? )= ` SF T 4+ 0xu  )\ ^H Bl L>\}THE GRAPEVINE INTERFACE2running the physical computers on which the servers exist. These administrative facilities are inaddition to the Registration Service facilities for updating the naming database: these administrativefacilities are concerned with running individual computers. The administrative facilities are a log, aterminal interface to inspect and change the servers' state, and a terminal display on the physicalcomputer.This document proceeds in several parts. Section two describes the names and values contained inthe naming database. Section three describes the message delivery facility provided by the MailServers. Section four specifies the network protocols for accessing individual servers. Section fivediscusses algorithms which allow you to provide transparency of replication, distribution and failure.Lastly, the administrative facilities are described.!fuvuXvuvGu b;' `Sg ^Z \!B Z W^ V!K TV60 RL P4v Pz>^THE GRAPEVINE INTERFACE32.The Naming DatabaseThe Grapevine naming database provides several facilities. These include: naming messagerecipients, handling distribution lists for messages, naming and locating services and servers,authenticating users and servers, providing public access control and authentication services, andconfiguring the naming database and the message delivery system. This section describes thenaming database; subsequent sections describe how to use the database for these various purposes.The naming database often is concerned with names or values which are strings of characters. In allcases, a string is restricted to be no more than 64 characters. The communication protocols consideran attempt to transmit a string of more than 64 characters to be a protocol violation.A Name is a string of characters. The string usually contains the character ".". Only the last "." inthe string is interesting. The part of the string after the last "." is known as the registry, and thepart of the string before that "." is known as the simple-name. Thus a Grapevine name may beconsidered assimple-name . registryIn the degenerate case where a name contains no ".", the entire name should be considered to bethe registry. Names which differ only in the case of letters are considered to be equal.Each name in the database is associated with a value. There are two types of name, each with itsassociated form of value; these types are individual and group. The type of a name is specifiedwhen the database entry is created, and may not be changed until the name is deleted.The following information constitutes the value associated with a name whose type is individual.The precise bit patterns representing these values are of concern only when we discuss the actualcommunication protocols.A timestamp. Timestamps are used extensively in Grapevine as unique identifiers. Theyare formed by concatenating a host identification with a clock value. The timestampassociated with a database entry has the property that if the value of the entry changes, thenso does the timestamp. The timestamp may also change at other times. The timestamp isintended to assist a client in maintaining cached information that was derived from thedatabase; it is also used internally by the registration servers.A password. Universally within Grapevine, passwords are represented by 64-bit values.Passwords are used to allow authentication of individuals. They are also intended for use inencryption-based security protocols, although no such protocols are available at present. Byconvention, these values are derived from text strings by the following algorithm. Yourusers will probably be displeased if you use any different algorithm. Note that thisalgorithm does not preserve the information content of the password text, and so is notideal for encryption based protocols.MakeKey:PROC[text: STRING]RETURNS[key: PACKED ARRAY [0..8) OF [0..256)] =BEGINkey _ ALL[0];FOR i: CARDINAL IN [0..text.length) DOj: [0..LENGTH[key]) = i MOD LENGTH[key];c: [0..128) = LOOPHOLE[LowerCase[text[i]]];key[j] _ BITXOR[ key[j], BITSHIFT[c, 1] ];!fuvuXvuvGu aw2 ^u.+ ]<# [:9) YoX W.4 T; xu Re QV MxuE L5Qxu Jj (x u H #EX B#< @Y =@xu ;*x uxu  :'U 7` 5UI 30xu ?.E,1-+">)W9'A$xu="V 0-%$4Z0%:%(sysysysysysys (y]sysysysysy sys ysys ys 3ys ys H >^aTHE GRAPEVINE INTERFACE4ENDLOOP;END;A connect-site. A connect-site is a string. Although the registration servers place norestriction on the contents of the string, it usually represents the address of a computer.A forwarding-list. This is an ordered list of strings (usually names). The intended semanticsof a forwarding-list are described in section three.A mailbox-list. This is an ordered list of strings (usually names). The intended semanticsof a mailbox-list are described in section three.The following information constitutes the value associated with a name whose type is group. Theprecise bit patterns representing these values are of concern only when we discuss the actualcommunication protocols.A timestamp. The value and semantics of this timestamp are as for the timestampassociated with an individual.A remark. This is a string, which is intended as a human hint about the purpose ormeaning of the group; Grapevine attaches no semantics to the remark.A member-list. This is an ordered list of strings (usually names).An owners-list. This is an ordered list of strings (usually names). The owners-list is usedby Grapevine as an access control list for updates to the naming database, to describe theset of individuals who may make arbitrary modifications to group. Clients may possibly usethis list for other purposes.A friends-list. This is an ordered list of strings (usually names). The friends-list is used byGrapevine as an access control list for updates to the naming database, to describe the setof individuals who may add themselves to the group or remove themselves from the group.Clients may possibly use this list for other purposes.In addition to the above values, the database entry for a name contains various values concernedwith the propagation of database updates between servers. These additional values are not generallyuseful to clients. The client can observe these extra values only through the "ReadEntry" operationin the registration server enquiry protocol.Certain pseudo-names are available, which are accepted by the registration servers when clients makecertain database enquiries, although the names do not correspond to explicit entries in the namingdatabase. These names may also be used in access control lists. The particular enquiry operationswhich accept these names are detailed with the registration server protocol specification. Each ofthese names behaves, for the purpose of those enquiry operations or access controls, as if it is agroup. Only the timestamp and member-list of these pseudo-groups are accessible. For any registryreg, the names Groups.reg and Groups^.reg behave as if the name was a group with a member-listcontaining the name of each group in the registry reg. For any registry reg, the namesIndividuals.reg and Individuals^.reg behave as if the name was a group with a member-listcontaining the name of each individual in the registry reg. For any group of the form x.reg, thenames Owners-x.reg and Owner-x.reg behave as if the name was a group whose member-listcontains the owners-list of the group x.reg (but if that owners-list is empty, then the member-listcontains the friends-list of the group reg.gv). If a string of the form *.reg appears in an accesscontrol list, it is treated as matching any name of the form x.reg. Finally, the string "*" may be!fuvuXvuvGubys`Sys]Kux u,[ MXxxu;V4Sx u9Q1 N\ MR K>H6xu(FkCcxu AAE>x u6;x u:95%7A6(3 x u61UJ/L -6 *>" (Z '#=' %X, "Px u> W A" c &'; [Z xu x ux u5 2xu xu xuxu5 17xuxu fx ux u4 xu8 'xu xu =xu! =]LfTHE GRAPEVINE INTERFACE5used in access control lists, to mean that unrestricted access is allowed. As will be seen, these namesallow clients to send mail to the owners-list of a group, to determine the set of names which areindividuals or groups in a particular registry, and to specify more flexible access controls.Several names are guaranteed to be present in the naming database. Some of these are present toenable clients to locate appropriate registration servers when the client wishes to perform someenquiry or update on the naming database. Others are present as part of the message service, toenable clients to locate mail servers. Appropriate algorithms for using these names are described insection five. These names are as follows.Every registration server and every mail server has a name which is registered in the namingdatabase. Every registration server name is in the "gv" (for Grapevine) registry. These names havetype "individual"; the connect-site of such a name is a string representation of the PUP networkaddress of that server. Note that the network address of a Grapevine server may change from timeto time.The naming database also defines which strings are valid registries. For any string reg, the string isvalid as a registry if and only if the group reg.gv exists in the naming database. Thus for a namesuch as "foo.baz" to be valid, the group "baz.gv" must exist. Each registration server knows onlyabout the names in some set of registries; the registration server knows about all the names inthose registries. Typically, any particular registry is known about by several registration servers.For any valid registry reg, the member-list of the group reg.gv contains precisely the names of theregistration servers which know about names whose registry is reg. Thus, given a name such as"foo.baz", the member-list of the group "baz.gv" contains the names of the registration servers thatare concerned with the database entry for "foo.baz". All registration servers know about names inthe registry "gv".Thus, in order to determine the network address of some registration server that is concerned with aname such as "foo.baz", the client may contact any registration server, then ask it for the member-list of "baz.gv", then for each name in that member-list determine its connect-site; the client maythen choose from amongst that set of connect-sites. Section five describes how this algorithm maybe made acceptably efficient.The string "GrapevineRServer" is registered in the Xerox research internet name lookup serverdatabase. This name in that database maps to the network addresses of several computers. Some(but not necessarily all) of those computers are registration servers. "GrapevineRServer" exists withthe intent of assisting clients in contacting some initial registration server. Clients may also useother techniques, such as broadcast protocols, to contact an initial registration server. Once theclient has contacted an initial registration server, the naming database should be used to contactother registration servers.For example if "Cabernet.gv" and "Zinfandel.gv" are the names of two registration servers, thenthose names would be registered as individuals. The connect-site for Cabernet.gv would be a stringsuch as "3#14#", and the connect-site for Zinfandel.gv would be a string such as "60#354#". If"pa" was a valid registry, then the group "pa.gv" would exist. If Cabernet.gv and Zinfandel.gv bothknow about names in the registry "pa", then "Cabernet.gv" and "Zinfandel.gv" would appear in themember-list for "pa.gv". Both servers necessarily know about names in the registry "gv". Thename "GrapevineRServer" in the name lookup server database would be likely to contain thenetwork addresses 3#14# and 60#354#.!fuvuXvuvGu bb `S2/ ^] [U YB WA V!N TV* QN3) O3 0O,)O4TO,O M>vu K&; J# G=xu EQxu0 C[ AS ?!D >&xuxu$ <\%xu :9+ 8_ 6 3\ 2)L 0_] .E , )2+ 'Y &,f $a:+ "Y ,6  =" //4 dM T +5 E :J o$ (>XiTHE GRAPEVINE INTERFACE6The registry "ms" (for message servers) is a valid registry. The name "MailDrop.ms" is registeredin the naming database as a group; the member-list for that group contains precisely the names ofthose mail servers which may be willing to accept mail from clients for delivery. Thus, todetermine the network address of some Grapevine mail server, a client should obtain the member-list of "MailDrop.ms", and obtain the connect-site of names appearing in the member-list of thatgroup. Use of "MailDrop.ms" is discussed further in section five.For example, if the existing mail servers are "Cabernet.ms" and "Zinfandel.ms", then those nameswould be registered as individuals with appropriate connect-sites. The member-list for"MailDrop.ms" would contain those two names.The name "DeadLetter.ms" is registered in the naming database; the use of this name is describedin section three.!fuvuXvuvGu b a)bvab; `Sb ^; \!xu: Z5+ Y)B V!;% TVF'G0 R, ON M Mr=wTHE GRAPEVINE INTERFACE73.MessagesThe Grapevine mail servers will transport messages on behalf of clients. It is the purpose of thissection to describe the content of those messages and the semantics of message delivery.A message should be thought of as a property list and a body. The property list of a message isconstructed by a mail server when a client successfully submits a message to it for delivery, asdescribed in the mail submission protocol. The property list contains the name of the sender asprovided by the client, a return-to name for notifying non-delivery of the message, a postmarkspecifying the time at which the message was submitted, and a list of names which are the recipientsto whom the client asked the mail server to deliver the message. The precise representation of thesevalues is defined in the mail retrieval protocol. The body of a message consists of a sequence ofitems. Each item consists of a type, a length, and some data. The type is a number in the range[0..216). The length is a number in the range [0..232). The data consists of a sequence of bytes.The length specifies the number of bytes in the data.The message system guarantees that when a client retrieves mail, the property list is as constructedwhen the message was submitted, and the message body is identical to that submitted. The messagesystem is not concerned with the data content of clients' messages.The "type" of message body items is a name space that must be managed by convention if themessage system is to be of general utility. If a client wishes to attach a meaning to some type, heshould register the value of that type with the Grapevine message system maintainers. Types in therange 0 through 777B are reserved for use in representing the property list of messages in the mailretrieval protocol. The following types are pre-defined, in that their values are used internally byGrapevine.10BPostmark in property lists20BSender name in property lists30BReturn-to name in property lists40BRecipient names list in property lists1010BHuman-readable textual message2000BRegistration server database update2100BMail server "re-mail" hint177777BEnd-of-message itemWhen a client submits a message to a mail server, the mail server promises that it will deliver themessage. We now define what this delivery means. The mail servers deliver the message (bodyplus property list) to each of the recipients. For each recipient, the meaning of delivery is asfollows.If the recipient name is registered in the naming database as an individual, and the forwarding-listof that individual is empty, and the mailbox-list of the individual is not empty, then we proceed asfollows. The mailbox-list of an individual contains the names of several Grapevine mail servers.The names in an individual's mailbox-list are considered to be an ordered list of the names of theservers that may be suitable for buffering the individual's incoming messages. The mail server willattempt to cause the message to be buffered for the individual in one of those servers; the earliernames in the mailbox-list are preferred over the later names. Generally this will succeed, andgenerally the message will be buffered in the server whose name is first in the mailbox-list. If theattempt succeeds, the message is buffered for the client in the client's in-box in that Grapevine mailserver. The property list and message body may subsequently be read from an in-box by a clientusing the Grapevine mail retrieval protocol. If the message cannot be delivered to any of the!fuvuXvuvGu aw2 ^u?$ ]X Yx uxu$ X2K VgRxu Txu2x RuBx Qu32 O='; Mrxuxuxu ) KL5vKu-L5vKu# I5 F'= E D C@C @7E >m8, <\ :T 9 e 7B 4:2p0.&-+E#){' $)/xu "!< !^ H @P uJ D b T KA# '8 K 1xu &9 V-1 >]nTHE GRAPEVINE INTERFACE8servers in the recipient's mailbox-list within 2 days, or if the recipient name becomes invalid duringthe delivery process, then the message is considered to be undeliverable to this recipient and themail server will attempt to send an undeliverable notification to the name given as the return-toname in the message's property list, as described below.If the recipient name is registered in the naming database as an individual, and the individual'sforwarding-list is not empty, then the individual is treated as if it were a group whose member-listcontained the names found in the forwarding-list of the individual.If the recipient name is registered in the naming database as a group, then the message is deliveredto recipients whose names appear in the member-list of that group. Those recipients maythemselves be groups. If any of those recipients are invalid recipients, then the mail server willattempt to send an undeliverable notification to the name manufactured by concatenating "Owners-"with the group name, as described below.If the recipient name is not registered in the naming database, or if the recipient name is registeredin the naming database as an individual but the individual's forwarding-list and mailbox-list areboth empty, then the name is considered to be an invalid recipient. In such a case, if the recipientname was one of those supplied by a client when the message was submitted, then the mail serverwill attempt to send an undeliverable notification to the name given as the return-to name in themessage's property list, as described below; if the recipient name came from a group, then it ishandled as described in connection with delivery to groups.In order to send an undeliverable notification to some name (either that provided as return-to nameby the originating client, or one representing the owners-list of a group), the mail server proceeds asfollows. The mail server generates a new message whose body is a single item of type "text",containing a human-readable explanation of the failure that occurred; the mail server attempts todeliver this message to the appropriate name. If the appropriate name turns out to be an invalidrecipient, then this message is sent to "DeadLetter.ms". The intention is that sending to"DeadLetter.ms" will cause the notification to be seen by some system administrator. Additionally,a summary of the undeliverable notification and a copy of the header part of any text item of thereturned message are always sent in a text message to "DeadLetter.ms".The above describes the delivery semantics as they would be if the Grapevine message systemexisted in isolation. However, this is not so and the semantics are actually modified as describedbelow. The foreign mail systems with which Grapevine cooperates are: the IFS mail servers, theTENEX system running on MAXC, and the ARPAnet message system (accessed through MAXC). Weuse the phrase foreign mail server to indicate a host running one of these systems.The mailbox-list of an individual may contain not only the names of Grapevine mail servers, butalso names of foreign mail servers. These names are strings representing either the PUP networkaddress of the host running the foreign mail server or a PUP Name Lookup Server name for thathost. If during the delivery algorithm for an individual recipient the Grapevine mail serverencounters a name from a mailbox-list specifying a foreign mail server, and if the Grapevine mailserver decides that this is the best place for buffering the message, then the Grapevine mail serverwill forward the message to that foreign mail server using the MTP protocol. In doing so, theGrapevine mail server will forward only the first message body item of type text (if any); theproperty list and any other message body items are lost. If the chosen foreign mail server rejectsthe recipient name, or if the chosen foreign mail server appears not to exist, and if the postmark ofthe message is more than 24 hours old, then the recipient is considered to be an invalid recipient.(The 24 hour delay is to cover transients while the Grapevine database entry for the recipient is!fuvuXvuvGu b \ `S V ^$x u" \8 Y#> WN V!C S=' QN K OJ Mx uA K( H?' GL EQe CJ Ax u, ?^ >&; ; x uB 9TK 7 P 5;& 3J 2)$6 0_.5 .] ,F )2) ''< &, xu8vu $avuvu vu%vu "xu1 [ $1vu 'vu! /C dK *: ?vu  '7 :N o,9 !B ZN =\x~THE GRAPEVINE INTERFACE9being modified, because such changes cannot be synchronized with changes to the foreign mailserver.) This facility allows individuals registered in the Grapevine naming database to havemailboxes on these foreign mail servers; typically, such an individual would have only one name intheir mailbox-list.If during the delivery algorithm a recipient name is encountered which is not registered in thenaming database, but the recipient name is of the form x.reg and the name reg.Foreign is registeredin the naming database as an individual, then the mail server will treat the recipient name as aforeign recipient name. If the recipient name does not contain the character "^", then the Grapevinemail server treats the recipient as if it was an individual whose mailbox-list was that of reg.Foreign.If the recipient name contains the character "^", then the mail server expects the recipient name toname a file on the MTP server reg; the mail server will retrieve this file through the FTP protocol tothat server, connecting on socket 7; the mail server will attempt to parse this file as a distributionlist and will deliver the message to the resulting names. This mechanism allows clients ofGrapevine to address individuals and distribution lists which exist on foreign mail servers and arenot registered in the Grapevine database. For example, if "xrcc.foreign" is registered as anindividual with a mailbox-list containing "Aklak", then any name such as "foo.xrcc" is acceptable asan individual recipient and messages for "foo.xrcc" will be forwarded to the IFS mail server"Aklak". In particular, the name "ArpaGateway.foreign" is registered as an individual, whosemailbox-list causes forwarding to a foreign mail server which understands about ARPAnet mailrecipients. To address a text message to an ARPAnet recipient such as "Saltzer@MIT-Multics", onewould include "Saltzer@MIT-Multics.ArpaGateway" amongst the recipients of the message aspresented to the Grapevine mail servers.A mail server occasionally wishes to use a remote file server to store messages which are beingbuffered for clients. It does this to avoid over-filling its local disk with messages for people who donot read their mail often enough (or are on vacation, etc.). For a mail server whose name is x.msthe group Archive-x.ms should exist. The member-list of that group should contain path namesindicating the desired remote server and directory. Each of these servers should have a LEAFprotocol server enabled, and should have an account for the name x, with a password that matchesthat of x.ms. The mail server will try each of the file servers in that group (if necessary), in orderof closeness on the Internet. For example, if "Cabernet.ms" is a mail server, and the group"Archive-Cabernet.ms" has members "[Ivy]" and "[Ibis]"; then the mail serverwould store on the server "Ivy" files with titles such as "Cabernet.ms>Birrell.pa-19-Jan-81-23-20-59-PDT!1".!fuvuXvuvGu b\ `S5) ^M \ YV W'xu x u V![ TVxuN R)2x u PF N vuxu6vu M,T KaS IC GI FS D7Mvu BlH @Ovu > !vuvu = vu/ ;A( 89(7 6o \ 4Ox 2u x u( 14%v /DuAxu -zxuF ++1 )> (B &O &>B%THE GRAPEVINE INTERFACE104.ProtocolsThis section describes the protocols which may be used to invoke the facilities provided byindividual Grapevine servers. They will also be used to interrogate the Grapevine naming databasein order to find suitable Grapevine servers at various times. In addition to the protocols definedhere, the Grapevine servers implement the following PUP protocols: FTP, MTP, Telnet,Miscellaneous Services (for Authentication Request and Mail Check Laurel only), Echo.Each of the following protocols uses some underlying transmission medium. This medium is eitherPUP packets, or PUP Byte Stream Protocol streams. In either case, the medium providescommunication to a specified network address, and transports an ordered sequence of 8-bit bytes.PUP packets provide unreliable (but high probability) uni-directional transmission of small numbersof bytes with no notification of failure; the Byte Stream Protocol provides reliable bi-directionaltransmission of arbitrarily large numbers of bytes, with notification of failure. Values of severaldata types occur in the Grapevine protocols. The representation of these values is described here,in terms of the sequence of bytes provided by the transmission media.The Grapevine servers are unforgiving of protocol violations. If a client violates the protocol, theserver's typical response will be to terminate the byte stream or ignore the PUP, as appropriate.A character is a single byte containing the ASCII value of the character.A boolean is a single byte containing 1 for TRUE, 0 for FALSE.An ack is a single byte of undefined value.A word is a pair of bytes; the first contains the more significant 8 bits.A number is a word containing the binary representation of an integer in the range [0..216).A long number is a pair of words representing an integer in the range [0..232), the first wordcontaining the less significant 16 bits (this is the Mesa representation).A timestamp is three words. The first word is an uninterpreted bit-pattern (though strikingly similarto a PUP network address); the second and third constitute a long number. This long number isapproximately the number of seconds since midnight, January 1st, 1901 that had passed at the timethat the timestamp was created.A password is 8 bytes representing in order the bits of a password value as defined above inconnection with the naming database.A string is a sequence of bytes as follows. The first two bytes form a number which specifies thenumber of characters in the string. The third and fourth bytes are ignored. This header is followedby the characters of the string. If the number of characters is odd, there follows one extra byte(with undefined value). This is derived from the Mesa representation of a string. Note that thisrepresentation occupies an even number of bytes. All strings are restricted to be no more than 64characters. An attempt to transmit more than 64 characters (i.e. 34 words) in one of these values isa violation of these protocols.A name, a connect-site, and a remark are each represented by a string (and are therefore restrictedto 64 characters).!fuvuXvuvG?u aw2 ^uX ]02 [:#@ Yo94vu vu:vu WU TY Rvu vu/ QG O=vuO Mr V KU IS HE E L C@Lvu @7xu!vu =/xu#vuvu :'xu% 7xuD 4xu/!4v4u 1x u;1v1u /DJ ,<xuX *rvu2$ (I & #xu: " $ xu(2 7\ l] K Z  U B :xux uxu; o F (>XSTHE GRAPEVINE INTERFACE11An operation is a number used to specify a command, whose values are specified in the individualprotocols.A name-type is a byte with values as specified by the following Mesa type constructor:NameType: TYPE = MACHINE DEPENDENT{group(0), individual(1), notFound(2), dead(3), (255) };A code is a byte with values as specified by the following Mesa type constructor:Code: TYPE = MACHINE DEPENDENT{done(0), noChange(1), outOfDate(2), NotAllowed(3),BadOperation(4), BadProtocol(5), BadRName(6), BadPassword(7),WrongServer(8), AllDown(9), (255) };A return-code is a code followed by a name-type. In the protocol descriptions, a return-code isdenoted by [a, b] to indicate transmission of the code "a" followed by the name-type "b".A component is a number, followed by a sequence of words. The number specifies how manywords.A string-list is a component whose words constitute a sequence of strings. The strings must be inalphabetic order. The ordering is obtained by converting all upper case letters to lower case, thensorting by ASCII value of the characters. Note that this implies that the servers will deliver thevarious lists of strings (other than mailbox site lists, described later) from database entries to clientsin alphabetic order.!fuvuXvuvG?u bxuxu. `S ]KxuKZCs ysysys(Xx7 UpuxuKRhsysysys(P2(N=(M$ Jux u#0 H61( E-xuD Cc @[x uR >d < vuB :I! 90 8=/"THE GRAPEVINE INTERFACE124.1Registration Server ProtocolsThe registration server responds with PUP type "iAmEcho" (type 2) to PUP's of type "echoMe" (type1) and length no more than 128 bytes sent to it on socket 52B.The registration server is usually willing establish a Byte Stream Protocol connection in response toan RFC packet sent to socket 50B (any unwillingness usually indicates that this server is restarting oris feeling overloaded). The protocol accepted on such byte streams is as follows. The protocolconsists of a sequence of commands. For each command, the client sends a word representing anoperation, probably followed by some arguments, then the server sends a return-code, possiblyfollowed by some results. The arguments and results depend on the command. The commandseach operate on the database entry for some name. Unless otherwise specified, that name may notbe one of the pseudo-names ("Owners-foo.reg", et al). The commands have the followingproperties in common.If the registry of the name in question is invalid, then the return-code is [BadRName, notFound]and there are no other results.If the registry of the name is valid, but this registration server is not concerned with names in thatregistry, then the return-code is [WrongServer, notFound] and there are no other results; in this casethe client should contact some other registration server. This facility allows a client to assume that aparticular registration server knows about a name until the client is told otherwise.If the registry of the name is valid and this registration server is concerned with that registry, butthe name is not registered in the database, then (except for CreateIndividual, CreateGroup andNewName!) the return-code is [BadRName, notFound] or [BadRName, dead]. and there are noother results. The distinction between "notFound" and "dead" is not intended to be useful toclients, although it may occasionally be useful to a human administrator. The distinction ariseswhen a name is deleted from the naming database. For about 14 days after the deletion, the namemay appear as "dead" instead of "notFound"; at any time a name may revert from "dead" to"notFound", at the whim of the registration servers. The distinction is important in the registrationservers' database update propagation algorithm.In the descriptions of the commands, the above possible outcomes are implicitly assumed.The following commands allow clients to read the database.Expand: operation=1, arguments = [ name, timestamp ]If the present timestamp of the database entry equals the given one, then the return-code is[noChange, group] or [noChange, individual] as appropriate, and there are no other results.Otherwise, the results are a timestamp and a string-list. The timestamp is the currenttimestamp of the database entry. If the name has type group then the return-code is [done,group] and the string-list contains the group's member-list; if the name has type individualand the individual's forwarding-list is non-empty, then the return-code is [done, group] andthe string-list contains the individual's forwarding-list; if the name has type individual andthe individual's forwarding-list is empty, then the return-code is [done, individual] and thestring-list contains the strings (if any) from the individual's mailbox-list, in chronologicalorder of when they were added to the mailbox-list (this is used as the order of priority bymail servers). The argument of this command may be a pseudo-name of the form Owners-!fuvuXvuvG?u bz2 _u&vuvu ]K> ZC"C XxvuS V V Txu< S$xu/ QNxu8 O\ M.xu# K H'9 G D)= BI/7 @~i >U ;X 9^ 84# 6K6' 4a 2C 0O /!42 -V/ *NX $: !xu.9#+0 IQ SDU_#:)^ ^D @x L=\DTHE GRAPEVINE INTERFACE13x.reg or Owner-x.reg, but not one of the form Groups.reg, Groups^.reg, Individuals.reg,Individuals^.reg, *.reg or "*".ReadMembers: operation=2, arguments = [ name, timestamp ]If the database entry has type individual, then the return-code is [BadRName, individual]and there are no other results.If the present timestamp of the database entry equals the given one, then the return-code is[noChange, group], and there are no other results.Otherwise, the return-code is [done, group] and the results are a timestamp and a string-list.The timestamp is the current timestamp of the database entry. The string-list contains thegroup's member-list. The argument of this command may be any pseudo-name other than*.reg or "*".ReadOwners: operation=3, arguments = [ name, timestamp ]This is the same as ReadMembers, except that the string-list returned contains the owners-list of the database entry, and the pseudo-names are not supported.ReadFriends: operation=4, arguments = [ name, timestamp ]This is the same as ReadOwners, except that the string-list returned contains the friends-listof the database entry.ReadEntry: operation=5, arguments = [ name, timestamp ]The result is a timestamp followed by a number, followed by that number of components.The timestamp is at present of undefined value. The components are the entire databaseentry for the name. If the caller has been authenticated by the IdentifyCaller command (asfor database updates) and is in the "gv" registry, then the components for an individualinclude the individual's password, otherwise the password is represented by zeroes.CheckStamp: operation=6, arguments = [ name, timestamp ]If the present timestamp of the database entry equals the given one, then the return-code is[noChange, group] or [noChange, individual] as appropriate, and there are no other results.Otherwise, the return-code is [done, group] or [done, individual] as appropriate and theresult is a timestamp which is the current timestamp of the database entry. The argumentof this command may be any pseudo-name other than *.reg or "*".ReadConnect: operation = 7, argument = [ name ]If the database entry has type group, then the return-code is [BadRName, group] and thereare no other results.Otherwise the return-code is [done, individual] and the result is the connect-site given in thedatabase entry.ReadRemark: operation = 8, argument = [ name ]If the database entry has type individual, then the return-code is [BadRName, individual]and there are no other results.!fuvuXvuvG?ubxux ux ux uxu`Sxuxu ]Kx u.ZC?XxUp9#S2PKN?M2"K>xu H6x u.E-:CcC @[x u.=S?; 8x u.5x=3/(1&50 L.MS +Ex u.(=9#&s+0#jP!L 2xu x u$O /0(  x u$ ? M :]THE GRAPEVINE INTERFACE14Otherwise the return-code is [done, group] and the result is the remark given in thedatabase entry.Authenticate: operation = 9, argument = [ name, password ]If the database entry has type group, then the return-code is [BadRName, group] and thereare no other results.If the given password does not equal the password given in the database entry then thereturn-code is [BadPassword, individual].Otherwise the return-code is [done, individual]; there is no further result.IdentifyCaller: operation = 33, argument = [ name, password ]If this registration server does not know about the registry of the given name, then thisserver will consult other registration servers as necessary to perform the operation; it willnot give the return-code [WrongServer, name-type]. If the necessary other servers are notcontactable, then the return-code is [AllDown, notFound] and there is no other result.If the database entry has type group, then the return-code is [BadRName, group] and thereis no other result.If the given password does not equal the password given in the database entry then thereturn-code is [BadPassword, individual].Otherwise the return-code is [done, individual]; there is no further result.Use of this command affects the state of the connection, as described with the databaseupdate commands.The following commands allow clients to perform database enquiries in support of access controls.For each of them, if the database entry is of type individual, then the return-code is [BadRName,individual] and there is no other result. For the "closure" commands, the registration server mayneed to consult other registration servers; if for some reason it cannot do so, then the return-codewill be [AllDown, group] and there will be no other result. Otherwise, the return-code is [done,group] and the result is a boolean, TRUE iff the second given name is a member of the appropriatelist(s). The IsInList operation provides access to all the facilities of operations 40 through 45, andshould be used instead of those operations. Operations 40 through 45 are historical.IsMemberDirect: operation = 40, argument = [ name, string ]The result is TRUE if the string is one of the strings in the member-list of the databaseentry. Each argument of this command may be any pseudo-name.IsOwnerDirect: operation = 41, argument = [ name, string ]The result is TRUE if the string is one of the strings in the owners-list of the database entry.IsFriendDirect: operation = 42, argument = [ name, string ]The result is TRUE if the string is one of the strings in the friends-list of the database entry.!fuvuXvuvG?ub@`S ]Kx u.ZCO XxUp7S)PL Mxu/J?H&8FZE-$2B%O @[=S7;)8L5x83 .*P ,_a *G (A# 'K %5 vu9 #j xu7 !U xu- vu@= x u- vuG xu- vuO D ^>ZTHE GRAPEVINE INTERFACE15IsMemberClosure: operation = 43, argument = [ name, string ]The result is TRUE if the string is one of the strings in the member-list of the databaseentry, or if this operation would return TRUE when applied to any of the names in that list.Thus this operation traverses the graph implied by the names in that list, and may involvecommunication with other registration servers. Loop detection is applied as necessary. Thisoperation may be quite expensive. Each argument of this command may be any pseudo-name.IsOwnerClosure: operation = 44, argument = [ name, string ]As for IsMemberClosure, but starting with the owners-list of the database entry. The namemay not be one of the pseudo-names.IsFriendClosure: operation = 45, argument = [ name, string ]As for IsMemberClosure, but starting with the friends-list of the database entry.IsInList: operation = 46, argument = [ name, string, byte, byte, byte ]This provides a general access control testing operation, and supersedes operations 40through 45. If the first byte is 1, then instead of testing membership in lists associated withthe name, it tests in lists associated with the name's registry; that is, if the name is of theform x.reg, the operation will test membership in lists of the group reg.gv; otherwise thefirst byte should be 0. The second byte should be 0 to test membership of the members-list, 1 to test the owners-list, 2 to test the friends-list. The third byte should be 0 to testdirect membership, 1 to test membership in the closure, and 2 to test membership in the"up-arrow closure". The "up-arrow" closure is like normal closure, except that the closurepursues only contained names of the form x^.reg, such as "CSL^.pa" but not "Birrell.pa";this is very much more efficient than full closure. If any of the bytes does not have one ofthe specified values, it is treated as a protocol error.The algorithms used by the registration servers to propagate updates of the naming database are notatomic, in the following sense. When a client requests a registration server to perform a databaseupdate, if the registration server is able to perform the update, the client is given anacknowledgement when the registration server has made the required change to its own copy of thedatabase. Subsequently, the registration server guarantees to propagate the update to otherregistration servers so that all copies of the database will be updated. In the interval after the firstregistration server has performed the update but before all other registration servers have performedthe update, clients may observe two copies of the database, one in which the update has occurredand one where it has not yet occurred. Thus clients may get a transiently inconsistent view of thenaming database, and clients should be prepared to deal with this fact. In all normal cases, thewindow for this inconsistency is short (in the region of one minute), but there is no upper bound tothe length of this window.The following commands allow clients to make updates to the naming database. In allcircumstances, these commands return a return-code and no other result. In addition to the possibleoutcomes described above as being in common for all registration server commands, the updatecommands have the following properties in common.!fuvuXvuvG?u bxu-_ vu@]K)vu "[RY>W!2V! Sxu-P?NF# K>xu-H6Q E-xu?B%V@[4,>W<xu"xu:?90 V7f75O 3xu)2H0;8 )_ 'FxuY %|*+= #T !@ H! Q;* A _ &; 'U \ T G &> G 1 =[^=THE GRAPEVINE INTERFACE16The update commands ask the registration server to change the state of registration of some namein the naming database; this name is sent as the first argument. The registration server will consultvarious access control lists associated with this name to determine whether the requested updateshould be permitted. For any given name there are four access control lists that are of interest. Wewill call them "owners-acl", "friends-acl", "reg-owners-acl" and "reg-friends-acl". For any groupsn.reg the owners-acl is the owners-list of that group and the friends-acl is the friends-list of thatgroup. For any group sn.reg, the reg-owners-acl is the owners-list of the group reg.gv and the reg-friends-acl is the friends-list of reg.gv (the reg-owners-acl and reg-friends-acl are both empty lists ifreg.gv doesn't exist). If during this connection the command IdentifyCaller has not been made, or ifthe last call of that command gave a return-code other than [done, individual], then any of thefollowing commands will give the return-code [NotAllowed, notFound]. Otherwise, the "caller" isthe name that was given as argument of the last call of IdentifyCaller during this connection. Theregistration server consults the access control list indicated for each particular command below, todetermine whether the caller's name is in that list. This is done using the closure operations(IsMemberClosure, IsFriendClosure, IsOwnerClosure, as appropriate). If the caller is not in theindicated list, and the list was the friends-acl, then the registration server applies this algorithmrecursively using the owners-acl. If the caller is not in the indicated list, and the list was theowners-acl, then the registration server applies this algorithm recursively using the reg-friends-acl. Ifthe caller is not in the indicated list, and the list was the reg-friends-acl, then the registration serverapplies this algorithm recursively using the reg-owners-acl. If the caller is not in the indicated lists,then the return-code is [NotAllowed, notFound]. These access control checks are typically moreefficient than this algorithm would indicate, but they are still potentially quite expensive. The listscontrolling the various update commands are as follows.CreateIndividual, DeleteIndividual, CreateGroup, DeleteGroup, NewName, AddMailbox,RemoveMailbox: the reg-owners-acl.ChangePassword, ChangeConnect: if the name is the caller's, then the operation is allowed;otherwise it is controlled by the reg-friends-acl.AddForwarding, RemoveForwarding: the reg-friends-acl.AddMember, RemoveMember: if the string which is the second argument is equal to the caller'sname, then the operation is treated as AddSelf or RemoveSelf; otherwise if the name is in the "gv"registry, then the reg-friends-acl; otherwise the owners-acl.ChangeRemark, AddListOfMembers: if the name is in the "gv" registry, then the reg-friends-acl;otherwise the owners-acl.AddSelf, RemoveSelf: if the name is not in the "gv" registry then the operation is controlled by thefriends-acl; if the name is in the "gv" registry then if the caller is in the "gv" registry, then theoperation is allowed otherwise it is controlled by the reg-friends-acl.AddOwner, RemoveOwner, AddFriend, RemoveFriend: the owner-acl.If the requested update is such that it would not change the database, then the return-code is[noChange, name-type]. If the registration server determines that there is contradictory informationin the database that is newer than the requested update, the return-code is [outOfDate, name-type];this situation is exceedingly unlikely, but is possible. Several of the update commands haverestrictions on the type or existence of some name before the operation may be performed. If theserestrictions are violated, the return-code is [BadRName, name-type], where "name-type" isindividual or group if the name is registered with inappropriate type, and is notFound or dead if!fuvuXvuvG?u bI `S-: ^'9 \R Z<& Y)xuG W^xu' xu Uxu@ SxuN QB P4,4 Ni V LB" J=" I U G?R Et[ CU Ad @j >JL <K :7 7xH0I" 5 u 2xu< 12 .xu *xu4 )4&xux u' 'i= $axu0 " xuM V G x/u ^ +: TL  O G !8"! * T >](gTHE GRAPEVINE INTERFACE17the name is needed but is not registered.Otherwise, the update is made and the return-code is [done, name-type].CreateIndividual: operation = 12, argument = [ name, password ]The name must not presently be registered in the database. This registers the name withtype individual, with the given password, with an empty string for connect-site and withempty forwarding-list and mailbox-list.DeleteIndividual: operation = 13, argument = [ name ]The name must have type individual. This removes the name from the database.CreateGroup: operation = 14, argument = [ name ]The name must not presently be registered in the database. This registers the name withtype group, with an empty string for remark, with an empty member-list and friends-list,and with an empty owners-list.DeleteGroup: operation = 15, argument = [ name ]The name must have type group. This removes the name from the database.ChangePassword: operation = 16, argument = [ name, password ]The name must have type individual. This sets the individual's password to be that given.ChangeConnect: operation = 17, argument = [ name, connect-site ]The name must have type individual. This sets the individual's connect-site to be thatgiven.ChangeRemark: operation = 18, argument = [ name, remark ]The name must have type group. This sets the group's remark to be that given.AddMember: operation = 19, argument = [ name, string ]The name must have type group. This adds the string to the members-list of the group.AddMailbox: operation = 20, argument = [ name, string ]The name must have type individual. This adds the string to the mailbox-list of theindividual.AddForward: operation = 21, argument = [ name, string ]The name must have type individual. This adds the string to the forwarding-list of theindividual.AddOwner: operation = 22, argument = [ name, string ]The name must have type group. This adds the string to the owners-list of the group.AddFriend: operation = 23, argument = [ name, string ]!fuvuXvuvG?u b) _G \xu/Y KW;SUp' Rhxu%O`M LXx u%IP KGEE Bx u%?H