Transformación operativa

Concurrency control method for collaborative software

La transformación operativa ( OT ) es una tecnología para admitir una variedad de funcionalidades de colaboración en sistemas de software colaborativo avanzados . OT se inventó originalmente para mantener la coherencia y controlar la concurrencia en la edición colaborativa de documentos de texto sin formato. Sus capacidades se han ampliado y sus aplicaciones se han ampliado para incluir deshacer grupos, bloqueo, resolución de conflictos, notificación y compresión de operaciones, reconocimiento de grupos, HTML/XML y edición de documentos estructurados en árbol, herramientas colaborativas de productividad de oficina, uso compartido de aplicaciones y computación colaborativa. -Herramientas de diseño de medios asistidos. ^[1] En 2009, OT se adoptó como técnica central detrás de las funciones de colaboración en Apache Wave y Google Docs .

Historia

La transformación operativa fue iniciada por C. Ellis y S. Gibbs ^[2] en el sistema GROVE (GRoup Outline Viewing Edit) en 1989. Varios años más tarde, se identificaron algunos problemas de corrección y se adoptaron varios enfoques ^{[3] [4] [5] [ 6]} se propusieron de forma independiente para resolver estos problemas, a lo que siguió otra década de esfuerzos continuos para ampliar y mejorar la OT por parte de una comunidad de investigadores dedicados. En 1998, se creó un Grupo de Interés Especial sobre Edición Colaborativa ^[7] para promover la comunicación y la colaboración entre investigadores de EC y OT. Desde entonces, SIGCE organiza talleres anuales de CE junto con las principales conferencias de CSCW ( Trabajo cooperativo asistido por computadora ), como ACM, CSCW, GROUP y ECSCW.

Arquitectura del sistema

Los sistemas de colaboración que utilizan transformaciones operativas suelen utilizar almacenamiento de documentos replicados, donde cada cliente tiene su propia copia del documento; los clientes operan en sus copias locales sin bloqueos ni bloqueos , y los cambios luego se propagan al resto de los clientes; esto garantiza al cliente una alta capacidad de respuesta en un entorno que de otro modo sería de alta latencia, como Internet. Cuando un cliente recibe los cambios propagados desde otro cliente, normalmente transforma los cambios antes de ejecutarlos; la transformación garantiza que todos los sitios mantengan los criterios de coherencia dependientes de la aplicación ( invariantes ). Este modo de operación da como resultado un sistema particularmente adecuado para implementar funciones de colaboración, como la edición simultánea de documentos, en un entorno de alta latencia como la web .

Lo esencial

Idea básica detrás de OT

La idea básica de OT se puede ilustrar utilizando un escenario simple de edición de texto como se muestra a continuación. Dado un documento de texto con una cadena "abc" replicada en dos sitios colaboradores; y dos operaciones concurrentes:

1. O1 = Insertar[0, "x"] (para insertar el carácter "x" en la posición "0")
2. O2 = Eliminar[2, "c"] (para eliminar el carácter "c" en la posición "2")

generado por dos usuarios en los sitios colaboradores 1 y 2, respectivamente. Supongamos que las dos operaciones se ejecutan en el orden de O1 y O2 (en el sitio 1). Después de ejecutar O1, el documento pasa a ser "xabc". Para ejecutar O2 después de O1, O2 debe transformarse contra O1 para convertirse en: O2' = Eliminar[3, "c"], cuyo parámetro posicional se incrementa en uno debido a la inserción de un carácter "x" por parte de O1. Al ejecutar O2' en "xabc" se elimina el carácter correcto "c" y el documento se convierte en "xab". Sin embargo, si O2 se ejecuta sin transformación, elimina incorrectamente el carácter "b" en lugar de "c". La idea básica de OT es transformar (o ajustar) los parámetros de una operación de edición de acuerdo con los efectos de operaciones concurrentes ejecutadas previamente para que la operación transformada pueda lograr el efecto correcto y mantener la coherencia del documento.

Modelos de consistencia

Una funcionalidad de OT es apoyar el mantenimiento de la coherencia en los sistemas de edición colaborativa. Se han propuesto varios modelos de coherencia en la comunidad investigadora, algunos generalmente para sistemas de edición colaborativos y otros específicamente para algoritmos OT.

El modelo CC

En el artículo de Ellis y Gibbs de 1989 "Control de concurrencia en sistemas de software colaborativo", ^[2] se requieren dos propiedades de coherencia para los sistemas de edición colaborativa:

• Preservación de la causalidad : garantiza que el orden de ejecución de las operaciones causalmente dependientes sea el mismo que su orden natural de causa-efecto durante el proceso de colaboración. La relación causal entre dos operaciones se define formalmente por la relación " sucedió antes " de Lamport. Cuando dos operaciones no son causalmente dependientes, son concurrentes. Se pueden ejecutar dos operaciones simultáneas en diferente orden en dos copias de documentos diferentes.
• C onvergencia: garantiza que las copias replicadas del documento compartido sean idénticas en todos los sitios en reposo (es decir, que todas las operaciones generadas se hayan ejecutado en todos los sitios).

