Efficient Operation Of Conversion Consistency Maintenance Method Of Research

Operational Transformation (OT) is an advanced consistency maintenance tech-nology for many distributed collaborative applications, and data consistency mainte-nance is the fundamental research issue in collaborative computing. Compared with the traditional consistency control techniques, such as operation serialization and two-phase locking (2PL), OT makes it possible to perform real-time communication and collaboration even on the wide-area network with high communication latency. With the rapid development of Internet and the proliferation of mobile devices, a large num-ber of new collaborative applications are emerging. However, the algorithm features and performance of existing OT technology cannot meet the consistency maintenance requirements in these emerging collaborative applications. Hence, how to extend and optimize the existing OT technology to meet these evolving requirements are the fron-tiers of OT research.Based on the recent research results of operational transformation, this disserta-tion makes the following four major contributions to reflect the new requirements of collaborative applications:1. A string-wise transformation algorithm ABTS with formal proof and its opti-mized version ABTSO are proposed. ABTS can handle the complicated cascading splits of operations. Based on ABTS, ABTSO optimizes the time complexity of handling string-wise operations. The analysis and experiment evaluation suggest that ABTSO surpasses the state-of-the-art OT algorithm in both network bandwidth usage and the computational resource consumption.2. An efficient sequence transformation algorithm ABST that can support mobile asynchronous collaboration is proposed. The mobile devices generally have limited processing power and a large number of operations may accumulate on mobile devices in the mobile environment. To reflect these characteristics of mobile collaboration, ABST is designed to efficiently handle long sequences that consist of a large number of offline operations. It improves the time complexity of the state-of-the-art from cubic to linear. Compared with the state-of-the-art algorithm, ABST improves the performance thousands times based on the experimental data on a mobile device.3. Based on the sequence transformation, a synchronization protocol for the emerg-ing real-time web collaboration is proposed. Combined the standard Web communica- tion architecture with the real-time collaboration requirements, TIPS unifies the concur-rency control, consistency maintenance and data synchronization into one framework. Compared with other operational transformation algorithms, TIPS can support large-scale dynamic web-based collaborative applications without the overheads associated with vector timestamps.4. A selective undo framework named ERU is proposed. It allows users to undo any operation in the history. ERU supports full-featured selective undo in the collab-orative environment. Its correctness has been formally proved, and the known undo puzzles are well solved in ERU. Compared with the high time complexity of handling undo operation in existing OT algorithms, the time complexity of handling both do and undo in ERU is linear.