BXU Logo

Buxoro Xalqaro
Universiteti

9-tom, 2-son, b. 327–331, Nashr: 2026-09-23

TAQSIMLANGAN TIZIMLARDA KONFLIKTSIZ REPLIKATSIYALANUVCHI MA’LUMOT TURLARI (CRDT): NAZARIY TAHLIL VA RESURS-CHEKLANGAN REAL VAQTLI MUHITLAR UCHUN KONTSEPTUAL KENGAYTMA

КОНФЛИКТНО-СВОБОДНЫЕ РЕПЛИЦИРУЕМЫЕ ТИПЫ ДАННЫХ (CRDT) В РАСПРЕДЕЛЁННЫХ СИСТЕМАХ: ТЕОРЕТИЧЕСКИЙ АНАЛИЗ И КОНЦЕПТУАЛЬНОЕ РАСШИРЕНИЕ ДЛЯ РЕСУРСООГРАНИЧЕННЫХ СРЕД РЕАЛЬНОГО ВРЕМЕНИ

CONFLICT-FREE REPLICATED DATA TYPES (CRDTs) IN DISTRIBUTED SYSTEMS: THEORETICAL ANALYSIS AND A CONCEPTUAL EXTENSION FOR RESOURCE-CONSTRAINED REAL-TIME ENVIRONMENTS

  • Munirov Jonibek Jamshed o’g’li — Osiyo xalqaro universiteti, stajor-o’qituvchi

To'liq matn (PDF)

Annotatsiya

Maqolada taqsimlangan tizimlarda replikalar o‘rtasida markazlashgan muvofiqlashtiruvchi yoki konsensus protokolisiz izchillikni ta’minlash muammosi - konfliktsiz replikatsiyalanuvchi ma’lumot turlari (Conflict-free Replicated Data Types, CRDT) nazariyasi asosida tahlil qilingan. CAP teoremasi va kuchli oxir-oqibat konsistentligi (Strong Eventual Consistency) tushunchalaridan kelib chiqib, CRDT’ning ikki asosiy turi - holatga asoslangan (CvRDT) va operatsiyaga asoslangan (CmRDT) - hamda ularning trafik samaradorligini oshiruvchi delta-mutatsiya kengaytmasi tizimli tarzda ko‘rib chiqilgan. Hamkorlikdagi matn tahrirlash, taqsimlangan fayl tizimlari va peer-to-peer virtual borliq (VR) muhitlaridagi amaliy qo‘llanilish tajribalari tahlil qilinib, mavjud tatbiqlarning uchta asosiy cheklovi - metadata (tombstone) o‘sishi, barcha yangilanishlarga nisbatan ustuvorlik-neytralligi va murakkab turlarda delta hajmining kattalashuvi - aniqlangan. Ushbu tahlil asosida maqolada delta-CRDT arxitekturasiga tarmoq holati va ma’lumot ahamiyatiga asoslangan uzatish navbati qatlamini CRDT’ning matematik konfliktsizlik xossalarini buzmagan holda qo‘shishga asoslangan “ustuvorlik-ogoh delta-CRDT” kontseptual modeli taklif etiladi. Model resurs-cheklangan (past o‘tkazuvchanlik, yuqori tebranishli) tarmoq sharoitida ishlaydigan real vaqtli ko‘p foydalanuvchili tizimlar uchun mo‘ljallangan.

Аннотация

В статье анализируется проблема обеспечения согласованности между репликами в распределённых системах без централизованного координатора или протокола консенсуса на основе теории бесконфликтных реплицируемых типов данных (CRDT). Рассмотрены два основных типа CRDT - на основе состояния (CvRDT) и на основе операций (CmRDT), а также их дельта-расширение. Проанализирован опыт применения в совместном редактировании текста, распределённых файловых системах и peer-to-peer VR-средах, выявлены три основных ограничения существующих реализаций. На основе этого предлагается концептуальная модель «приоритетно-осведомлённого» дельта-CRDT для ресурсно-ограниченных сред реального времени.

Abstract

This article analyzes the problem of ensuring consistency among replicas in distributed systems without a centralized coordinator or consensus protocol, based on the theory of Conflict-free Replicated Data Types (CRDTs). Building on the CAP theorem and the notion of Strong Eventual Consistency, the two principal CRDT families - state-based (CvRDT) and operation-based (CmRDT) - and their delta-mutation extension are systematically reviewed. Practical application experience in collaborative text editing, distributed file systems, and peer-to-peer virtual reality (VR) environments is analyzed, and three key limitations of existing implementations are identified: metadata (tombstone) growth, priority-neutrality toward all updates, and delta-size inflation for complex data types. Based on this analysis, the article proposes a conceptual “priority-aware delta-CRDT” model that adds a transmission-scheduling layer - driven by network state and data relevance - on top of delta-CRDTs without violating their mathematical conflict-freedom guarantees. The model targets real-time multi-user systems operating over resource-constrained (low-bandwidth, high-jitter) networks.

Kalit so'zlar: CRDT, taqsimlangan tizimlar, kuchli oxir-oqibat konsistentligi, delta-CRDT, CAP teoremasi, holat replikatsiyasi, resurs-cheklangan tarmoqlar

Foydalanilgan adabiyotlar

  1. Brewer E. A. CAP Twelve Years Later: How the “Rules” Have Changed // IEEE Computer. - 2012. - Vol. 45, No. 2. - P. 23–29. DOI: 10.1109/MC.2012.37
  2. Vogels W. Eventually Consistent // Communications of the ACM. - 2009. - Vol. 52, No. 1. - P. 40–44. DOI: 10.1145/1435417.1435432
  3. Shapiro M., Preguiça N., Baquero C., Zawirski M. Conflict-Free Replicated Data Types // Stabilization, Safety, and Security of Distributed Systems (SSS 2011), LNCS vol. 6976. - Springer, 2011. - P. 386–400.
  4. Almeida P. S., Shoker A., Baquero C. Efficient State-Based CRDTs by Delta-Mutation // Networked Systems (NETYS 2015), LNCS vol. 9466. - Springer, 2015. - P. 62–76. (arXiv:1410.2803). URL: https://arxiv.org/abs/1410.2803
  5. Almeida P. S., Shoker A., Baquero C. Delta State Replicated Data Types // Journal of Parallel and Distributed Computing. - 2018. - Vol. 111. - P. 162–173. DOI: 10.1016/j.jpdc.2017.08.003
  6. Sun C., Sun D., Ng A., Cai W., Cho B. Real Differences between OT and CRDT under a General Transformation Framework for Consistency Maintenance in Co-Editors // Proceedings of the ACM on Human-Computer Interaction. - 2020. - Vol. 4, No. GROUP, Article 1–26. DOI: 10.1145/3375186
  7. Dantas A., Baquero C. CRDT-Based Game State Synchronization in Peer-to-Peer VR // arXiv:2503.17826, 2025. URL: https://arxiv.org/abs/2503.17826
  8. Ke Q., Lv Y., Zhang Z., Shen Z., Yu Y., Chen H., Song Z., Gan X., Li J., Li D., Yao X., Wang M., Zhang Y. CrossFS: Improving Cross-Domain File System Performance with CRDT-Based Metadata Synchronization // ACM Transactions on Storage. - 2026. - Vol. 22, No. 2, Article 1–25. DOI: 10.1145/3777470
  9. Li S., Zhang C., Li B., Gao C., Lyu M. R. When Shared Worlds Break: Demystifying Defects in Multi-User Extended Reality Software Systems // arXiv:2510.01182, 2025. URL: https://arxiv.org/abs/2510.01182