Here's a page of diagrams I drew for a friend in 1997 (97.04.03 = April 3, not "Y2K-compliant"), showing what I think is the technical essence of Xanadu (now Udanax). I will talk in the present tense although full blown Xanadu isn't up as I write this.

Some Context

Xanadu is a server network something like the Web. Browsers are called "front ends," and servers "back ends." There is a unified address space something like URLs, with server/author/document-and-version/address-within-document. Addresses in requests can be as fine-grained as single character positions. The browser talks to one server, which coordinates responses from the peer-to-peer server network as if everything were inside one machine. These diagrams are about how that virtual machine does the magic of storing documents related by common content, versioning, and links. I will repeat all the text in case it's unclear on the drawings.

Main diagram, top left

Top half ("Single Virtual Address Space" with "Arrangements") and bottom half ("Shared Stuff"). "Stuff" refers to text, but also pictures and other data. Arrangements are shown as dots with lines extending down into the pool of stuff. Conceptually, an arrangement is just an ordered list of pointers to pieces of stuff. Every version of every document is an arrangement of stuff. Links are arrangements, too; that's explained below.

"Transclusion" refers to this sharing of stuff, with the added property that when arrangements share the same piece of stuff, that commonality can be traced to its exact location within each arrangement.

(There is sometimes confusion over what "the same stuff" means. If two authors both type the word "the," is that a single shared piece of stuff? Not in Xanadu. Instead, as characters are typed in by authors, they are given identities, internal addresses, and those identities are kept when chunks of text are copied and pasted into new documents, or when new versions of documents are made.)

Both arrangements and stuff are "only added", meaning that (to a first approximation) you only create new things, never delete existing things or edit them in place. Editing is done by creating a new version.

(By the way, stuff is "shared" as in between documents, not necessarily between different users. Xanadu has rules for keeping documents private, or declaring them visible to everyone (publishing) or to a select group ("privashing").

List on the top right

The basic Operations that a user can can perform with the system. This roughly corresponds to the Front-End-to-Back-End protocol, or FEBE view of the world: ...all in terms of virtual address: server.author.document.version.position (all address fields can themselves be structured, meaning server IDs, user IDs, document/version IDs and positions within documents can all be dotted numbers like IP addresses, Dewey Decimal numbers, chapter.section.paragraph.character addresses, or whatever.)

The heart of Xanadu is an indexing system that makes these operations of creation, retrieval and correspondence-tracing efficient.

Middle of the right side

Access to each version is reasonably fast, no matter how many version accumulate. This is in contrast to versioning systems like CVS, where one version (in CVS, the last) is fastest, and other versions are slower because pointers have to be traced through the string of versions. In Xanadu (and some other systems), versions are all on a par, because they all point straight into the stuff rather than to each other. (This despite the user having created one version out of another.) Also, retrieving a piece of a large document is fast, because Xanadu doesn't have to retrieve or construct the whole document in order to retrieve a part.

Middle diagram: tracing links into a changed file

This diagram sets up an issue that Ted Nelson calls "links times versions": how do you trace a link that was made to an earlier version of a file, into the corresponding locations in a later version? To understand this issue you need to know more about Xanadu links.

On the World Wide Web (so far, 2004), a link comes from a single (generally short) span of positions in a document. It's the blue word you click on. The to end of a link generally points to a whole web page, or sometimes to an "#anchor" point placed within a page by the to-page's author.

In Xanadu, both the from and to ends of a link can cover a set of spans of text. We'll concentrate on the to end here. I can pick out a paragraph in the middle of someone else's document and make a link from my comment about that paragraph. The author of the to document doesn't have to set up an anchor for me to link to; I just refer to the range of addresses corresponding to the paragraph I want to talk about.

Now suppose the author of the to document supercedes it with a new version. This is the situation in the middle diagram. The author of B made a link to [a paragraph in] Av1 [document A version 1]. Meanwhile A has been changed. The author of Av1 has produced Av2. Chunks of text have moved from places in Av1 to new places in Av2, shown by "correspondences" and diagonal lines between the two versions. The original paragraph may even have been split into pieces that were moved to separate places. The issue: Where does the link point to now?

Eventually both A and B could go through many revisions. But following links needs to be reasonably fast, no matter how many versions of the from and to documents have accumulated since the link was made.

How can the link work fast? Don't we have to trace it back through all the versions of B, then over to the first version of A, then forward through all the versions of A, something like that? No.

The explanation starts on the left of the middle diagram. A link is just an included piece of the linked-to document. The link is actually a separate little arrangement of stuff, that includes the paragraph from A version 1. Since the link and Av1 share that piece of stuff, a reader's browser can find the location of that stuff within Av1 by asking the server to "show correspondence [between the link and Av1] to follow the link." Once the location of the stuff in Av1 is fetched, the browser can show the paragraph in its proper context.

Bottom section: Really--how it works

Even if many versions of both B and A have piled up, following the link works with the same short set of steps: ask for the correspondence between the link and the version of the linked-to document that you're interested in (typically the latest). The job doesn't get knotted in the trails of versions, because both the link and all the versions point straight into the stuff, and the server traces from link, to stuff, straight back to the version of interest.

I hereby place the text and diagrams above in the public domain. --Steve Witham