HANDLING SPLIT BRAIN SCENARIOS WITHIN REPLICA STATE DICOVERY PROTOCOL
DOI:
https://doi.org/10.28925/2663-4023.2026.35.1443Keywords:
distributed computing; crash fault tolerance; failure detectors; state synchronization; cluster management; state convergence; Replica State Discovery Protocol (RSDP); eventual consistency.Abstract
Distributed systems often require coordination capabilities for resource and task allocation among participating nodes. Traditional coordination solutions rely on centralized control planes or leader election algorithms involving risks of authoritative decisions. In that regard, the Replica State Discovery Protocol (RSDP) was created to achieve similar capability in a one-rank network. RSDP defines peer-to-peer communication phases aimed at gathering a cluster state consisting of participants’ perspectives. The architecture takes into account diverse requirements of different execution environments with a stratified system and modular approach towards constructing cluster state reducers responsible for their own data slices. When a network must organize into a coherent system, the potential losses of messages and nodes, as well as entire communication links, must be considered and handled on the protocol’s design layer. One of the common pitfalls in that regard is network fragmentation and the requirement to guarantee cluster stability in such scenarios. Previous work of RSDP has been concentrated on crash fault tolerance and operational stability but has also explicitly acknowledged the absence of a formal mechanism for handling split-brain events. The purpose of this article is to provide a theoretical basis for building state reducers of two categories: those that tolerate network partitioning and those requiring additional reconciliation mechanisms. It is also within the ambit of this work to formally describe and verify such a mechanism without extending the initial set of messages used for the protocol and avoiding additional communication or coordination overhead to handle such events.
Downloads
References
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
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Максим Котов, Сергій Толюпа
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