Dado que las operaciones concurrentes pueden ejecutarse en diferentes órdenes y las operaciones de edición no son conmutativas en general, las copias del documento en diferentes sitios pueden divergir (inconsistentes). El primer algoritmo OT fue propuesto en el artículo de Ellis y Gibbs ^[2] para lograr la convergencia en un editor de texto grupal; El vector de estado (o reloj vectorial en la informática distribuida clásica) se utilizó para preservar la propiedad de precedencia.

El modelo CCI

El modelo CCI fue propuesto como una gestión de consistencia en sistemas de edición colaborativa. ^{[4] [8]} Bajo el modelo CCI, se agrupan tres propiedades de consistencia:

• Preservación de causalidad : igual que en el modelo CC.
• C onvergencia: igual que en el modelo CC.
• Preservación de la intención : garantiza que el efecto de ejecutar una operación en cualquier estado del documento sea el mismo que la intención de la operación. La intención de una operación O se define como el efecto de ejecución que se puede lograr aplicando O en el estado del documento a partir del cual se generó O.

El modelo CCI amplía el modelo CC con un nuevo criterio: la preservación de la intención. La diferencia esencial entre convergencia y preservación de la intención es que la primera siempre se puede lograr mediante un protocolo de serialización, pero la segunda no puede lograrse mediante ningún protocolo de serialización si las operaciones siempre se ejecutaron en sus formas originales. Lograr la propiedad de preservación de intención no serializable ha sido un desafío técnico importante. Se ha descubierto que la TO es particularmente adecuada para lograr la convergencia y la preservación de la intención en sistemas de edición colaborativos.

El modelo CCI es independiente de los tipos de documentos o modelos de datos, tipos de operaciones o técnicas de soporte (OT, multiversiones, serialización, deshacer/rehacer). No estaba destinado a la verificación de la corrección de técnicas (por ejemplo, OT) que están diseñadas para datos y modelos operativos específicos y para aplicaciones específicas. En ^[4] , la noción de preservación de la intención se definió y perfeccionó en tres niveles: primero, se definió como un requisito de coherencia genérico para los sistemas de edición colaborativa; En segundo lugar, se definió como condiciones operativas previas y posteriores a la transformación basadas en el contexto para funciones genéricas de OT; En tercer lugar, se definió como criterio de verificación de operación específica para guiar el diseño de funciones OT para dos operaciones primitivas: inserción y eliminación de cadenas, en editores colaborativos de texto plano.

El modelo CSM

La condición de preservación de la intención no se especificó formalmente en el modelo CCI a efectos de pruebas formales. Los enfoques SDT ^[9] y LBT ^[10] intentan formalizar condiciones alternativas que puedan demostrarse. El modelo de consistencia propuesto en estos dos enfoques consta de las siguientes condiciones formales:

• Causalidad : la misma definición que en el modelo CC
• Efectos de operación única : el efecto de ejecutar cualquier operación en cualquier estado de ejecución logra el mismo efecto que en su estado de generación.
• Efectos de múltiples operaciones : la relación de efectos de dos operaciones cualesquiera se mantiene después de que ambas se ejecuten en cualquier estado.

El modelo CA

El modelo CSM anterior requiere que se especifique un orden total de todos los objetos del sistema. Efectivamente, la especificación se reduce a nuevos objetos introducidos mediante operaciones de inserción. Sin embargo, la especificación del pedido total implica políticas específicas de la aplicación, como aquellas para romper los vínculos de inserción (es decir, nuevos objetos insertados por dos operaciones actuales en la misma posición). En consecuencia, el pedido total se vuelve específico de la aplicación. Además, en el algoritmo, se debe mantener el orden total en las funciones de transformación y el procedimiento de control, lo que aumenta la complejidad temporal/espacial del algoritmo.

Alternativamente, el modelo CA se basa en la teoría de la admisibilidad . ^[11] El modelo CA incluye dos aspectos:

• Causalidad : la misma definición que en el modelo CC
• Admisibilidad : La invocación de cada operación es admisible en su estado de ejecución, es decir, cada invocación no debe violar ninguna relación de efectos (ordenamiento de objetos) que haya sido establecida por invocaciones anteriores.

Estas dos condiciones implican convergencia. Todos los sitios cooperantes convergen en un estado en el que hay un mismo conjunto de objetos que están en el mismo orden. Además, el ordenamiento está efectivamente determinado por los efectos de las operaciones cuando se generan. Dado que las dos condiciones también imponen restricciones adicionales en el ordenamiento de los objetos, en realidad son más fuertes que la convergencia. El modelo CA y el enfoque de diseño/prueba se detallan en el artículo de 2005. ^[11] Ya no requiere que se especifique un orden total de objetos en el modelo de consistencia y se mantenga en el algoritmo, lo que por lo tanto da como resultado una reducción de las complejidades de tiempo/espacio en el algoritmo.

Estructura del sistema OT

OT es un sistema de múltiples componentes. Una estrategia establecida para diseñar sistemas OT ^{[2] [3] [4] [5] [12] [13]} es separar los algoritmos de control (o integración) de transformación de alto nivel de las funciones de transformación de bajo nivel.

El algoritmo de control de transformación se ocupa de determinar:

1. ¿Qué operación debería transformarse frente a una nueva operación causalmente preparada?
2. El orden de las transformaciones.

