Операциональное преобразование

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

Операциональное преобразование (ОП) представляет собой технологию для поддержки целого ряда функциональных возможностей сотрудничества в передовых системах groupware. ОП было изначально придумано для поддержания согласованности и concurrency control при совместном редактировании простых текстовых документов. Два десятилетия исследований дополнили его возможности и расширили его приложения, включающие групповое undo, блокировку, разрешение конфликтов, уведомления и компрессию операций, выработку осознания работы в группе, редактирование HTML/XML и древовидных документов, совместных офисных высокопроизводительных инструментов, совместно-разделяемых приложений и совместных инструментов для дизайна компьютерно-ориентированных медиа. Недавно ОП было применено в качестве технологического ядра в Google Wave, благодаря его возможностям при совместной работе, что выводит ОП на новый уровень приложений, базирующихся на веб-технологиях.

История

Впервые концепцию Операционального Преобразования разработали С. Эллис, С. Гиббс [1] в системе GROVE (GRoup Outtie Viewing Edit) в 1989 году. Несколько лет спустя были определены некоторые вопросы корректности и несколько независимых подходов [2][3][4][5] решения этих вопросов, которые привели к следующему десятилетию продолжающихся усилий расширения и улучшения ОП сообществом посвященных этому исследователей. В 1998 году для развития связей и сотрудничества между исследователями СР и ОП была создана Группа Особого Интереса в Совместном Редактировании — Special Interest Group of Collaborative Editing (SIGCE) Архивировано 24 декабря 2012 года.. С тех пор SIGCE проводит ежегодные семинары по СР в ходе основных конференций CSCW (Компьютерная Поддержка Совместной Работы), таких как ACM CSCW, GROUP и ECSCW.

Архитектура системы

Системы для совместной работы используют ОП, как правило, воспроизводя архитектуру для хранения общих документов, чтобы обеспечить достаточное время отклика в средах с высокой латентностью, таких как Интернет. Общие документы копируются в локальное хранилище каждого сайта совместной работы, так что операции редактирования сразу же могут выполняться на локальных сайтах, а затем передаются удаленным сайтам. Операции редактирования с удаленных сайтов, приходящие на локальный сайт, уже как правило преобразованы и затем применены. Преобразование гарантирует, что критерий согласованности, зависящий от приложения, будет достигаться на всех сайтах. Свободное от блокировок, свойство неблокируемости ОП делает локальное время отклика не чувствительным к сетевым задержкам. В результате, ОП очень хорошо подходят для осуществления возможностей совместной работы, такой как групповое редактирование в Веб/Интернет контексте.

Основы

Основной идеей ОП
Основной идеей ОП

Основная идея ОП может быть проиллюстрирована на примере сценария редактирования простого текста следующим образом: Дан текстовый документ со строкой "abc", реплицированный на двух сайтах совместной работы; а также две одновременных операции:

  1. O1 = Insert[0, "x"] (вставить символ "x" в позиции "0")
  2. O2 = Delete[2, "c"] (удалить символ "c" в позиции "2")

генерируемые двумя пользователями на сайтах совместной работы 1 и 2, соответственно. Предположим, что две операции выполняются в следующем порядке: сначала O1 и затем O2 (на сайте 1). После выполнения O1 текст в документе становится "xabc". Для выполнения O2 после O1, O2 должна быть уже преобразована относительно O1 и предстать в следующем виде: O2'= Delete[3, "c"], где параметр позиции увеличен на единицу в связи со вставкой символа "x" операцией O1. Выполнение O2' на "xabc" должно удалить правильный символ "c" и текст этого документа становится "xab". Если же выполнять операцию O2 без преобразования, тогда будет неправильно удален символ "b" вместо "c". Основной идеей ОП является преобразование (или изменение) параметров операций редактирования в согласии с эффектами выполнения в предыдущих одновременных операциях так, чтобы преобразованная операция могла сработать корректно и не нарушать согласованность в документе.

Модели согласованности

Одной из функциональностей ОП является поддержка средств согласованности в системах совместного редактирования. Сообществом исследователей был предложен целый ряд моделей согласованности, несколько из них являются общими для систем совместного редактирования, и несколько — специальными для алгоритмов ОП.

CC модель

В [1] для систем совместного редактирования потребовались два свойства согласованности:

  • Causality (Каузальность) или свойство старшинства по предшествованию: гарантирует, что порядок выполнения причинно-зависимых операций будет таким же, как их естественный причинно-следственный порядок, согласно процессу совместной работы. Каузальная связь между двумя операциями формально определяется соотношением Лампорта "happened-before". Если две операции каузально независимы, они являются параллельными. Две параллельных операции могут выполняться в различном порядке на двух разных копиях документов.
  • Сonvergence (Сходимость): гарантирует, что реплицированные копии общего документа будут идентичными на всех сайтах (то есть, все генерируемые операции будут выполнены на всех сайтах).

Так как параллельные операции могут быть выполнены в разном порядке и операции редактирования обычно не коммутативны, копии документа на различных сайтах могут отличаться (быть несовместимыми). Первый алгоритм ОП был предложен в [1] для достижения конвергенции в групповом текстовом редакторе; для хранения свойства старшинства использовался вектор состояния (или вектор часов в классических распределенных вычислениях).

CCI модель

CCI модель была предложена в качестве общего фреймворка для управления согласованностью в системах совместного редактирования [3][6]. Внутри CCI модели, сгруппированы вместе три свойства согласованности:

  • Сausality Preservation (Сохранность Каузальности): то же самое, что и свойство старшинства по предшествованию в CC модели.
  • Сonvergence: то же самое, что свойство конвергентности в CC модели.
  • Intention Preservation (Сохранность Намерения): гарантирует, что эффект выполнения операции в любом состоянии документа, будет таким же, как и намеревалось при выполнении операции. Намерение операции O определяется как эффект выполнения, который может быть достигнут путём применения O на состоянии документа, из которого О была сгенерирована.

CCI модель расширяет CC модель новым критерием: Сохранность Намерения. Существенная разница между конвергенцией и сохранностью намерения состоит в том, что первое всегда может быть достигнуто путём сериализации протокола, однако последнее не может быть достигнуто за счёт сериализации какого-либо протокола, если операции всегда будут выполняться в их первоначальных формах. Обеспечение свойства сохранности несериализуемого намерения являлось главной технической задачей. Обнаружилось, что ОП очень хорошо подходит для обеспечения конвергенции и сохранности намерения в системах совместного редактирования.

CCI модель не зависима от типов документов или моделей данных, видов операций, или вспомогательных технологий (ОП, мульти-версионность, сериализация, undo/redo). Она не предназначена для проверки правильности методов (например ОП), которые разрабатывались для конкретных данных и операционных моделей и для конкретных приложений. В [3] понятие сохранности намерения определялось и уточнялось на трёх уровнях: во-первых, оно было определено как исходное требование согласованности в системах совместного редактирования; во-вторых, оно была определено как операция, основанная на контексте условий пред- и пост-преобразования для исходных функций ОП; в-третьих, оно было определено как специфичная операция проверки критериев, которыми следует руководствоваться при разработке функций OП для двух простейших операций: строковые функции вставки и удаления в простых текстовых редакторах для совместной работы.

CSM модель

Условие сохранности намерения не было формально определено в CCI модели для целей формальных доказательств. В SDT [7] и LBT [8] подходах сделаны попытки формализовать альтернативные условия, которые могут быть использованы для доказательств. Модель согласованности, предложенная в этих двух подходах, состоит из следующих формальных условий:

  • Causality (Каузальность): определяет то же самое, что и в CC модели
  • Single-operation effects (Следствия выполнения одной операции): следствие от выполнения любой операции в любом состоянии выполнения достигает того же эффекта, что и в его исходном состоянии
  • Мulti-operation effects (Следствия выполнения нескольких операций): зависимость следствий любых двух операций поддерживаются и после того, как они оба будут выполнены в любых состояниях

CA модель

Приведенная выше CSM модель требует, чтобы в системе был определен общий порядок всех объектов. Следовательно, спецификация сводится к новым объектам, представляемым операциями вставки. Однако, спецификация общего порядка влечет за собой применение зависимых от приложения стратегий, таких как при разрыве связей для вставки (т.е., когда новые объекты вставляются двумя текущими операций в одну и ту же позицию). Таким образом, общий порядок становится зависимым от приложения. Более того, в функциях преобразования и процедуре управления алгоритма общий порядок должен сохраняться, что приводит к увеличению сложности времени/пространства алгоритма.

В качестве альтернативы, CA модель основывается на Admissibilty Theory [9] (Теории допустимости). CA модель включает в себя два аспекта:

  • Сausality (Каузальность): определяет то же самое, что и в CC модели
  • Аdmissibility (Допустимость): Вызов каждой операции является допустимым в своем состоянии исполнения, т.е. каждый вызов не должен нарушать каких-либо связанных следствий (построения объектов), которые были созданы более ранними вызовами.

Эти два условия подразумевают собой конвергенцию. Все кооперирущие между собой сайты сходятся в одном и том же состоянии, в котором имеется один и тот же набор объектов, что находятся в одном и том же порядке. Более того, порядок фактически определяет следствия операций, которые они генерируют. Поскольку два условия также вводят дополнительные ограничения на порядок объектов, они фактически имеют больший приоритет, чем конвергенция. CA модель и подходы к его дизайну/обоснованиям были разработаны в 2005 году в статье [9]. Это уже не требовало того, чтобы общий порядок объектов был определен в модели согласованности и поддерживался алгоритмом, что, соответственно, приводет к уменьшению сложности времени/пространства алгоритма.

Структура системы ОП

ОП представляет собой систему из нескольких компонентов. Одна установленная стратегия проектирования систем ОП [1][2][3][4][10][11] состоит в том, чтобы отделить высокоуровневые алгоритмы управления преобразованием (или интеграцией) от функций преобразования низкого уровня.

Разделение по функциональному назначению в системе ОП
Разделение по функциональному назначению в системе ОП

Алгоритм управления преобразованием связан с определением:

  1. Какая операция должна быть преобразована перед каузально-произошедшей новой операцией
  2. Порядка преобразований

Управляющий алгоритм вводит соответствующий набор функций преобразования, которые определяют, как преобразовать одну операцию перед другой в зависимости от типов операции, позиций и других параметров. Корректность распределения обязанностей этих двух уровней формально конкретизируется набором свойств и условий преобразования. Различные системы ОП с разными алгоритмами управления, функций и коммуникационными топологиями требуют поддержки разных наборов свойств преобразования. Разделение систем ОП на эти два уровня позволяет разрабатывать исходные управляющие алгоритмы, которые могут применяться для различных типов приложений с разными данными и операционными моделями.

Другой альтернативный подход предложен в [9].В этом подходе, алгоритм ОП является корректным, если он удовлетворяет двум формализованным критериям корректности:

  1. Сохранности каузальности
  2. Сохранности допустимости

До тех пор, пока система удовлетворяет этим двум критериям, после того, как все операции будут выполнены на всех сайтах, копии данных становятся конвергентными (с дополнительными ограничениями). Нет необходимости принудительно для достижения конвергентности вводить общий порядок выполнения. Их подход в основном заключается в том, чтобы сначала идентифицировать и подтвердить достаточные условия для нескольких функций преобразования, а затем разрабатывать процедуры контроля для обеспечения этих достаточных условий. Таким образом, процедуры управления и функции преобразования синергетически (совместно) достигают корректности, т.е. сохранности каузальности и допустимости. В этом подходе нет необходимости соблюдения критериев свойств преобразований, таких как, например, TP2, поскольку это не требует работы (включения) функций преобразования во всех возможных случаях.

Данные ОП и операционные модели

В каждой системе ОП существуют две основополагающие модели: модель данных, которая определяет, как операции адресуются к объектам данных в документе и операционная модель, которая определяет набор операций, которые могут быть непосредственно преобразовываться функциями ОП. Различные системы ОП могут иметь разные данные и операционные модели. Например, модель данных первой системы ОП [1] представляет собой единое линейное адресное пространство; а её операционная модель состоит из двух примитивных операций: посимвольная вставка и удаление. Базовая операционная модель была расширена третьей примитивной операцией обновления, для поддержки совместной обработки документов Word [12] и редактирования 3D моделей [13]. Базовая модель данных ОП была расширена в иерархию из нескольких областей с линейной адресацией [14][15], которая стала способна моделировать широкий спектр различных документов. В процессе адаптации данных, часто требуется спроецировать конкретно зависимые от применения модели данных на ОП-совместимые модели данных [16][17].

Для поддержки операций в системе ОП на уровне приложений, существуют два подхода:

  1. Подход с моделью исходных операций: который отталкивается в разработке функций преобразования от трёх примитивных операций: вставки, удаления и обновления [16]. Такой подход нуждается в работе по привязке процесса приведения применяемых операций к этим примитивным операциям. В этом подходе, операционная модель ОП является исходной, при этом одни и те же функции преобразования могут быть использованы для разных приложений.
  2. Подход с операционной моделью, зависящей от конкретного приложения: который отталкивается в разработке функций преобразования от каждой пары операций приложения [17][18]. В приложении с m различных операций, потребуется m x m функций преобразования, необходимых для поддержки этого приложения. В рамках этого подхода, функции преобразования являются зависимыми от конкретного приложения и не могут быть повторно использованы в других приложениях.

Функции ОП

Разнообразные функции ОП были разработаны для систем ОП с разными возможностями и использования в разных приложениях. Функции ОП, используемые в разных системах OП, могут называться по-разному, но все они могут быть классифицироваться по двум категориям:

  • одна — включающее преобразование Inclusion Transformation (или прямое преобразование): IT (Oa, Ob) или [math]\displaystyle{ T(op_1,op_2) }[/math], которая преобразует операцию Oa перед другой операцией Ob таким образом, что учитывается (включается) фактическое влияние Ob; и
  • другая — исключающее преобразование Exclusion Transformation (или обратное преобразование): ET (Oa, Ob) или [math]\displaystyle{ T^{-1}(op_1,op_2) }[/math], которая преобразует операцию Oa перед другой операцией Ob таким образом, что влияние Ob фактически исключается (не учитывается).

Например, рассмотрим строковую операцию ins(p, c, sid), где p — позиция вставки, с — вставляемый символ и sid — идентификатор на сайте, где сгенерирована операция. Мы можем написать следующую функцию преобразования: 

[math]\displaystyle{ T }[/math](ins([math]\displaystyle{ p_1,c_1,sid_1 }[/math]),ins([math]\displaystyle{ p_2,c_2,sid_2 }[/math])) :-
  if ([math]\displaystyle{ p_1 \lt  p_2 }[/math]) return ins([math]\displaystyle{ p_1,c_1,sid_1 }[/math])
  else if ([math]\displaystyle{ p_1=p_2 }[/math] and [math]\displaystyle{ sid_1 \lt  sid_2 }[/math]) return ins([math]\displaystyle{ p_1,c_1,sid_1 }[/math])
  else return ins([math]\displaystyle{ p_1+1,c_1,sid_1 }[/math])

[math]\displaystyle{ T^{-1} }[/math](ins([math]\displaystyle{ p_1,c_1,sid_1 }[/math]),ins([math]\displaystyle{ p_2,c_2,sid_2 }[/math])) :-
  if ([math]\displaystyle{ p_1 \lt  p_2 }[/math]) return ins([math]\displaystyle{ p_1,c_1,sid_1 }[/math])
  else if ([math]\displaystyle{ p_1=p_2 }[/math] and [math]\displaystyle{ sid_1 \lt  sid_2 }[/math]) return ins([math]\displaystyle{ p_1,c_1,sid_1 }[/math])
  else return ins([math]\displaystyle{ p_1-1,c_1,sid_1 }[/math])

Некоторые системы ОП используют обе функции: IT и ET, а некоторые используют только IT функцию. Сложность разработки функций ОП определяется различными факторами:

  • функциональностью системы ОП: поддерживает ли система ОП действия do (обеспечивает ли согласованность), undo, блокировок [19], информирования, разделения приложения другими пользователями [16][20][21][22] и т.д.;
  • корректностью характеристик ответных реакций в системе ОП: какие свойства преобразования вводятся (CP1/TP1, CP2/TP2, IP2, IP3, RP), используется ли ET;
  • операционной моделью системы ОП: является ли модель оперирования исходной (например, примитивные вставки, удаления, обновления), или зависимой от конкретного приложения (все операции целевого приложения); и
  • моделью данных системы OП: будут ли данные в каждой операции посимвольными (индивидуальными объектами), строковыми (последовательностями объектов), иерархическими, или иметь другие структуры.

Свойства преобразований

Для обеспечения корректности системы ОП определены разные варианты свойств преобразований. Эти свойства могут обслуживаться либо алгоритмом управления преобразования [3][4][11][17][23][24], либо функциями преобразования [25]. Различные конструкции системы ОП имеют разное распределение функций между этими компонентами. Ниже приведены спецификации этих свойств и требуемые ими предварительные условия.

Свойства конвергенции

Иллюстрация свойства TP1
Иллюстрация свойства TP2

Следующие два свойства имеют отношение к достижению конвергенции.

  • CP1/TP1: Для каждой пары одновременных операций [math]\displaystyle{ op_1 }[/math] и [math]\displaystyle{ op_2 }[/math] определённых для одного и того же состояния, функция преобразования [math]\displaystyle{ T }[/math] удовлетворяет свойству CP1/TP1 тогда и только тогда, когда: [math]\displaystyle{ op_1 \circ T(op_2,op_1) \equiv op_2 \circ T(op_1,op_2) }[/math], где [math]\displaystyle{ op_i \circ op_j }[/math] означает последовательность операций, содержащей [math]\displaystyle{ op_i }[/math] следующей за [math]\displaystyle{ op_j }[/math] и где [math]\displaystyle{ \equiv }[/math] означает эквивалентность двух последовательностей операций. Предварительные условия CP1/TP1: CP1/TP1 требуется только в том случае, если система ОП разрешает любым двух операциям выполняться в разном порядке.
  • CP2/TP2: Для каждых трёх одновременных операций [math]\displaystyle{ op_1, op_2 }[/math] и [math]\displaystyle{ op_3 }[/math] определённых для одного и того же состояния документа, функция преобразования [math]\displaystyle{ T }[/math] удовлетворяет свойству CP2/TP2 тогда и только тогда, когда: [math]\displaystyle{ T(op_3, op_1 \circ T(op_2,op_1)) = T(op_3, op_2 \circ T(op_1,op_2)) }[/math]. CP2/TP2 предусматривает тождество между двумя операциями, преобразованными относительно двух эквивалентных последовательностей операций: преобразование [math]\displaystyle{ op_3 }[/math] перед последовательностью операции [math]\displaystyle{ op_2 }[/math] следующей за [math]\displaystyle{ T(op_1,op_2) }[/math] должно давать такую же операцию, как и преобразование [math]\displaystyle{ op_3 }[/math] перед последовательностью, сформированную из [math]\displaystyle{ op_1 }[/math] и [math]\displaystyle{ T(op_2,op_1) }[/math]. Предварительные условия CP2/TP2: CP2/TP2 требуется только в том случае, если система ОП позволяет двум операциям [math]\displaystyle{ op_1 }[/math] и [math]\displaystyle{ op_2 }[/math] быть IT-преобразоваными в два разных состояниях документа (или контекста).

Свойства инверсии

Следующие три свойства имеют отношение к достижению требуемого эффекта групповой отмены. Этими свойствами являются:

  • IP1: При любом состоянии документа [math]\displaystyle{ S }[/math] и последовательности [math]\displaystyle{ op \circ \overline{op} }[/math], мы имеем тождество [math]\displaystyle{ S \circ op \circ \overline{op} = S }[/math], которое означает, что последовательность [math]\displaystyle{ op \circ \overline{op} }[/math] эквивалентна единственной идентичности операции I в том, что касается воздействия на состояние документа. Это свойство требуется в системах ОП для обеспечения корректности эффекта групповой отмены, но не связано с функциями IT.
  • IP2: Свойство IP2 выражает то, что последовательность [math]\displaystyle{ op \circ \overline{op} }[/math] не оказывает никакого влияния на преобразование других операций. Функции преобразования удовлетворяют свойству IP2 тогда и только тогда, когда выполняется тождество [math]\displaystyle{ T(op_x, op \circ \overline{op})=op_x }[/math], которое означает, что результат преобразования [math]\displaystyle{ op_x }[/math] перед последовательностью [math]\displaystyle{ op \circ \overline{op} }[/math] эквивалентно результату преобразования [math]\displaystyle{ op_x }[/math] перед определяющей операцией I. Предварительные условия IP2: IP2 требуется только в случае, если система ОП позволяет операциям [math]\displaystyle{ op_x }[/math] быть преобразованными перед парой операций действия и отмены [math]\displaystyle{ op \circ \overline{op} }[/math], один за другим.
  • IP3: Если заданы две одновременных операции [math]\displaystyle{ op_1 }[/math] и [math]\displaystyle{ op_2 }[/math], определяемые на одном и том же состоянии документа (или контекста), тогда [math]\displaystyle{ \overline{op_1}' = T(\overline{op_1}, T(op_2, op1)) }[/math] и [math]\displaystyle{ \overline{op_1'} = \overline{T(op_1, op_2)} }[/math]. Функции преобразования удовлетворяют свойству IP3 тогда и только тогда, когда выполняется тождество [math]\displaystyle{ \overline{op_1}' = \overline{op_1'} }[/math], которое означает, что преобразованная инверсия операции [math]\displaystyle{ \overline{op_1}' }[/math] эквивалентна инверсии преобразованной операции [math]\displaystyle{ \overline{op_1'} }[/math]. Предварительные условия IP3: IP3 требуется только в случае, если система ОП позволяет операции инверсии [math]\displaystyle{ \overline{op_1} }[/math] быть преобразованной перед операцией [math]\displaystyle{ op_2 }[/math], которая является одновременной и определяется на том же состоянии документа (или контекстно-эквивалентно) что и [math]\displaystyle{ op_1 }[/math].

Алгоритмы управления (интеграции) ОП

Разнообразные алгоритмы управления ОП были разработаны для систем ОП с различными возможностями и для разных приложений. Сложность разработки алгоритма управления ОП определяется несколькими факторами. Ключевым различающим фактором того или иного алгоритма является способность поддерживать управление параллельным выполнением (do), и/или групповой отменой (undo) [2][6][10][24][26]. Кроме того, разные схемы алгоритмов управления ОП допускают различные компромиссы в:

  • назначении обязанностей за обеспечением корректности между алгоритмом управления и функциями преобразования, и
  • сложном характере времени-пространства системы ОП.

Большинство существующих алгоритмов управления ОП для управления одновременным выполнением в качестве теоретической основы выбрали теорию каузальности/одновременности: каузально связанные операции должны выполняться в своем каузальном порядке; одновременные операции должны быть преобразованы до своего выполнения. Тем не менее, и это понятно, только одно условие одновременности выполнения не может охватить все условия преобразования в ОП [2][3][4][6][27] В недавней работе о теории контекста операций было предложено детально представить концепцию состояния документа, что может быть использовано для формального выражения условий преобразования ОП для поддержки разработки и верификации алгоритма управления ОП [24].

В нижеследующей таблице приводится обзор некоторых существующих алгоритмов управления/интеграции ОП

Алгоритмы (системы) управления/интеграции ОП Требуемые типы функций преобразования Поддержка на базе ОП действий (do) Поддержка на базе ОП отмены (undo) Преобразование свойств, поддерживаемых алгоритмом управления Преобразование свойств, поддерживаемых функциями преобразования Преобразование порядка и ограничения распространенности Представление меток времени
dOPT [1] (GROVE) T (IT) Да Нет Отсутствует CP1/TP1, CP2/TP2 Каузальный порядок Вектор состояния
selective-undo [10] (DistEdit) Transpose (IT и ET) Нет Выборочная отмена Не доступно CP1/TP1, CP2/TP2, RP, IP1, IP2, IP3 Каузальный порядок ??
adOPTed [2][26] (JOINT EMACS) LTransformation (IT) Да Хронологическая отмена IP2, IP3 CP1/TP1, CP2/TP2, IP1 Каузальный порядок Вектор состояния
Jupiter [4] xform (IT) Да Нет CP2/TP2 CP1/TP1 Каузальный порядок + центральный сервер преобразования Скалярные
ОП Google Wave [17] преобразование и композиция (IT) Да ?? CP2/TP2 CP1/TP1 Каузальный порядок + центральный сервер преобразования + протокол распространения stop'n'wait Скалярные
GOT [3] (REDUCE) IT и ET Да Нет CP1/TP1, CP2/TP2 Отсутствует Каузальный порядок + дискретный общий порядок Вектор состояния
GOTO [5] (REDUCE, CoWord, CoPPT, CoMaya) IT и ET Да Нет Отсутствует CP1/TP1, CP2/TP2 Каузальный порядок Вектор состояния
AnyUndo [6] (REDUCE, CoWord, CoPPT, CoMaya) IT и ET Нет Отмена любой операции IP2, IP3, RP IP1, CP1/TP1, CP2/TP2 Каузальный порядок Вектор состояния
SCOP [23] (NICE) IT Да Нет CP2/TP2 CP1/TP1 Каузальный порядок + центральный сервер преобразования Скалярное
COT [24] (REDUCE, CoWord, CoPPT, CoMaya) IT Да Отмена любой операции CP2/TP2, IP2, IP3 CP1/TP1, IP1 Каузальный порядок + дискретный общий порядок Вектор контекста
TIBOT [28] IT Да Нет CP2/TP2 CP1/TP1 Каузальный порядок Скалярные
SOCT4 [11] Прямое преобразование (IT) Да Нет CP2/TP2 CP1/TP1 Каузальный порядок + непрерывный общий порядок Скалярное
SOCT2 [27] Прямое преобразование (IT) и обратное преобразование (ET) Да Нет Отсутствует CP1/TP1, CP2/TP2, RP Каузальный порядок Вектор состояния
MOT2 [29] Прямое преобразование (IT) Да Нет ?? CP1/TP1 ?? ??

Непрерывный общий порядок является строгим общим порядком, который можно определить по отсутствию элементов, т.е. 1,2,3,4, ... представляет собой непрерывный общий порядок, а 1,2,3,5, ... не является непрерывным общим порядком.

Алгоритмы на основе преобразований, предложенные в [8][9] базируются на альтернативных моделях согласованности CSM и CA, описанных выше. Их подходы отличаются от тех, что перечислены в таблице. Для сохранности каузальности в них используется вектор временных меток. Другими условиями корректности является сохранность зависимости одно-/мульти- следствий операций или сохранность допустимости. Эти условия обеспечиваются совместной работой процедуры управления и функций преобразования. Рассматривать TP1/TP2 в их работе нет необходимости. Потому они не перечислены в таблице выше.

Существуют и некоторые другие алгоритмы управления оптимистического согласования, которые находят альтернативные методы для разработки алгоритмов преобразования, но не вписываются в приводимую выше таксономию и описания характеристик. Они перечислены ниже:

  • Маркировка и возврат [30]

Программное обеспечение ОП

  • Совместные редакторы простого текста (одномерные документы)
    • Subethaedit (коммерческое)
    • Ace (бесплатное, с открытым исходным кодом)
    • Gobby (бесплатное, с открытым исходным кодом)
    • MoonEdit (бесплатное для некоммерческого использования, с открытым исходным кодом)
    • ICT [21][22] представляет собой исследовательский прототип, который подходит для любой команды редактирования любого (текстового) редактора.Его управление согласованностью основывается на сочетании различий и операционального преобразования.
  • Совместные высокопроизводительные приложения (двумерные документы)
    • CoWord [31] представляет собой текстовый процессор, основанный на Microsoft Word, для совместной работы в режиме реального времени
    • CoPowerPoint представляет собой редактор презентаций, основанный на Microsoft PowerPoint, для совместной работы в режиме реального времени
  • Совместные инструменты для компьютерного медиа-дизайна (трехмерные документы)
    • CoMaya Архивная копия от 22 сентября 2009 на Wayback Machine представляет собой инструмент для 3D дизайна, основанный на Autodesk Maya, для совместной работы в режиме реального времени
  • Веб-приложения*
    • Google Wave использует ОП как часть Google Wave Federation Protocol [17]. Aлгоритм ОП в Google Wave базируется на коде Jupiter [4]
    • Etherpad Архивная копия от 1 ноября 2012 на Wayback Machine является бесплатным веб-ориентированным редактором для совместной работы несколькими группами участников. Доступна коммерческая версия для работы в интрасетях
  • Системы управления версиями
    • So6 [32] является бесплатной системой управления версиями с открытым исходным кодом, интегрированной в платформу LibreSource.

Дополнительные ресурсы онлайн

Внешние ссылки

Ссылки

  1. ↑ 1,0 1,1 1,2 1,3 1,4 1,5 Ellis, C.A.; Gibbs, S.J. Concurrency control in groupware systems (неопр.) // ACM SIGMOD Record. — 1989. — Т. 18, № 2. — С. 399—407. — doi:10.1145/66926.
  2. ↑ 2,0 2,1 2,2 2,3 2,4 Ressel, Matthias and Nitsche-Ruhland, Doris and Gunzenh\"{a}user, Rul. An integrating, transformation-oriented approach to concurrency control and undo in group editors // CSCW '96: Proceedings of the 1996 ACM conference on Computer supported cooperative work. — 1996. — P. 288--297. — doi:10.1145/240080.240305.
  3. ↑ 3,0 3,1 3,2 3,3 3,4 3,5 3,6 Chengzheng Sun; Xiaohua Jia ; Yanchun Zhang ; Yun Yang ; David Chen. Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems (англ.) // ACM Trans. Comput.-Hum. Interact.[англ.] : journal. — 1998. — Vol. 5, no. 1. — P. 63—108. — doi:10.1145/274444.274447.
  4. ↑ 4,0 4,1 4,2 4,3 4,4 4,5 Nichols, D.A.; Curtis, P.; Dixon, M. & Lamping, J. (1995), High-latency, low-bandwidth windowing in the Jupiter collaboration system, Proceedings of the 8th annual ACM symposium on User interface and software technology: 111–120 
  5. ↑ 5,0 5,1 Sun, C. Operational transformation in real-time group editors: issues, algorithms, and achievements // Proceedings of the 1998 ACM conference on Computer supported cooperative work. — ACM Press New York, NY, USA, 1998. — P. 59-68.
  6. ↑ 6,0 6,1 6,2 6,3 C. Sun. Undo as concurrent inverse in group editors (англ.) // ACM Trans. Comput.-Hum. Interact.[англ.] : journal. — 2002. — Vol. 9. — P. 309——361. — doi:10.1145/586081.586085.
  7. ↑ Du Li. Preserving Operation Effects Relation in Group Editors // Proceedings of the ACM CSCW'04 Conference on Computer-Supported Cooperative Work. — ACM Press New York, NY, USA, 2004. — P. 457--466.
  8. ↑ 8,0 8,1 Rui Li; Du Li. [10.1109/TPDS.2007.35 A New Operational Transformation Framework for Real-Time Group Editors] (англ.) : journal. — IEEE Press, 2007. — Vol. 18(3). — P. 307——319.
  9. ↑ 9,0 9,1 9,2 9,3 Rui Li. Commutativity-Based Concurrency Control in Groupware // Proceedings of the First IEEE Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom'05). — 2005.
  10. ↑ 10,0 10,1 10,2 Prakash, Atul and Knister, Michael J. A framework for undoing actions in collaborative systems (англ.) // ACM Trans. Comput.-Hum. Interact.[англ.] : journal. — 1994. — Vol. 1. — P. 295——330. — doi:10.1145/198425.198427.
  11. ↑ 11,0 11,1 11,2 Vidot, N. Copies convergence in a distributed real-time collaborative environment // Proceedings of the 2000 ACM conference on Computer supported cooperative work. — ACM Press New York, NY, USA, 2000. — P. 171-180. Архивная копия от 12 октября 2004 на Wayback Machine
  12. ↑ D. Sun and S. Xia and C. Sun and D. Chen. Operational transformation for collaborative word processing // Proc. of the ACM Conf. on Computer-Supported Cooperative Work. — 2004. — P. 437-446.
  13. ↑ Agustina and F. Liu and S. Xia and H. Shen and C. Sun. CoMaya: Incorporating advanced collaboration capabilities into {3D} digital media design tools // Proc. of ACM Conf. on Computer-Supported Cooperative Work. — 2008. — P. 5-8.
  14. ↑ Davis, Aguido Horatio and Sun, Chengzheng and Lu, Junwei. Generalizing operational transformation to the standard general markup language // CSCW '02: Proceedings of the 2002 ACM conference on Computer supported cooperative work. — New Orleans, Louisiana, USA, 2002. — P. 58--67. — doi:http://doi.acm.org/10.1145/587078.587088[Ошибка: Неверный DOI!].
  15. ↑ Claudia-Lavinia Ignat. Customizable collaborative editor relying on treeOPT algorithm // ECSCW'03: Proceedings of the eighth conference on European Conference on Computer Supported Cooperative Work. — Kluwer Academic Publishers, 2003. — P. 315-334.
  16. ↑ 16,0 16,1 16,2 C.Sun, S.Xia, D.Sun, D.Chen, H.Shen, and W.Cai. Transparent adaptation of single-user applications for multi-user real-time collaboration (англ.) // ACM Trans. Comput.-Hum. Interact.[англ.] : journal. — 2006. — Vol. 13. — P. 531——582. — doi:10.1145/1188816.1188821.
  17. ↑ 17,0 17,1 17,2 17,3 17,4 Операциональное преобразование в Google Wave (недоступная ссылка — история ). (недоступная ссылка)
  18. ↑ Christopher R. Palmer. Operation transforms for a distributed shared spreadsheet // CSCW '98: Proceedings of the 1998 ACM conference on Computer supported cooperative work. — ACM Press, 1998. — P. 69-78.
  19. ↑ C. Sun and R. Sosic. Optional Locking Integrated with Operational Transformation in Distributed Real-Time Group Editors // In Proc. of the 18th ACM Symposium on Principles of Distributed Computing. — 1999. — P. 43-52.
  20. ↑ Begole, James and Rosson, Mary Beth and Shaffer, Clifford A. Flexible collaboration transparency: supporting worker independence in replicated application-sharing systems (англ.) // ACM Trans. Comput.-Hum. Interact.[англ.] : journal. — 1999. — Vol. 6. — P. 95——132. — doi:10.1145/319091.319096.
  21. ↑ 21,0 21,1 Li, Du and Li, Rui. Transparent sharing and interoperation of heterogeneous single-user applications // CSCW '02: Proceedings of the 2002 ACM conference on Computer supported cooperative work. — New Orleans, USA, 2002. — P. 246--255.
  22. ↑ 22,0 22,1 Li, Du and Lu, Jiajun. A lightweight approach to transparent sharing of familiar single-user editors // CSCW '06: Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work. — Banff, Alberta, Canada, 2006. — P. 139--148. — doi:10.1145/1180875.1180896.
  23. ↑ 23,0 23,1 {Shen, Haifeng and Sun, Chengzheng},. {Flexible notification for collaborative systems}, // {CSCW '02: Proceedings of the 2002 ACM conference on Computer supported cooperative work},. — {2002},. — P. {77--86},. — doi:{http://doi.acm.org/10.1145/587078.587090}[Ошибка: Неверный DOI!].
  24. ↑ 24,0 24,1 24,2 24,3 D. Sun and C. Sun. Context-based Operational Transformation for Distributed Collaborative Editing Systems (англ.) // IEEE Trans. on Parallel and Distributed Systems : journal. — 2009. Архивировано 12 июня 2009 года.
  25. ↑ Gerald Oster; Pascal Molli ; Pascal Urso ; Abdessamad Imine. Tombstone Transformation Functions for Ensuring Consistency in Collaborative Editing Systems (англ.) // Procs. 2nd Intl. Conf. on Collaborative Computing: Networking, Appln. and Worksharing : journal. — 2006.
  26. ↑ 26,0 26,1 M. Ressel and R. Gunzenhauser. Reducing the Problems of Group Undo // Proc. of the ACM Conf. on Supporting Group Work. — 1999. — P. 131-139.
  27. ↑ 27,0 27,1 Suleiman, M. Concurrent Operations in a Distributed and Mobile Collaborative Environment // Proceedings of the Fourteenth International Conference on Data Engineering, February. — 1998. — P. 23-27.
  28. ↑ R. Li, D. Li and C. Sun. A Time Interval Based Consistency Control Algorithm for Interactive Groupware Applications // ICPADS '04: Proceedings of the Parallel and Distributed Systems, Tenth International Conference. — 2004. — P. 429. — doi:10.1109/ICPADS.2004.12.
  29. ↑ M. Cart, Jean Ferrié,. Synchronizer Based on Operational Transformation for P2P Environments (англ.) : journal. — 2006.
  30. ↑ Gu, Ning and Yang, Jiangming and Zhang, Qiwei. Consistency maintenance based on the mark \& retrace technique in groupware systems // GROUP '05: Proceedings of the 2005 international ACM SIGGROUP conference on Supporting group work. — 2005. — P. 264--273. — doi:10.1145/1099203.1099250.
  31. ↑ Xia, Steven and Sun, David and Sun, Chengzheng and Chen, David and Shen, Haifeng. Leveraging single-user applications for multi-user collaboration: the coword approach // CSCW '04: Proceedings of the 2004 ACM conference on Computer supported cooperative work. — ACM, 2004. — P. 162--171. — doi:http://doi.acm.org/10.1145/1031607.1031635[Ошибка: Неверный DOI!].
  32. ↑ Pascal Molli. Using the transformational approach to build a safe and generic data synchronizer // Proceedings of the 2003 international ACM SIGGROUP conference on Supporting group work. — ACM Press New York, NY, USA, 2003. — P. 212-220.
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Операциональное_преобразование&oldid=5903881