The SharedDocument class, adapted from Bo's JAMM implementation and used for synchronous text editing in various bridge-based components, relies on a vector clock implementation to track which clients have seen which messages.

The vector clock mechanism needs to be able to generate an array of integer timestamps, one per client, which can be compared to see if two messages generated by different clients have a defined order or were concurrent. These timestamp arrays need to have the same relative order on all clients, which presents a problem for a replicated system like CORK.

Our current (020725) scheme, there is significant opportunity for a race condition. When the document listener detects an attempt to edit the document locally:
  1. The list of clients in the global clock is retrieved
  2. If none of the clients are active, the clock is cleared and the client claims index 1 (index 0 is reserved for the server)
  3. If at least one other client is active, the client claims a new index at the end of the list, expanding the list by 1
  4. An AddParticipant message containing the client id and claimed index is generated and sent to the other clients

Having the clients determine their own indexes in problematic, since two could claim the same index fairly easily. Possible solutions to this include:
  1. Maintain per-client orderings. Each client would have to know what every other client thought the ordering was, and translate timestamp orders as needed. The approach preserves the almost fully decentralized model, but will likely impose significant overhead.
  2. Move index determination to the server. The AddParticipantChange could contain the client id of the requesting client and possibly a list of known "dead" clients, but would not contain a requested index. When this change is first applied, an index will be determined and assigned. The Change will then be re-broadcast to all clients, ensuring that everybody assigns the same index.
  3. Assign an index when the object is retrieved.

Option (2) is likely to be significantly more efficient than option (1), but the timing of the AddParticipant operation is still a little tricky:
  • Adding the participant when the listener is first attached is wasteful, and also presents problems if the document is not editable but becomes editable at a later time.
  • Adding the participant on the first edit and blocking until the index is assigned could be problematic in the case where the user does not actually have permission to add themselves, since no reply will be generated. While we can check for this case prior to generating the AddParticipant message, the opportunity for a race condition still exists.
  • Sending the AddParticipant message and then marking the GlobalClock as "index pending" until the reply is recieved is probably the safest (but most complex) approach. Any edits generated before the reply is recieved would have to be saved and broadcast on index assignment.


NOTE: This type of Change behavior (where behavior changes based on server-side vs client-side execution) may be problematic if/when we move to a federated server scheme, unless changes are first sent to the master server and then re-distributed on reply. The current scheme of simply saving a flag indicating that the change has been applied once may need to be replaced with a more general mechanism that provides details about the context in which the change is being applied. (e.g., remote client, originating client, cache server, master server)

Changes introduced in October 2002 take avantage of the fact that (in the current shared editor implementation) we never need to generate a fully ordered list of events. The cork.util.VectorClock maintains parallel lists of client ids and counters, along with methods for looking up the counter for a given id. Clients send an AddParticipant message on the first edit, which also includes a list of dead paraticipants.

/public/projects/bridge/design/Vector clock management Login | Web Editor | Full Editor
Last modified 9/11/03 1:58 PM by isenhour (history)
Site contents