An Operational Transformation Algorithm and Performance Evaluation

Abstract

Operational transformation (OT) is an optimistic concurrency control method that has been well established in realtime group editors and has drawn significant research attention in the past decade. It is generally believed that the use of OT automatically achieves high local responsiveness in group editors. However, no performance study has been reported previously on OT algorithms to the best of our knowledge. This paper extends a recent OT algorithm and studies its performance. By theoretical analyses and performance experiments, this paper proves that the worst-case execution time of OT only appears in rare cases, and shows that local responsiveness of OT-based group editors in fact depends on a number of factors such as the size of the operation log. The paper also reveals that these two results have general implications on OT algorithms and hence the design of OT-based group editors must pay attention to performance issues.