A LibreSource Synchronizer Q is composed by:

• a queue of operations. Operations are ordered by timestamps. An operation is addblock, mkdir, createnode etc...
• the last timestamp (lastTicket). lastTicket is the last timestamp delivered by Q.
• a publish(op) method. Operation op receive a new timestamp and is stored in Q.

int publish(Operation op) {
  lastTicket++
  Q[lastTicket]=op
  return lastTicket
}

• a retreive method : retreive(ticket). return the operation with timestamp=ticket

Operation retreive(int ticket) {
  return Q[ticket]
}

A workspace W can be connected to one or more LibreSource Synchronizer. A workspace contains a state currentState representing files user is working on.

For each connection C, a Workspace is defined by:

• a timestamp siteTicket. siteTicket is the last timestamp integrated on C.
• a log Hg. Hg is the log of operation integrated on C.
• a state referenceState. It allows LibreSource Synchronizer to detect changes made by users by diffing currentState and referenceState. referenceState is built by applying all integrated operation of C (Hg) on an empty initial state.
• a computeDifference(state1,state2) method. This method returns the sequence of operations that generates state2 starting from state1. In order to compute these differences between two text files, we use an implementation of Diff algorithm (MM85, Mye86). For XML documents, we use an implementation of XyDiff algorithm (CAM02).
• a commit() method. This method publishs local operations to the queue on the server.

void commit() {
  if(queue.lastTicket > siteTicket) {
    abort "must be up-to-date in order to commit"
  }
  Operation[] locals = computeDifference(referenceState, currentState)
  for(int i=0; i<locals.length; i++) {
    int ticket = queue.publish(locals[i])
    execute(locals[i], referenceState)
    Hg[ticket] = locals[i]
  }
  siteTicket = queue.lastTicket
}

This method starts with a check of the connection status (it must have integrated all available published operations that have been previously published on the server queue). Then, the method calculates the sequence of locals operations generated by the user (which has not been published yet). Each operation is sent in order to be timestamped, and then executed on the reference state. Finally, this operation is appended to the history Hg according to the timestamps order.

• an update() method. This method updates the local copy in retrieving operations that were already published in the queue.

void update() {
  Operation[] remotes
  int i=0
  while(siteTicket < queue.lastTicket) {
    siteTicket++
    i++
    remotes[i] = queue.retrieve(siteTicket)
  }
  Operations[] locals = computeDifference(referenceState, currentState)
  merge(remotes, locals)
}

This method retrieves all available operations on the queue (those which have not been integrated yet). Then, the method computes the sequence of locals operations. As, these two sequences are concurrent, they must be merged.

• a merge(Operation[], Operation[]) method. This method merges two sequences of concurrent operations.

void merge(Operation[] remote, Operation[] locals) {
  for(int i=0; i<remotes.length, i++) {
    Operation opr = remotes[i]
    int ticket = remotes[i].ticket
    for(int j=0; j<locals.length; j++) {
      Operation opl = locals[j]
      local[j] = T(opl, opr)
      opr = T(opr, opl)
    }
    execute(remote[i], referenceState)
    Hg[ticket] = remotes[i]
    execute(opr, currentState)
    siteTicket = ticket
  }
}

This method relies on the SOCT4 integration principle. Each operation remotes[i], that must be integrated, is transformed according to the sequence of locals operations to a new operation called opr. Consequently, this operation can be executed on the current state user is working on. The non transformed operation remote[i] is added to the history Hg. Then, this operation is executed on referenceState in order to maintain consistency between this state and the history.