El algoritmo de control invoca un conjunto correspondiente de funciones de transformación, que determinan cómo transformar una operación frente a otra según los tipos de operación, posiciones y otros parámetros. Las responsabilidades de corrección de estas dos capas se especifican formalmente mediante un conjunto de propiedades y condiciones de transformación. Diferentes sistemas OT con diferentes algoritmos de control, funciones y topologías de comunicación requieren mantener diferentes conjuntos de propiedades de transformación. La separación de un sistema OT en estas dos capas permite el diseño de algoritmos de control genéricos que son aplicables a diferentes tipos de aplicaciones con diferentes datos y modelos operativos.

El otro enfoque alternativo se propuso en ^[11] . En su enfoque, un algoritmo OT es correcto si satisface dos criterios de corrección formalizados:

1. Preservación de la causalidad
2. Preservación de la admisibilidad

Siempre que se cumplan estos dos criterios, las réplicas de datos convergen (con restricciones adicionales) después de que se ejecuten todas las operaciones en todos los sitios. No es necesario imponer un orden total de ejecución para lograr la convergencia. Su enfoque generalmente consiste en identificar y probar primero las condiciones suficientes para unas pocas funciones de transformación y luego diseñar un procedimiento de control para garantizar esas condiciones suficientes. De esta manera, el procedimiento de control y las funciones de transformación trabajan sinérgicamente para lograr la corrección, es decir, la causalidad y la preservación de la admisibilidad. En su enfoque, no es necesario satisfacer propiedades de transformación como TP2 porque no requiere que las funciones de transformación (inclusivas) funcionen en todos los casos posibles.

Datos OT y modelos de operación.

Existen dos modelos subyacentes en cada sistema OT: el modelo de datos que define la forma en que las operaciones abordan los objetos de datos en un documento y el modelo de operación que define el conjunto de operaciones que pueden ser transformadas directamente por las funciones OT. Diferentes sistemas OT pueden tener diferentes datos y modelos operativos. Por ejemplo, el modelo de datos del primer sistema OT ^[2] es un espacio de direcciones lineal único; y su modelo de operación consta de dos operaciones primitivas: insertar y eliminar por caracteres. El modelo de operación básico se ha ampliado para incluir una tercera actualización de operación primitiva para admitir el procesamiento colaborativo de documentos de Word ^[14] y la edición de modelos 3D. ^[15] El modelo básico de datos OT se ha ampliado a una jerarquía de múltiples dominios de direccionamiento lineal, ^{[16] [17] [18]} que es capaz de modelar una amplia gama de documentos. A menudo se requiere un proceso de adaptación de datos para asignar modelos de datos específicos de la aplicación a un modelo de datos compatible con OT. ^{[19] [20]}

Existen dos enfoques para soportar operaciones a nivel de aplicación en un sistema OT:

1. Enfoque de modelo de operación genérico: que consiste en diseñar funciones de transformación para tres operaciones primitivas: insertar, eliminar y actualizar. ^[19] Este enfoque necesita un proceso de adaptación de operaciones para mapear las operaciones de la aplicación a estas operaciones primitivas. En este enfoque, el modelo de operación OT es genérico, por lo que las funciones de transformación se pueden reutilizar para diferentes aplicaciones.
2. Enfoque del modelo de operación específico de la aplicación: que consiste en diseñar funciones de transformación para cada par de operaciones de la aplicación. ^{[20] [21]} Para una aplicación con m operaciones diferentes, se necesitan funciones de transformación mxm para soportar esta aplicación. En este enfoque, las funciones de transformación son específicas de la aplicación y no se pueden reutilizar en diferentes aplicaciones.

funciones OT

Se han diseñado varias funciones de OT para sistemas OT con diferentes capacidades y utilizadas para diferentes aplicaciones. Las funciones OT utilizadas en diferentes sistemas OT pueden recibir nombres diferentes, pero se pueden clasificar en dos categorías:

• Transformación de inclusión (o transformación directa): IT(Oa, Ob) o , que transforma la operación Oa frente a otra operación Ob de tal manera que efectivamente se incluya el impacto de Ob. Éste es, por ejemplo, el caso de dos inserciones en nodos diferentes. ${\displaystyle T(op_{1},op_{2})}$
• Transformación de exclusión (o transformación hacia atrás): ET (Oa, Ob) o , que transforma la operación Oa frente a otra operación Ob de tal manera que efectivamente se excluye el impacto de Ob. Este es, por ejemplo, el caso de una inserción y una eliminación en diferentes nodos ^[22] ${\displaystyle T^{-1}(op_{1},op_{2})}$

Por ejemplo, supongamos un tipo String con una operación ins(p, c, sid) donde p es la posición de inserción, c es el carácter a insertar y sid es el identificador del sitio que ha generado la operación. Podemos escribir la siguiente función de transformación de inclusión: ^[23]

