This is the text version of a paper originally prepared with FrameMaker, so
details such as italics and footnotes are missing.  The full citation of the
paper is as follows:

  Saltzer, J. H., "Needed:  A Systematic Structuring Paradigm for
  Distributed Data," Operating Systems Review 27, 2 (April, 1993),
  pp. 77-81.  Originally distributed as paper #41 in 5th ACM
  SIGOPS Workshop on Models and Paradigms for Distributed Systems
  Structuring, September 21-23, 1992, Le Mont Saint-Michel, France,
  pp. 1-5.

This paper is also available in PostScript form.

==============================================================================

NEEDED: A SYSTEMATIC STRUCTURING PARADIGM FOR DISTRIBUTED DATA

by Jerome H. Saltzer
Library 2000
M.I.T. Laboratory for Computer Science
September 10, 1992



The purpose of this note is to alert the distributed and operating
systems communities to a research and design exercise that is going on
in an adjacent application-oriented community. This research and design
exercise involves inventing a paradigm for distributed system
structuring that is distinctly different from that of remote procedure
call and related paradigms that are the usual focus of the distributed
systems community.

The class of applications involved might be roughly characterized as
distributed, linked data. The remote procedure call paradigm, in which
a client asks a server to perform some named computation on a set of
supplied arguments and return a result, is not an especially congenial
fit to this application, although it may be a useful tool at a lower
level of abstraction in resolving links. Perhaps because the application
of linked data has not been widely considered, it is not clear yet what
is an appropriate form for the structuring paradigm, or even whether or
not the problem has been posed carefully enough to allow one to propose
specific structures. This note describes the problem as it has been posed
in the distributed data community, and points to a few early attempts to
suggest mechanisms; it does not claim to settle the issue.

The interesting requirement in distributed storage of related data
lies in those data relations that can be characterized as cross-
reference. There are many different applications in which one object
might need to contain a cross-reference to another, remote, object. As
examples, one might propose to build a distributed hypertext system, a
sales reporting system for a corporation that has many branch offices,
an office system that allows one worker to incorporate an element of a
remote spreadsheet into a local one by reference, a distributed legal
case database, with cross-references among cases, and also from state to
federal cases and back, or simply an electronic library.

For concrete scenarios consider the specific application of an on-
line electronic library (comparable scenarios arise in most of the other
application examples.) In the electronic library, the primary scenarios
of interest are the following: The maintainer of a document storage
service has installed a new document and wants to advertise the new
document to clients and clients of clients, and allow search services to
store and pass along cross-references (in this application a cross-
reference is usually called a “citation”) to the new document. In a
related scenario, the client of a search service has completed a search
and wants to be able to store a persistent cross-reference to one of the
items discovered. Storing the search query that was used to discover the
item is one common suggestion, but that method is not very satisfactory,
because that particular search may have returned several items in its
result set, or it may have been framed in terms of something unrelated
to what makes the document interesting. In addition, since collections
grow and shrink, there is no guarantee that the search service will
return the same result set for the same query at a future time—especially
if the document itself might change in such a way as to cause the query
not to find it. In yet another related scenario, the user of a document
discovers in it a cross-reference to another document, and wants to make
a copy of that cross-reference, in persistent storage for future use.
And in a final scenario, a client includes a cross-reference in a
document which it then submits to be stored by some storage service,
possibly a different one.

In each scenario, some client intends to place the cross-reference in
persistent storage somewhere, for presentation to the storage service at
an unknown time in the future. When the client eventually presents the
cross-reference to the storage service, it hopes to retrieve the cited
item.

In an electronic library, such cross-references may be used:

•	by an author, in creating a new document, to cite previous, related
documents.

•	by the librarian of a storage service, in adding a document to a
collection, making concrete an author's traditional text citations.

•	by a user of a search service, to prepare a list on a personal note
pad of discovered documents.

•	by a search service as the internal connection between its index and
the documents held by a storage service. (e.g., to connect a
bibliographic record with the corresponding document).

•	by a search service, as the method of telling the client how to obtain
the item from a storage service.

•	by a client, to pass along to another client

•	by an author, to cite anchor (that is, identified internal) points
within another document.

The following simple scenario perhaps captures best of all the
required structuring behavior: At the application level, a user has
brought up a document in a display window, and upon browsing through it
noticed that it mentions another document. The browser provides as a
feature that the user be able to point to the cross-reference with the
mouse, click, and expect to see the cited document appear on the screen
in another window.

There are a number of interesting constraints on the solution, at
least in the electronic library application. Some of the other
applications have analogous constraints:

•	The storage service to which the cross-reference is eventually
presented may be different from the one that provided the original
cross-reference—it may be a backup system, or even a competitive
provider.

•	The interval between creation and use of the cross-reference can be
quite long, perhaps decades, during which time the storage service may
have been upgraded, relocated, merged with other storage services, and
placed under different administrative control.

•	Cross-references will persist long enough that the system that is
intended to resolve them will become obsolete.

•	Between creation and use of the cross-reference, the cited document
may have been deleted, updated, or superseded. Something graceful
should happen if multiple versions are available. If the “document”
is actually a dynamic piece of data such as a current stock quote,
perhaps something different, yet graceful, should happen.

•	Between creation and use of the cross-reference, the organization of
the library may have been revised, and the target document may now be
classified differently.

