From Udanax to Xudanu

60 years of connected documents: the algorithms, the people, and the modern realization of Ted Nelson's xanalogical structure.

1. The Vision (1960)

In 1960, Theodor Holm Nelson conceived a system where documents would never be copied, links would never break, and every quotation could be traced to its origin. He called it Project Xanadu. He called the literary structure xanalogical — a unique symmetrical connective system with two complementary forms of connection:

The World Wide Web, built 30 years later, implemented neither. It gave us fragile one-way links, embedded in flat files, with no recognition of content identity or version change. Nelson's response:

For 40 years, over 100 people worked on Project Xanadu. About 25 were active at the software design level. They produced at least 10 major design iterations, from xu60 (1960) through xu99 (1999). The most complete implementation was Udanax Gold (xu92), released as open source in 1999.

2. The Green and Gold Innovations

Project Xanadu produced two major working implementations. Udanax Green (xu88, 1988) was the foundational system — a working client-server architecture with the complete data model. Udanax Gold (xu92, 1992) extended it with Drexler's ent system for versioning and reconciliation. Both were released as open source in 1999.

Udanax Green (xu88, 1988)

Principally designed and implemented by Roger Gregory and Mark S. Miller. The first complete working implementation of xanalogical structure. Documented in the extensive FEBE (Front End-Back End) Protocol Manual.

Udanax Gold (xu92, 1992)

Designed by Mark S. Miller, Dean Tribble, and Ravi Pandya, based on K. Eric Drexler's ent data system. Extended Green with built-in versioning and reconciliation.

2a. Enfilade Theory

An enfilade is a tree data structure with two simultaneous properties that seem contradictory:

• Upward search property — flags propagate from children to parents, enabling O(log n) filtering
• Downward structural property — structural transformations can be imposed from the root downward

This dual-property tree was invented by Mark S. Miller, Stuart Greene, and Roger Gregory around 1980 — before either Green or Gold was coded. It was first implemented in Udanax Green (xu88). A single tree serves as both a search index (fast filtering by content fingerprint) and a structural container (impose displacements, transforms, versions).

Figure 1: The enfilade. Flags OR upward for search; structural transforms push downward. A single tree does both.

Why it matters: without enfilades, finding all documents containing a specific content fingerprint requires scanning every document — O(n). With enfilades and canopy propagation, it's O(log n). For a million documents, that's the difference between 1,000,000 operations and 20.

2b. Tumbler Addressing

Tumblers are multi-segment universal addresses for content in a distributed docuverse. Designed by Gregory and Miller for Udanax Green (xu88). They use hierarchical sequences like 4.3.1.7.2 where each segment narrows the location: server, work, edition, span, character.

Tumbler: 4.3.1.7.2
         │ │ │ │ └─ character position
         │ │ │ └─── span within edition
         │ │ └───── edition number
         │ └─────── work number
         └───────── server number

Tumbler arithmetic supports span operations — unions, intersections, differences — using transfinite arithmetic. This means you can ask "what content overlaps between version 1 and version 3 of this document?" as a pure arithmetic operation on tumblers.

2c. The ent System (Gold)

The ent (designed by K. Eric Drexler, ~1988-92) is a singular enfiladic structure with built-in versioning. It's a tree where every branch represents a version fork, and the tree structure itself encodes the complete version history of a document.

Figure 2: The ent. Versions branch and merge. The tree structure encodes the complete version DAG.

The ent enables non-destructive editing: creating a new version doesn't modify any previous version. It also enables DagWood reconciliation — merging divergent branches by finding the common ancestor and combining non-conflicting changes.

2d. Backfollow Engine (Green)

The backfollow engine answers the question: "Where else does this content appear?" Given a piece of text, it finds all documents containing that text — not by searching, but by content fingerprint matching.

Every piece of content gets a fingerprint (originally a hash, now BLAKE3). The backfollow engine maintains an index mapping fingerprints to all documents containing that content. Query: O(log n) via canopy tree.

2e. Canopy Trees (Green)

Canopy trees (BertCanopy and SensorCanopy) are balanced binary indices built on top of enfilades. They enable fast filtering of transclusion queries — instead of scanning every position in every document, the canopy prunes the search space.

Bert flags track which content fingerprints appear in subtrees. Sensor flags track which positions have specific properties. Both propagate upward (OR of children) enabling pruning: if a subtree doesn't contain the desired flag, skip it entirely.

2f. Content Lists (Green)

In the xanalogical model, a document is not a blob of text. It's a list of references pointing to content at permanent addresses. Editing modifies the reference list, never the content itself.

Figure 3: A document is a list of references. Content lives separately at permanent addresses. Transclusions reference other documents.

2g. DagWood Reconciliation (Gold)

DagWood is a DAG-based reconciliation system for merging concurrent edits. When two users edit the same document simultaneously, DagWood finds the common ancestor, compares both branches against it, and automatically merges non-conflicting changes.

This predates operational transform (OT) and CRDTs by decades. The key insight: represent the edit history as a DAG (directed acyclic graph), then find the maximum consistent merge of both branches.

3. The "nu": Modern Enhancements

The name xudanu combines "xu" (from Xanadu) with "nu" (new). The "nu" represents what modern computer science adds to Nelson's 1960 vision:

3a. BLAKE3 Content Addressing

Nelson's "central proprietary secret" was "the freezing of content addresses into permanent universal IDs." Gold used simple hashes. We use BLAKE3 — a modern cryptographic hash running at ~1 GB/s, producing 256-bit collision-resistant fingerprints.

3b. Ed25519 Per-Character Attribution

Gold tracked content identity (who transcluded what) but had no cryptographic proof of authorship. We add Ed25519 signatures on every text element — each character range is signed by its author's key.

Figure 4: Every character range carries an Ed25519 signature, author identity, and ISO 8601 timestamp. Court-grade non-repudiation.

3c. CRDT Collaborative Editing

Gold used grab/release locks — only one user could edit at a time. We replaced this with a CRDT (Conflict-free Replicated Data Type) layered on top of the O-tree. Multiple users edit simultaneously, with automatic convergence.

3d. Inline Transclusion (Single Source of Truth)

Gold's compound spans existed as a side-table alongside the O-tree — two copies that could drift apart. We moved transclusion directly INTO the O-tree as RangeElement::Transclusion — a zero-width element that IS the reference. One store. No drift.

3e. Attribution Propagation

When content is transcluded, the original author's identity and signature follow the content through transclusion chains. If alice writes text in document A, and david transcludes it into document B, document B's attribution panel shows alice as the author — with "via work:A" provenance.

This works recursively through transclusion chains (up to 32 levels), with cycle detection. It's Nelson's golden thread — following authorship back to the ultimate source.

3e. Attribution Propagation

When content is transcluded, the original author's identity and signature follow the content through transclusion chains. If alice writes text in document A, and david transcludes it into document B, document B's attribution panel shows alice as the author — with "via work:A" provenance.

Figure 5: Real attribution panel showing propagation. Alice's content (Jun 24) flows through transclusion into david's document (Jun 26) with original authorship and timestamps preserved.

4. The Lineage

5. What Remains

Nelson's complete vision includes features we have not yet built:

The hard part — the algorithms, the data structures, the mathematical foundation — is done. What remains is visualization, infrastructure, and the economic layer. Nelson's team spent 40 years on the hard part. We're building the rest.