HANDLING SPLIT BRAIN SCENARIOS WITHIN REPLICA STATE DICOVERY PROTOCOL

Максим Котов; Сергій Толюпа

doi:10.28925/2663-4023.2026.35.1443

Автор(и)

Максим Котов Київський національний університет імені Тараса Шевченка https://orcid.org/0000-0003-1153-3198
Сергій Толюпа Київський національний університет імені Тараса Шевченка https://orcid.org/0000-0002-1919-9174

DOI:

https://doi.org/10.28925/2663-4023.2026.35.1443

Ключові слова:

розподілені обчислення; відмовостійкість до збоїв; детектори збоїв; синхронізація станів; управління кластерами; конвергенція станів; протокол виявлення стану репліки (RSDP); остаточна узгодженість.

Анотація

Розподілені системи часто потребують засобів координації для розподілу ресурсів і завдань між вузлами-учасниками. Традиційні рішення для координації спираються на централізовані площини керування або алгоритми вибору лідера, що пов’язано з ризиками, властивими прийняттю рішень єдиним авторитетним вузлом. У цьому контексті було розроблено протокол виявлення стану реплік (RSDP) для забезпечення аналогічних можливостей у мережі рівноправних вузлів. RSDP визначає етапи взаємодії між вузлами, спрямовані на формування стану кластера на основі даних, отриманих від окремих учасників. Архітектура враховує вимоги різних середовищ виконання завдяки багаторівневій системі та модульному підходу до створення компонентів зведення стану (редукторів), кожен з яких відповідає за певний фрагмент даних. Коли мережа має організуватися в цілісну систему, на рівні проєктування протоколу необхідно передбачити обробку ситуацій, пов’язаних із втратою повідомлень, виходом із ладу вузлів або розривом каналів зв’язку. Однією з поширених проблем у цьому аспекті є фрагментація мережі та необхідність гарантування стабільності кластера за таких умов. Попередні дослідження RSDP були зосереджені на стійкості до відмов типу «зупинка» (crash faults) та операційній стабільності, проте в них також визнавалася відсутність формального механізму обробки ситуацій розколу системи (split-brain). Мета цієї статті – створити теоретичне підґрунтя для побудови редукторів стану двох категорій: тих, що стійкі до розділення мережі, і тих, що потребують додаткових механізмів узгодження даних. Також у межах цієї роботи здійснюється формальний опис і верифікація такого механізму без розширення початкового набору повідомлень протоколу та без додаткових витрат ресурсів на комунікацію чи координацію для обробки зазначених ситуацій.

Завантаження

Дані завантаження ще не доступні.

Посилання

Kotov, M., & Toliupa, S. (2025). Layered architecture for RSDP V3.0: Modular distributed consensus and coordination. In Networks and sustainability. TCSET 2024 (Lecture Notes in Electrical Engineering, Vol. 1473). Springer. https://doi.org/10.1007/978-3-032-02272-1_6

Kotov, M., et al. (2025). Byzantine fault tolerance in distributed systems: Advancing the Replica State Discovery Protocol v2.0. CEUR Workshop Proceedings, 3991, 121–138. https://ceur-ws.org/Vol-3991/paper10.pdf

Kotov, M., Toliupa, S., & Buchyk, O. (2026). Decentralization model for the Replica State Discovery Protocol. In 2026 IEEE 18th International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (TCSET) (pp. 1–6). IEEE. https://doi.org/10.1109/TCSET65181.2026.11461147

Toliupa, S., et al. (2024). Stateful cluster leader failover models and methods based on Replica State Discovery Protocol. CEUR Workshop Proceedings, 3933, 120–140. https://ceur-ws.org/Vol-3933/Paper_10.pdf

Kotov, M., & Toliupa, S. (2026). Crash fault tolerance in the Replica State Discovery Protocol: Formal convergence guarantees and empirical validation [Manuscript submitted for publication].

Gilbert, S., & Lynch, N. (2002). Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News, 33(2), 51–59. https://doi.org/10.1145/564585.564601

