Aa@YA33HH $ d   dFootnote TableFootnote**. . / - : \ \enTOCHeading  Ientchl I Y J Igu<$lastpagenum><$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear>;<$monthname> <$daynum>, <$year> <$hour>:<$minute00> <$ampm>"<$monthnum>/<$daynum>/<$shortyear><$monthname> <$daynum>, <$year>"<$monthnum>/<$daynum>/<$shortyear> <$fullfilename> <$filename> <$paratext[Title]> <$paratext[Heading]> <$curpagenum> <$marker1> <$marker2> (Continued)Heading & Page <$paratext> on page<$pagenum>Pagepage<$pagenum>aSee Heading & Page%See <$paratext> on page<$pagenum>. Table & Page7Table<$paranumonly>, <$paratext>, on page<$pagenum>+ (Sheet <$tblsheetnum> of <$tblsheetcount>) ##Ploo$$P%%QA&&P''P ((QA7AQnA??QeAnBBACntAchlBI YCguDEFenuGHme>I>, JKthnLnumMyeaN;Ome>P>, Q$hoRuteSm>T$moU$da<$VyeaW$moe>XynuyeYmoZm>/um[hor\]ena ^$fi_ pa`t[Tatebadic$cuumd mae> fkerg(Cod)hHei & jparkn plenume$pnm>aSeodingep <exqn prenus Tate7uaray>vparwon xgeny+z$tb{> o|eet}~ #oo%!QC"d!(#%Qnd"B&(hlH$ #$! H$ UU`HW Hz $#%! Hz hoUU`AW HH%$! HHmoUTUT`BN rH$ &'"  H$ UU`CW Hz '&(" Hz d)UUhDWW# n pHH('" HHUTUT`EN d)y>*5H3K ^*+) H RH RVFootnoteHqv? ^+*,) HzHzV% Single LineH',+.)--FootnoteQn -,B  HvDf ^.,/) HHV Double LineH /.2)01 Double Line 01/10/UTH 2/4)33 Single Line 32 HZ425) TableFootnoteEGX-Rb ^54) EPoEPoV TableFootnoted677UTH@76 H@9'KUTUT`FN!ACM SIGOPS 5th European Workshop oURUT`GN^ -UPUT`IN?NEEDED: A SYSTEMATIC STRUCTURING PARADIGM FOR DISTRIBUTED DATA @UNUT`JNby Jerome H. Saltzer SULUT`zN Library 2000 fUJUT`{N'M.I.T. Laboratory for Computer Science yUHUT`|NSeptember 10, 1992 UFUT`^N 2UDUT KNZThe purpose of this note is to alert the distributed and operating systems communities to UBUTKNTa research and design exercise that is going on in an adjacent application-oriented U@UTKN[community. This research and design exercise involves inventing a paradigm for distributed U>UTKN_system structuring that is distinctly different from that of remote procedure call and related U<UT@KNIparadigms that are the usual focus of the distributed systems community. U:UT LNYThe class of applications involved might be roughly characterized as distributed, linked U8UTLNurZdata. The remote procedure call paradigm, in which a client asks a server to perform some U6UTLNST[named computation on a set of supplied arguments and return a result, is not an especially 0  U4UTLNdcongenial fit to this application, although it may be a useful tool at a lower level of abstraction ^U2UTLNWin resolving links. Perhaps because the application of linked data has not been widely uni'U0UTLN]considered, it is not clear yet what is an appropriate form for the structuring paradigm, or 4U.UTLNXeven whether or not the problem has been posed carefully enough to allow one to propose edAU,UTLNK]specific structures. This note describes the problem as it has been posed in the distributed lNU*UTLN\data community, and points to a few early attempts to suggest mechanisms; it does not claim [U(UT@LNs to settle the issue. dnU&UT QNchVThe interesting requirement in distributed storage of related data lies in those data {U$UTQNch^relations that can be characterized as cross-reference. There are many different applications U"UTQN r[in which one object might need to contain a cross-reference to another, remote, object. As on,U UTQNe Wexamples, one might propose to build a distributed hypertext system, a sales reporting PeUUTQNap_system for a corporation that has many branch offices, an office system that allows one worker yeUUTQNpr_to incorporate an element of a remote spreadsheet into a local one by reference, a distributed haUUTQNul]legal case database, with cross-references among cases, and also from state to federal cases bUUT@QNit+and back, or simply an electronic library. UUT RNZFor concrete scenarios consider the specific application of an on-line electronic library UUTRNetZ(comparable scenarios arise in most of the other application examples.) In the electronic UUTRNin[library, the primary scenarios of interest are the following: The maintainer of a document re UUTRN aXstorage service has installed a new document and wants to advertise the new document to ncUUTRNteXclients and clients of clients, and allow search services to store and pass along cross-ypU UTRNal]references (in this application a cross-reference is usually called a citation) to the new *U UTRN a[document. In a related scenario, the client of a search service has completed a search and nto7UUTRNfe_wants to be able to store a persistent cross-reference to one of the items discovered. Storing sesd8as99itHH98 c HH7;+naUTUTRNspWthe search query that was used to discover the item is one common suggestion, but that narURUTRNofZmethod is not very satisfactory, because that particular search may have returned several !UPUTRNte\items in its result set, or it may have been framed in terms of something unrelated to what ha.UNUTRNdo\makes the document interesting. In addition, since collections grow and shrink, there is no of;ULUTRNw Zguarantee that the search service will return the same result set for the same query at a HUJUTRNreYfuture timeespecially if the document itself might change in such a way as to cause the lUUHUTRN c`query not to find it. In yet another related scenario, the user of a document discovers in it a stbUFUTRNroZcross-reference to another document, and wants to make a copy of that cross-reference, in oUDUTRNcpersistent storage for future use. And in a final scenario, a client includes a cross-reference in |UBUTRNch\a document which it then submits to be stored by some storage service, possibly a different RU@UT@RNt one. tU>UT SN tYIn each scenario, some client intends to place the cross-reference in persistent storage eU<UTSNbeZsomewhere, for presentation to the storage service at an unknown time in the future. When U:UTSNdd`the client eventually presents the cross-reference to the storage service, it hopes to retrieve eaU8UT@SNetthe cited item. t U6UT`TNue=In an electronic library, such cross-references may be used: u`UZchOby an author, in creating a new document, to cite previous, related documents. n y VZ s]by the librarian of a storage service, in adding a document to a collection, making concrete oD @VZ w(an author's traditional text citations. e,ݸ WZRVby a user of a search service, to prepare a list on a personal note pad of discovered 'wP@WZ documents. R: XZhiXby a search service as the internal connection between its index and the documents held FXZU>Vby a storage service. (e.g., to connect a bibliographic record with the corresponding SD@XZ e document). Seݰ YZorWby a search service, as the method of telling the client how to obtain the item from a SrwH@YZvestorage service. e`ZZo -by a client, to pass along to another client 8x`[Zth\by an author, to cite anchor (that is, identified internal) points within another document. seTUT PNUTThe following simple scenario perhaps captures best of all the required structuring yRUTPN s^behavior: At the application level, a user has brought up a document in a display window, and ĈPUTPN wYupon browsing through it noticed that it mentions another document. The browser provides vшNUTPNli^as a feature that the user be able to point to the cross-reference with the mouse, click, and ވLUT@PNicIexpect to see the cited document appear on the screen in another window. JUT \NbyZThere are a number of interesting constraints on the solution, at least in the electronic HUT@\NmePlibrary application. Some of the other applications have analogous constraints: ieD ]ZheZThe storage service to which the cross-reference is eventually presented may be different ݚ]ZotVfrom the one that provided the original cross-referenceit may be a backup system, or *w2@]Zn even a competitive provider. = _ZowXThe interval between creation and use of the cross-reference can be quite long, perhaps PIb_Z tRdecades, during which time the storage service may have been upgraded, relocated, VC@_ZupXmerged with other storage services, and placed under different administrative control. Nhݒ uZas[Cross-references will persist long enough that the system that is intended to resolve them ވLuw*@uZexwill become obsolete. d:th;;HH;: teHH9=as,he `ZUTRBetween creation and use of the cross-reference, the cited document may have been `ZWdeleted, updated, or superseded. Something graceful should happen if multiple versions y b D@`Z]are available. If the document is actually a dynamic piece of data such as a current stock ,,@`Z]Aquote, perhaps something different, yet graceful, should happen. v?wp aZn ZBetween creation and use of the cross-reference, the organization of the library may have L@aZheIbeen revised, and the target document may now be classified differently. e^ bZorTBetween creation and use of the cross-reference, the physical and low-level logical askD8bZ wWconfiguration of the storage server may have been revised, and the target document may @uw@bZob?be in a different directory or on a different physical volume. wh cZZBetween creation and use of the cross-reference, the storage representation of the target @cZ uTdocument may have been discovered to be defective, and restored from a backup copy. te dZerRThe initial discovery mechanism may identify only the document; a later discovery D0@dZf 0process may identify anchor points of interest. s eZtoUThe user who presents the cross-reference may or may not be authorized to obtain the ew`@eZa document. cr fZthUA single document may by indexed by several different search services that are under r@fZrgdifferent administrations. fieD( gZTIn response to presentation of a cross-reference, a storage server may, rather than w-@gZD8Idelivering the desired document, instead return another cross-reference. ,&wX hZcu]If a client makes inquiries of several different search services, it would like to merge the .3hZcZseveral responses, which requires that it be possible to figure out which of the returned ?@hZc!cross-references are duplicates. eRdUT iNe,[As can be seen from this laundry list of constraints, the requirements on cross-references id_bUTiNcu[among distributed data objects read more like the list of requirements for a sophisticated sl`UT@iNtoDname service than they are like the requirements on an RPC service. ed^UT jNw`VIt would appear that at the minimum, a cross-reference internally must be composed of \UTjNt ]at least two components. The first would be an identifier, perhaps to be presented to a name ZUTjNns]server, that allows the client to discover an appropriate and current server name, port, and 8XUTjN;aprotocol to use, and to verify upon connection that the service at the other end is the intended uVUTjNif\one. A second component probably is a specific object identifier that server is expected to hiTUTjNt ^recognize. Beyond that, one moves into the realm of speculation. There might be an expiration ͈RUTjN]date after which the server doesn't guarantee to honor the cross-reference, and perhaps also eڈPUTjN^a backup query, which might be useful in identifying the object after the expiration date (or NUTjN_in the case of some other failure) of the original cross-reference. Finally, one might want to Nw`LUTjNthainclude some kind of check data to verify that the object retrieved is actually the one that was tJUTjN fZpreviously cited. Another potential component, whose rationale is much less clear, is the HUTjNcl]identity of an application that knows how to interpret the stored object, and that should be cFUTjNve`launched in conjunction with the arrival of a response from the server, or perhaps spliced into A(DUT@jNpr,the path between the client and the server. rv;BUT kNhiYThe details of how such a cross-reference might be engineered, so that it can be stored, eH@UTkNat_passed from client to client, and in the end be recognizable by the server, are an interesting nceU>UTkN eYdesign challenge. Several projects have run up against the challenge, and have suggested b<UTkNe ^various strategies that solve parts of the problem. At least six somewhat different ideas are o:UT@kNanextant: Ld<d ==y HH=< llHH;Apr)ly lZteTTim Berners-Lee has proposed the cross-reference scheme used in his World-Wide Web. tilZonXThis proposal is moderately complete, but it concentrates mostly on developing a syntax la D@lZioVthat can be parsed by a computer and also read by a person. It takes the view that it ,lZ bWshould be possible to create a document identifier that is both unique and perpetually -re9wp@lZngvalid. so L mZreXClifford Lynch, to stimulate discussion of the topic within the Coalition for Networked thXmZntSInformation developed a list of requirements, and for each some observations about nsteD8@mZd /mechanics that might address that requirement. atew nZrtMBrewster Kahle has proposed the cross-reference scheme used in his Wide-Area nwh@nZInformation Service. `oZFF. H. Ayers has made a proposal for a universal standard book number.  ZUTheodor Nelson, for the Xanadu hypertext system, proposed a universal, hierarchical iD0ZebUdocument numbering scheme with provision for versions and internal anchor points. It tZ sVcovers several of the requirements mentioned earlier by assuming complete homogeneity w`@Zw among the linked items. b pZleRApple Computer, in the System 7 Alias Manager for the Macintosh, has worked out a pZo Rsophisticated system for linking files within a Macintosh and across a network of D(pZtwTcooperating machines. The Alias Manager uses a combination of symbolic relative and chpZ aXabsolute path names as well as unique file, volume, and system identifiers, to maintain wX@pZ KUlinks in the face of renaming, hierarchy restructuring, and restoration from backup. 'U4UT qNicUEach proposal addresses one or more parts of the problem, but none covers the entire 4U2UTqNQrange of requirements. More important, the discussions by Lynch and by Kahle are iAU0UTqNXcharacterized by mentions of requirements not met, and possible alternative approaches, inNU.UTqN^together with questions about whether or not the requirements are real. Interestingly, almost [U,UTqNw \as if to recursively emphasize the need for a solution to this problem, most of the current r hU*UTqN hbliterature on the subject is not found in traditional journals, reports, or libraries, but rather uU(UT@qNf Cis found only on-line in various repositories within the internet. comU&UT`rNic lU$UT`}N Conclusion XabU"UT sNasWAs mentioned at the outset, this note has only described the problem, not proposed any UliU UTsN rZsolutions; even this description is not likely to resemble the one that will someday seem UUT@sNon obvious. aUUT`N,  UUT`MNtiAcknowledgements qUUT ~NuiUIdeas and suggestions came from discussions with Mitchell Charity, Jim OToole, Mark UUT@~N mPDay, Tim Berners-Lee, Andrew Birrell, Dave Redell, Paul McJones, and Ron Weiss. !UUT`N w 4UUT`tNet Bibliography rGUUT NNalOTim Berners-Lee, Jean-Francois Groff, and Robert Cailliau. Universal Document neeTUUTNNo ZIdentifiers on the Network. CERN, February 1992. On-line location: info.cern.ch:/pub/www/aU UT@NNl doc/udi1.ps rtd>UT?B oH@?B> s H@icU$UTUT`ONCo ud@enAAthHHA@ blHH= r tiUTUT vNcrUClifford Lynch. Workshop on ID and Reference Structures for Networked Information. bURUTvN^24 October 1991. (Call for participation. On-line location: CNI-ARCH listserv mailing list at !UPUT@vNonUuccvma.bitnet. Also found in UWAIS-discussion digestN #33, 27 November, 1991.) 4UNUT wNveVBrewster Kahle. Document Identifiers, or International Standard Book Numbers for the AULUTwNUTZElectronic Age. Version 2.2, September 1991. On-line location: quake.think.com:/pub/wais/NUJUT@wNNdoc/doc-ids.txt onaUHUT xNN,QF. H. Ayres. The Universal Standard Book Number (USBN): why, how and a progress dnUFUTxN^report. UProgram: Automated Library and Information Systems 10N, 2 pp. 75-80. (London: {UDUT@xN5Association for Information Management: April, 1976) UBUT yN]Theodore H. Nelson. ULiterary Machines, Edition 87.1. N(San Antonio, Texas: Theodor H. U@UT@yNtiNelson: 1987) U>UT Nch]Apple Computer. Alias Manager, UInside Macintosh Volume VIN, chapter 27. (New York: 4U<UT@NllAddison-Wesley: 1991) lUf{՘#B?> illUf{՘#itlsUU QS-=This is a a position paper for the ACM SIGOPS Fifth European wUUQleAWorkshop, to be held at Le Mont St. Michel, France, September 21- UU@Qw 23, 1992.  d!beLeftd"e.Righto/pd)w Referenceoidd6xFirstH. d8Std: wd<UFd> Firstr: d@In @No ) H yTh oNe n Li ahhi ,on .Textf ageCellBodyfe > CellHeading@i opeFootnote@TdHeadingBody@o H. H 8St    wh < Pgff  TableFootnotefTn Te TableTitleT:Table : fM  CellHeadingfM CellBody @PTitleBodyfPT  TableTitleT:Table : @Q  H  <Pg   h  fBody@W  f Header@W   Footer$@B $MH     h Bo BulletB:\t@ H   f  h  Body@N H Q    h  Text@N H W    h  Header@N Text@ BH     h  Text$@ZB $H     h  BulletB:\tM]O M N  P Q Q REmphasis S Subscript T Superscript U  WEmphasis  V W Z  Z;%ThinMediumDoubleThick@ Very Thinyy zHHHHHFormat A {HHHHHFormat BcrCommentCourier Helveticau New Century SchlbkTimesRegularRomansMediumBold RegularItalickXoB67lK*fKдG\H|va]P~he5j<غjA틹Uɠm-BX e3>ƕgȐ