DistribuTech WhiteBoard v0.7

1.  Networking

1.1  The Basics

The basic semantics of our connection protocol is as follows:

 

1.2  Messages

Key:
OpUniqueID:  A unique ID created by a member process before it sends a message
MemberID:  A identifier that uniquely describes a member
Timestamp or TS:  An identifier created by the leader to impose total order
Shape:  An object representing a graphical entity

Message:  PleaseDraw (OpUniqueID, Shape)
Member -> Leader
Submit a draw request to the leader.

Message:  DoDraw (MemberID, OpUniqueID, Shape, Message_TS)
Leader -> Member
Disseminate draw order to members.  MemberID and OpUniqueID are provided so that shape originator may clean up in-flight list.  Message timestamp becomes the timestamp of the shape so that the shapes are ordered.

Message:  PleaseModify (OpUniqueID, Shape_TS, Shape)
Member -> Leader
Submit a modify request to the leader.  Shape is uniquely identified by its associated timestamp.

Message:  DoModify (MemberID, OpUniqueID, Shape_TS, Shape, Message_TS)
Leader -> Member
Disseminate modify order to members.  MemberID and OpUniqueID are provided so that shape originator may clean up in-flight list.  Shape timestamp identifies the shape, while message timestamp orders the message.

Message:  PleaseDelete (Shape_TS, OpUniqueID)
Member -> Leader
Submit a shape delete request to the leader.  Shape is uniquely identifies by its associated timestamp.

Message:  DoDelete (MemberID, OpUniqueID, Shape_TS, Message_TS)
Leader -> Member
Disseminate delete order to members.  MemberID and OpUniqueID are provided so that shape originator may clean up in-flight list.  Shape timestamp identifies the shape, while message timestamp orders the message.

Message:  SceneUpdate (<[MemberID,ObjectUniqueID, Shape, Message_TS]>, Message_TS)
Leader -> Member
Disseminates the entire current scene to a member.  The bracket notation indicates a list of arbitrary size.

Message:  Request (Function, OpUniqueID)
Member -> Leader
Request a function be performed, such as image compression.

Message:  Check (Function, Message_TS)
Leader -> Member
Poll all members, ask users (or members without user interaction) if the function should be performed.

Message:  Response (Message_TS, bool)
Member -> Leader
A response to a poll from a member.  The message timestamp corresponds with that of the Check message, and the Boolean value indicates the response.

Message:  Confirm (MemberID, OpUniqueID, Message_TS, bool, Confirm_TS)
Leader -> Member
Disseminate poll results to members to commit or abort action.  Message timestamp corresponds with that of the Check message, and Confirm timestamp orders message against others.

Message:  AreYouLeader (MemberID)
Used to attempt to join group if not in the group.  If in the group, used to ask if leader is still alive or request group view update.

Message:  IAmLeader (MemberList)
Reply to an AreYouLeader.  Also a mechanism for group membership update from leader to members.

Message:  IMightBeLeader (MemberList)
Reply to an AreYouLeader.  Given to disseminate membership list to a potential new member and to block while the member verifies that the leader is alive.

Message:  IAmNotLeader (MemberList)
Sent from group member to a potential new member.  Sends current group view, leader first in the list, and requests a redirect.

Message:  GoneAway (MemberID)
Sent when a member gracefully exits the group.

 

1.3  Functions

Our protocol offers the capability to perform functions that require a consensus of members, either with or without human intervention.  The consensus is gathered using a process similar to two-phase commit.  The function that we have in mind currently is this:

Function:  Collapse (Shape_TS)
This function, if committed, would combine all shapes and the background image into a single image.  This function potentially saves space and can act as garbage collection.  The argument offers the capability of only collapsing shapes up to a particular timestamp and leaving the rest as mobile.

This mechanism offers the capacity to add any function that requires consensus.  For instance, it may become necessary to gain a consensus that a member is serving inadequately as a leader -- a vote of no confidence, for instance, based on slow network traffic.

 

1.4  CRC's for Networking Objects

Class:  Leader

Responsibilities:

Collaborators:

Class:  Member

Responsibilities:

Collaborators:

Class:  Listener

Responsibilities:

Collaborators:

2.  Networking Use Cases

2.1  Use case 1

Goal: A new group is started when B joins A.