Brewer, E. (2012). CAP twelve years later: How the “rules” have changed. Computer, 45(2), 23–29. https://doi.org/10.1109/MC.2012.37

Dwork, C., Lynch, N., & Stockmeyer, L. (1988). Consensus in the presence of partial synchrony. Journal of the ACM, 35(2), 288–323. https://doi.org/10.1145/42282.42283

Chandra, T. D., & Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2), 225–267. https://doi.org/10.1145/226643.226647

Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2), 374–382. https://doi.org/10.1145/3149.214121

Shapiro, M., et al. (2011). Conflict-free replicated data types. In Stabilization, safety, and security of distributed systems (Lecture Notes in Computer Science, Vol. 6976, pp. 386–400). Springer. https://doi.org/10.1007/978-3-642-24550-3_29

Hellerstein, J. M., & Alvaro, P. (2020). Keeping CALM: When distributed consistency is easy. Communications of the ACM, 63(9), 72–81. https://doi.org/10.1145/3369736

Almeida, P. S. (2023). Approaches to conflict-free replicated data types [Preprint]. arXiv. https://doi.org/10.48550/arXiv.2310.18220

Birman, K., & Joseph, T. (1987). Exploiting virtual synchrony in distributed systems. In Proceedings of the 11th ACM Symposium on Operating Systems Principles (SOSP ’87) (pp. 123–138). Association for Computing Machinery. https://doi.org/10.1145/41457.37515

Moser, L. E., et al. (1994). Extended virtual synchrony. In Proceedings of the 14th International Conference on Distributed Computing Systems (ICDCS) (pp. 56–65). IEEE. https://doi.org/10.1109/ICDCS.1994.302392

Babaoğlu, Ö., Davoli, R., & Montresor, A. (2001). Group communication in partitionable systems: Specification and algorithms. IEEE Transactions on Software Engineering, 27(4), 308–336. https://doi.org/10.1109/32.917522

Chockler, G. V., Keidar, I., & Vitenberg, R. (2001). Group communication specifications: A comprehensive study. ACM Computing Surveys, 33(4), 427–469. https://doi.org/10.1145/503112.503113

Gray, C., & Cheriton, D. (1989). Leases: An efficient fault-tolerant mechanism for distributed file cache consistency. In Proceedings of the 12th ACM Symposium on Operating Systems Principles (SOSP ’89) (pp. 202–210). Association for Computing Machinery. https://doi.org/10.1145/74850.74870

Burrows, M. (2006). The Chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation (OSDI ’06) (pp. 335–350). USENIX Association. https://dl.acm.org/citation.cfm?id=1298487

Ongaro, D., & Ousterhout, J. (2014). In search of an understandable consensus algorithm. In 2014 USENIX Annual Technical Conference (USENIX ATC 14) (pp. 305–319). USENIX Association. https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro

Oki, B. M., & Liskov, B. H. (1988). Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proceedings of the 7th ACM Symposium on Principles of Distributed Computing (PODC ’88) (pp. 8–17). Association for Computing Machinery. https://doi.org/10.1145/62546.62549

Gifford, D. K. (1979). Weighted voting for replicated data. In Proceedings of the 7th ACM Symposium on Operating Systems Principles (SOSP ’79) (pp. 150–162). Association for Computing Machinery. https://doi.org/10.1145/800215.806583

Lamport, L., Malkhi, D., & Zhou, L. (2010). Reconfiguring a state machine. ACM SIGACT News, 41(1), 63–73. https://doi.org/10.1145/1753171.1753191

Das, A., Gupta, I., & Motivala, A. (2002). SWIM: Scalable weakly-consistent infection-style process group membership protocol. In Proceedings of the International Conference on Dependable Systems and Networks (DSN 2002) (pp. 303–312). IEEE. https://doi.org/10.1109/DSN.2002.1028914

Replica State Discovery Protocol. (n.d.). Fault-tolerance-tla: TLA+ specification and TLC verification artifacts [Source code]. GitHub. Retrieved September 13, 2026, from https://github.com/Replica-State-Discovery-Protocol/fault-tolerance-tla