Design Document

Inkboard

Steven Montgomery & Matt Weinstock

October 31, 2004

Function

This project is an extension of the open-source, scalable vector drawing program called Inkscape. As such, all original functionality of Inkscape will be preserved. Inkscape is based on the W3C's XML based vector graphics format SVG and Inkscape documents are XML, SVG, and CSS2 compliant. For this project, all enhancements will be based on the latest Inkscape stable build at project start, which is v0.39.

The goal of the Inkboard project is to add functionality for a shared whiteboard to Inkscape. This will allow for communication between different instances of Inkscape through the XMPP protocol used by Jabber instant messaging servers. Inkboard will keep all instances of a shared document concurrent between all connected users of the Inkboard. In Inkscape, changes made in the GUI modify the underlying XML document. For Inkboard, a change to the document must also trigger a message to the other users viewing the shared document. Likewise, Inkboard must accept and interpret messages sent by other users through Jabber and modify the local copy of the shared document accordingly. These Inkboard messages will be sent through a Jabber server. As such, the messages must conform to the XMPP and Jabber protocol. Any changes in the protocol will be client-side.

There are currently several possible options for keeping the document synchronized for all users connected to the Inkboard.
The first methodology is a nominal host setup:

Each user is assigned a “host order number” upon connecting to a shared document. One user’s application is the “nominal host”, and decides the order in which changes will be made to the document based on the order in which it receives messages. All change messages are sent to all instances of Inkscape connected to the document, and each message is given an ID that is unique when considered in combination with the sender (ex: Message 3 from User 5 can be differentiated from Message 3 from User 2). No instance sharing the document implements any change until instructed to do so by the nominal host. After a time-out period, yet to be determined, the host would send an “order message” that identifies the messages the host has received and the order in which they are to be implemented. The non-host instances, then implement the changes in that order. If the host ceases sharing the document, then the instance with the lowest “host order number” becomes the new nominal host. New users beginning to share the document would receive the document from the nominal host (or possibly be directed to request it from another sharing instance by the host).
The second possible methodology is a random back-off(Aloha) solution:
Every user keeps a copy of the shared document in its current state, implementing changes when they are received from other users. Each time a change to the document is sent by any user, it is given a universal identifying number that is incremented for each change. After a user sends a change message, a fixed time is given for detecting conflicts with the message. If the user receives a new message with the same ID number, the sender will recognize the collision. If a collision is detected, all users involved in the collision (those who both sent and received a message involved in the collision) will send a jam message to all other users, informing them of the collision state. All instances of the application involved in the collision will then engage in “random back-off” behavior, each waiting a random time before attempting to send their change. Because each user is implementing changes in the order they are received(which is not guaranteed to be the order in which they were sent), there must be a mechanism to undo some changes and redo them in a different order. When a new user begins to share the document, his or her instance of Inkscape would accept the current version of the document from the first responder, saving all change messages until the document is ready. The user would also receive the current universal change number from the responder.
The third possible methodology is a hybrid of the two mentioned above:
As always, each change made is sent to all connected users. Like the random back-off setup, users implement changes as they are received. If a collision is detected, either by the host or one of the senders, the host chooses an arbitrary order and sends an order message to all connected users. Like in random back-off, a mechanism for undoing changes is needed.
The fourth possible methodology is a wholly different approach in which, rather than avoid conflicts, each client simply resolves them locally. The client side resolution system:
Like in the previous setups, every user is assigned an ID number based on the order in which they joined the session. A new user would receive a list of IDs along with the document when they first connect and would be assigned the next sequential ID. All users tag their changes with a universal identifying number as in the random back-off setup and receiving users implement changes as they are received. If a user receives a message with a duplicate universal identifying number, the user simply re-executes the changes in the order determined by the user ID numbers assigned upon joining the Inkboard. A queue of old changes would have to be kept by every user to allow this to happen. In addition, each change must be an absolute change, such that the starting state of the object is not needed to determine the new state. In the methodology, the user would only need to re-execute changes that occurred on the same object.

The sharing of a document will be accessed and controlled through drop-down menus. Jabber login will be in a dialog box. Document accept messages will be popup windows. Information relating to the connection and changes made will be displayed in the status bar.

Form

In order to send messages over the XMPP protocol, a new namespace will need to be devised. It must contain tags for all possible changes that can be made to an Inkscape document. At this point in time, the exact namespace for messages to be sent over Jabber is undetermined.

Connection Class

Change Class

Class Diagram

Economy

As an open-source project, the finished project and source code will be available for anyone to download and modify as they wish. Also, because this is an open-source project, the client has asked for several releases to be made available on SourceForge.net. These source code releases will be available for free to anyone wishing to download and try out the project.

Time

The project will be completed in three quarters and should be completely handed off to the client by May 15, 2005. The project will be treated as a branch of the open-source project Inkscape. The client will phase in any features we develop when he wishes.

To Do List

#

Who

Due

What

1

12/05/2004

Steven Montgomery
Matt Weinstock

Decide on which methodology to use for conflict resolution

2

12/17/2004

Steven Montgomery
Matt Weinstock

Increment form as we implement class structure

Revision History

Date

Who

Revision

10/31/2004

Steven Montgomery
Matt Weinstock

Document creation

11/11/2004

Steven Montgomery

Added preliminary design of class structure

11/13/2004

Steven Montgomery

Added class diagram