Интернет магазин китайских планшетных компьютеров

Компьютеры - Операциональное преобразование - Модели согласованности

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

CC модель

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

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

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

CCI модель

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

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

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

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

CSM модель

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

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

CA модель

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

В качестве альтернативы, CA модель основывается на Admissibilty Theory . CA модель включает в себя два аспекта:

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

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