Transformación Operativa

La Transformación Operativa es una técnica en la construcción de sistemas de software colaborativos. Dicha tecnología nos sirve para aplicar control de concurrencia optimista en entornos de edición colaborativa. Con todo ello nos permitirá una variedad de funcionalidades de colaboración en sistemas software colaborativos avanzados.

Esta estrategia transforma las operaciones concurrentes para que, aplicadas a estados intermedios (que posiblemente sean inconsistentes), den como resultado un estado final consistente.

Historia

La Transformación Operativa fue iniciada por C. Ellis y S. Gibbs en 1989 en el sistema GROVE (Group Outline Viewing Edit). Varios años más tarde, se identificaron una serie de problemas correctivos y se propusieron de forma independiente varios enfoques para abordar estos problemas, seguidos de otra década de esfuerzos constantes por parte de una comunidad de investigadores dedicados para ampliar y mejorar la Transformación Operativa (TO). En 1998, se estableció un Grupo de interés especial sobre Edición Colaborativa para facilitar la comunicación y la colaboración entre los investigadores de EC y TO. Desde entonces, SIGCE ha organizado talleres anuales de CE junto con las principales conferencias CSCW (Trabajo cooperativo asistido por computadora) como ACM, CSCW, GROUP y ECSCW.

Funcionamiento

Un funcionamiento básico de TO se puede ilustrar con un escenario de edición de texto simple de la siguiente manera. Dado un documento de texto con la cadena "abc" replicado en dos sitios colaboradores y dos operaciones simultáneas:

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

   

   Ejemplo Transformación Operativa

Estas operaciones se generan respectivamente en los sitios colaboradores 1 y 2.

Por ejemplo, si dos operaciones se generan en orden O1 y O2 (en el sitio 1). Tras ejecutar O1, el documento se convierte en "xabc". Para ejecutar O2 después de O1, O2 debe transformar O1 para convertirse en O2 '= Eliminar[3, "c"], cuyo parámetro posicional se incrementa en 1 ya que O1 insertó el carácter "x". Al ejecutar O2 ' en 'xabc' se elimina el carácter 'c' correcto y el documento se convierte en 'xab'.Sin embargo, si O2 se ejecuta sin transformarse previamente, eliminará por error el carácter "b" en lugar de "c".

La idea básica de TO es transformar (o ajustar) los parámetros de una operación de edición de acuerdo con el efecto de las operaciones concurrentes realizadas antes, para que la operación transformada logre el efecto correcto y mantenga la consistencia del documento.

Requisitos

Los requisitos de la Transformación Operativa son los siguientes:

• Convergencia: La totalidad de réplicas del documento han de ser iguales después de aplicar todas las operaciones.
• Consistencia: Las operaciones han de aplicarse en un mismo orden en la totalidad de los nodos

1. Basándose en la relación "sucede antes que"
2. No lo garantiza la Transformación Operativa. Por ejemplo, podremos usar una ordenación causal mediante relojes vectoriales.

• Intención: el efecto de realizar una operación ha de ser el mismo que el efecto que se buscaba en la réplica local sobre la que se aplica al inicio

1. Para conseguirlo, en cada nodo las operaciones han de transformarse según las operaciones que hayan ocurrido anteriormente.

Modelos de consistencia

Una función de TO es apoyar el mantenimiento de la consistencia en los sistemas de edición colaborativa. La comunidad de investigación ha propuesto varios modelos de coherencia, generalmente algunos de uso común en sistemas de edición colaborativa, mientras que otros son específicos de algoritmos TO.

El modelo CC

En el artículo de Ellis y Gibbs de 1989 "Control de concurrencia en sistemas de trabajo en grupo", un sistema de edición colaborativo requiere dos propiedades de consistencia:

• Preservación de causalidad: Asegura que las operaciones dependientes causalmente se ejecuten en el mismo orden que su orden causa-efecto natural durante el proceso cooperativo. La relación causal entre dos operaciones se define formalmente por la relación "sucedió antes" de Lamport. Cuando dos operaciones no tienen dependencia causal, son concurrentes. Se pueden realizar dos operaciones simultáneamente en diferentes órdenes en dos copias diferentes del documento.
• Convergencia: garantiza que las réplicas del documento compartido sean idénticas en todos los sitios estacionarios (es decir, todas las operaciones generadas se han realizado en todos los sitios).

Debido a que las operaciones simultáneas se pueden realizar en diferentes órdenes y las operaciones de edición generalmente no son conmutativas, las copias de documentos en diferentes ubicaciones pueden divergir (inconsistencias). El primer algoritmo TO se propuso en el artículo de Ellis y Gibbs para lograr la convergencia en un editor de texto grupal; los vectores de estado (o relojes de vectores en la computación distribuida clásica) se utilizan para preservar la propiedad de precedencia.

El modelo CCI

El modelo CCI se propone como gestión de consistencia en sistemas de edición colaborativa. En el modelo CCI se agrupan tres atributos de coherencia:

• Preservación de causalidad: Igual que en el modelo CC.
• Convergencia: Igual que el modelo CC.
• Preservación de la intención: garantiza que el efecto de una operación realizada 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 un efecto de ejecución que se puede lograr aplicando el O al estado del documento que produjo O.

El modelo CCI amplía el modelo CC con un nuevo estándar: 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 puede lograrse mediante un protocolo de serialización, pero la segunda puede no ser posible mediante ningún protocolo de serialización si las operaciones siempre se realizaron en sus forma originales. La implementación de propiedades de preservación de la intención no serializables siempre ha sido un gran desafío técnico. Se ha encontrado que la Transformación Operativa 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 del tipo de documento o modelo de datos, tipo de operación o técnica de soporte (TO, versiones múltiples, serialización, deshacer/rehacer). No está diseñado para la verificación de corrección de técnicas(p. ej., TO) que están diseñadas para datos específicos y modelos operativos y aplicaciones específicas. El concepto de preservación de la intención se define y refina en tres niveles:

1. Primero, se define como un requisito de consistencia genérico para los sistemas de edición colaborativa.
2. Segundo, se definió como condiciones previas y posteriores a la transformación basadas en el contexto de operación para funciones OT genéricas.
3. Tercero, se definió como criterio de verificación de operaciones específicas para guiar el diseño de funciones TO para dos operaciones primitivas: inserción y eliminación de cadenas, en editores colaborativos de texto sin formato.

El modelo CSM

Para propósitos de pruebas formales, las condiciones de preservación de la intención no se especifican formalmente en el modelo CCI. Los métodos SDT y LBT intentan formalizar condiciones alternativas que se pueden demostrar. El modelo de consistencia propuesto en estos dos enfoques incluye las siguientes condiciones formales:

• Causalidad: misma definición que en el modelo CC
• Efectos de operación simple: 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 operación múltiple: dos operaciones cualesquiera mantienen la relación de efectos después de que ambas operaciones se ejecuten en cualquier estado.

El modelo CA

El modelo CSM anterior requiere especificar el orden total de todos los objetos en el sistema. En efecto, la especificación se reduce a nuevos objetos introducidos por operaciones de inserción. Sin embargo, especificar un pedido total implica estrategias específicas de la aplicación, como romper los lazos de inserción (es decir, nuevos objetos insertados por dos operaciones actuales en la misma posición). Por lo tanto, el pedido total se vuelve específico de la aplicación. Además, en el algoritmo se ha de mantener el orden total en la función de transformación y en el proceso de control, lo que aumenta la complejidad espacio-temporal del algoritmo.

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

• Causalidad: 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 efecto (objeto de solicitud) establecida por invocaciones anteriores.

Estas dos condiciones implican convergencia. Todos los sitios que cooperan convergen en un estado en el que existe un mismo conjunto de objetos que están en el mismo orden. Además, la ordenación está determinada por los efectos de las operaciones cuando se generan. Dado que estas dos condiciones también imponen restricciones adicionales sobre el orden de los objetos, en realidad son más fuertes que la convergencia. El modelo CA y la metodología de diseño/prueba se detallan en un documento de 2005. Ya no requiere que el orden total de los objetos se especifique en el modelo de consistencia y se mantenga en el algoritmo, lo que reduce la complejidad de tiempo/espacio del algoritmo.

Referencias

1. Rodrigo Santamaría. Apuntes Sistemas Distribuidos Universidad de Salamanca. | Tema 8 - Replicación

• Datos: Q4335231