Distributed Whiteboard Design

Team: Synchrony or Bust

Overview

Our distributed whiteboard uses a decentralized architecture in which each participant broadcasts its updates to the whiteboard state to all other participants. However, we do appoint an abiter to resolve ambiguities when participants fail, to keep track of a group membership view, and to establish ordering. We believe our design will easily accomodate several users, and that with some simple enhancements could scale far beyond that.

The whiteboard is composed of shapes--ovals, lines, text, and so on. To ensure that a shape is not updated simultaneously by two participants, each shape has an owner. Only the owner can give a shape to someone else (or, if the owner has failed, the arbiter assumes this power). Newly created shapes are owned by their creator. Updating a shape you own is fast; you don't need to get anyone else's approval. If someone else owns it, you will notice a delay as you ask for a transfer of ownership. The update process is described in detail below.

Selection

A shape can be in one of three states: unselected, selection_pending, or selected. A participant can only select shapes it owns, and can only modify selected shapes. When a user selects a foreign shape (i.e. one owned by another user), the shape enters the selection_pending state until ownership is granted. (Ownership will not be granted if another participant has the shape selected.) Visual feedback shows which state shapes are in. For example, we could follow the convention of placing small black rectangles at the corners of the bounding boxes of selected shapes. These rectangles could be filled white while the selection is pending.

The user requests a selection by activating the selection tool and clicking on the shape's outline. Thus, each shape has a method ("intersects") that returns true if a small rectangle around the click-point intersects the shape. The selection algorithm will thus work like this: User clicks on point X. A list of all shapes whose bounding boxes contain point X is made. This list is traversed in reverse-layer order (i.e. with the shape on top first). If the shape intersects the click-point, it is selected, and the algorithm terminates.

A user can select multiple shapes at a time, either by shift-clicking or by dragging a rectangle around a group of shapes. A shape's bounding box must be fully enclosed in this rectangle for it to be selected.

When selections pend, they do not block, so the user can go on selecting additional shapes. Or, the user may abandon a request by selecting another object. (Ownership may still be eventually granted--the shape will just not be selected.)

Updates applied when multiple shapes are selected will apply to all the selected shapes.

Tools

At any given time, one of the following modes will be active:

As with most drawing programs, the user can hold down the shift key to force the horizontal and vertical dimensions of the shape to be equal. The irregular polygon tool creates a connected series of line segments if you click at various points, a closed polygon if the final point is close to the initial, and a "scribble" if the button is held down. A scribble is approximated as sequence of short line segments.

There are also functions to delete, cut, or copy selected shapes.

Shape modification

A user may perform the following actions on an existing shape:

A shape must be selected before it can be modified. If multiple shapes are selected, the modification will be applied to all of them.

Layering

Each shape, regardless of its owner, must have a place in the shape list. The screen is drawn by traversing this shape list, so that the shapes "on top" are drawn last. This will be especially important if we add support for solid (filled) shapes. Moreover, each participant must maintain the same shape ordering, or they will end up with different whiteboards. Our solution for this appears in the "Considerations for Distribution" section below.

Merging

Users may want to combine drawings they did offline. We have a mechanism for copy and paste. The selection list makes this straightforward. We will need to ensure that the copy buffer remains intact when the user loads a new whiteboard or joins a new session.

Foreign pointers

To satisfy the requirement that users see each others' pointers, each participant periodically broadcasts the location of his pointer to all others. Ordering is not important. Participants display these periodic updates and smooth transitions between them.

Considerations for Distribution

The peer-to-peer network we create is fully connected. Whenever a participant changes the state of the whiteboard, it must notify all other participants. The sections below explain how we ensure that each participant maintains an identical view of the whiteboard despite failures and unordered delivery.

New shapes

The user who is creating a new shape must have immediate visual feedback, complete with animation (e.g. as you are drawing a circle, that circle grows as you drag the pointer further from its origin). However, since different participants may create shapes at the same time, they must agree on the order in which these shapes are placed on the shape list. We assign this task to the arbiter, A. When participant P creates shape X, it draws this shape and tentatively appends it to its shape list--say, after shape V (step a in the figure below). Then P asks A which shape X should follow (step b). If A responds with a different shape, W, then P must wait to receive the broadcast of W, and then erase X (saving a bitmap of what was under it), redraw the bitmap, draw W, then draw X (step c). In either case, it broadcasts X along with its layering info (either W or V). Note that W might not be the only new shape that preceedes X.

