Operational transformation for orthogonal conflict resolution in real-time collaborative 2D editing systems

• Main Authors: Sun, Chengzheng, Wen, Hongkai, Fan, Hongfei
• Other Authors: School of Computer Engineering
• Format: Conference or Workshop Item
• Language: English
• Published: 2013
• Online Access: https://hdl.handle.net/10356/99008; http://hdl.handle.net/10220/12603
• Institution: Nanyang Technological University

Operational Transformation (OT) is commonly used for conflict resolution in real-time collaborative applications, but none of existing OT techniques is able to solve a special type of conflict - orthogonal conflict, which may occur when concurrent operations are inserting/deleting an arbitrary number of objects in different dimensions of a two-dimensional (2D) workspace, such as spreadsheet documents. This paper is the first to identify and solve the orthogonal conflict problem by extending OT with a new capability of resolving 2D conflicts. Extending OT from one- to two-dimensional conflict resolution is fundamental to the theory and application of OT, and technically challenging as well because 2D orthogonal conflict is different from but intimately related to the one-dimensional positional shifting conflict and necessitates new and integral solutions for multi-dimensional conflicts. In this paper, we present formal definitions of orthogonal conflict, pseudo-code description, design rationale analysis, and correctness verification and complexity analysis of the 2DOT solution.