Entry criteria: A and B are each in groups of one.

  1. B sends an AYL message to A.

  2. A responds with an IML to B.

  3. A checks its members list to see who the current leader is. A will be the current leader.

  4. A sends a scene update to B.

  5. A adds B to the members list and sends a IAL message to B.

  6. A broadcasts an IAL message.

2.2  Use case 2

Goal: A new member C joins an existing group, via the non-leader member B.

Entry criteria: A and B are in a group, and A is the leader.

  1. C sends an AYL message to B.

  2. B responds with a IML to C. The IML is a courtesy response. It also provides with a membership list to start with, in case B fails before the use case completes. C could use the members list to contact other members.

  3. B checks its members list to see who the current leader is. A will be the current leader.

  4. B sends an AYL message to A.

  5. A checks its members list to see who the current leader is. A will be the current leader.

  6. A sends an IAL message to B.

  7. B sends an INL message to C.

  8. C contacts A and joins the group as in Use case 1.

2.3  Use case 3

Goal: A non-leader member C wants to draws a new object. (Nominal)

Entry criteria: A, B, C and D are in a group (in that order), and A is the leader.

  1. C creates a PLS Draw message and adds it to its in-flight list.

  2. C sends a PLS Draw message to A.

  3. A sends a Do Draw message to all members of the group, except C. The message is sent in the membership order. That is, message is sent to self, B, and D.

  4. A sends Do Draw message to C.

  5. C removes the PLS Draw message from the in-flight list.

Note: Members process messages in the order the leader sends them out.

2.4  Use case 4

Goal: A non-leader member D fails.

Entry criteria: A, B, C and D are in a group (in that order), and A is the leader.

  1. D fails, perhaps due to application fault or network fault.

  2. A detects D’s failure via lost TCP connection.

  3. A removes D from members list.

  4. A sends IAL message to all members.

2.5  Use case 5

Goal: The leader A fails.

Entry criteria: A, B, C and D are in a group (in that order), and A is the leader. C has sent a message to A, and A has sent it to only D.

  1. A fails, perhaps due to application fault or network fault.

  2. C detects A’s failure via lost TCP connection.

  3. C checks its members list to see who the next leader should be. B will be the first candidate.

  4. C sends an AYL message to B.

  5. If B has not yet detected A’s failure
    B checks its members list to see who the current leader is. A will be the current leader.
    B sends an AYL message to A.
    B detects A’s failure.

  6. B checks its members list to see who the next leader should be. B will be the first candidate.

  7.  B sends an IAL message to C.

  8. B sends a scene update to C.

  9. B broadcasts an IAL message.

  10. C sends the message it had sent to A, but this time to B.

  11. D joins B similarly when it discovers A’s failure (steps 2-9).

  12. B sends the Do message to self and D.

  13. B sends the Do message to C.

2.6  Use case 6

Goal:  A Successful rejoin by C after loosing Network connectivity from the rest of the group