T(entradas( ),entradas( )) :- ${\displaystyle p_{1},c_{1},sid_{1}}$ ${\displaystyle p_{2},c_{2},sid_{2}}$ si ( ) devuelve ins ( ) ${\displaystyle p_{1}<p_{2}}$ ${\displaystyle p_{1},c_{1},sid_{1}}$ de lo contrario si ( y ) devuelve ins( ) ${\displaystyle p_{1}=p_{2}}$ ${\displaystyle sid_{1}<sid_{2}}$ ${\displaystyle p_{1},c_{1},sid_{1}}$ de lo contrario, devuelve entradas ( ) ${\displaystyle p_{1}+1,c_{1},sid_{1}}$

También podemos escribir la siguiente función de transformación de exclusión: ^[23]

 ${\displaystyle T^{-1}}$(ins( ),ins( )) :- ${\displaystyle p_{1},c_{1},sid_{1}}$ ${\displaystyle p_{2},sid_{2}}$ si ( ) devuelve ins ( ) ${\displaystyle p_{1}<p_{2}}$ ${\displaystyle p_{1},c_{1},sid_{1}}$ de lo contrario si ( y ) devuelve ins( ) ${\displaystyle p_{1}=p_{2}}$ ${\displaystyle sid_{1}<sid_{2}}$ ${\displaystyle p_{1},c_{1},sid_{1}}$ de lo contrario, devuelve entradas ( ) ${\displaystyle p_{1}-1,c_{1},sid_{1}}$

Algunos sistemas OT utilizan funciones tanto de TI como de ET, y algunos utilizan únicamente funciones de TI. La complejidad del diseño de la función OT está determinada por varios factores:

• la funcionalidad del sistema OT: si el sistema OT admite hacer (mantenimiento de coherencia), deshacer, bloquear, ^[24] conciencia, compartir aplicaciones, ^{[19] [25] [26] [27]} , etc.;
• la responsabilidad de corrección en el sistema OT: qué propiedades de transformación (CP1/TP1, CP2/TP2, IP2, IP3, RP) cumplir; si se utiliza ET;
• el modelo de operación del sistema OT: si el modelo de operación OT es genérico (por ejemplo, inserción, eliminación, actualización primitiva) o específico de la aplicación (todas las operaciones de la aplicación de destino); y
• el modelo de datos del sistema OT: si los datos en cada operación son por caracteres (un objeto individual), por cadenas (una secuencia de objetos), jerárquicos u otras estructuras.

Propiedades de transformación

Se han identificado varias propiedades de transformación para garantizar la corrección del sistema OT. Estas propiedades pueden mantenerse mediante el algoritmo de control de transformación ^{[4] [5] [13] [20] [28] [29]} o mediante las funciones de transformación. ^[30] Los diferentes diseños de sistemas OT tienen diferentes divisiones de responsabilidades entre estos componentes. Las especificaciones de estas propiedades y las condiciones previas para exigirlas se detallan a continuación.

Propiedades de convergencia

Ilustración de la propiedad TP1

Ilustración de la propiedad TP2

Las dos propiedades siguientes están relacionadas con el logro de la convergencia.

• CP1/TP1 : Para cada par de operaciones concurrentes y definidas en el mismo estado, la función de transformación T satisface la propiedad CP1/TP1 si y sólo si: donde denota la secuencia de operaciones que contienen seguido de ;y donde denota la equivalencia de las dos secuencias de operaciones. Condición previa CP1/TP1 : CP1/TP1 se requiere solo si el sistema OT permite ejecutar dos operaciones cualesquiera en órdenes diferentes. ${\displaystyle op_{1}}$ ${\displaystyle op_{2}}$ ${\displaystyle op_{1}\circ T(op_{2},op_{1})\equiv op_{2}\circ T(op_{1},op_{2})}$ ${\displaystyle op_{i}\circ op_{j}}$ ${\displaystyle op_{i}}$ ${\displaystyle op_{j}}$ ${\displaystyle \equiv }$
• CP2/TP2 : Por cada tres operaciones concurrentes y definidas en el mismo estado de documento, la función de transformación T satisface la propiedad CP2/TP2 si y solo si: . CP2/TP2 estipula la igualdad entre dos operaciones transformadas con respecto a dos secuencias de operaciones equivalentes: la transformación de contra la secuencia de operación seguida de debe dar la misma operación que la transformación de contra la secuencia formada por y . Condición previa de CP2/TP2 : CP2/TP2 se requiere solo si los sistemas OT permiten dos operaciones y se transforman en TI en dos estados (o contextos) de documentos diferentes. ${\displaystyle op_{1},op_{2}}$ ${\displaystyle op_{3}}$ ${\displaystyle T(op_{3},op_{1}\circ T(op_{2},op_{1}))=T(op_{3},op_{2}\circ T(op_{1},op_{2}))}$ ${\displaystyle op_{3}}$ ${\displaystyle op_{2}}$ ${\displaystyle T(op_{1},op_{2})}$ ${\displaystyle op_{3}}$ ${\displaystyle op_{1}}$ ${\displaystyle T(op_{2},op_{1})}$ ${\displaystyle op_{1}}$ ${\displaystyle op_{2}}$

Propiedades inversas

Las siguientes tres propiedades están relacionadas con lograr el efecto de deshacer grupo deseado. Ellos son:

• IP1 : Dado cualquier estado de documento S y la secuencia , tenemos , lo que significa que la secuencia es equivalente a una operación de identidad única I con respecto al efecto en el estado del documento. Esta propiedad es necesaria en un sistema OT para lograr el efecto de deshacer correcto, pero no está relacionada con las funciones de TI. ${\displaystyle op\circ {\overline {op}}}$ ${\displaystyle S\circ op\circ {\overline {op}}=S}$ ${\displaystyle op\circ {\overline {op}}}$
• IP2 : La propiedad IP2 expresa que la secuencia no tiene efecto sobre la transformación de otras operaciones. Las funciones de transformación satisfacen IP2 si y solo si: , lo que significa que el resultado de la transformación contra la secuencia es equivalente al resultado de la transformación contra la operación de identidad I. Precondición de IP2 : IP2 se requiere solo si los sistemas OT permiten que se realice una operación. transformado contra un par de operaciones de hacer y deshacer , una por una. ${\displaystyle op\circ {\overline {op}}}$ ${\displaystyle T(op_{x},op\circ {\overline {op}})=op_{x}}$ ${\displaystyle op_{x}}$ ${\displaystyle op\circ {\overline {op}}}$ ${\displaystyle op_{x}}$ ${\displaystyle op_{x}}$ ${\displaystyle op\circ {\overline {op}}}$
• IP3 : dadas dos operaciones simultáneas y definidas en el mismo estado (o contexto) del documento, si y . Las funciones de transformación satisfacen la propiedad IP3 si y sólo si , lo que significa que la operación inversa transformada es igual a la inversa de la operación transformada . Condición previa de IP3 : IP3 se requiere solo si el sistema OT permite que una operación inversa se transforme en una operación que es concurrente y está definida en el mismo estado de documento que (o en contexto equivalente a) . ${\displaystyle op_{1}}$ ${\displaystyle op_{2}}$ ${\displaystyle {\overline {op_{1}}}'=T({\overline {op_{1}}},T(op_{2},op_{1}))}$ ${\displaystyle {\overline {op_{1}'}}={\overline {T(op_{1},op_{2})}}}$ ${\displaystyle {\overline {op_{1}}}'={\overline {op_{1}'}}}$ ${\displaystyle {\overline {op_{1}}}'}$ ${\displaystyle {\overline {op_{1}'}}}$ ${\displaystyle {\overline {op_{1}}}}$ ${\displaystyle op_{2}}$ ${\displaystyle op_{1}}$

Algoritmos de control (integración) de OT

Se han diseñado varios algoritmos de control de OT para sistemas OT con diferentes capacidades y para diferentes aplicaciones. La complejidad del diseño del algoritmo de control de OT está determinada por múltiples factores. Un factor diferenciador clave es si un algoritmo es capaz de soportar el control de concurrencia (hacer) y/o deshacer en grupo. ^{[3] [8] [12] [29] [31]} Además, diferentes diseños de algoritmos de control de OT generan diferentes compensaciones en:

• asignar responsabilidades de corrección entre el algoritmo de control y las funciones de transformación, y
• Complejidad espacio-temporal del sistema OT.

La mayoría de los algoritmos de control de OT existentes para el control de concurrencia adoptan la teoría de causalidad/concurrencia como base teórica: las operaciones relacionadas causalmente deben ejecutarse en su orden causal; Las operaciones concurrentes deben transformarse antes de su ejecución. Sin embargo, era bien sabido que la condición de concurrencia por sí sola no puede capturar todas las condiciones de transformación de OT. ^{[3] [4] [5] [8] [32]} En un trabajo reciente, se ha propuesto que la teoría del contexto de operación represente explícitamente la noción de un estado de documento, que puede usarse para expresar formalmente las condiciones de transformación OT para soportar el diseño y verificación de algoritmos de control de OT. ^[29]

La siguiente tabla ofrece una descripción general de algunos algoritmos de integración/control de OT existentes.

Un orden total continuo es un orden total estricto en el que es posible detectar un elemento faltante, es decir, 1,2,3,4,... es un orden total continuo, 1,2,3,5,... no es un orden total continuo.

Los algoritmos basados ​​en transformaciones propuestos en ^{[10] [11]} se basan en los modelos de consistencia alternativos "CSM" y "CA" como se describe anteriormente. Sus enfoques difieren de los enumerados en la tabla. Utilizan marcas de tiempo vectoriales para preservar la causalidad. Las otras condiciones de corrección son la preservación de la relación de efectos de operación "única"/"múltiple" o la preservación de la "admisibilidad". Estas condiciones se garantizan sinérgicamente mediante el procedimiento de control y las funciones de transformación. No es necesario discutir TP1/TP2 en su trabajo. Por lo tanto, no figuran en la tabla anterior.

Existen otros algoritmos de control de consistencia optimistas que buscan formas alternativas de diseñar algoritmos de transformación, pero que no encajan bien con la taxonomía y caracterización anteriores. Por ejemplo, marcar y volver sobre ^[35]

Los problemas de corrección de la OT llevaron a la introducción de esquemas post-OT sin transformación, como WOOT, ^[36] Logoot ^[37] y Causal Trees (CT). ^[38] Los esquemas "Post-OT" descomponen el documento en operaciones atómicas, pero solucionan la necesidad de transformar las operaciones empleando una combinación de identificadores de símbolos únicos, marcas de tiempo vectoriales y/o lápidas.

Crítica de TO

Si bien el enfoque clásico de OT de definir operaciones a través de sus compensaciones en el texto parece simple y natural, los sistemas distribuidos del mundo real plantean serios problemas. Es decir, que las operaciones se propagan a una velocidad finita, los estados de los participantes suelen ser diferentes, por lo que las combinaciones resultantes de estados y operaciones son extremadamente difíciles de prever y comprender. Como lo expresaron Li y Li, "Debido a la necesidad de considerar una cobertura de casos complicada, las pruebas formales son muy complicadas y propensas a errores, incluso para los algoritmos OT que solo tratan dos primitivas de caracteres (insertar y eliminar)". ^[39]

De manera similar, Joseph Gentle, ex ingeniero de Google Wave y autor de la biblioteca Share.JS, escribió: "Desafortunadamente, implementar OT apesta. Hay un millón de algoritmos con diferentes compensaciones, en su mayoría atrapados en artículos académicos. […] Wave tardó 2 años escribirlo y si lo volviéramos a escribir hoy, tomaría casi el mismo tiempo escribirlo una segunda vez." ^[40] Pero luego modifica su comentario con "Ya no creo que esa ola tardaría 2 años en implementarse ahora, principalmente debido a los avances en los marcos web y los navegadores web". ^[41]

Para que OT funcione, es necesario capturar cada cambio en los datos: "Obtener una instantánea del estado suele ser trivial, pero capturar las ediciones es un asunto completamente diferente. […] La riqueza de las interfaces de usuario modernas puede hacer que esto sea problemático, especialmente dentro de un entorno basado en navegador". Una alternativa a OT es la sincronización diferencial. ^[42]

Otra alternativa a la OT es utilizar tipos de secuencia de tipos de datos replicados libres de conflictos .

Ver también

• Sincronización de datos
• Editores colaborativos en tiempo real
• Tipos de datos replicados sin conflictos
• Modelos de consistencia
• Replicación optimista

Referencias

1. Sol, Chengzheng. "Preguntas frecuentes sobre OT". Archivado desde el original el 23 de junio de 2020.
2. Ellis, California; Gibbs, SJ (1989). "Control de concurrencia en sistemas groupware". Registro ACM SIGMOD . 18 (2): 399–407. CiteSeerX 10.1.1.465.2026 . doi : 10.1145/67544.66963. S2CID  6488575. 
3. Ressel, Matthias y Nitsche-Ruhland, Doris y Gunzenhäuser, Rul (1996). Un enfoque integrador y orientado a la transformación para el control de concurrencia y deshacer en editores de grupo . CSCW '96: Actas de la conferencia ACM de 1996 sobre trabajo cooperativo apoyado por computadora. págs. 288–297. doi :10.1145/240080.240305.{{cite conference}}: CS1 maint: multiple names: authors list (link)
4. Chengzheng Sun; Xiaohua Jia; Yanchun Zhang; Yun Yang; David Chen (1998). "Lograr la convergencia, la preservación de la causalidad y la preservación de la intención en sistemas de edición cooperativos en tiempo real". Transmisión ACM. Comput.-Hum. Interactuar . 5 (1): 63–108. CiteSeerX 10.1.1.56.1251 . doi :10.1145/274444.274447. S2CID  14447070. 
5. Nichols, DA; Curtis, P.; Dixon, M.; Lamping, J. (1995). "Ventanas de alta latencia y bajo ancho de banda en el sistema de colaboración de Júpiter". Actas del octavo simposio anual de ACM sobre interfaz de usuario y tecnología de software : 111–120. Archivado desde el original el 30 de noviembre de 2015 . Consultado el 27 de septiembre de 2009 .
6. sol, C.; Ellis, C. (1998). Transformación operativa en editores de grupos en tiempo real: problemas, algoritmos y logros. Actas de la conferencia ACM de 1998 sobre trabajo cooperativo apoyado por computadora. ACM Press Nueva York, NY, Estados Unidos. págs. 59–68.
7. "SIGCE: un grupo internacional de interés especial en edición colaborativa". cooffice.ntu.edu.sg . Archivado desde el original el 24 de diciembre de 2012 . Consultado el 10 de enero de 2020 .
8. C. Sol (2002). "Deshacer como inverso concurrente en editores de grupo". Transmisión ACM. Comput.-Hum. Interactuar . 9 (4): 309–361. doi :10.1145/586081.586085. S2CID  47453660.
9. Du Li; Rui Li (2004). Preservar la relación de efectos de operación en editores de grupo . Actas de la Conferencia ACM CSCW'04 sobre trabajo cooperativo asistido por computadora. ACM Press Nueva York, NY, Estados Unidos. págs. 457–466.
10. Rui Li; Du Li (2007). "Un nuevo marco de transformación operativa para editores de grupos en tiempo real". Transacciones IEEE en sistemas paralelos y distribuidos . 18 (3). Transacciones IEEE en sistemas distribuidos y paralelos: 307–319. doi :10.1109/TPDS.2007.35. S2CID  18822760.
11. Rui Li; Du Li (2005). Control de concurrencia basado en conmutatividad en software colaborativo . Actas de la Primera Conferencia IEEE sobre Computación Colaborativa: Redes, Aplicaciones y Trabajo Compartido (CollaborateCom'05).
12. Prakash, Atul y Knister, Michael J. (1994). "Un marco para deshacer acciones en sistemas colaborativos". Transmisión ACM. Comput.-Hum. Interactuar . 1 (4): 295–330. CiteSeerX 10.1.1.51.4793 . doi :10.1145/198425.198427. S2CID  10705127. 
13. Vidot, N .; Carro, M.; Ferrie, J.; Suleiman, M. (2000). Copia la convergencia en un entorno colaborativo distribuido en tiempo real (PDF) . Actas de la conferencia ACM de 2000 sobre trabajo cooperativo apoyado por computadora. ACM Press Nueva York, NY, Estados Unidos. págs. 171–180. Archivado desde el original (PDF) el 12 de octubre de 2004.
14. D. Sun y S. Xia y C. Sun y D. Chen (2004). Transformación operativa para el procesamiento de textos colaborativo . Proc. de la Conferencia ACM. sobre Trabajo Cooperativo Asistido por Computadora. págs. 437–446.
15. Agustina y F. Liu y S. Xia y H. Shen y C. Sun (noviembre de 2008). CoMaya: incorporación de capacidades de colaboración avanzadas en herramientas de diseño de medios digitales {3D} . Proc. de la Conferencia ACM. sobre Trabajo Cooperativo Asistido por Computadora. págs. 5–8.
16. Davis, Aguido Horatio y Sun, Chengzheng y Lu, Junwei (2002). "Generalización de la transformación operativa al lenguaje de marcado general estándar" . CSCW '02: Actas de la conferencia ACM de 2002 sobre trabajo cooperativo apoyado por computadora. Nueva Orleans, Luisiana, Estados Unidos. págs. 58–67. doi :10.1145/587078.587088.{{cite conference}}: CS1 maint: multiple names: authors list (link)
17. Claudia-Lavinia Ignat; Moira C. Norrie (2003). Editor colaborativo personalizable basado en el algoritmo treeOPT . ECSCW'03: Actas de la octava conferencia sobre la Conferencia europea sobre trabajo cooperativo asistido por ordenador. Editores académicos de Kluwer. págs. 315–334. doi :10.1007/978-94-010-0068-0_17.
18. Claudia-Lavinia Ignat; Moira C. Norrie (2008). "Edición multinivel de documentos jerárquicos". Trabajo Cooperativo Asistido por Computadora (CSCW) . 17 (5–6): 423–468. doi :10.1007/s10606-007-9071-2. S2CID  42752275.
19. C.Sun, S.Xia, D.Sun, D.Chen, H.Shen y W.Cai (2006). "Adaptación transparente de aplicaciones monousuario para colaboración multiusuario en tiempo real". Transmisión ACM. Comput.-Hum. Interactuar . 13 (4): 531–582. doi :10.1145/1188816.1188821. S2CID  14184705.{{cite journal}}: CS1 maint: multiple names: authors list (link)
20. "Transformación operativa de Google Wave". Archivado desde el original el 31 de mayo de 2009 . Consultado el 29 de mayo de 2009 .
21. Christopher R. Palmer; Gordon V. Cormack (1998). Transformaciones de operación para una hoja de cálculo compartida distribuida . CSCW '98: Actas de la conferencia ACM de 1998 sobre trabajo cooperativo apoyado por computadora. Prensa ACM. págs. 69–78. doi : 10.1145/289444.289474 .
22. Kagorskii, Anton. "Transformaciones Operacionales como algoritmo de resolución automática de conflictos". medio.com . Consultado el 21 de diciembre de 2021 .
23. "Funciones de transformación de Tombstone para garantizar la coherencia en los sistemas de edición colaborativos". Conferencia IEEE sobre informática colaborativa: redes, aplicaciones y trabajo compartido . 2006-11-07.
24. C. Sun y R. Sosic (1999). Bloqueo opcional integrado con transformación operativa en editores de grupos distribuidos en tiempo real . En Proc. del 18º Simposio ACM sobre principios de informática distribuida. págs. 43–52.
25. Begole, James y Rosson, Mary Beth y Shaffer, Clifford A. (1999). "Transparencia de colaboración flexible: apoyo a la independencia de los trabajadores en sistemas replicados para compartir aplicaciones". Transmisión ACM. Comput.-Hum. Interactuar . 6 (2): 95-132. CiteSeerX 10.1.1.23.1185 . doi :10.1145/319091.319096. S2CID  17895848. {{cite journal}}: CS1 maint: multiple names: authors list (link)
26. Li, Du y Li, Rui (2002). Interoperación y uso compartido transparente de aplicaciones heterogéneas de un solo usuario . CSCW '02: Actas de la conferencia ACM de 2002 sobre trabajo cooperativo apoyado por computadora. Nueva Orleans, Estados Unidos. págs. 246-255.
27. Li, Du y Lu, Jiajun (2006). Un enfoque ligero para compartir de forma transparente editores familiares de un solo usuario . CSCW '06: Actas de la conferencia del vigésimo aniversario de 2006 sobre el trabajo cooperativo apoyado por computadora. Banff, Alberta, Canadá. págs. 139-148. doi :10.1145/1180875.1180896.
28. Shen, Haifeng y Sun, Chengzheng (2002). Notificación flexible para sistemas colaborativos . CSCW '02: Actas de la conferencia ACM de 2002 sobre trabajo cooperativo apoyado por computadora. págs. 77–86. doi :10.1145/587078.587090.
29. D. Sun y C. Sun (2009). "Transformación operativa basada en el contexto para sistemas de edición colaborativos distribuidos". Transacciones IEEE en sistemas paralelos y distribuidos . 20 (10): 1454-1470. doi :10.1109/TPDS.2008.240. S2CID  18740053.
30. Gerald Oster; Pascal Molli; Pascal Urso; Abdessamad Imine (2006). "Funciones de transformación de Tombstone para garantizar la coherencia en los sistemas de edición colaborativos" (PDF) . Procesos. 2do Internacional Conf. Sobre informática colaborativa: redes, Appln. Y trabajo compartido . Consultado el 26 de julio de 2007 .
31. M. Ressel y R. Gunzenhauser (1999). Reducir los problemas de deshacer en grupo . Proc. de la Conferencia ACM. sobre el trabajo en grupo de apoyo. págs. 131-139.
32. Suleiman, M.; Carro, M.; Ferrie, J. (1998). Operaciones concurrentes en un entorno colaborativo distribuido y móvil . Actas de la Decimocuarta Conferencia Internacional sobre Ingeniería de Datos, febrero. págs. 23-27. doi :10.1109/ICDE.1998.655755.
33. R. Li, D. Li y C. Sun (2004). "Un algoritmo de control de coherencia basado en intervalos de tiempo para aplicaciones interactivas de software colaborativo" . ICPADS '04: Actas de los sistemas distribuidos y paralelos, Décima Conferencia Internacional. pag. 429. doi :10.1109/ICPADS.2004.12.
34. M. Carro, Jean Ferrié (2007). Sincronizador Basado en Transformación Operacional para Entornos P2P (PDF) . Actas de la Tercera Conferencia Internacional sobre Computación Colaborativa: Redes, Aplicaciones y Trabajo Compartido. págs. 127-138 . Consultado el 26 de julio de 2007 .
35. Gu, Ning y Yang, Jiangming y Zhang, Qiwei (2005). Mantenimiento de consistencia basado en la técnica mark\&retrace en sistemas groupware . GRUPO '05: Actas de la conferencia internacional ACM SIGGROUP de 2005 sobre apoyo al trabajo en grupo. págs. 264-273. doi :10.1145/1099203.1099250.{{cite conference}}: CS1 maint: multiple names: authors list (link)
36. Imine, Abdessamad y Molli, Pascal y Oster, Gerald y Urso, Pascal (2005). Editores de grupos en tiempo real sin transformación operativa. Informe de investigación INRIA RR-5580. pag. 24.{{cite conference}}: CS1 maint: multiple names: authors list (link)
37. Stéphane Weiss y Pascal Urso y Pascal Molli (2010). "Logoot-Undo: sistema de edición colaborativa distribuida en redes P2P". Transacciones IEEE en sistemas paralelos y distribuidos . 21 (8). Transacciones IEEE en sistemas distribuidos y paralelos: 1162. doi :10.1109/TPDS.2009.173. S2CID  14172605.
38. Víctor Grishchenko (2010). Hipertexto profundo con control de revisión integrado implementado en expresiones regulares (PDF) . Actas del VI Simposio Internacional sobre Wikis y Colaboración Abierta (WikiSym '10). Archivado desde el original (PDF) el 9 de marzo de 2012 . Consultado el 30 de junio de 2010 .
39. Du Li y Rui Li (2010). "Un marco de transformación operativa basado en la admisibilidad para sistemas de edición colaborativos". Trabajo Cooperativo Asistido por Computadora (CSCW) . 19 (1). Trabajo cooperativo asistido por computadora: 1–43. doi :10.1007/s10606-009-9103-1. S2CID  35748875.
40. "CompartirJS". 2011-11-06. Archivado desde el original el 11 de mayo de 2012 . Consultado el 16 de agosto de 2013 .
41. "¡Sí, ese soy yo! Por si sirve de algo, ya no creo que esa ola tarde 2 años... | Hacker News". noticias.ycombinator.com . Consultado el 13 de febrero de 2019 .
42. Neil Fraser (enero de 2009). "Sincronización diferencial".

enlaces externos

• Preguntas frecuentes sobre OT: Preguntas y respuestas frecuentes sobre transformación operativa
• SIGCE: Grupo de Interés Especial de Edición Colaborativa
• Taller internacional sobre sistemas de edición colaborativa
• Sistema distribuido en línea: edición colaborativa
• Explicación sencilla de OT en Google Docs
• Conceptos básicos de OT en Open Coweb Framework

Charlas online relevantes

• Google Wave: edición colaborativa en vivo
• Google Tech Talk: problemas y experiencias en el diseño de sistemas de edición colaborativos en tiempo real
• Charla de Microsoft Research: Mantenimiento de la coherencia en sistemas de edición colaborativa en tiempo real