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

Concurrency control method for collaborative software

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

История

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

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

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

Основы

Основная идея ОТ

Основную идею OT можно проиллюстрировать, используя простой сценарий редактирования текста следующим образом. Дан текстовый документ со строкой «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". Основная идея OT заключается в преобразовании (или корректировке) параметров операции редактирования в соответствии с эффектами ранее выполненных параллельных операций, чтобы преобразованная операция могла достичь правильного эффекта и сохранить согласованность документа.

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

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

Модель СС

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

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

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

Модель CCI

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

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

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

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

Модель CSM

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

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

Модель СА

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

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

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

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

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

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

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

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

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

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

1. Сохранение причинности
2. Сохранение допустимости

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

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

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

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

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

Функции ОТ

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

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

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

T(вставки( ),вставки( )) :- ${\displaystyle p_{1},c_{1},sid_{1}}$ ${\displaystyle p_{2},c_{2},sid_{2}}$ если ( ) вернуть ins( ) ${\displaystyle p_{1}<p_{2}}$ ${\displaystyle p_{1},c_{1},sid_{1}}$ иначе если ( и ) вернуть ins( ) ${\displaystyle p_{1}=p_{2}}$ ${\displaystyle sid_{1}<sid_{2}}$ ${\displaystyle p_{1},c_{1},sid_{1}}$ иначе вернуть ins( ) ${\displaystyle p_{1}+1,c_{1},sid_{1}}$

Мы также можем записать следующую функцию преобразования исключения: ^[23]

 ${\displaystyle T^{-1}}$(вставки( ),вставки( )) :- ${\displaystyle p_{1},c_{1},sid_{1}}$ ${\displaystyle p_{2},sid_{2}}$ если ( ) вернуть ins( ) ${\displaystyle p_{1}<p_{2}}$ ${\displaystyle p_{1},c_{1},sid_{1}}$ иначе если ( и ) вернуть ins( ) ${\displaystyle p_{1}=p_{2}}$ ${\displaystyle sid_{1}<sid_{2}}$ ${\displaystyle p_{1},c_{1},sid_{1}}$ иначе вернуть ins( ) ${\displaystyle p_{1}-1,c_{1},sid_{1}}$

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

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

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

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

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

Иллюстрация объекта TP1

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

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

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

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

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

• IP1 : При любом состоянии документа S и последовательности , мы имеем , что означает, что последовательность эквивалентна одной операции идентичности I относительно эффекта на состояние документа. Это свойство требуется в системе OT для достижения правильного эффекта отмены, но не связано с функциями IT. ${\displaystyle op\circ {\overline {op}}}$ ${\displaystyle S\circ op\circ {\overline {op}}=S}$ ${\displaystyle op\circ {\overline {op}}}$
• IP2 : Свойство IP2 выражает, что последовательность не влияет на преобразование других операций. Функции преобразования удовлетворяют IP2 тогда и только тогда, когда: , что означает, что результат преобразования против последовательности эквивалентен результату преобразования против операции тождества I. Предварительное условие IP2 : IP2 требуется только в том случае, если системы OT позволяют преобразовывать операцию против пары операций do и undo , одну за другой. ${\displaystyle op\circ {\overline {op}}}$ ${\displaystyle T(op_{x},op\circ {\overline {op}})=op_{x}}$ ${\displaystyle op_{x}}$ ${\displaystyle op\circ {\overline {op}}}$ ${\displaystyle op_{x}}$ ${\displaystyle op_{x}}$ ${\displaystyle op\circ {\overline {op}}}$
• IP3 : Даны две параллельные операции , определенные в одном и том же состоянии документа (или контексте), если и . Функции преобразования удовлетворяют свойству IP3 тогда и только тогда, когда , что означает, что преобразованная обратная операция равна обратной преобразованной операции . Предварительное условие IP3 : IP3 требуется только в том случае, если система OT допускает преобразование обратной операции против операции , которая является параллельной и определена в том же состоянии документа, что и (или эквивалентна по контексту) . ${\displaystyle op_{1}}$ ${\displaystyle op_{2}}$ ${\displaystyle {\overline {op_{1}}}'=T({\overline {op_{1}}},T(op_{2},op_{1}))}$ ${\displaystyle {\overline {op_{1}'}}={\overline {T(op_{1},op_{2})}}}$ ${\displaystyle {\overline {op_{1}}}'={\overline {op_{1}'}}}$ ${\displaystyle {\overline {op_{1}}}'}$ ${\displaystyle {\overline {op_{1}'}}}$ ${\displaystyle {\overline {op_{1}}}}$ ${\displaystyle op_{2}}$ ${\displaystyle op_{1}}$

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

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

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

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

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

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

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

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

