Алгоритма для распределенных систем с шардированием для инфраструктуры устройств межмашинного взаимодействия
Автор: Котилевец И.Д., Иванова И.А.
Рубрика: Управление сложными системами
Статья в выпуске: 3, 2024 года.
Бесплатный доступ
Статья посвящена разработке консенсусного алгоритма для распределенной системы с шардированием, предназначенной для инфраструктуры устройств межмашинного взаимодействия. Проанализированы существовавшие преимущества и недостатки распределенных систем и шардирования, а также описаны необходимые свойства консенсусного алгоритма. Рассмотрены модели коммуникаций в распределенных системах, включая синхронную, асинхронную и частично синхронную системы. Представленный алгоритм предполагает частично синхронную среду доставки сообщений и обмен сообщениями между узлами через прямые соединения. Этот алгоритм обеспечивает сходимость, целостность и согласованность данных, а также отказоустойчивость и высокую масштабируемость. Алгоритм включает использование стандартного формата уникальных идентификаторов для описания узлов, хеш-функций для описания состояния раунда консенсуса и обмена сообщениями между шардами для координации узлов. Кроме того, используется функция псевдослучайных перестановок для упорядочения операций в рамках одного раунда. В завершение представлены результаты замеров быстродействия системы и общие заключения о работоспособности представленного алгоритма.
Распределенные системы, консенсусный алгоритм, шардирование, отказоустойчивость, согласованность данных
Короткий адрес: https://sciup.org/148330050
IDR: 148330050 | DOI: 10.18137/RNU.V9187.24.03.P.74
Список литературы Алгоритма для распределенных систем с шардированием для инфраструктуры устройств межмашинного взаимодействия
- Baran P. On distributed communications: I. Introduction to distributed communications networks. Santa Monica, CA: RAND Corporation, 1964. DOI: 10.7249/RM3420
- Lamport L., Shostak R., Pease M. The Byzantine Generals Problem // AC M Transactionson Programming Languages and Systems. 1982. Vol. 4. No. 3. P. 382–401. URL: https://lamport.azurewebsites.net/pubs/byz.pdf (accessed 22.04.2024).
- Lamport L. The Part-Time Parliament // AC M Transactions on Computer Systems. 1998. Vol. 16. No. 2. P. 133–169. URL: https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf (accessed 22.04.2024).
- Fischer M., Lynch N., Paterson M. Impossibility of Distributed Consensus with One Faulty Process // Journal of the Association for Computing Machinery. 1985. Vol. 32. No. 2. P. 374–382. DOI: https://doi.org/10.1145/3149.214121
- Dwork C., Lynch N., Stockmeyer L. Consensus in the Presence of Partial Synchrony // Journal of the Association for Computing Machinery. 1988. Vol. 35. No. 2. P. 288–323. DOI: https://doi.org/10.1145/42282.42283
- Chan B.Y., Pass R. Simplex Consensus: A Simple and Fast Consensus Protocol // Rothblum G., Wee H. (Eds) Theory of Cryptography. TCC 2023. Lecture Notes in Computer Science. Vol. 14372. Springer, Cham, 2023. DOI: https://doi.org/10.1007/978-3-031-48624-1_17
- Malkhi D., Nayak K. HotStuff-2: Optimal Two-Phase Responsive BFT // Cryptology ePrint Archive. 2023. Paper 2023/397. URL: https://ia.cr/2023/397 (accessed 22.04.2024).
- Zamani M., Movahedi M., Raykova M. RapidChain: Scaling Blockchain via Full Sharding // CCS ‘18: Proceedings of the 2018 AC M SIGSAC Conference on Computer and Communications Security. 2018. P. 931–948. DOI: https://doi.org/10.1145/3243734.3243853
- Jing Chen, Gorbunov S., Micali S., Vlachos G. Algorand agreement: Super fast and partition resilient byzantine agreement // Cryptology ePrint Archive. 2018. Paper 2018/377. URL: https://eprint.iacr.org/2018/377.pdf (accessed 22.04.2024).
- Buchman E. Kwon J., Milosevic Z. The latest gossip on BFT consensus // arXiv preprint. 2018. DOI: https://doi.org/10.48550/arXiv.1807.04938
- Ongaro D., Ousterhout J.K. In Search of an Understandable Consensus Algorithm // USENIX Annual Technical Conference. Philadelphia, PA , 2014, June 19–20. P. 305–319. URL: https://www.usenix.org/system/files/conference/atc14/atc14-paper-ongaro.pdf (accessed 10.12.2023).
- Castro M., Liskov B. Practical Byzantine Fault Tolerance // Proceedings of the Third Symposium on Operating Systems Design and Implementation. New Orleans, USA , 1999, February. Vol. 99. P. 173–186. URL: https://pmg.csail.mit.edu/papers/osdi99.pdf (accessed 10.12.2023).
- Buterin V. Ethereum: A Next-Generation Smart Contract and Decentralized Application Platform // Ethereum Foundation. 2014. URL: https://ethereum.org/content/whitepaper/whitepaper-pdf/ Ethereum_Whitepaper_-_Buterin_2014.pdf (accessed 03.12.2023).
- van Saberhagen N. CryptoNote V 2.0 // Monero Project. 2013. October 17. URL: https://github.com/monero-project/research-lab/blob/master/whitepaper/whitepaper.pdf accessed
- 18 Bénézit F., Thiran P., Vetterli M. Interval consensus: From quantized gossip to voting // 2009 IEEE International Conference on Acoustics, Speech and Signal Processing. Taipei, Taiwan, 2009. P. 3661–3664. DOI: 10.1109/ICASSP.2009.4960420
- Pelckmans K. Randomized Gossip Algorithms for Achieving Consensus on the Majority Vote // IFAC Proceedings Volumes. 2013. Vol. 46. No. 11. P. 275–280. DOI: https://doi.org/10.3182/20130703-3-FR-4038.00099
- Baird L. The Swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance // Swirlds tech report. 2016. SWIRLDS -TR-2016-01. URL: https://www.swirlds.com/downloads/SWIRLDS - TR-2016-01.pdf (accessed 03.12.2023).
- van Ditmarsch H., Gattinger M., Ramezanian R. Everyone Knows That Everyone Knows: Gossip Protocols for Super Experts // Studia Logica. 2023. Vol. 111. Pp. 453–499. DOI: https://doi.org/10.1007/s11225-022-10032-3
- Stathakopoulou C., Pavlovic M., Vukolić M. State Machine Replication Scalability Made Simple // EuroSys ‘22: Proceedings of the Seventeenth European Conference on Computer Systems. Rennes, France, April 5–8, 2022. Pp. 17–33. DOI: https://doi.org/10.1145/3492321.3519579
