ctre: cutting the Gordian knot of OT complexity

Presenter: Victor Grishchenko, postdoc at TU Delft

Abstract. Operational Transformation (OT) is the theory behind Google Wave and Docs; it has a history of more than 20 years. In particular, that means the theory is based on assumptions 20 years old. Revision of those assumptions led to the causal trees theory which literally does more with less. It cuts the legendary Gordian knot of OT complexity by introducing unique symbol identifiers. It is simple, obviously correct, employs very basic data structures (Unicode strings) and processes them with very simple algorithms - mostly regexes, i.e. stackless DFA (Deterministic Finite State Automaton) / NFA (Nondeterministic Finite State Automaton) -, hence the name CTRE (Causal Trees in Regular Expressions). In application to linear texts, apart from real-time collaborative editing, CTRE also offers distributed revision control and deep hypertext functionality that cannot be naturally implemented with OT.

Documents: PDF

Date and Place

On February 24th, 2011

LORIA
Centre de Recherche INRIA Nancy-Grand Est
615, rue du Jardin Botanique
54600 Villers-ls-Nancy

Meeting will take place in Room A-008