Проблемы корректности OT привели к введению схем пост-OT без преобразований, таких как WOOT, ^[36] Logoot ^[37] и Causal Trees (CT). ^[38] Схемы «Post-OT» разлагают документ на атомарные операции, но они обходят необходимость в операциях преобразования, используя комбинацию уникальных идентификаторов символов, временных меток векторов и/или надгробий.

Критика ОТ

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

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

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

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

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

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

Ссылки

1. Сан, Чэнчжэн. "OT FAQ". Архивировано из оригинала 2020-06-23.
2. Эллис, CA; Гиббс, SJ (1989). «Управление параллелизмом в системах группового программного обеспечения». ACM SIGMOD Record . 18 (2): 399–407. CiteSeerX 10.1.1.465.2026 . doi :10.1145/67544.66963. S2CID  6488575. 
3. Ressel, Matthias и Nitsche-Ruhland, Doris и Gunzenhäuser, Rul (1996). Интегрирующий, ориентированный на преобразования подход к управлению параллелизмом и отмене в групповых редакторах . CSCW '96: Труды конференции ACM 1996 года по компьютерной поддержке совместной работы. стр. 288–297. doi :10.1145/240080.240305.{{cite conference}}: CS1 maint: multiple names: authors list (link)
4. Чэнчжэн Сан; Сяохуа Цзя; Яньчунь Чжан; Юнь Ян; Дэвид Чен (1998). «Достижение конвергенции, сохранения причинности и сохранения намерения в системах кооперативного редактирования в реальном времени». ACM Trans. Comput.-Hum. Interact . 5 (1): 63–108. CiteSeerX 10.1.1.56.1251 . doi :10.1145/274444.274447. S2CID  14447070. 
5. Николс, DA; Кертис, P.; Диксон, M.; Лампинг, J. (1995). «Высоко-латентное, низко-полосное оконное управление в системе сотрудничества Jupiter». Труды 8-го ежегодного симпозиума ACM по пользовательскому интерфейсу и программным технологиям : 111–120. Архивировано из оригинала 2015-11-30 . Получено 2009-09-27 .
6. Sun, C.; Ellis, C. (1998). Операционная трансформация в редакторах групп в реальном времени: проблемы, алгоритмы и достижения. Труды конференции ACM 1998 года по совместной работе с компьютерной поддержкой. ACM Press New York, NY, USA. С. 59–68.
7. "SIGCE - Международная специальная группа по совместному редактированию". cooffice.ntu.edu.sg . Архивировано из оригинала 2012-12-24 . Получено 2020-01-10 .
8. C. Sun (2002). «Отмена как параллельная обратная операция в групповых редакторах». ACM Trans. Comput.-Hum. Interact . 9 (4): 309–361. doi :10.1145/586081.586085. S2CID  47453660.
9. Ду Ли; Руи Ли (2004). Сохранение связи между эффектами операций в групповых редакторах . Труды конференции ACM CSCW'04 по компьютерно-поддерживаемой совместной работе. ACM Press New York, NY, USA. С. 457–466.
10. Rui Li; Du Li (2007). «Новая структура оперативного преобразования для редакторов групп реального времени». Труды IEEE по параллельным и распределенным системам . 18 (3). Труды IEEE по параллельным и распределенным системам: 307–319. doi :10.1109/TPDS.2007.35. S2CID  18822760.
11. Руи Ли; Ду Ли (2005). Управление параллелизмом на основе коммутативности в групповом программном обеспечении . Труды первой конференции IEEE по совместным вычислениям: сети, приложения и совместная работа (CollaborateCom'05).
12. Пракаш, Атул и Книстер, Майкл Дж. (1994). «Структура отмены действий в системах совместной работы». ACM Trans. Comput.-Hum. Interact . 1 (4): 295–330. CiteSeerX 10.1.1.51.4793 . doi :10.1145/198425.198427. S2CID  10705127. 
13. Видот, Н.; Карт, М.; Ферри, Дж.; Сулейман, М. (2000). Конвергенция копий в распределенной среде совместной работы в реальном времени (PDF) . Труды конференции ACM 2000 года по совместной работе с компьютерной поддержкой. ACM Press New York, NY, USA. С. 171–180. Архивировано из оригинала (PDF) 2004-10-12.
14. D. Sun и S. Xia и C. Sun и D. Chen (2004). Операционная трансформация для совместной обработки текстов . Труды конференции ACM по совместной работе с компьютерной поддержкой. С. 437–446.
15. Агустина и Ф. Лю и С. Ся и Х. Шен и К. Сан (ноябрь 2008 г.). CoMaya: Внедрение расширенных возможностей совместной работы в инструменты проектирования {3D} цифровых медиа . Труды конференции ACM по совместной работе с компьютерной поддержкой. стр. 5–8.
16. Дэвис, Агуидо Горацио и Сан, Чэнчжэн и Лу, Цзюньвэй (2002). Обобщение операционного преобразования для стандартного общего языка разметки . CSCW '02: Труды конференции ACM 2002 года по компьютерной поддержке совместной работы. Новый Орлеан, Луизиана, США. С. 58–67. doi :10.1145/587078.587088.{{cite conference}}: CS1 maint: multiple names: authors list (link)
17. Клаудия-Лавиния Игнат; Мойра С. Норри (2003). Настраиваемый коллаборативный редактор, основанный на алгоритме treeOPT . ECSCW'03: Труды восьмой конференции Европейской конференции по компьютерной поддержке совместной работы. Kluwer Academic Publishers. С. 315–334. doi :10.1007/978-94-010-0068-0_17.
18. Клаудия-Лавиния Игнат; Мойра С. Норри (2008). «Многоуровневое редактирование иерархических документов». Совместная работа с компьютерной поддержкой (CSCW) . 17 (5–6): 423–468. doi :10.1007/s10606-007-9071-2. S2CID  42752275.
19. C.Sun, S.Xia, D.Sun, D.Chen, H.Shen и W.Cai (2006). «Прозрачная адаптация однопользовательских приложений для многопользовательского взаимодействия в реальном времени». ACM Trans. Comput.-Hum. Interact . 13 (4): 531–582. doi :10.1145/1188816.1188821. S2CID  14184705.{{cite journal}}: CS1 maint: multiple names: authors list (link)
20. "Google Wave Operational Transform". Архивировано из оригинала 2009-05-31 . Получено 2009-05-29 .
21. Кристофер Р. Палмер; Гордон В. Кормак (1998). Операционные преобразования для распределенной общей электронной таблицы . CSCW '98: Труды конференции ACM 1998 года по совместной работе с компьютерной поддержкой. ACM Press. стр. 69–78. doi : 10.1145/289444.289474 .
22. Кагорский, Антон. «Операционные преобразования как алгоритм автоматического разрешения конфликтов». medium.com . Получено 21 декабря 2021 г. .
23. "Функции преобразования Tombstone для обеспечения согласованности в системах совместного редактирования". Конференция IEEE по совместным вычислениям: сетевые технологии, приложения и совместное использование ресурсов . 2006-11-07.
24. C. Sun & R. Sosic (1999). Необязательная блокировка, интегрированная с операционным преобразованием в распределенных редакторах групп реального времени . В трудах 18-го симпозиума ACM по принципам распределенных вычислений. С. 43–52.
25. Беголь, Джеймс и Россон, Мэри Бет и Шаффер, Клиффорд А. (1999). «Гибкая прозрачность сотрудничества: поддержка независимости работников в реплицированных системах совместного использования приложений». ACM Trans. Comput.-Hum. Interact . 6 (2): 95–132. CiteSeerX 10.1.1.23.1185 . doi :10.1145/319091.319096. S2CID  17895848. {{cite journal}}: CS1 maint: multiple names: authors list (link)
26. Ли, Ду и Ли, Руи (2002). Прозрачное совместное использование и взаимодействие гетерогенных однопользовательских приложений . CSCW '02: Труды конференции ACM 2002 года по совместной работе с компьютерной поддержкой. Новый Орлеан, США. С. 246–255.
27. Ли, Ду и Лу, Цзяцзюнь (2006). Облегченный подход к прозрачному совместному использованию знакомых однопользовательских редакторов . CSCW '06: Труды 20-й юбилейной конференции 2006 года по совместной работе с использованием компьютеров. Банф, Альберта, Канада. С. 139–148. doi :10.1145/1180875.1180896.
28. Shen, Haifeng & Sun, Chengzheng (2002). Гибкое уведомление для систем совместной работы . CSCW '02: Труды конференции ACM 2002 года по совместной работе с компьютерной поддержкой. стр. 77–86. doi :10.1145/587078.587090.
29. D. Sun & C. Sun (2009). «Контекстно-ориентированное операционное преобразование для распределенных систем совместного редактирования». Труды IEEE по параллельным и распределенным системам . 20 (10): 1454–1470. doi :10.1109/TPDS.2008.240. S2CID  18740053.
30. Джеральд Остер; Паскаль Молли; Паскаль Урсо; Абдессамад Имин (2006). "Функции преобразования надгробий для обеспечения согласованности в системах совместного редактирования" (PDF) . Труды 2-й Международной конференции по совместным вычислениям: сетевые технологии, приложения и совместная работа . Получено 26 июля 2007 г.
31. M. Ressel & R. Gunzenhauser (1999). Уменьшение проблем групповой отмены . Труды конференции ACM по поддержке групповой работы. С. 131–139.
32. Сулейман, М.; Карт, М.; Феррие, Дж. (1998). Параллельные операции в распределенной и мобильной среде совместной работы . Труды четырнадцатой международной конференции по инжинирингу данных, февраль. стр. 23–27. doi :10.1109/ICDE.1998.655755.
33. Р. Ли, Д. Ли и К. Сан (2004). Алгоритм контроля согласованности на основе временного интервала для интерактивных приложений группового программного обеспечения . ICPADS '04: Труды параллельной и распределенной системы, Десятая международная конференция. стр. 429. doi :10.1109/ICPADS.2004.12.
34. M. Cart, Jean Ferrié (2007). Synchronizer Based on Operational Transformation for P2P Environments (PDF) . Труды 3-й Международной конференции по совместным вычислениям: сетевые технологии, приложения и совместное использование ресурсов. стр. 127–138 . Получено 26 июля 2007 г.
35. Гу, Нин и Ян, Цзянмин и Чжан, Цивэй (2005). Поддержание согласованности на основе метода отметки \& повторной трассировки в системах группового программного обеспечения . GROUP '05: Труды международной конференции ACM SIGGROUP 2005 года по поддержке групповой работы. стр. 264–273. doi :10.1145/1099203.1099250.{{cite conference}}: CS1 maint: multiple names: authors list (link)
36. Имин, Абдессамад и Молли, Паскаль и Остер, Джеральд и Урсо, Паскаль (2005). Редакторы групп в реальном времени без операционного преобразования. Исследовательский отчет INRIA RR-5580. стр. 24.{{cite conference}}: CS1 maint: multiple names: authors list (link)
37. Стефан Вайс и Паскаль Урсо и Паскаль Молли (2010). "Logoot-Undo: Распределенная система совместного редактирования в сетях P2P". IEEE Transactions on Parallel and Distributed Systems . 21 (8). IEEE Transactions on Parallel and Distributed Systems: 1162. doi :10.1109/TPDS.2009.173. S2CID  14172605.
38. Виктор Грищенко (2010). Глубокий гипертекст со встроенным контролем версий, реализованный в регулярных выражениях (PDF) . Труды 6-го Международного симпозиума по вики и открытому сотрудничеству (WikiSym '10). Архивировано из оригинала (PDF) 2012-03-09 . Получено 2010-06-30 .
39. Ду Ли и Руи Ли (2010). «Основанная на допустимости операционная структура трансформации для систем совместного редактирования». Совместная работа с компьютерной поддержкой (CSCW) . 19 (1). Совместная работа с компьютерной поддержкой: 1–43. doi :10.1007/s10606-009-9103-1. S2CID  35748875.
40. "ShareJS". 2011-11-06. Архивировано из оригинала 2012-05-11 . Получено 2013-08-16 .
41. "Да, это я! Как бы там ни было, я больше не верю, что эта волна займет 2 года... | Hacker News". news.ycombinator.com . Получено 13.02.2019 .
42. Нил Фрейзер (январь 2009 г.). «Дифференциальная синхронизация».

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

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

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

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