Chinese Journal of Computers   Full Text
Title	A New Multiple Versions Incremental Creation Algorithm
Authors	YANG Jun DOU Wan-Feng
Address	(College of Mathematics and Computer Science, Nanjing Normal University, Nanjing 210097) (Key Laboratory of Virtual Geographic Environment, Nanjing Normal University, Nanjing 210097)
Year	2008
Issue	No.4(702—710)
Abstract &   Background	Abstract The multi-versioning technique based on object replication strategy can meet consistency model while the conflict operations occur in the cooperative graphics editing systems(CGES)，but it does not efficiently solve conflict between non-geometry attribute operations and complex graphics objects. A new distributed multi-versioning model based on version replication is proposed for consistency maintenance of discordant conflicting operations according to the conflicting features and types of concurrent operations in CGES. To guarantee intention of conflicting operations, leaf-versions must be replicated from the original version based on the reduce strategy, and then applying conflicting operations to the corresponding object of the different replicated versions. The leaf-versions can be created by MOVIC algorithm in which the comparison-number of compatible operations is too much. A Fast Multiple Versions Incremental Creation (FMVIC) algorithm based on the compatible and conflict group is presented in this paper. The final versions constructed by the FMVIC algorithm is the same as that constructed by the MOVIC algorithm, but it can decrease the comparison-number of compatible operations and narrow the scope of comparison operations for the removing redundant versions. keywords cooperative graphics editing； concurrency control； version replication； consistency model； compatible and conflict groups background Real-time collaborative graphics editing systems allow a group of users to view and edit the same graphics document at the same time from geographically dispersed sites connected via the Internet. To interact freely and naturally, the collaborative graphics editing systems should meet the following requirements: Interactive in real-time, collaborative distribution and non-restriction in operations. Consistency maintenance in the face of concurrent access to shared objects is one of the core issues in the design of these types of systems. It seems that the only way is to adopt a replicated architecture for the storage of shared documents. To support concurrent editing in the replicated architecture, consistency maintenance is one of the core issues. There are four strategies to solve conflicts among operations, lock mechanism, serialization, dOPT and object replication. The multi-versioning technique based on object replication strategy can meet consistency model while the conflict operations occur in the cooperative graphics editing systems(CGES)，but it does not efficiently solve conflict between non-geometry attribute operations and complex graphics objects. A new distributed multi-versioning model based on version replication and reduce strategy are proposed to guarantee intention of conflicting operations. Based on MOVIC algorithm, a Fast Multiple Versions Incremental Creation (FMVIC) algorithm based on the compatible and conflict group is presented in this paper. The final versions constructed by the FMVIC algorithm is the same as that constructed by the MOVIC algorithm, but it can decrease the comparison-number of compatible operations and narrow the scope of comparison operations for the removing redundant versions. The research work is supported by the Natural Science Foundation for Higher School of Jiangsu Province of China under grant No.07KJD520112. The project is aimed at related techniques in real-time collaborative editing systems. The research team has gained a fruitful achievement in some related areas, such as collaboration transparency, heterogeneous synchronized collaborative design. In consistency maintenance area, they have proposed a cooperative multi-versioning approach, developed different strategies and researched the object identification scheme on the multiple object versions. The work in this paper focuses on a new strategy about the version replication and improving efficiency of distributed algorithm for incremental creation of multiple versions.