AbiTalk Protocol Proposal

History

Draft 0.5: Clarify network topology and sign on process; add <connect/>, <listdocuments/> and <document/> commands; removed invite command.

Draft 0.4 (22/05/05): Scope checking added to token negotiation; added <lockout/> command.

Draft 0.3 (21/05/05): Removed <document/> as the document should be transmitted using change records as envisaged by the GOCollab proposal. Reworked the handshake in order to minimise the document lockout.

Draft 0.2: Added 'encoding' and 'compression' attributes to <document>;

Draft 0.1 (18/05/05): Tokens of limited scope; more detailed token negotiation & error handling; new commands (invite, chksum); changed <error> to <status>; UT_AbiTalk::Result enum.

Draft 0.0 (17/05/05): Original proposal.

Introduction

AbiTalk is an attempt to define a protocol that would allow for exchange of information necessary to implement collaborative features, such as those proposed in GOCollab. The principal challenge in a collaborative conversation is the maintaining of the coordinate systems in the two documents in synchronic state. The GOCollab proposal assumes that all conversation partners maintain a coordinance mapping for this purpose. This idea, however, depends on being able to establish an initial synchronic state, and this task is the principal concern of the AbiTalk protocol.

There are number of issues that this protocol does not strive to address:

This protocol is not interested in what kind of information is required to accomplish the collaboration; it simply assumes that any application using it defines the specific commands required to achieve it's aims and that it registers handlers for these commands with the generic AbiTalk handler. What this protocol does is to define the handshake process and provides means through which it is to be extended to exchange arbitrary information between the communicating processes.

This protocol is not interested in the underlying transport mechanism. A simplest implementation could just use TCP/IP, but a more robust implementation might prefer some other protocol that would minimise problems with firewalls, etc.

This protocol does not define a sing-on process; that is the responsibility of the underlying carrier protocol.

The initial proposal is for the protocol to be xml-based (using xml 1.0 specification); this is not critical to the protocol, but has two significant advantages. First of all, parsing becomes a simple matter due to the built-in xml parser in AbiWord (and presumably in other GOffice applications). Second, and perhaps more significant, AbiWord piece table is xml-like, so that representing AbiWord events in xml should be straightforward.

Topology

The protocol work with a nominal host topology. Where there is no formal server, a mechanism needs to be put in place for promoting one of the clients to a nominal host if the existing host is no longer present; this mechanism is not specified by AbiTalk.

Message Format

A message passed between two processes has the following format

<%cmd%>[content]</%cmd%>[<%cmd%>[content]</%cmd%>]

</abitalk>

version: identifies version of AbiWord sending the message.

uid: the uuid of the document which is the subject of conversation; if not provided, the commands to follow can only carry out operations on the application, not documents.

token: authorisation token. The token is a standard uuid with time stamp adjusted to indicate when the authorisation token expires. Tokens are connected to a specific document uid. If no token is provided the only legitimate commands to follow are <token> and <getdoc> (see below).

Single message can contain one or more commands:

%cmd%: specific command name, which can be followed by set of attributes

[content]: content specific to given command (optional)

The entire <abitalk></abitalk> fragment represents an atomic operation on the document from the user's point of view (i.e., an operation which can be undone by a single Undo command). The user-atomic operation can consist of an arbitrary number of operations carried on the document.

Control commands (predefined)

The following commands are predefined by the protocol:

