D.A. Bulgakov1

1 State University of Aerospace Instrumentation (SUAI) (St. Petersburg, Russia)

The gossip protocol used in modern blockchain networks does not guarantee the coordinated propagation of dependent transactions. The mechanisms for propagating and processing transactions are designed independently, which leads to their asynchronous arrival at network nodes. At the same time, transaction execution is scheduled with partial ordering, which causes a mismatch between the order of arrival and the permissible order of service, an increase in the number of pending transactions, and a decrease in processing efficiency.

This paper introduces a model of a local transaction dependency graph with incomplete information, constructed within a node’s memory pool. In contrast to models assuming full knowledge of the dependency structure, the proposed approach considers the case where some predecessor transactions have not yet been observed by the node. Missing dependencies are formalized, their effect on the formation of the feasible set of transactions is investigated, and the selection of the next transaction for processing is examined with regard to fees, conflicts, and the unlocking effect on dependent vertices.

Bulgakov D.A. Incomplete dependency graphs for transaction scheduling in distributed systems // Achievements of Modern Radioelectronics. 2026. V. 80. № 9. P. 122−128. DOI: https://doi.org/10.18127/j20700784-202609-13

1. Kutuzov O.I., Tatarnikova T.M. K ocenivaniyu i sopostavleniyu ocheredej klassicheskix i fraktal`ny`x sistem massovogo obsluzhivaniya. Informacionno-upravlyayushhie sistemy`. 2016. № 2(81). S. 48–55. DOI:10.15217/issn1684-8853.2016.2.48 (in Russian).
2. Saldamli G., Upadhyay C. and al. Improved gossip protocol for blockchain applications. Cluster Computing. 2022. V. 25. Iss. 3. P. 1915–1926. DOI: 10.1007/s10586-021-03504-z
3. He X., Cui Y., Jiang Y. An improved gossip algorithm based on semi-distributed blockchain network. International Conference On Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC). 2019. Guilin. P. 24–27. DOI: 10.1109/CyberC.2019.00014
4. Kaul S., Piduguralla M. i dr. Dependency-Aware Execution Mechanism in Hyperledger Fabric Architecture. Stabilization, Safety, and Security of Distributed Systems: Proceedings of 27th International Symposium. SSS 2025. Kathmandu, Nepal. DOI: 10.48550/arXiv.2509.07425
5. Narapureddy A. AI-Driven Dynamic Dependency Graph Generation for Predictive Observability in Distributed Systems. International Journal of Computer Engineering & Technology. 2025. V. 16. № 1. P. 2796–2818. DOI: 10.34218/IJCET_16_01_197
6. Guo Q., Li W. and al. Large-amount Blockchain Transaction Conflict Resolution Technology Based on Dependency Graph for Multi-property Assets. IEEE International Conference on High Performance Computing & Communications, Data Science & Systems, Smart City & Dependability in Sensor, Cloud & Big Data Systems & Application (HPCC/DSS/SmartCity/DependSys). Melbourne, Australia. 2023. P. 443–450. DOI: 10.1109/HPCC-DSS-SmartCity-DependSys60770.2023.00067
7. Shelest M.N., Tatarnikova T.M. Metod ocenivaniya by`strodejstviya bol`shix informacionny`x sistem s klasterizaciej tranzakcij. Izvestiya vy`sshix uchebny`x zavedenij. Priborostroenie. 2022. T. 65. № 9. S. 623–629. (in Russian).
8. Zhang Z., Hong C. i al. DAG-based Blockchain Supporting Real-Time Transactions. IEEE Transactions on Parallel and Distributed Systems. 2024. 35(8). 1349–1363. DOI: 10.1109/TPDS.2024.3416751