Design and implementation of software tools for property verification in operational transformation

• Main Author: Luo, Jianlin
• Other Authors: Sun Chengzheng
• Format: Final Year Project
• Language: English
• Published: 2014
• Subjects: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: http://hdl.handle.net/10356/59249
• Institution: Nanyang Technological University

Operational Transformation (OT) as a real-time collaborative computing technology has been extensively studied over the past two decades. One of the aspects that has not been fully explored is the correctness of those OT systems whose operation model consists of string-wise primitive operations. To detect and resolve puzzles – subtle and characteristic collaborative editing scenarios in which an OT system may fail, in this project we devised a verification system that can independently and exhaustively cover all possible transformation cases in which puzzles may exist. This particular software tool will also be able to verify the soundness of customized string-wise transformation functions. This report will present the design and development of the integrated verification software tool to verify Union-Effect Convergence Property 1 (CP1), Convergence Property 2 (CP2), Inverse Property 2 (IP2) and Inverse Property 3 (IP3) for string-wise operational model. It will also discuss the intricate issues faced in the development process and the algorithms implemented to tackle them. Lastly, this report will also present the experiments conducted using this integrated verification tool, particularly the compliance of attempted customized transformation matrices with the listed transformation properties. The verification results are listed and analyzed.