Entry Criteria: C looses contact with the rest of the group. C is not the leader.

  1. A is the leader.
  2. C looses Network connectivity to A.
  3. C figures A is dead – tries B (the next on the list and “Leader Pro-tem”with “Are you leader?”
  4. B checks with A – A is still leader.
  5. B tells C  that A is the leader, and to try to connect with A.
  6. C tries to connect to A. C retries up to a fixed number of times determined by implementation
  7.  If C gets through, A updates C with the current membership
  8. A sends a Scene update to A.
  9. Since A hasn’t crashed, it compares the object Id’s received in the scene update to those it has on it’s “In Flight” list. Those received are deleted, those not received are then resent.
  10.  If C has crashed instead of just lost network connectivity, then all “In flight” information is lost, and C accepts the scene update from A.

2.7  Use Case 7

Goal: Members agree to collapse the current drawing to a single background image.

Entry Criteria: One user decides to request a collapse

  1. One member requests a collapse, and at what point in the sequence the collapse should occur The user may request it, or it may automatically happen in some way – although this causes problems from the users.
  2. Leader performs a basic 2 phase commit.
  3. Leader sends first phase of commit (request). All member must  respond, ack or nak.
  4. If there is consensus to proceed, Send commit message.
  5. Collapse happens. Messages sent during this process are still appended to the draw list – collapse happens from a specific defined point.
  6. If you’ re unreachable, you don’t get a vote.
  7. If someone joins in the middle, they are given the message and the leader blocks until they “Catch up”.
  8. If the leader dies before the final step, a new leader is chosen, and the new leader retries transaction if requested.

3.  Data Structures

Each member maintains three key data structures: Members, In-flight, and Scene.

 

3.1  Members

Members is a list of group members arranged in the leadership succession order. The current leader is always at the head of the list. Members receive a copy of the list from other members, but only the leader updates (add or delete) the list. The leader timestamps the list, so other members can determine the freshness of their copy.

At startup, each member is in a group with itself as the leader. Hence the member creates a list with just self in it. When it attempts to join a group (successfully or not), the member receives a members list from the member it contacts. The list is current and binding only if the leader sent it, otherwise the list is only suggestive. A member receives a suggestive list with the IML and INL responses from other members.

The list—suggestive or definitive—received on the first attempt to join a group is implicitly the latest. The list received from the leader at any time should be absolutely the latest. In all other cases, a member determines a list’s freshness from the list’s timestamp, and replaces its list if the list received is fresher.

The leader adds a new entry to the members list before it sends an IYL message in response to an AYL message. The AYL message will contain the new member. The position of the new member depends on the position of the member in the leadership succession order. The leadership succession order is simply the order in which members join a group. This policy works well because a group is a network of peers, but other algorithms could be used to determine succession order.

The leader removes a member from the members list when it receives a GAW message from that member. It also removes a member from the list when it determines that a member is no longer in the network.

The leader timestamps the members list and broadcasts an IAL message whenever the membership changes.

Possible failure detection opportunity: A member receives an IAL message, but the members list it receives is older than its list.

 

3.2  In-flight

In-flight is a list of drawing events generated at the member and sent out to the leader for broadcasting to other members. Ordering of this list is immaterial. Drawing objects in this list are likely already displayed on the local view of the whiteboard, albeit marked temporary. The member deletes an in-flight object when it receives that object from the leader in a Draw message.

A member does not change the in-flight list in response to any other message.

 

3.3  Scene 

Scene is a list of drawing objects arranged in the order received from the leadership. The objects may be applied in order to a base image to create the current scene. All members are obliged to maintain the order of the list and update the view when a new object is received.

The scene is updated in response to one of following messages: Draw, Delete, Scene Update, and Collapse. When a member receives a Draw message from the leader, it first adds the accompanying object to the scene. If the object received originated locally, it removes that object from the in-flight list and makes the view of that object permanent. If the object originated elsewhere, it draws the object and marks it permanent.

When a member receives a Delete message from the leader, it deletes the object indicated from the scene. It then erases the object from the view.

When a member receives a scene update message from the leader, it replaces the scene with the scene just received, paints the base image, and applies all objects in the new scene.

When a member receives a collapse message from the leader, it does everything it does in response to a scene update. It then also makes the current view the base image. The collapse operation can easily be treated as a part of a checkpoint operation.

Note: The system does not define a specific collapse message. Instead, the collapse operation is implemented using a Two-Phase Commit protocol. A member asks for a collapse operation in a Request message. The leader requests a collapse operation in a Check message, and broadcasts the current scene when no member has denied that request.

4.  Graphics Basics and CRC's

Most of the specifics of how graphics will be treated will be dealt with after encountering the standards committee.  What we have right now is as follows.

 

4.1  The Basics

  1. The whiteboard is merely a graphical representation of a list of shapes
  2. The list of shapes should be the same on all members because of the ordering protocol
  3. There is a toolbox from which the user may select a graphical object to place on the screen
  4. Graphical objects (shapes) are placed with two clicks to indicate two corners of the object in space
  5. Shapes, when placed, modified or deleted, are placed in the in-flight list until a DO message is received by the leader
  6. All shape placement is instantaneous to the member that places it
  7. The pointer is represented as a shape that is modified periodically
  8. A whiteboard state can be saved to or loaded from a file

 

4.2  CRC's

Class: Shape

Responsibilities:

Collaborators:

Class: ImageCollapse

Responsibilities:

Collaborators:

Class: FileInterface

Responsibilities:

Collaborators:

Class: DisplayEngine

Responsibilities:

Collaborators:

Class: Display

Responsibilities:

Collaborators: