Optimistic and Efficient Concurrency Control for Asynchronous Collaborative Systems

Concurrency control is a key issue in distributed systems. A number of techniques have been devised to tackle the issue, but these techniques are generally unsuitable to be used in collaborative systems, which have the special requirements of consistency maintenance, responsiveness, and unconstrained interaction. OT (Operational Transformation) is an optimistic concurrency control technique originally invented for synchronous collaborative systems to meet these requirements. But existing transformation control algorithms are inefficient to be used in asynchronous systems. In this paper, we present an OT-based concurrency control solution for asynchronous collaborative systems, including an efficient contextualization-based transformation control algorithm underpinned by operation propagation and replaying protocols to achieve contextualization. The solution has been formally verified in terms of consistency maintenance and demonstrated by a variety of prototype collaborative applications.