Эпистемический подход к бесконфликтно реплицируемым типам
Эпистемический подход к бесконфликтно реплицируемым типам
Аннотация
Оптимистическая репликация является одним из ключевых подходов к обеспечению высокой доступности географически распределённых систем, позволяя репликам временно расходиться в состоянии с последующим асинхронным согласованием. Несмотря на то, что широко распространённые бесконфликтные реплицируемые типы данных (Conflict-free Replicated Data Types, CRDT) гарантируют сильную сходимость, встроенные в них механизмы разрешения конфликтов, как правило, являются неявными и недостаточно гибкими, что ограничивает их применение в сценариях, требующих семантической прозрачности и участия пользователя в процессе разрешения конфликтов. В работе исследуется эпистемическая модель конфликтов – формальная модель, обеспечивающая явное, гибкое и не требующее координации разрешение конфликтов при сохранении гарантий сходимости. Во-первых, показано, что CRDT, основанные на состоянии, на операциях и на дельта-состояниях (delta-CRDT), естественным образом формализуются в рамках эпистемической модели, которая предоставляет единый аппарат для их бесконфликтного представления. Во-вторых, множества рассматриваются как фундаментальный реплицируемый тип данных, лежащий в основе более сложных реплицируемых структур, таких как списки, графы и отображения. Для них в рамках эпистемической модели определяются соответствующие процедуры разрешения конфликтов, реализующие семантики, известные в теории CRDT. Тем самым демонстрируется, что эпистемическая модель конфликтов обладает достаточной выразительной мощностью для формализации семантики существующих реализаций CRDT, одновременно сохраняя их интерпретируемость и семантическую прозрачность.
Ключевые слова
Издание
Труды Института системного программирования РАН, том 38, вып. 5, 2026, стр. 37-50.
ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).
DOI: 10.15514/ISPRAS-2026-38(5)-3
Для цитирования
Полный текст статьи в формате pdf (на английском)
Вернуться к содержанию тома