Federation Protocol

Intent

The Federation Protocol is used between Wave Providers to sync waves between themselves. This is transparent to the end user, who reaps the benefits without caring that this is going on under the hood.

This is a rewrite of an existing protocol to improve clarity.

Dependancies

Connection

This standard expects a bi-directional TLS secured stream (e.g. a secured XMPP connection). Some stanzas require cryptographic keys and signatures.

Streams are opened for individual wavelets

Terms

This list assumes I do not have to define XML terms I use.

Stanza
A XML element representing an action in XMPP.
Document
A XML-like structure fully explained in Documents.
Delta
A change in a document. Communicated across Federation instead of the documents themselves. Explained fully in Deltas.
Annotations
A mapping of keys to values on a tag contained in a document.
Federation Remote
A Wave Provider which does not store the master copy of the relavent document.
Federation Host
A Wave Provider which stores the master copy of a relevant document.
encoded to base . . .
Representation of a number as a string where the base is the number of digits possible for each charactor (e.g. For normal output we use base 10). If the base is not described, assume 10.

Authors/Reviewers

Objects

The federation protocol provides an exchange of deltas, which is a change in documents stored on the participating servers. This section explains these objects (deltas, documents, and their contained operations and items respectfully).

Deltas

A delta is a change in a document as described by a sequence of items. It can be described by the C structure:

struct Delta { Operation** ops; }

The operations in a delta start processing at the first tag of a document with no annotations and ends at the last tag with no annotations.

Documents

A document is a sequence of open, close and text tags all with textual content and "annotations". It may be thought of like XML except the text can have attributes too and can be represented by the C structures (with added "hash" type refering to a key to value mapping):

struct Document { str name; //identifier for the document Tag** tags; } struct Tag { TagType type; str text; hash annotations; } enum TagType { TAG_TYPE_START; TAG_TYPE_END; TAG_TYPE_TEXT; }

Document Name

A document name is in two parts, the domain of the Host and the id for the document, in the format "domain!id". For the most part, the id does not have any requirements (apart from those discussed in the format standard).

The format standard uses seperate documents for blips and wavelets. The names may be either unique within a connection or between all connections.

Operations

Operations are the building blocks of deltas and are effectively function calls. They may be approximated by the C structure:

Struct Operation { str type; void** arguments; }

Operation Library

Operations, as mentioned above, are effectively function calls. This section lists all available operation routines to be used in a delta.

These operations act on an input and output document, copying data from the input to the output. Both documents keep track of cursor and current annotations. They are also told what to expect in the input document so as to catch mismatched deltas.

Operation Routine Arguments
(with C types)
Input Document Effect
(psuedocode)
Output Document Effect
(psuedocode)
retain int itemCount Adds itemCount to cursor Copies itemCount charactors from input content. Adds itemCount to cursor
replaceAttributes hash<str> oldAttributes, newAttributes Access item at cursor Ensure it had oldAttributes for annotations. Increment cursor. Insert cloned item from old document Replace it's annotations with newAttributes
updateAttributes
(More succinct than replaceAttributes)
hash<str[2]> attributesUpdate Access item at cursor Ensure it's annotations are the same as the first value for each value in attributesUpdate Insert cloned item from old document Create a hash with second value for each key in attributesUpdate Set the cloned item's annotations to that hash
characters str characters N/A Insert characters as an item.
elementStart str type, hash<str> attrs N/A Create item of type start, name of type, and annotations of attrs. Append to document
ElementEnd N/A Inserts end tag.
deleteCharacters int characters Increment cursor by characters. N/A
deleteElementStart str type, hash<str> attrs Retrieve item at cursor Ensure it has a type of start, a name of type, and annotations of attrs. Increment cursor. N/A
deleteElementEnd Ensure item at cursor is an end item. Increment cursor. N/A
AnnotationsBoundary char** ends, hash<str[2]> changes Increment cursor Append cloned item in oldDocument. for each end in eds delete key end from cloned item's annotations Apply changes like updateAttributes

Delta Format

Deltas are transfered using a mini-language inspired by Unix CLI.

Each function is seperated by a semicolon (;) and it's name and arguments are seperated using spaces ( ), with the first item being the operation.

Brackets can surround arguments if they contain spaces or are simalorly unclear. Commas (,) are used to seperate data in a collection, while colons (:) are used to pair key:value pairs in a hash.

An example of this mini-language is:

elementStart foo ship:Serenity,class:firefly;characters (Hello world!);elementEnd

Stanzas

This section lists the stanzas which can be sent in the Federation Protocol via pubsub.

wave

The start of each session should include this element, which is described by the following DTD:

<!ELEMENT wave #PCDATA> <--Contains the wave ID for which all the document names are a part of-->

signature

Before submiting a first delta to a Federation Host, the Federation Remote must send it a signature stanza. This element can be described using the following DTD:

<!ELEMENT signature (certificate+)> <!ATTLIST signature domain CDATA #REQUIRED <!--Should be your domain name--> algorithm CDATA #REQUIRED <!--The cryptographic algorithm of your certificates.--> > <!ELEMENT signature #CDATA> <!--Content should be base 64 encoded certificate-->

The Federation Remote must reply if the certificate passes with a plain "signature-response" element.

signer-request

If a Federation Remote recieves data from a Federation Host that it doesn't have a certificate for, it should send a signer-request stanza. This element can be described using the following DTD:

<!ELEMENT signer-request #EMPTY> <!ATTLIST version CDATA #REQUIRED <!--The logical version of the wave--> wavelet-identifier CDATA #REQUIRED <!--The document name--> >

The Federation Host who recieves this should respond with a signature stanza as described above.

wavelet-update

The wavelet-update element is sent in a message stanza from a Federation Host to update documents in Federation Remotes, i.e. when it's document changes. It can be described with the following DTD:

<!ELEMENT wavelet-update (applied-delta*)> <!ATTLIST wavelet-update doc-name CDATA #REQUIRED <--The wavelet identifier--> > <!ELEMENT applied-delta #PCDATA> <--Contains the delta, as described in Delta Format-->

submit-request

The submit-request element is sent in a pubsub event stanza for a Federation Remote to update a document on a Federation host. It can be described using the DTD:

<!ELEMENT wavelet-update (delta*)> <!ATTLIST wavelet-update doc-name CDATA #REQUIRED> <!ELEMENT delta CDATA #REQUIRED > <--Contains the delta as described in Delta Format-->

The Federation host should save the delta in the document, reply with a submit-response, and send a wavelet-update

submit-response

submit-response is sent in a pubsub response stanza in response to a submit-delta. It can be described by the DTD:

<!ELEMENT submit-response (hashed-version!)> <!ATTLIST submit-response operations-applied CDATA #REQUIRED <!--The number of operations applied to the document--> application-timestamp CDATA #REQUIRED <!--Unix timestamp representing the time the deltas were applied.--> error-message CDATA #REQUIRED <!--Describes an error that accord. Written to logs and purposefully does not describe what these messages should be.--&g; > <!ELEMENT hashed-version #EMPTY> <:!ATTLIST hashed-version version CDATA #REQUIRED <!--The logical version of the wave after applying the delta--> >

delta-history

The delta-history element is used within a PubSub event stanza. It is sent whenever a Federation Remote needs information from a Federation Host about previously applied deltas.

e.g. When a Federation Host first connects. This element can be described with the DTD:

<!ELEMENT delta-history #EMPTY> <!ATTLIST delta-history doc-name CDATA #REQUIRED <!--The document identifier of a document--> start-version CDATA #REQUIRED <!--Integer representing starting version--> end-version CDATA #REQUIRED <!--Integer representing ending version--> response-lenght-limit CDATA <!--The prefered length limit--> >

When a Federation Host recieves this, it should respond with a history-response element.

history-response

The history-response element is used within a PubSub response stanza as the response to a delta-history request. It can be described with the DTD:

<!ELEMENT history-response (history-truncated?, applied-delta* commit-notice?)> <!ELEMENT history-truncated #EMPTY> <!ATTLIST history-truncated version CDATA #REQUIRED> <!ELEMENT commit-notice #EMPTY> <!ATTLIST commit-notice version CDATA #REQUIRED>

Changes Since Previous Version

There may be changes that the author is not aware of which came in through inclarities. However, that was the call for this document which should be clearer.

These are the changes that are known: