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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Операциональное преобразование (ОП) представляет собой технологию для поддержки целого ряда функциональных возможностей сотрудничества в передовых системах 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). С тех пор, 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) или T(op_1,op_2), которая преобразует операцию Oa перед другой операцией Ob таким образом, что учитывается (включается) фактическое влияние Ob; и
  • другая — исключающее преобразование Exclusion Transformation (или обратное преобразование): ET (Oa, Ob) или T^{-1}(op_1,op_2), которая преобразует операцию Oa перед другой операцией Ob таким образом, что влияние Ob фактически исключается (не учитывается).

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

T(ins(p_1,c_1,sid_1),ins(p_2,c_2,sid_2)) :-
  if (p_1 < p_2) return ins(p_1,c_1,sid_1)
  else if (p_1=p_2 and sid_1 < sid_2) return ins(p_1,c_1,sid_1)
  else return ins(p_1+1,c_1,sid_1)
T^{-1}(ins(p_1,c_1,sid_1),ins(p_2,c_2,sid_2)) :-
  if (p_1 < p_2) return ins(p_1,c_1,sid_1)
  else if (p_1=p_2 and sid_1 < sid_2) return ins(p_1,c_1,sid_1)
  else return ins(p_1-1,c_1,sid_1)

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

Свойства инверсии[править | править вики-текст]

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

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

Алгоритмы управления (интеграции) ОП[править | править вики-текст]

Разнообразные алгоритмы управления ОП были разработаны для систем ОП с различными возможностями и для разных приложений. Сложность разработки алгоритма управления ОП определяется несколькими факторами. Ключевым различающим фактором того или иного алгоритма является способность поддерживать управление параллельным выполнением (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 представляет собой инструмент для 3D дизайна, основанный на Autodesk Maya, для совместной работы в режиме реального времени
  • Веб-приложения*
    • Google Wave использует ОП как часть Google Wave Federation Protocol [17]. Aлгоритм ОП в Google Wave базируется на коде Jupiter [4]
    • Etherpad является бесплатным веб-ориентированным редактором для совместной работы несколькими группами участников. Доступна коммерческая версия для работы в интрасетях
  • Системы управления версиями
    • So6 [32] является бесплатной системой управления версиями с открытым исходным кодом, интегрированной в платформу LibreSource.

Дополнительные ресурсы онлайн[править | править вики-текст]

См. также[править | править вики-текст]

Внешние ссылки[править | править вики-текст]

Ссылки[править | править вики-текст]

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