This has the desirable feature that users can create new shapes without experiencing awkward delays. The most awkward thing that can happen is that another user's shape can suddenly appear "between" two you just drew.

Modified shapes

The concept of ownership makes updates simple. Only the owner of a shape can change it. Each shape has a version number that is incremented whenever the shape is changed. Participants ignore changes with version numbers equal to or less than their current version of the shape. The owner must broadcast changes to all other participants.

Because of layering, it does not matter if participants receive broadcasts in different orders. If you receive a new shape that comes after a shape you haven't received yet, you just wait until you get that shape, then draw them both.

Changing a shape's layer requires special consideration. Since it involves swapping the shape's position in a linked list with that of the shape before or after it, any shape whose next-pointer needs to be changed will need to be owned by the participant requesting the layer change.

Broadcasts

Participants are responsible for broadcasting changes they make, yet we have said nothing of atomic or totally ordered broadcasts. The layering imposed by the arbiter ensures that each participant draws shapes in the same order. The version numbers ensure that participants only display the most recent version of a shape. But what happens if a participant unexpectedly leaves the system? It is clear that we cannot incorporate a new shape right when its creator informs us of it: what if they die before informing everyone?

Here is the key. Arbiters are elected deterministically based on their ID. For a given membership view, everyone knows who will follow the current arbiter (call this arbiter1), who will come next (arbiter2), and so on. The participant A who creates or modifies a shape will broadcast in arbiter-order. The arbiter is then responsible for broadcasting the update if A fails.

(Note that if A fails before notifying the arbiter, all is well, because no one sees the update.) So when A finishes its broadcast of the change, it must broadcast a "done" message, again in arbiter-order, so that the arbiter knows it does not have to rebroadcast this particular update.

If a rebroadcast is necessary, participants may receive duplicate messages. Because of shape versioning, this does not matter.

Joins

Newcomer N can "ring" any participant P. P will answer the connection, send N a copy of the whiteboard, and let N know who the arbiter is so it can request a copy of the membership view. Until N is fully connected, P "adopts" it, forwarding all shape updates. N cannot modify the whiteboard until it becomes fully connected.

A future enhancement might be to make this "adoption" permanent, and route all of N's traffic through P. This could improve performance on a WAN: P would become a sort of gateway that local clients connected to. Thus traffic over the WAN would be minimized.

Disconnections

When a client disconnects cleanly, it will take the following steps:

  1. Transfer arbitership to next-in-line if necessary
  2. Broadcast a "leaving" message (in arbiter-order)
  3. Transfer shape ownerships to arbiter
  4. Close all connections

If the client exits uncleanly, the arbiter must assume ownership of all its orphaned shapes.  When the client reconnects to the meeting, it must flush all of its whiteboard state information and follow the Join procedure described above.

Failure Detection

Failures are detected in the system through the use of heartbeats.  Every participant piggy-backs a heartbeat signal in the Pointer location message. In the case where a participant is idle, an explicit heartbeat is sent to the other members.  Heartbeats are expected to be send every period (the amount of time will be determined in practice). A failure occurs if a heartbeat is not received from a participant for 3 consecutive periods.  Accurate and Complete failures are assumed and supported (If a participant goes down, every other participant will recognize that the node is down).

Leader Election

The non-failed participant with the lowest ID is always wins the arbiter election. The arbiter sends periodic heartbeat messages to other participants. When these messages stop, the next in line assumes the responsibility. Becoming the arbiter involves

  1. Assuming ownership of shapes owned by the previous arbiter
  2. Establishing your membership view as the current view
  3. Broadcasting the fact that you are the new arbiter
  4. Continuing any uncompleted shape-update broadcasts

Design

Class: Whiteboard

Responsibilities:

Collaborators:

Class: Shape

Responsibilities:

Collaborators:

Class: Listener

Responsibilities:

Collaborators:

Class: Communicator

Responsibilities:

Collaborators:

Class: Arbiter

Responsibilities:

Collaborators:

Class: View

Responsibilities:

Collaborators:

Class: Message

Responsibilities (serialized messages to represent):

Collaborators: