Transformación operativa

La "Operación Transformación" vuelve a dirigir aquí. Para el evento cross-media, consulte Operation Transformation (serie de televisión) .

La transformación operativa ( OT ) es una tecnología para admitir una variedad de funcionalidades de colaboración en sistemas de software colaborativos avanzados . OT se inventó originalmente para el mantenimiento de la coherencia y el control de 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, bloquear, 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 de productividad de oficina colaborativas, uso compartido de aplicaciones y equipo colaborativo. -herramientas de diseño de medios asistidas. ^[1] En 2009, la OT se adoptó como una técnica central detrás de las funciones de colaboración en Apache Wave.y Google Docs .

Historia

La Transformación Operacional 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 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 TO 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 CE y TO. Desde entonces, SIGCE lleva a cabo talleres anuales de CE junto con los principales CSCW ( Trabajo cooperativo asistido por computadora) conferencias, como ACM, CSCW, GROUP y ECSCW.

Arquitectura del sistema

Los sistemas de colaboración que utilizan transformaciones operativas suelen utilizar el almacenamiento de documentos replicados, donde cada cliente tiene su propia copia del documento; clientes operan en sus copias locales en un sin bloqueo , sin bloqueo de forma, y los cambios se propagan al resto de los clientes; esto asegura al cliente una alta capacidad de respuesta en un entorno 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 asegura que los criterios de coherencia dependientes de la aplicación ( invariantes) son mantenidos por todos los sitios. 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

La idea básica de OT se puede ilustrar utilizando un escenario de edición de texto simple de la siguiente manera. Dado un documento de texto con una cadena "abc" replicado 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. Suponga que las dos operaciones se ejecutan en el orden de O1 y O2 (en el sitio 1). Después de ejecutar O1, el documento se convierte en "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 O1. La ejecución de O2 'en "xabc" elimina el carácter correcto "c" y el documento se convierte en "xab". Sin embargo, si O2 se ejecuta sin transformación, borra 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 previamente ejecutadas para que la operación transformada pueda lograr el efecto correcto y mantener la consistencia del documento.

Modelos de consistencia

Una funcionalidad de OT es apoyar el mantenimiento de la coherencia en los sistemas de edición colaborativos. 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 de TO.

El modelo CC

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

• C preservación ausality: asegura el orden de ejecución de las operaciones de causalmente dependientes ser el mismo que su orden causa-efecto natural durante el proceso de colaboración. La relación causal entre dos operaciones se define formalmente mediante la relación " sucedió antes " de Lamport . Cuando dos operaciones no son causalmente dependientes, son concurrentes. Se pueden ejecutar dos operaciones simultáneas en un orden diferente en dos copias de documentos diferentes.
• C onvergence: asegura la copias replicadas del documento compartido sean idénticos en todos los sitios en la quiescencia (es decir, todas las operaciones generadas han sido ejecutadas 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 de TO se propuso 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 de vector en la computación distribuida clásica) se usó para preservar la propiedad de precedencia.

El modelo CCI

El modelo CCI se propuso como una gestión de la coherencia en los sistemas de edición colaborativa. ^{[4] [8]} En el modelo CCI, se agrupan tres propiedades de coherencia:

• C preservación ausality: el mismo que en el modelo de CC.
• C onvergence: el mismo que en el modelo de CC.
• Me preservación ntention: asegura que el efecto de la ejecución de una operación en cualquier estado del documento sea la misma 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 la convergencia y la preservación de la intención es que la primera siempre se puede lograr mediante un protocolo de serialización, pero la segunda puede no 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 gran desafío técnico. Se ha encontrado que la TO es particularmente adecuada para lograr la convergencia y la preservación de la intención en los sistemas de edición colaborativa.

El modelo CCI es independiente de los tipos de documentos o modelos de datos, tipos de operaciones o técnicas de soporte (OT, múltiples versiones, serialización, deshacer / rehacer). No fue diseñado para la verificación de la corrección de técnicas (por ejemplo, OT) que están diseñadas para datos específicos y modelos de operación y para aplicaciones específicas. En ^[4], la noción de preservación de la intención se definió y perfeccionó en tres niveles: en primer lugar, se definió como un requisito de coherencia genérico para los sistemas de edición colaborativa; En segundo lugar, se definió como condiciones previas y posteriores a la transformación basadas en el contexto de operación para funciones genéricas de OT; En tercer lugar, se definió como un criterio de verificación de operación específico para guiar el diseño de funciones OT para dos operaciones primitivas: insertar y eliminar en forma de cadena, en editores de texto sin formato colaborativos.

El modelo CSM

La condición de preservación de la intención no se especificó formalmente en el modelo CCI para propósitos 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:

• C ausalidad : la misma definición que en el modelo CC
• S efectos ingle-operación : el efecto de ejecutar cualquier operación en cualquier estado de ejecución consigue el mismo efecto que en su estado de generación
• M efectos ulti-operación : la relación efectos de cualesquiera dos operaciones se mantiene después de que ambos están ejecutados 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 por operaciones de inserción. Sin embargo, la especificación del orden total implica políticas específicas de la aplicación, como las de romper los lazos 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, el orden total debe mantenerse en las funciones de transformación y el procedimiento de control, lo que aumenta las complejidades de tiempo / espacio del algoritmo.

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

• C ausalidad : la misma definición que en el modelo CC
• A dmissibility : 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 efectos (objeto de pedido) que ha sido establecido por invocaciones anteriores.

Estas dos condiciones implican convergencia. Todos los sitios que cooperan convergen en un estado en el que hay un mismo conjunto de objetos que están en el mismo orden. Además, la ordenación está determinada efectivamente por los efectos de las operaciones cuando se generan. Dado que las dos condiciones también imponen restricciones adicionales en el orden de los objetos, en realidad son más fuertes que la convergencia. El modelo CA y el enfoque de diseño / prueba se elaboran en el documento 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.

Algoritmos de control de OT (determina qué operaciones se transforman frente a otras de acuerdo con sus relaciones de concurrencia / contexto)

Propiedades y condiciones de OT (dividir responsabilidades entre algoritmos y funciones)

Funciones de transformación OT (determina cómo transformar un par de operaciones primitivas de acuerdo con los tipos de operación, posiciones y otros parámetros)

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

1. ¿Qué operación debe transformarse frente a una nueva operación causalmente lista?
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 modelos de datos y operación.

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 satisfagan estos dos criterios, las réplicas de datos convergen (con restricciones adicionales) después de que todas las operaciones se ejecutan en todos los sitios. No es necesario imponer un orden total de ejecución para lograr la convergencia. Por lo general, su enfoque consiste en identificar y probar primero las condiciones suficientes para algunas 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 funcionan sinérgicamente para lograr la corrección, es decir, la preservación de la causalidad y la admisibilidad. En su enfoque, no hay necesidad de satisfacer propiedades de transformación como TP2 porque no requiere que las funciones de transformación (inclusivas) funcionen en todos los casos posibles.

Modelos de operación y datos OT

Existen dos modelos subyacentes en cada sistema de 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 directamente transformadas por las funciones de OT. Los diferentes sistemas OT pueden tener diferentes modelos de datos y operación. 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 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 mapear modelos de datos específicos de la aplicación a un modelo de datos compatible con OT. ^{[19] [20]}

Existen dos enfoques para respaldar las operaciones de nivel de aplicación en un sistema OT:

1. Enfoque del 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 aplicación con 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 OT para sistemas OT con diferentes capacidades y se utilizan para diferentes aplicaciones. Las funciones de OT que se utilizan en diferentes sistemas de OT se pueden nombrar de manera diferente, pero se pueden clasificar en dos categorías:

• Transformación de inclusión (o transformación hacia adelante): IT (Oa, Ob) o , que transforma la operación Oa frente a otra operación Ob de tal manera que se incluye efectivamente el impacto de Ob.${\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 el impacto de Ob queda efectivamente excluido.${\displaystyle T^{-1}(op_{1},op_{2})}$

Por ejemplo, suponga 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:

T (ins ( ), ins ( )): -${\displaystyle p_{1},c_{1},sid_{1}}$${\displaystyle p_{2},c_{2},sid_{2}}$ if ( ) return ins ( )${\displaystyle p_{1}<p_{2}}$${\displaystyle p_{1},c_{1},sid_{1}}$ else if ( y ) return ins ( )${\displaystyle p_{1}=p_{2}}$${\displaystyle sid_{1}<sid_{2}}$${\displaystyle p_{1},c_{1},sid_{1}}$ si no regresa ins ( )${\displaystyle p_{1}+1,c_{1},sid_{1}}$

${\displaystyle T^{-1}}$(ins ( ), ins ( )): -${\displaystyle p_{1},c_{1},sid_{1}}$${\displaystyle p_{2},c_{2},sid_{2}}$ if ( ) return ins ( )${\displaystyle p_{1}<p_{2}}$${\displaystyle p_{1},c_{1},sid_{1}}$ else if ( y ) return ins ( )${\displaystyle p_{1}=p_{2}}$${\displaystyle sid_{1}<sid_{2}}$${\displaystyle p_{1},c_{1},sid_{1}}$ si no regresa ins ( )${\displaystyle p_{1}-1,c_{1},sid_{1}}$

Algunos sistemas de TO usan funciones de TI y ET, y algunos usan solo 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, ^[22] reconocimiento, compartir aplicaciones, ^{[19] [23] [24] [25]} etc .;
• la responsabilidad de la 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 primitiva, supresión, actualización) 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 de 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 se pueden mantener mediante el algoritmo de control de transformación ^{[4] [5] [13] [20] [26] [27]} o mediante las funciones de transformación. ^{[28] Los} diferentes diseños de sistemas de TO tienen una división de responsabilidades diferente entre estos componentes. Las especificaciones de estas propiedades y las condiciones previas para requerirlas se dan a continuación.

Propiedades de convergencia

Ilustración de la propiedad TP1

Ilustración de la propiedad TP2

Las siguientes dos propiedades están relacionadas con la consecución 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 solo si: donde denota la secuencia de operaciones que contiene seguido de ; y donde denota la equivalencia de las dos secuencias de operaciones. Condición previa de CP1 / TP1 : CP1 / TP1 solo se requiere si el sistema OT permite que se ejecuten dos operaciones cualesquiera en diferentes órdenes.${\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 simultáneas y definida en el mismo estado de documentos, la función de transformación T satisface la propiedad CP2 / TP2 si y sólo si: . CP2 / TP2 estipula la igualdad entre dos operaciones transformadas con respecto a dos secuencias equivalentes de operaciones: 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 documento 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 la consecución del efecto de deshacer grupo deseado. Son:

• IP1 : Dado cualquier estado de documento S y la secuencia , tenemos , lo que significa que la secuencia es equivalente a una sola operación de identidad I con respecto al efecto sobre 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 satisfacer IP2 si y sólo si: , que significa que el resultado de transformar en contra de la secuencia es equivalente al resultado de transformar en contra de la operación identidad I. IP2 condición previa : IP2 sólo es necesario si los sistemas de OT permite una operación a ser 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 concurrentes y definidas en el mismo estado de documento (o contexto), si y . Las funciones de transformación satisfacen la propiedad IP3 si y solo 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 solo se requiere si el sistema OT permite transformar una operación inversa frente a una operación que es concurrente y está definida en el mismo estado de documento que (o equivalente al contexto) .${\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 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 de diferenciación clave es si un algoritmo es capaz de soportar el control de concurrencia (hacer) y / o deshacer el grupo. ^{[3] [8] [12] [27] [29]} Además, los diferentes diseños de algoritmos de control de OT hacen 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 OT. ^{[3] [4] [5] [8] [30]} 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 respaldar el diseño y verificación de algoritmos de control OT. ^[27]

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

Algoritmos de control / integración de OT (sistemas)	Tipos de función de transformación requeridos	¿Admite Do basado en OT?	¿Soporta deshacer basado en OT?	Propiedades de transformación soportadas por algoritmo de control	Propiedades de transformación soportadas por funciones de transformación	Restricciones de propagación y orden de transformación	Marca de tiempo
dOPT [2] (ARBOLA)	T (IT)	sí	No	Ninguno	CP1 / TP1, CP2 / TP2	Orden causal	Vector de estado
deshacer-selectivo [12] (DistEdit)	Transponer (TI y ET)	No	Deshacer selectivo	N / A	CP1 / TP1, CP2 / TP2, RP, IP1, IP2, IP3	Orden causal	??
ADOPTADO [3] [29] (EMAC CONJUNTO)	LTransformation (IT)	sí	Deshacer cronológico	IP2, IP3	CP1 / TP1, CP2 / TP2, IP1	Orden causal	Vector de estado
Júpiter [5]	xform (IT)	sí	No	CP2 / TP2	CP1 / TP1	Orden causal + servidor de transformación central	Escalar
Google Wave OT [20]	transformar y composición (IT)	sí	No	CP2 / TP2	CP1 / TP1	Orden causal + servidor de transformación central + protocolo de propagación stop'n'wait	Escalar
GOT [4] (REDUCIR)	TI y ET	sí	No	CP1 / TP1, CP2 / TP2	Ninguno	Orden causal + Orden total discontinua	Vector de estado
GOTO [6] (REDUCIR, CoWord , CoPPT, CoMaya)	TI y ET	sí	No	Ninguno	CP1 / TP1, CP2 / TP2	Orden causal	Vector de estado
AnyUndo [8] (REDUCIR, CoWord , CoPPT, CoMaya)	TI y ET	No	Deshacer cualquier operación	IP2, IP3, RP	IP1, CP1 / TP1, CP2 / TP2	Orden causal	Vector de estado
SCOP [26] (AGRADABLE)	ESO	sí	No	CP2 / TP2	CP1 / TP1	Orden causal + servidor de transformación central	Escalar
COT [27] (REDUCIR, CoWord , CoPPT, CoMaya)	ESO	sí	Deshacer cualquier operación	CP2 / TP2, IP2, IP3	CP1 / TP1, (no ET, por lo tanto no es necesario IP1)	Orden causal + Orden total discontinua	Vector de contexto
TIBOT [31]	ESO	sí	No	CP2 / TP2	CP1 / TP1	Orden causal	Escalar
SOCT4 [13]	Transformación hacia adelante (TI)	sí	No	CP2 / TP2	CP1 / TP1	Orden causal + Orden total continua	Escalar
SOCT2 [30]	Transformación hacia adelante (TI) y transformación hacia atrás (ET)	sí	No	Ninguno	CP1 / TP1, CP2 / TP2, RP	Orden causal	Vector de estado
MOT2 [32]	Transformación hacia adelante (TI)	sí	No	??	CP1 / TP1, CP2 / TP2	??	escalar

Un orden total continuo es un orden total estricto donde 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" descritos anteriormente. Sus enfoques difieren de los enumerados en la tabla. Usan 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 relación de "admisibilidad". Estas condiciones están garantizadas por el procedimiento de control y las funciones de transformación de forma sinérgica. No es necesario discutir TP1 / TP2 en su trabajo. Por lo tanto, no se enumeran en la tabla anterior.

Existen algunos otros algoritmos de control de coherencia optimistas que buscan formas alternativas de diseñar algoritmos de transformación, pero no se ajustan bien a la taxonomía y caracterización anteriores. Por ejemplo, marcar y retroceder ^[33]

Los problemas de corrección de OT llevaron a la introducción de esquemas post-OT sin transformación, como WOOT, ^[34] Logoot ^[35] y Causal Trees (CT). ^[36] 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 OT

Si bien el enfoque clásico de TO de definir operaciones a través de sus compensaciones en el texto parece ser simple y natural, los sistemas distribuidos del mundo real plantean problemas serios. Es decir, que las operaciones se propagan con 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 carácter (insertar y eliminar)". ^[37]

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 tomó 2 años para escribir y si lo reescribimos hoy, tomaría casi el mismo tiempo para escribir una segunda vez ". ^[38] Pero luego enmienda su comentario con "Ya no creo que Wave tardaría 2 años en implementarse ahora, principalmente debido a los avances en los marcos web y los navegadores web". ^[39]

Para que OT funcione, se debe capturar cada cambio en los datos: "Obtener una instantánea del estado suele ser trivial, pero capturar 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 . ^[40]

Otra alternativa a OT es el uso de tipos de secuencia de tipos de datos replicados sin 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 de OT" . Archivado desde el original el 23 de junio de 2020.
2. Ellis, CA; 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 .
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". ACM Trans. Computación-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 Jupiter" . 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 grupo en tiempo real: problemas, algoritmos y logros . Actas de la conferencia ACM de 1998 sobre trabajo cooperativo apoyado por computadoras. ACM Press Nueva York, NY, EE. UU. págs. 59–68.
7. "SIGCE - un grupo de interés especial internacional sobre 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. Sun (2002). "Deshacer como inverso concurrente en editores de grupo" . ACM Trans. Computación-Hum. Interactuar . 9 (4): 309–361. doi : 10.1145 / 586081.586085 . S2CID 47453660 . 
9. Du Li; Rui Li (2004). Conservación de la relación de los efectos de la operación en los editores de grupo . Actas de la Conferencia ACM CSCW'04 sobre trabajo cooperativo asistido por computadora. ACM Press Nueva York, NY, EE. UU. págs. 457–466.
10. Rui Li; Du Li (2007). "Un nuevo marco de transformación operativa para editores de grupo en tiempo real" . Transacciones IEEE en sistemas paralelos y distribuidos . Transacciones IEEE en sistemas paralelos y distribuidos. 18 (3): 307–319. doi : 10.1109 / TPDS.2007.35 . S2CID 18822760 . 
11. Rui Li; Du Li (2005). Control de simultaneidad basado en conmutatividad en software colaborativo . Actas de la Primera Conferencia IEEE sobre Computación Colaborativa: Redes, Aplicaciones y Uso Compartido (CollaborateCom'05).
12. Prakash, Atul y Knister, Michael J. (1994). "Un marco para deshacer acciones en sistemas colaborativos". ACM Trans. Computación-Hum. Interactuar . 1 (4): 295–330. CiteSeerX 10.1.1.51.4793 . doi : 10.1145 / 198425.198427 . S2CID 10705127 .  
13. Vidot, N .; Carrito, M .; Ferrie, J .; Suleiman, M. (2000). Copia la convergencia en un entorno colaborativo distribuido en tiempo real (PDF) . Actas de la conferencia ACM 2000 sobre trabajo cooperativo apoyado por computadora. ACM Press Nueva York, NY, EE. UU. 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 colaborativo de textos . Proc. de la ACM Conf. 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 ACM Conf. 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 2002 sobre trabajo cooperativo apoyado por computadora. Nueva Orleans, Luisiana, Estados Unidos. págs. 58–67. doi : 10.1145 / 587078.587088 .
17. Claudia-Lavinia Ignat; Moira C. Norrie (2003). Editor colaborativo personalizable que se basa 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" . ACM Trans. Computación-Hum. Interactuar . 13 (4): 531–582. doi : 10.1145 / 1188816.1188821 . S2CID 14184705 . 
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). La operación se transforma en 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. C. Sun y R. Sosic (1999). Bloqueo opcional integrado con transformación operativa en editores de grupo distribuidos en tiempo real . En Proc. del 18º Simposio ACM sobre Principios de Computación Distribuida. págs. 43–52.
23. Begole, James y Rosson, Mary Beth y Shaffer, Clifford A. (1999). "Transparencia de colaboración flexible: apoyo a la independencia del trabajador en sistemas de uso compartido de aplicaciones replicados". ACM Trans. Computación-Hum. Interactuar . 6 (2): 95-132. CiteSeerX 10.1.1.23.1185 . doi : 10.1145 / 319091.319096 . S2CID 17895848 .  
24. Li, Du y Li, Rui (2002). Intercambio e interoperación transparente de aplicaciones heterogéneas de un solo usuario . CSCW '02: Actas de la conferencia ACM 2002 sobre trabajo cooperativo apoyado por computadora. Nueva Orleans, Estados Unidos. págs. 246-255.
25. Li, Du y Lu, Jiajun (2006). Un enfoque ligero para el intercambio transparente de editores de usuario único familiares . CSCW '06: Actas de la conferencia del vigésimo aniversario de 2006 sobre trabajo cooperativo apoyado por computadora. Banff, Alberta, Canadá. págs. 139-148. doi : 10.1145 / 1180875.1180896 .
26. Shen, Haifeng y Sun, Chengzheng (2002). Notificación flexible para sistemas colaborativos . CSCW '02: Actas de la conferencia ACM 2002 sobre trabajo cooperativo apoyado por computadora. págs. 77–86. doi : 10.1145 / 587078.587090 .
27. 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 . 
28. 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) . Procs. 2do Intl. Conf. En Computación Colaborativa: Redes, Appln. Y trabajo compartido . Consultado el 26 de julio de 2007 .
29. M. Ressel y R. Gunzenhauser (1999). Reducir los problemas de deshacer en grupo . Proc. de la ACM Conf. sobre apoyo al trabajo en grupo. págs. 131-139.
30. Suleiman, M .; Carrito, M .; Ferrié, 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 .
31. R. Li, D. Li y C. Sun (2004). Un algoritmo de control de coherencia basado en intervalos de tiempo para aplicaciones de software colaborativo interactivo . ICPADS '04: Actas de los sistemas paralelos y distribuidos, Décima Conferencia Internacional. pag. 429. doi : 10.1109 / ICPADS.2004.12 .
32. M. Carro, Jean Ferrié (2007). Sincronizador basado en transformación operativa para entornos P2P (PDF) . Actas de la 3ª Conferencia Internacional sobre Computación Colaborativa: Redes, Aplicaciones y Trabajo Compartido. págs. 127-138 . Consultado el 26 de julio de 2007 .
33. 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 el trabajo grupal de apoyo. págs. 264-273. doi : 10.1145 / 1099203.1099250 .
34. Imine, Abdessamad y Molli, Pascal y Oster, Gerald y Urso, Pascal (2005). Editores de grupo en tiempo real sin transformación operativa . Informe de investigación de INRIA RR-5580. pag. 24.
35. Stephane Weiss y Pascal Urso y Pascal Molli (2010). "Logoot-Undo: Sistema de edición colaborativo distribuido en redes P2P" . Transacciones IEEE en sistemas paralelos y distribuidos . Transacciones IEEE en sistemas paralelos y distribuidos. 21 (8): 1162. doi : 10.1109 / TPDS.2009.173 . S2CID 14172605 . 
36. Victor Grishchenko (2010). Hipertexto profundo con control de revisión integrado implementado en expresiones regulares (PDF) . Las Actas del VI Simposio Internacional sobre Wikis y Colaboración Abierta (WikiSym '10) . Archivado desde el original (PDF) el 2012-03-09 . Consultado el 30 de junio de 2010 .
37. Du Li y Rui Li (2010). "Un marco de transformación operacional basado en la admisibilidad para sistemas de edición colaborativos" . Trabajo cooperativo asistido por computadora (CSCW) . Trabajo cooperativo asistido por computadora. 19 (1): 1–43. doi : 10.1007 / s10606-009-9103-1 . S2CID 35748875 . 
38. "ShareJS" . 2011-11-06. Archivado desde el original el 11 de mayo de 2012 . Consultado el 16 de agosto de 2013 .
39. "¡Sí, ese soy yo! Por lo que vale, ya no creo que esa ola tardaría 2 años ... | Hacker News" . news.ycombinator.com . Consultado el 13 de febrero de 2019 .
40. Neil Fraser (enero de 2009). "Sincronización diferencial" .

enlaces externos

• Preguntas frecuentes de TO: 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 colaborativos
• Sistema distribuido en línea: edición colaborativa
• Explicación simple 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