Team: Synchrony or Bust
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
A shape can be in one of three states: 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.
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.
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.
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
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.
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.
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.
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.
When a client disconnects cleanly, it will take the following steps:
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. 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). 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
Class: Whiteboard
Responsibilities:
Class: Shape
Responsibilities:
Class: Listener
Responsibilities:
Class: Communicator
Responsibilities:
Class: Arbiter
Responsibilities:
Class: View
Responsibilities:
Class: Message
Responsibilities (serialized messages to represent):
Tools
Shape modification
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
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.
Modified shapes
Broadcasts
Joins
Disconnections
Failure Detection
Leader Election
Design
Collaborators:
Collaborators:
Collaborators:
Collaborators:
Collaborators:
Collaborators:
Collaborators: