Операционная трансформация - Operational transformation

«Операция трансформации» перенаправляется сюда. Информацию о кросс-медиа-мероприятии см. Операция Трансформация (сериал).

Операционная трансформация (ОТ) - это технология для поддержки ряда функций совместной работы в расширенных программное обеспечение для совместной работы системы. Первоначально OT был изобретен для поддержания согласованности и контроль параллелизма в совместном редактировании текстовых документов. Его возможности были расширены, а его приложения расширены, включая групповую отмену, блокировку, разрешение конфликтов, уведомление об операциях и сжатие, поддержку групп, HTML / XML и редактирование документов с древовидной структурой, инструменты для совместной работы в офисе, совместное использование приложений и совместный компьютер. инструменты для медиа-дизайна.^[1] В 2009 году OT был принят в качестве ключевой технологии, лежащей в основе функций совместной работы в Apache Wave и Гугл документы.

История

Оперативная трансформация была начата К. Эллис и С. Гиббс^[2] в системе GROVE (GRoup Outline Viewing Edit) в 1989 году. Несколько лет спустя были выявлены некоторые проблемы с корректностью и несколько подходов^[3][4][5][6] были независимо предложены для решения этих проблем, после чего последовало еще одно десятилетие непрерывных усилий сообщества преданных своему делу исследователей по расширению и улучшению ОТ. В 1998 году Специальная группа по совместному редактированию^[7] был создан для развития коммуникации и сотрудничества между исследователями КЭ и ОТ. С тех пор SIGCE проводит ежегодные семинары CE вместе с крупными CSCW (Совместная работа при поддержке компьютера ) конференции, такие как ACM, CSCW, GROUP и ECSCW.

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

Системы совместной работы, использующие операционные преобразования, обычно используют хранилище реплицированных документов, где каждый клиент имеет свою собственную копию документа; клиенты работают со своими локальными копиями в без блокировки, неблокирующий образом, а затем изменения распространяются на остальных клиентов; это обеспечивает высокую скорость отклика клиента в среде с большой задержкой, такой как Интернет. Когда клиент получает изменения, распространенные от другого клиента, он обычно преобразует изменения перед их выполнением; преобразование гарантирует, что критерии согласованности, зависящие от приложения (инварианты ) поддерживаются всеми сайтами. Этот режим работы приводит к созданию системы, особенно подходящей для реализации функций совместной работы, таких как одновременное редактирование документов, в среде с высокой задержкой, такой как паутина.

Основы

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

1. O1 = Insert [0, «x»] (чтобы вставить символ «x» в позицию «0»)
2. O2 = Удалить [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». Основная идея OT состоит в том, чтобы преобразовать (или настроить) параметры операции редактирования в соответствии с эффектами ранее выполненных параллельных операций, чтобы преобразованная операция могла достичь правильного эффекта и поддерживать согласованность документа.

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

Одна из функций OT - поддерживать согласованность в системах совместного редактирования. В исследовательском сообществе был предложен ряд моделей согласованности, некоторые в основном для систем совместного редактирования, а некоторые специально для алгоритмов ОТ.

Модель CC

В статье Эллиса и Гиббса 1989 г. «Управление параллелизмом в системах коллективного пользования»,^[2] Для систем совместного редактирования требуются два свойства согласованности:

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

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

Модель CCI

Модель CCI была предложена для управления согласованностью в системах совместного редактирования.^[4][8] В модели CCI три свойства согласованности сгруппированы вместе:

• CСохранение аузальности: то же, что и в модели CC.
• Cсовпадение: то же, что и в модели CC.
• яСохранение внимания: гарантирует, что эффект от выполнения операции на любое состояние документа будет таким же, как и намерение операции. Намерение операции O определяется как эффект выполнения, который может быть достигнут путем применения O к состоянию документа, из которого был сгенерирован O.

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

Модель CCI не зависит от типов документов или моделей данных, типов операций или поддерживающих технологий (OT, многовариантность, сериализация, отмена / повтор). Он не предназначался для проверки правильности методов (например, OT), которые разработаны для конкретных данных и операционных моделей, а также для конкретных приложений. В,^[4] понятие сохранения намерения было определено и уточнено на трех уровнях: во-первых, оно было определено как общее требование согласованности для систем совместного редактирования; Во-вторых, это было определено как условия до и после преобразования на основе контекста операции для общих функций OT; В-третьих, он был определен как конкретный критерий проверки операции для руководства проектированием функций ОТ для двух примитивных операций: строковой вставки и удаления в совместных текстовых редакторах.

Модель CSM

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

• Cаузальность: то же определение, что и в модели CC
• Sоднократные эффекты: эффект от выполнения любой операции в любом состоянии выполнения достигает того же эффекта, что и в состоянии его генерации
• Mсверхоперационные эффекты: отношение эффектов любых двух операций сохраняется после того, как они обе выполняются в любом состоянии

Модель CA

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

В качестве альтернативы CA модель основана на теория допустимости.^[11] Модель CA включает два аспекта:

• Cаузальность: то же определение, что и в модели CC
• Адопустимость: Вызов каждой операции допустим в состоянии ее выполнения, т.е. каждый вызов не должен нарушать какое-либо отношение эффектов (упорядочение объектов), которое было установлено предыдущими вызовами.

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

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

ОТ - это система из нескольких компонентов. Единая устоявшаяся стратегия проектирования систем ОТ^{[2][3][4][5][12][13]} состоит в том, чтобы отделить высокоуровневые алгоритмы управления преобразованием (или интеграции) от функций преобразования нижнего уровня.

Алгоритмы управления ОТ (определить, какие операции преобразуются относительно других в соответствии с их отношениями параллелизма / контекста)

Свойства и условия ОТ (разделите обязанности между алгоритмами и функциями)

Функции преобразования ОТ (определить, как преобразовать пару примитивных операций в соответствии с типами операций, позициями и другими параметрами)

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

1. Какую операцию следует преобразовать в причинно готовую новую операцию
2. Порядок преобразований

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

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

1. Сохранение причинно-следственной связи
2. Сохранение допустимости

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

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

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

Существует два подхода к поддержке операций на уровне приложений в системе OT:

1. Подход к общей модели операций: разработка функций преобразования для трех примитивных операций: вставки, удаления и обновления.^[19] Этот подход требует процесса адаптации операций для сопоставления операций приложения с этими примитивными операциями. В этом подходе операционная модель OT является общей, поэтому функции преобразования можно повторно использовать для различных приложений.
2. Подход к модели операций для конкретного приложения: который заключается в разработке функций преобразования для каждой пары операций приложения.^[20][21] Для приложения с m различными операциями необходимо m x m функций преобразования для поддержки этого приложения. В этом подходе функции преобразования зависят от приложения и не могут быть повторно использованы в других приложениях.

OT функции

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

• Преобразование включения (или прямое преобразование): IT (Oa, Ob) или ${displaystyle T(op_{1},op_{2})}$, который преобразует операцию Oa в другую операцию Ob таким образом, что влияние Ob эффективно учитывается.
• Преобразование исключения (или обратное преобразование): ET (Oa, Ob) или ${displaystyle T^{-1}(op_{1},op_{2})}$, который преобразует операцию Oa в другую операцию Ob таким образом, что влияние Ob эффективно исключено.

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

T (ins (${displaystyle p_{1},c_{1},sid_{1}}$), ins (${displaystyle p_{2},c_{2},sid_{2}}$)) :- если (${displaystyle p_{1}<p_{2}}$) return ins (${displaystyle p_{1},c_{1},sid_{1}}$) иначе, если (${displaystyle p_{1}=p_{2}}$ и ${displaystyle sid_{1}<sid_{2}}$) return ins (${displaystyle p_{1},c_{1},sid_{1}}$) else return ins (${displaystyle p_{1}+1,c_{1},sid_{1}}$)

${displaystyle T^{-1}}$(ins (${displaystyle p_{1},c_{1},sid_{1}}$), ins (${displaystyle p_{2},c_{2},sid_{2}}$)) :- если (${displaystyle p_{1}<p_{2}}$) return ins (${displaystyle p_{1},c_{1},sid_{1}}$) иначе, если (${displaystyle p_{1}=p_{2}}$ и ${displaystyle sid_{1}<sid_{2}}$) return ins (${displaystyle p_{1},c_{1},sid_{1}}$) else return ins (${displaystyle p_{1}-1,c_{1},sid_{1}}$)

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

• функциональность системы OT: поддерживает ли система OT do (поддержание согласованности), отмену, блокировку,^[22] осведомленность, совместное использование приложений,^{[19][23][24][25]} так далее.;
• ответственность за правильность в системе ОТ: какие свойства трансформации (CP1 / TP1, CP2 / TP2, IP2, IP3, RP) соблюдать; используется ли ЕТ;
• операционная модель системы ОТ: является ли операционная модель ОТ общей (например, примитивная вставка, удаление, обновление) или специфичной для приложения (все операции целевого приложения); и
• модель данных системы ОТ: являются ли данные в каждой операции символьными (отдельный объект), строковыми (последовательность объектов), иерархическими или другими структурами.

Свойства трансформации

Выявлены различные свойства преобразования для обеспечения корректности системы ОТ. Эти свойства могут поддерживаться либо алгоритмом управления преобразованием^{[4][5][13][20][26][27]} или функциями преобразования.^[28] Различные конструкции систем ОТ имеют разное разделение ответственности между этими компонентами. Спецификации этих свойств и предварительные условия их требования приведены ниже.

Свойства сходимости

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

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

Следующие два свойства связаны с достижением сходимости.

• CP1 / TP1: Для каждой пары одновременных операций ${displaystyle op_{1}}$ и ${displaystyle op_{2}}$ определенная в том же состоянии, функция преобразования T удовлетворяет свойству CP1 / TP1 тогда и только тогда, когда: ${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 }$ обозначает эквивалентность двух последовательностей операций. Предварительное условие CP1 / TP1: CP1 / TP1 требуется только в том случае, если система OT позволяет выполнять любые две операции в разных порядках.
• CP2 / TP2: Для каждых трех одновременных операций ${displaystyle op_{1},op_{2}}$ и ${displaystyle op_{3}}$ определенная в том же состоянии документа, функция преобразования T удовлетворяет свойству CP2 / TP2 тогда и только тогда, когда: ${displaystyle T(op_{3},op_{1}circ T(op_{2},op_{1}))=T(op_{3},op_{2}circ T(op_{1},op_{2}))}$. CP2 / TP2 предусматривает равенство двух операций, преобразованных относительно двух эквивалентных последовательностей операций: преобразование ${displaystyle op_{3}}$ против последовательности операции ${displaystyle op_{2}}$ с последующим ${displaystyle T(op_{1},op_{2})}$ должен выполнять ту же операцию, что и преобразование ${displaystyle op_{3}}$ против последовательности, образованной ${displaystyle op_{1}}$ и ${displaystyle T(op_{2},op_{1})}$. Предварительное условие CP2 / TP2: CP2 / TP2 требуется только в том случае, если система OT допускает две операции ${displaystyle op_{1}}$ и ${displaystyle op_{2}}$ быть IT-преобразованным в двух разных состояниях документа (или контекстах).

Обратные свойства

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

• IP1: Для любого состояния документа S и последовательности ${displaystyle opcirc {overline {op}}}$, у нас есть ${displaystyle Scirc opcirc {overline {op}}=S}$, что означает последовательность ${displaystyle opcirc {overline {op}}}$ эквивалентен одной операции идентификации I в отношении воздействия на состояние документа. Это свойство требуется в системе OT для достижения правильного эффекта отмены, но не связано с функциями ИТ.
• IP2: Свойство IP2 выражает, что последовательность ${displaystyle opcirc {overline {op}}}$ не влияет на преобразование других операций. Функции преобразования удовлетворяют IP2 тогда и только тогда, когда: ${displaystyle T(op_{x},opcirc {overline {op}})=op_{x}}$, что означает, что результат преобразования ${displaystyle op_{x}}$ против последовательности ${displaystyle opcirc {overline {op}}}$ эквивалентно результату преобразования ${displaystyle op_{x}}$ против операции идентификации I. Предварительное условие IP2: IP2 требуется только в том случае, если системы OT допускают операцию ${displaystyle op_{x}}$ быть преобразованным в пару операций do и undo ${displaystyle opcirc {overline {op}}}$, по одному.
• IP3: Учитывая две одновременные операции ${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})}}}$. Функции преобразования удовлетворяют свойству IP3 тогда и только тогда, когда ${displaystyle {overline {op_{1}}}'={overline {op_{1}'}}}$, что означает, что преобразованная обратная операция ${displaystyle {overline {op_{1}}}'}$ равна операции, обратной преобразованной операции ${displaystyle {overline {op_{1}'}}}$. Предварительное условие IP3: IP3 требуется только в том случае, если система OT допускает обратную операцию ${displaystyle {overline {op_{1}}}}$ быть преобразованным против операции ${displaystyle op_{2}}$ который является параллельным и определен в том же состоянии документа, что (или контекстно эквивалентен) ${displaystyle op_{1}}$.

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