<getdoc [name="xxxx" | uid="xxxx"/>: request for the entire document identified by either a name, or the doc uid [the latter option is only available in response to ABT_ChecksumMismatch status, see below].

<connect client-id="xxxx"/>: opens connection to a known server.

client-id: an id that identifies the user; this has to be known to both the server and client (and needs to be set-up by the system administrator); the AbiTalk protocol does not specify the format which this id should take.

<listdocuments>[<document uid="xxx"/>]</listdocuments>: If the body of this command is empty, it is interpreted as request for a list of available documents on the server. The response to the request is provided by sending filling <listdocuments/> body with <document/> messages.

<document uid="xxx"/>: identifies document known to the server.

uid: uuid of the document.

<chksum uid="xxx">[sum]</chksum>: either request for checksum for specific document, or reply to checksum request; in the latter case the checksum is supplied as content of the element.

uid: uuid of the document for which the checksum is sought/provided.

<reqtoken type="0|1" [uid="xxxx"]/>: Request for authorisation token.

type: either 0 or one (see token handling below).

uid: required for type-1 tokens; specifies uid of previous type-0 token.

<token uid="xxxx" life="life in ms" chksum="xxx" type ="0|1" [start="pos1" end="pos2"]/>: Response to request for authorisation token (see token handling).

uid: token.uid in standard uuid format. The token is specific to the document uid, and has a limited lifespan; the expiry time is indicated by the uid time stamp.

life: indicates the intended life of the token in ms.

chksum: crc32 check sum for the document that will be compared to the remote document; this has to refer to the document before the changes that are to be broadcast were made (NB: will need to store checksums in AbiWord version table to allow for offline editing.)

type: 0 or 1 (see token handling below).

start/end: indicate that token is requested only for a limited range in the document.

<release uid="xxxx"/>: sent to release authorisation token; as soon soon as this command is sent, the token becomes invalid. This command is required for the entire transaction to be valid (see below notes on token handling).

uid: authorisation token.

<lockout owner-id="xxxx" uid="xxx" start="pos1" end="pos2" life="Xms" on="0|1"/>: indicates that an authorisation token has been issued to another conversation partner for the specified region of the document. The recepient might want to use visual means to indicate to the user that a particular region is locked for editing.

owner-id: uuid identifying the owner of the authorisation token.

uid: uuid identifying the document to which lockout applies.

start/end: the region of the document to which lockout applies.

life: the life span of the lockout in ms.

on: boolean value indicating whether the region is locked or unlocked for editing.

<status id="errno" [param="xxx"]>[verbose msg]</status>: send in response to executing previous message to indicate success or failure.

id: UT_AbiTalk::Result

enum Result { ABT_Success = 0,

ABT_Error = 1,

ABT_TokenExpired = 2, // param="uid"

ABT_NoCmdHandler = 3, // param="cmd"

ABT_CommandFailed = 4,

ABT_InvitationRejected = 5,

ABT_TokenPending = 6,

ABT_Unwind = 7,

ABT_ConnectionRefused = 8, // param="delay in s"

ABT_ChecksumMismatch = 9, // param="checksum"

ABT_UnknownDocument = 10,

ABT_TokenRequestCancelled = 11

};

param: an optional parameter specific to the status numberverbose msg: optional

verbose, human readable, error message.

Performative commands (user-defined)

The protocol only defines the control commands. The commands that are used to perform actual operations on the document are defined by the application and are handled by command handlers registered via UT_AbiTalk::registerHandler() with the AbiTalk handler. Their number and meaning has no direct impact on the protocol itself (i.e., the protocol can be easily expanded as new features are added). If a command is received for which no handler is available, status ABT_NoCmdHandler is returned to the sending process (see section on error handling below).

Sign-on process

The sign-on process is dependent on the nature of the conversation.

Sign-on in server-centred conversation

If the conversation is based on interaction with an automated sever, any authentication is the responsibility of the carrying protocol. Once the client is authenticated and it sends the <connect/> command to the AbiTalk hander. In response to the command, the server check that the client-id is valid, and if it is opens outgoing connection to the connecting client.

Sign-on in distributed context

In a distributed context, the sign on mechanism has to be provided by the carrier protocol; it is not specified by AbiTalk. Since the AbiTalk protocol is nominal-host-based, the carrying protocol has to provide means through which a client can be promoted to host if the original host leaves the conversation; again this mechanism is not part of AbiTalk.

Token handling

As indicated in the introduction, the principal challenge of collaborative conversation is to establish a correct initial state of the coordinate systems. This issue is complicated by network lag, particularly if more than two partners are involved in the conversation. The present proposal attempts to work around this through a two stage handshake. The first stage of the handshake is used to allow any pending messages to get through and the document stabilise, the second stage carries out the correlation of the documents.

In the following A and B are Abi processes, and A wishes to have a conversation with B. C is a third (silent) partner in the conversation.

The procedure by the initiator (A)

If A wishes to send commands to B, A needs an authorisitation token. There are two types of tokens; a token that gives A the authority to send commands to B is called type-1 token. There is also type-0 token which is in the initial negotiation.

To obtain a type-1 token, A first requests type-0 token (<reqtoken type="0"/>) and waits for response. While waiting, A has to process all messages from B up to either receiving a type-0 token or status ABT_TokenRequestCancelled. Also while waiting, all local events have to be temporarily suspended and queued up. (This is necessary because until A obtains the type-1 token, A is unable to notify B of these changes.)

If A receives ABT_TokenRequestCancelled, A has to restart the entire process.

Upon the receipt of type-0 token, A computes a checksum for the current state of the document and associates the token with mapping for translation of local document coordinances to those reflecting the state of the document at the receipt of the type-0 token. It then sends request for type-1 token (<reqtoken type="1" uid="xxxx"/>), and waits for the token. At this point the queued up local changes can be applied but they a separate queue has to be maintained so that these changes can be send to B later; it should be noted, however, that if revisions are not enabled in the documents, some of the events in the local queue might no longer be valid (as when the processing of remote messages resulted in the removal of a part of the document on which a local event carried out operations) -- these events have to be removed from both queues (NB: it is technically simpler to maintain a single queue and contain the local lockout until type-1 token is obtained.)

If the A receives ABT_TokenRequestCancelled, it has to restart the entire process.

If A receives type-1 token, it finds the mapping associated with the corresponding type-0 token, and replaces the token with the type-1 token. It can now start sending commands to B using the type-1 token, translating all coordiances using the mapping.

If A receives ABT_ChecksumMismatch in response to token-1 request, in the first instance it ascertains if it has a mapping that would allow it to translate local coordinaces to those with the identical check sum; it it has, it can re-request authorisation token for that particular checksum. If A does not have the means to for coordinance translation, it has to reload the document from B, and restart the authorisation process; it can then either discard the local changes or attempt to merge the differences between the local and remote documents and then send these changes back to B.

When finished with the whole command sequence, A has to release the token by sending <release uuid="xxx"> command. At this point B accepts all changes as permanent, and broadcasts the changes to other interested parties.

If A receives ABT_TokenExpired before it sent the release command, it will have to restart the entire process and resend all commands that we dispatches with the expired token.

A can cancel the entire transaction using the given type-1 token by sending B ABT_Unwind message.

When A first receives its type-1 token, it notes its intended life span. If A does not receive a status message for a particular message dispatched to B, A should wait for time equal to the intended life span of the token after the token expires; if no status message is received during this time, A should proceed as if receiving a generic ABT_Error status.

The procedure for the recipient (B)

Upon the receipt of the request for type-0 token from A, B waits for period of 2 * longest life span from outstanding tokens to allow any pending messages to be processed by all parties. After that B computes a checksum for the present state of the document, and creates a type-0 token. It also creates a mapping for translation of document coordinances from those corresponding to the state of the document at the point the token was created and associates that mapping with the type-0 token. It then sends the type-0 token to A.

Upon receipt of type-1 token request <reqtoken type="1" chksum="xxx" [start="x" end="y"] uid="xxx"/> B first checks that the request is associated with a valid type-0 token, if not B dispatches ABT_TokenRequestCancelled status, and destroys the associated type-0 token.

If the token-0 uid is valid, B checks the supplied chksum against the checksum associated with the type-0 token in its own records; if the checksums do not match, B sends ABT_ChecksumMismatch, setting the param attribute to the checksum of B's version of the document. It maintains the type-0 token waiting for A's response. If it receives any other command from A than a new request for type-1 token, it destroys the type-0 token.

If checksums and type-0 tokens match, B proceeds to check if there are any outstanding tokens for the same document (identified by uid) with an overlapping scope (i.e., whether document ranges indicated by start and end attributes overlap); if they do, B issues ABT_TokenRequestCancelled status and destroys the associated type-0 token.

If the token scope is unique, B creates type-1 token and replaces with it the type-0 associated with its mapping. It then dispatches the type-1 token to A.

If B receives any other requests for authorisation tokens from other parties while there is an outstanding type-0 token, B will queue these requests, and reply with status ABT_TokenPending. This queue will be processed as soon as either the type-0 token expires, or the associated type-1 token is issued. At the same time, B sends corresponding lockout-on message to all other partners.

When B receives <release/> command from A, it finalises all changes made with the specific type-1 token, destroys the token and dispatches lockout-off message to all other partners.

B keeps an eye on the life of all the issued tokens; if a token expires before the <release> cmd is received for any token, B reverses all operations carried on the document using that token and dispatches status ABT_TokenExpired to the token owner, and corresponding lockout-off message to all other conversation partners.

B can cancel a previously issued token at any time by dispatching ABT_TokenExpired status to A; in that case it has to dispatch lockout-off message to all other partners.

If B finds itself in situation where it repeatedly has to send ABT_TokenExpired to A, B should consider, in the first instance, to prolong the life of the token (within reasonable limits); if this does not remedy the situation, B can send ABT_ConnectionRefused, setting the param to length in seconds for which connection will continue to be refused (or 0 if indefinite).

Procedure for the silent partner (C)

The silent partner C is sent lockout on and off commands by the conversation partner who issues a type-1 token (B). C should not send format status response to receiving lockout commands.

C should not request an authorisation token with a scope that overlaps any of the locked regions, and might chose to indicate visually to the user that particular region of the document is currently locked. C also need to keep an eye on the lockout lifespans, and should cancel any that expire in the absence of lockout-off command.

Token life span

The lifespan of a token has to be chosen as a compromise between user responsiveness and the lockout of other users. At the not excessive typing speed of 5 characters per second an event is generated every 200ms. The token negotiation requires the minimum of four messages being exchanged, which can conceivably take over 1s to negotiate over a long distance connection.

Error Handling

A and B are communicating Abi processed.

For each message (i.e., the entire <abitalk></abitalk> fragment, not just an individual command) that A receives, it has to dispatch a status command indicating whether the operation succeeded. The only exception to this is a message that contains a single <lockout/> command, which A should process, but not respond to.

If the operation fails at any stage (i.e., return value is other than ABT_Success or ABT_NoCmdHandler), A has to reverse all operations carried out by B using the specific authorisation token. ABT_NoCmdHandler is a special case, discussed below.

For each message that B dispatches, it has to wait for a corresponding status message. If the status received is not ABT_Success or ABT_NoCmdHandler, B's authorisation token is no longer valid and any operations that B might have carried out previously with that token have been undone by A in the target document. B needs to take action appropriate to the status message and, if deemed appropriate, restart the process.

ABT_NoCmdHandler

If A cannot execute a performative cmd because no suitable handler is found, it dispatches status message ABT_NoCmdHandler to B, with param set to the command name, and waits for a response.

When B receives ABT_NoCmdHandler, it has two options, depending on the command involved. It can decide to abort the whole command sequence, in which case it dispatches ABT_Unwind status message back to A, after which the authorisation token is no longer valid; upon receipt of this message A undoes all operations carried out by B using the specified token.

Alternatively, B can respond to ABT_NoCmdHandler by sending ABT_Success status. In that case A will simply ignore the particular command, and proceed with processing the next one.

The response to ABT_NoCmdHandler is context sensitive and can vary in different contexts. Therefore, B's responses to ABT_NoCmdHandler must not be cached.

Example command

A sample command (after the intial hand shake and token retrieval) could look like:

</abitalk>

On receipt of the message, the abitalk protocol handler checks the incoming commands against known handlers. In this case 'insertspan' is not part of the protocol itself, so the handler interrogates it's list of registered handlers; if it finds one for 'insertspan' it passes the command attributes and content to the handler. If it does not find a suitable handler, it sends status message ABT_NoCmdHandler.

Implications for AbiWord

Certain requirements will need to be satisfied in order of collaborative conversation to be possible, so of which emerge from the proposed protocol, and have some implications for the existing AbiWord code base. The following should be noted:

All events persistent

All operations carried out by user will need to be representable by 'change records' (this is a consequence of the GOCollab philosophy); at present there are number of operations that do not fall into this category (this includes changes to style definitions, meta data and other document properties). This will also need to include changes to any application wide preference that affect how the document is perceived by the user.

Local event queue

There has to be a means of temporarily queueing document events on the local level during the token negotiation. This will require significant changes to the PieceTable.

Currently change records are created by the PieceTable and are atomic from the PieceTable point of view (being grouped into user-atomic groups for the purposes of undo). The queueing of document events would require two sets of change records: a first layer representing user-atomic changes would need to be created in the PD_Document functions and then filtered to the PieceTable functions through a single point of PD_Document; the filtering function would handle the queueing and would dispatch the first tier change records to the appropriate PieceTable functions (which then create the second level change records that are stored for undo purposes).

Is it open to consideration which tier of change records should be dispatched through the AbiTalk protocol. Dispatching the first tier change records would mean that fewer messages would be required, with increased processing carried out by all conversation partners. Considering the need to minimise effects of network lag, this might be the preferable option

An alternative solution to the event queue would be to discard any local operations during the token negotiation lockout. This is unlikely to be adequate though in the light of the earlier discussion of token life span.

Document merging

If offline editing is to be an option, the Merge Documents features must be implemented and work reliably.