7th International Conference on Collaborative Computing: Networking, Applications and Worksharing

Research Article

Constant-Time Operation Transformation and Integration for Collaborative Editing

Download208 downloads
  • @INPROCEEDINGS{10.4108/icst.collaboratecom.2011.247090,
        author={Weihai Yu},
        title={Constant-Time Operation Transformation and Integration for Collaborative Editing},
        proceedings={7th International Conference on Collaborative Computing: Networking, Applications and Worksharing},
        publisher={IEEE},
        proceedings_a={COLLABORATECOM},
        year={2012},
        month={4},
        keywords={group editor operational transformation concurrency control performance admissibility preservation},
        doi={10.4108/icst.collaboratecom.2011.247090}
    }
    
  • Weihai Yu
    Year: 2012
    Constant-Time Operation Transformation and Integration for Collaborative Editing
    COLLABORATECOM
    ICST
    DOI: 10.4108/icst.collaboratecom.2011.247090
Weihai Yu1,*
  • 1: University of Tromsø
*Contact email: weihai@cs.uit.no

Abstract

Operational transformation (OT) is the concurrency control mechanism for collaborative editors, due to its high responsiveness to local editing operations. However, collaborative editing is still not widely practiced. One of the reasons is that operation transformation and integration are computation intensive and time consuming. The state-of-the-art time complexity is currently O(|H|), where |H| is the length of operation histories, which can be large and grow indefinitely. Moreover, most of the published work is limited with character operations, leading to long operation histories and impractically large number of small messages over the network. This paper presents an approach that supports string operations and constant-time operation transformation and integration. The approach is based on admissibility preservation, a correctness criterion with which the correctness of the approach can be formally proven.