Для систем ОТ с разными возможностями и для разных приложений разработаны различные алгоритмы управления ОТ. Сложность разработки алгоритма управления ОТ определяется множеством факторов. Ключевым отличительным фактором является то, способен ли алгоритм поддерживать управление параллелизмом (do) и / или групповую отмену.^{[3][8][12][27][29]} Кроме того, разные конструкции алгоритмов управления ОТ имеют разные компромиссы в:

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

Большинство существующих алгоритмов управления OT для управления параллелизмом принимают теорию причинности / параллелизма в качестве теоретической основы: операции, связанные с причинностью, должны выполняться в их причинном порядке; параллельные операции должны быть преобразованы перед их выполнением. Однако было хорошо известно, что одно только условие параллелизма не может охватить все условия преобразования ОТ.^{[3][4][5][8][30]} В недавней работе была предложена теория операционного контекста для явного представления понятия состояния документа, которое может использоваться для формального выражения условий преобразования ОТ для поддержки проектирования и проверки алгоритмов управления ОТ.^[27]

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

Алгоритмы (системы) управления / интеграции ОТ	Требуемые типы функций преобразования	Поддержка Do на основе ОТ?	Поддерживать отмену на основе OT?	Свойства трансформации, поддерживаемые алгоритмом управления	Свойства преобразования, поддерживаемые функциями преобразования	Ограничения упорядочения преобразований и распространения	Отметка времени
dOPT[2] (РОЩА)	Т (IT)	да	Нет	Никто	CP1 / TP1, CP2 / TP2	Причинный порядок	Вектор состояния
выборочная отмена[12] (DistEdit)	Транспонировать (IT и ET)	Нет	Выборочная отмена	NA	CP1 / TP1, CP2 / TP2, RP, IP1, IP2, IP3	Причинный порядок	??
усыновленный[3][29] (ОБЪЕДИНЕННЫЙ EMACS)	LTransformation (IT)	да	Хронологическая отмена	IP2, IP3	CP1 / TP1, CP2 / TP2, IP1	Причинный порядок	Вектор состояния
Юпитер[5]	xform (IT)	да	Нет	CP2 / TP2	CP1 / TP1	Причинный порядок + Центральный сервер трансформации	Скалярный
Google Wave OT[20]	преобразование и композиция (IT)	да	Нет	CP2 / TP2	CP1 / TP1	Причинный порядок + центральный сервер трансформации + протокол распространения stop'n'wait	Скалярный
ПОЛУЧИЛ[4] (УМЕНЬШАТЬ)	IT и ET	да	Нет	CP1 / TP1, CP2 / TP2	Никто	Причинный порядок + прерывистый общий порядок	Вектор состояния
ИДТИ К[6] (УМЕНЬШАТЬ, CoWord, CoPPT, CoMaya)	IT и ET	да	Нет	Никто	CP1 / TP1, CP2 / TP2	Причинный порядок	Вектор состояния
AnyUndo[8] (УМЕНЬШАТЬ, CoWord, CoPPT, CoMaya)	IT и ET	Нет	Отменить любую операцию	IP2, IP3, RP	IP1, CP1 / TP1, CP2 / TP2	Причинный порядок	Вектор состояния
SCOP[26] (ОТЛИЧНО)	ЭТО	да	Нет	CP2 / TP2	CP1 / TP1	Причинный порядок + Центральный сервер трансформации	Скалярный
СОТ [27] (УМЕНЬШАТЬ, CoWord, CoPPT, CoMaya)	ЭТО	да	Отменить любую операцию	CP2 / TP2, IP2, IP3	CP1 / TP1, (нет ET, следовательно, IP1 не требуется)	Причинный порядок + прерывистый общий порядок	Вектор контекста
ТИБО [31]	ЭТО	да	Нет	CP2 / TP2	CP1 / TP1	Причинный порядок	Скалярный
SOCT4[13]	Прямое преобразование (ИТ)	да	Нет	CP2 / TP2	CP1 / TP1	Причинный порядок + Непрерывный общий порядок	Скалярный
SOCT2[30]	Прямая трансформация (IT) и обратная трансформация (ET)	да	Нет	Никто	CP1 / TP1, CP2 / TP2, RP	Причинный порядок	Вектор состояния
MOT2[32]	Прямое преобразование (ИТ)	да	Нет	??	CP1 / TP1, CP2 / TP2	??	скаляр

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

Алгоритмы на основе преобразований, предложенные в ^[10][11] основаны на альтернативных моделях согласованности «CSM» и «CA», как описано выше. Их подходы отличаются от приведенных в таблице. Они используют векторные метки времени для сохранения причинно-следственной связи. Другими условиями корректности являются сохранение отношения эффектов «одиночная -» / «множественная» или сохранение «допустимости». Эти условия обеспечиваются процедурой контроля и функциями трансформации в синергетическом режиме. Нет необходимости обсуждать TP1 / TP2 в их работе. Следовательно, они не перечислены в приведенной выше таблице.

Существуют и другие оптимистичные алгоритмы контроля согласованности, которые ищут альтернативные способы разработки алгоритмов преобразования, но не подходят для приведенной выше таксономии и характеристики. Например, Mark and Retrace^[33]

Проблемы корректности ОТ привели к внедрению пост-ОТ-схем без преобразований, таких как WOOT,^[34] Логоот^[35] и причинные деревья (CT).^[36] Схемы «Post-OT» разбивают документ на элементарные операции, но они обходят необходимость преобразования операций путем использования комбинации уникальных идентификаторов символов, временных меток векторов и / или надгробий.

Критика ОТ

В то время как классический подход ОТ к определению операций через их смещения в тексте кажется простым и естественным, в реальных распределенных системах возникают серьезные проблемы. А именно, что операции распространяются с конечной скоростью, состояния участников часто различны, поэтому результирующие комбинации состояний и операций чрезвычайно трудно предвидеть и понимать. Как выразились Ли и Ли: «Из-за необходимости учитывать сложное покрытие случаев формальные доказательства очень сложны и подвержены ошибкам даже для алгоритмов ОТ, которые обрабатывают только два посимвольных примитива (вставка и удаление)».^[37]