•	Between creation and use of the cross-reference, the physical and low-
level logical configuration of the storage server may have been
revised, and the target document may be in a different directory or
on a different physical volume.

•	Between creation and use of the cross-reference, the storage
representation of the target document may have been discovered to be
defective, and restored from a backup copy.

•	The initial discovery mechanism may identify only the document; a
later discovery process may identify anchor points of interest.

•	The user who presents the cross-reference may or may not be authorized
to obtain the document.

•	A single document may by indexed by several different search services
that are under different administrations.

•	In response to presentation of a cross-reference, a storage server
may, rather than delivering the desired document, instead return
another cross-reference.

•	If a client makes inquiries of several different search services, it
would like to merge the several responses, which requires that it be
possible to figure out which of the returned cross-references are
duplicates.

As can be seen from this laundry list of constraints, the requirements
on cross-references among distributed data objects read more like the
list of requirements for a sophisticated name service than they are like
the requirements on an RPC service.

It would appear that at the minimum, a cross-reference internally must
be composed of at least two components. The first would be an identifier,
perhaps to be presented to a name server, that allows the client to
discover an appropriate and current server name, port, and protocol to
use, and to verify upon connection that the service at the other end is
the intended one. A second component probably is a specific object
identifier that server is expected to recognize. Beyond that, one moves
into the realm of speculation. There might be an expiration date after
which the server doesn't guarantee to honor the cross-reference, and
perhaps also a backup query, which might be useful in identifying the
object after the expiration date (or in the case of some other failure)
of the original cross-reference. Finally, one might want to include some
kind of check data to verify that the object retrieved is actually the
one that was previously cited. Another potential component, whose
rationale is much less clear, is the identity of an application that
knows how to interpret the stored object, and that should be launched in
conjunction with the arrival of a response from the server, or perhaps
spliced into the path between the client and the server.

The details of how such a cross-reference might be engineered, so that
it can be stored, passed from client to client, and in the end be
recognizable by the server, are an interesting design challenge. Several
projects have run up against the challenge, and have suggested various
strategies that solve parts of the problem. At least six somewhat
different ideas are extant:

•	Tim Berners-Lee has proposed the cross-reference scheme used in his
World-Wide Web. This proposal is moderately complete, but it
concentrates mostly on developing a syntax that can be parsed by a
computer and also read by a person. It takes the view that it should
be possible to create a document identifier that is both unique and
perpetually valid.

•	Clifford Lynch, to stimulate discussion of the topic within the
Coalition for Networked Information developed a list of requirements,
and for each some observations about mechanics that might address that
requirement.

•	Brewster Kahle has proposed the cross-reference scheme used in his
Wide-Area Information Service.

•	F. H. Ayers has made a proposal for a universal standard book number.

•	Theodor Nelson, for the Xanadu® hypertext system, proposed a
universal, hierarchical document numbering scheme with provision for
versions and internal anchor points. It covers several of the
requirements mentioned earlier by assuming complete homogeneity among
the linked items.

•	Apple Computer, in the System 7 Alias Manager for the Macintosh, has
worked out a sophisticated system for linking files within a Macintosh
and across a network of cooperating machines. The Alias Manager uses
a combination of symbolic relative and absolute path names as well as
unique file, volume, and system identifiers, to maintain links in the
face of renaming, hierarchy restructuring, and restoration from
backup.

Each proposal addresses one or more parts of the problem, but none
covers the entire range of requirements. More important, the discussions
by Lynch and by Kahle are characterized by mentions of requirements not
met, and possible alternative approaches, together with questions about
whether or not the requirements are real. Interestingly, almost as if to
recursively emphasize the need for a solution to this problem, most of
the current literature on the subject is not found in traditional
journals, reports, or libraries, but rather is found only on-line in
various repositories within the internet.



Conclusion

As mentioned at the outset, this note has only described the problem,
not proposed any solutions; even this description is not likely to
resemble the one that will someday seem obvious.



Acknowledgements

Ideas and suggestions came from discussions with Mitchell Charity,
Jim O’Toole, Mark Day, Tim Berners-Lee, Andrew Birrell, Dave Redell, Paul
McJones, and Ron Weiss.



Bibliography

Tim Berners-Lee, Jean-Francois Groff, and Robert Cailliau. “Universal
Document Identifiers on the Network.” CERN, February 1992. On-line
location: info.cern.ch:/pub/www/doc/udi1.ps

Clifford Lynch. “Workshop on ID and Reference Structures for
Networked Information.” 24 October 1991. (Call for participation. On-
line location: CNI-ARCH listserv mailing list at uccvma.bitnet. Also
found in WAIS-discussion digest #33, 27 November, 1991.)

Brewster Kahle. “Document Identifiers, or International Standard Book
Numbers for the Electronic Age.” Version 2.2, September 1991. On-line
location: quake.think.com:/pub/wais/doc/doc-ids.txt

F. H. Ayres. “The Universal Standard Book Number (USBN): why, how and
a progress report.” Program: Automated Library and Information Systems
10, 2 pp. 75-80. (London: Association for Information Management: April,
1976)

Theodore H. Nelson. Literary Machines, Edition 87.1. (San Antonio,
Texas: Theodor H. Nelson: 1987)

Apple Computer.  “Alias Manager,” Inside Macintosh Volume VI, chapter
27. (New York: Addison-Wesley: 1991)