and undo model (single-step undo, chronological undo and selective undo). The global undo supports to undo any operation
released by all users (including both him/her and other users) while local undo restricts the undo scope of the operations to
those generated at local site. Single-step undo indicates that user can undo and only undo the latest operation released by
the local or another remote user. Chronological undo means that user can undo a sequence operation from the latest to the
oldest sequence. And Selective undo supports any undo at any time.
However, the classification of the above undo modes is related not with the original operations but with the decomposed
ones. For example, in Fig. 3, the intention of the Undo operation is to undo the creation of the two objects, but not the last
created object. This phenomenon occurs because the target operation of the Undo operation is the decomposed operation
but not the original ones. So strategies must be adopted to maintain the relationship between the original ops and the
decomposed ones. Bin [5] extends the Undo object from single character to string. That’s to say, we can undo a set of char-
acters, but not one character at one time. In this work, the operations of Insert or Delete are delayed to be combined as a
string operation and then broadcasted to remote sites. This work style is fit for the mobile environment since the network
bandwidth is limited. However, in order to achieve high concurrency, operations in the ordinary environment should be
broadcasted to remote sites as soon as possible. Cheng et al. [32] employs a complete re-run strategy based on full operation
for 3D collaborative modeling systems. It simply re-executes all the operations from the beginning except the Undo target
and operations depending on it. The complete re-run strategy is simple and its correctness can be guaranteed. However, it
has low efficiency and cannot be adaptive to large-scale design environments. He [27] proposes a group Undo/Redo mech-
anism for 3D collaborative modeling systems to support the ‘‘anytime, anywhere’’ Undo/Redo. It uses an Undo State Vector to
ensure the Undo/Redo intention preservation and model consistency maintenance. However, this work is mainly focused on
the feature modeling operations and the document structure in this work is modeled as Topological Entity Structure Tree
(TEST) which is different from our model at all.
3. The AST strategy and compound operations
3.1. Address space transformation strategy
Address space transformation strategy, proposed by Gu et al. [3], is a consistency maintenance method based on docu-
ment mark and retrace. Different with traditional OT strategy, AST takes the perspective of document status and thinks that
the intention violation of concurrent operations results from different document statuses of the operation execution and the
operation generation. Based on this perspective, AST introduces to retrace the document status to that when the operation is
generated by comparing the timestamp of the operation with those of the operations in the history buffer.
AST is firstly used in the text editor field, aiming to solving consistency maintenance problem of document consisting of
plain characters. It formats the document as a linear structure composed of character nodes, with every node appended to a
history buffer containing the operations that have taken this node as the operation target. Operations in the list are arranged
according to the execution order. The Effective/Ineffective status of the node is determined by comparing the timestamp of
the node with that of the site. In order to adapt AST strategy to collaborative design field, some strategies must be adopted
including address space mapping, etc. Please consult to [11] for more information about this.
The main idea of AST is as follows: (1) Operations released from local site are executed immediately after their releases;
(2) As for a remote operation, before its execution, causality-ready condition will be first examined. If it is not causally-ready,
it will be queued, since some other operations which have been executed in their generation sites have not been executed in
this site. If it is causally-ready, the document status of current site will first be retraced to that when the operation is
generated and then the operation is executed in this retraced document status. After executing the operation, the document
status will be retraced to current status. The readers are recommended to consult to [3] for more description about AST
strategy.
3.2. Compound operations
In this paper, compound operations refer to those original operations which have to be decomposed into one or several
primitive operations before their execution. Based on Multi-Object operations and Reference operations, compound opera-
tions can be classified into MO-SO, SO-RO and MO-RO. Here, definitions of four compound operations are introduced, and
some examples of compound operations including Copy-Paste, Mirror, Array and Extend are also detailed.
Compound Operations: operations that need to be decomposed into primitive operations before execution by the basic
consistency maintenance algorithms such as OT or AST. They either need some steps to be completed, or target multiple
objects at one time.
Copy-Paste: create an object with the same attribute of the reference object, which can be decomposed into one Copy and
several Insert primitive operations.
Mirror: create an object relative to a reference line or plane with the same attribute of the reference object, which can be
decomposed into one Select and several Insert primitive operations.
Array: create several objects at a time, which can be decomposed into one or several Insert primitive operations.
4 L. Gao et al. / Computers and Electrical Engineering xxx (2015) xxx–xxx
Please cite this article in press as: Gao L et al. Consistency maintenance of compound operations in real-time collaborative environments.
Comput Electr Eng (2015), http://dx.doi.org/1 0.1016/j.compeleceng.2015.06.021