Точно так же Джозеф Джентл, бывший инженер Google Wave и автор библиотеки Share.JS, написал: «К сожалению, реализация OT - отстой. Существует миллион алгоритмов с различными компромиссами, в основном заключенных в академических статьях. […] Wave занял 2 года. чтобы написать, и если бы мы переписали его сегодня, это заняло бы почти столько же времени, чтобы написать второй раз ».^[38] Но позже он исправляет свой комментарий следующим образом: «Я больше не верю, что реализация этой волны займет 2 года - в основном из-за достижений в веб-фреймворках и веб-браузерах». ^[39]

Для работы OT необходимо фиксировать каждое изменение данных: «Получение моментального снимка состояния обычно тривиально, но фиксирование изменений - совсем другое дело. […] Богатство современных пользовательских интерфейсов может сделать это проблематичным, особенно в среде на основе браузера ". Альтернативой ОТ является дифференциальная синхронизация.^[40]

Другой альтернативой ОТ является использование последовательностей типов бесконфликтный реплицированный тип данных.

Смотрите также

• Синхронизация данных
• Совместные редакторы в реальном времени
• Бесконфликтные реплицированные типы данных
• Модели согласованности
• Оптимистичная репликация

Рекомендации

1. Вс, Чэнчжэн. «ОТ FAQ».
2. Ellis, C.A .; Гиббс, С.Дж. (1989). «Контроль параллелизма в системах коллективного пользования». Запись ACM SIGMOD. 18 (2): 399–407. CiteSeerX  10.1.1.465.2026. Дои:10.1145/67544.66963.
3. Рессель, Маттиас и Ницше-Руланд, Дорис и Гунценхойзер, Рул (1996). «Интегрирующий, ориентированный на преобразование подход к управлению параллелизмом и отмене в групповых редакторах». CSCW '96: Материалы конференции ACM 1996 года по совместной работе при компьютерной поддержке. С. 288–297. Дои:10.1145/240080.240305.
4. Чэнчжэн Сунь; Сяохуа Цзя; Янчунь Чжан; Юнь Ян; Дэвид Чен (1998). «Достижение сходимости, сохранения причинно-следственной связи и сохранения намерений в системах совместного редактирования в реальном времени». ACM Trans. Comput.-Hum. Взаимодействовать. 5 (1): 63–108. CiteSeerX  10.1.1.56.1251. Дои:10.1145/274444.274447.
5. Nichols, D.A .; Curtis, P .; Диксон, М .; Лэмпинг, Дж. (1995). «Управление окнами с высокой задержкой и низкой пропускной способностью в системе совместной работы Jupiter». Материалы 8-го ежегодного симпозиума ACM по пользовательскому интерфейсу и программным технологиям: 111–120. Архивировано из оригинал на 2015-11-30. Получено 2009-09-27.
6. Sun, C .; Эллис, К. (1998). «Оперативная трансформация в групповых редакторах реального времени: проблемы, алгоритмы, достижения». Материалы конференции ACM 1998 г. по совместной работе с компьютерной поддержкой. ACM Press Нью-Йорк, Нью-Йорк, США. С. 59–68.
7. «SIGCE - Международная группа по совместному редактированию». cooffice.ntu.edu.sg. Архивировано из оригинал на 2012-12-24. Получено 2020-01-10.
8. К. Сан (2002). «Отменить как одновременное обратное в групповых редакторах». ACM Trans. Comput.-Hum. Взаимодействовать. 9 (4): 309–361. Дои:10.1145/586081.586085.
9. Ду Ли; Руи Ли (2004). «Сохранение взаимосвязи операционных эффектов в групповых редакторах». Материалы конференции ACM CSCW'04 по компьютерной совместной работе. ACM Press Нью-Йорк, Нью-Йорк, США. С. 457–466.
10. Руи Ли; Ду Ли (2007). «Новая платформа оперативного преобразования для групповых редакторов в реальном времени». Транзакции IEEE в параллельных и распределенных системах. 18 (3): 307–319. Дои:10.1109 / TPDS.2007.35.
11. Руи Ли; Ду Ли (2005). «Управление параллелизмом на основе коммутативности в групповом ПО». Материалы Первой конференции IEEE по совместным вычислениям: сети, приложения и совместная работа (CollaborateCom'05).
12. Пракаш, Атул и Книстер, Майкл Дж. (1994). «Фреймворк для отмены действий в совместных системах». ACM Trans. Comput.-Hum. Взаимодействовать. 1 (4): 295–330. CiteSeerX  10.1.1.51.4793. Дои:10.1145/198425.198427.
13. Видот, Н .; Тележка, М .; Ferrie, J .; Сулейман, М. (2000). «Конвергенция копий в распределенной среде совместной работы в реальном времени» (PDF). Материалы конференции ACM 2000 года по совместной работе с компьютерной поддержкой. ACM Press Нью-Йорк, Нью-Йорк, США. С. 171–180. Архивировано из оригинал (PDF) на 2004-10-12.
14. Д. Сун, С. Ся, С. Сун, Д. Чен (2004). «Оперативное преобразование для совместной обработки текста». Proc. конференции ACM Conf. о совместной работе с компьютерной поддержкой. С. 437–446.
15. Агустина, Ф. Лю, С. Ся, Х. Шен и К. Сунь (ноябрь 2008 г.). «CoMaya: Включение расширенных возможностей совместной работы в инструменты {3D} дизайна цифровых медиа». Proc. ACM Conf. о совместной работе с компьютерной поддержкой. С. 5–8.
16. Дэвис, Агуидо Горацио и Сун, Чэнчжэн и Лу, Цзюньвэй (2002). «Обобщение операционного преобразования на стандартный общий язык разметки». CSCW '02: Материалы конференции ACM 2002 года по совместной работе с компьютерной поддержкой. Новый Орлеан, Луизиана, США. С. 58–67. Дои:10.1145/587078.587088.
17. Клаудиа-Лавиния Игнат; Мойра С. Норри (2003). «Настраиваемый совместный редактор, основанный на алгоритме treeOPT». ECSCW'03: Материалы восьмой конференции Европейской конференции по совместной работе с компьютерной поддержкой. Kluwer Academic Publishers. С. 315–334. Дои:10.1007/978-94-010-0068-0_17.
18. Клаудиа-Лавиния Игнат; Мойра С. Норри (2008). «Многоуровневое редактирование иерархических документов». Совместная работа с компьютерной поддержкой (CSCW). 17 (5–6): 423–468. Дои:10.1007 / s10606-007-9071-2.
19. C.Sun, S.Xia, D.Sun, D.Chen, H.Shen и W.Cai (2006). «Прозрачная адаптация однопользовательских приложений для многопользовательской совместной работы в реальном времени». ACM Trans. Comput.-Hum. Взаимодействовать. 13 (4): 531–582. Дои:10.1145/1188816.1188821.
20. «Операционное преобразование Google Wave». Архивировано из оригинал на 2009-05-31. Получено 2009-05-29.
21. Кристофер Р. Палмер; Гордон В. Кормак (1998). «Операционные преобразования для распределенной общей электронной таблицы». CSCW '98: Материалы конференции ACM 1998 года по совместной работе при компьютерной поддержке. ACM Press. С. 69–78. Дои:10.1145/289444.289474.
22. К. Сан и Р. Сосич (1999). «Дополнительная блокировка, интегрированная с операционным преобразованием в распределенных групповых редакторах реального времени». В Proc. 18-го симпозиума ACM по принципам распределенных вычислений. С. 43–52.
23. Бегол, Джеймс и Россон, Мэри Бет и Шаффер, Клиффорд А. (1999). «Гибкая прозрачность совместной работы: поддержка независимости сотрудников в реплицированных системах совместного использования приложений». ACM Trans. Comput.-Hum. Взаимодействовать. 6 (2): 95–132. CiteSeerX  10.1.1.23.1185. Дои:10.1145/319091.319096.
24. Ли, Ду и Ли, Руи (2002). «Прозрачный обмен и взаимодействие разнородных однопользовательских приложений». CSCW '02: Материалы конференции ACM 2002 года по совместной работе с компьютерной поддержкой. Новый Орлеан, США. С. 246–255.
25. Ли, Ду и Лу, Цзяцзюнь (2006). «Облегченный подход к прозрачному совместному использованию знакомых однопользовательских редакторов». CSCW '06: Материалы 20-й юбилейной конференции 2006 г. по совместной работе с компьютерной поддержкой. Банф, Альберта, Канада. С. 139–148. Дои:10.1145/1180875.1180896.
26. Шен, Хайфэн и Сун, Чэнчжэн (2002). «Гибкое уведомление для коллективных систем». CSCW '02: Материалы конференции ACM 2002 года по совместной работе с компьютерной поддержкой. С. 77–86. Дои:10.1145/587078.587090.
27. Д. Сан и К. Сан (2009). «Оперативное преобразование на основе контекста для распределенных систем совместного редактирования». Транзакции IEEE в параллельных и распределенных системах. 20 (10): 1454–1470. Дои:10.1109 / TPDS.2008.240.
28. Джеральд Остер; Паскаль Молли; Паскаль Урсо; Абдессамад Имин (2006). «Функции преобразования Tombstone для обеспечения согласованности в системах совместного редактирования» (PDF). Procs. 2nd Intl. Конф. О совместных вычислениях: сети, Appln. И совместная работа. Получено 2007-07-26.
29. М. Рессель и Р. Гунценхаузер (1999). «Снижение проблем групповой отмены». Proc. конференции ACM Conf. по поддержке групповой работы. С. 131–139.
30. Сулейман, М .; Тележка, М .; Ферри, Дж. (1998). «Параллельные операции в распределенной и мобильной совместной среде». Материалы четырнадцатой Международной конференции по инженерии данных, февраль. С. 23–27. Дои:10.1109 / ICDE.1998.655755.
31. Р. Ли, Д. Ли и К. Сан (2004). «Алгоритм контроля согласованности на основе временного интервала для интерактивных приложений групповой работы». ICPADS '04: Proceedings of the Parallel and Distributed Systems, Десятая Международная конференция. п. 429. Дои:10.1109 / ICPADS.2004.12.
32. М. Карт, Жан Ферри (2007). «Синхронизатор на основе операционной трансформации для P2P-сред» (PDF). Труды 3-й Международной конференции по совместным вычислениям: сети, приложения и совместная работа. стр. 127–138. Получено 2007-07-26.
33. Гу, Нин и Ян, Цзянмин и Чжан, Цивэй (2005). «Обеспечение согласованности на основе техники mark & ​​retrace в системах группового программного обеспечения». GROUP '05: Материалы международной конференции ACM SIGGROUP 2005 года по поддержке групповой работы. С. 264–273. Дои:10.1145/1099203.1099250.
34. Имин, Абдессамад и Молли, Паскаль и Остер, Джеральд и Урсо, Паскаль (2005). «Групповые редакторы в реальном времени без оперативной трансформации»: 24.
35. Стефан Вайс, Паскаль Урсо и Паскаль Молли (2010). «Logoot-Undo: Распределенная система совместного редактирования в P2P-сетях». Транзакции IEEE в параллельных и распределенных системах. 21 (8): 1162. Дои:10.1109 / TPDS.2009.173.
36. Виктор Грищенко (2010). «Глубокий гипертекст со встроенным контролем версий, реализованный в регулярных выражениях» (PDF). Материалы 6-го Международного симпозиума по вики и открытому сотрудничеству (WikiSym '10). WikiSym 2010. Архивировано из оригинал (PDF) на 2012-03-09. Получено 2010-06-30.
37. Ду Ли и Руи Ли (2010). «Основанная на допустимости основанная на допустимости операционная трансформация систем совместного редактирования». Совместная работа с компьютерной поддержкой (CSCW). 19 (1): 1–43. Дои:10.1007 / s10606-009-9103-1.
38. «ShareJS». 2011-11-06. Архивировано из оригинал на 2012-05-11. Получено 2013-08-16.
39. «Да, это я! Как бы то ни было, я больше не верю, что эта волна займет 2 года ... | Hacker News». news.ycombinator.com. Получено 2019-02-13.
40. Нил Фрейзер (январь 2009 г.). «Дифференциальная синхронизация».

внешняя ссылка

• OTFAQ: Операционная трансформация Часто задаваемые вопросы и ответы
• SIGCE: Специальная группа по совместному редактированию
• Международный семинар по системам совместного редактирования
• Распределенная система онлайн - совместное редактирование
• Простое объяснение OT в Google Docs
• Основы OT в Open Coweb Framework

Соответствующие онлайн-переговоры

• Google Wave: совместное редактирование в реальном времени
• Google Tech Talk: проблемы и опыт разработки систем совместного редактирования в реальном времени
• Обсуждение Microsoft Research: Обеспечение согласованности в системах совместного редактирования в реальном времени