DOI
10.34229/KCA2522-9664.25.1.3
УДК 004.75
Г.М. ЖОЛТКЕВИЧ
Харківський національний університет ім. В.Н. Каразіна, Харків, Україна,
g.zholtkevych@karazin.ua
А.В. ЗОЗУЛЯ
Харківський національний університет ім. В.Н. Каразіна, Харків, Україна,
anna.zozulia@karazin.ua
РЕАЛІЗОВНІСТЬ ДІАГРАМ ПОДІЙ ТА ІСНУВАННЯ
ЛОГІЧНИХ ГОДИННИКІВ
Анотація. Розглянуто проблему зв’язку між коректністю діаграми подій розподіленого обчислення з погляду комунікації між локальними процесами цього обчислення та існуванням для такої діаграми логічного годинника. Проблему досліджено за допомогою програми The Coq Proof Assistant без припущення про справедливість закону виключення третього. Інакше кажучи, отримані результати є коректними з погляду конструктивної логіки, що важливо для комп’ютерних наук. Формально доведено, що існування логічного годинника для розподіленого обчислення забезпечує іррефлексивність причинно-наслідкового зв’язку, пов’язаного з цим обчисленням. Сформульовано гіпотезу про справедливість оберненого твердження.
Ключові слова: розподілені обчислення, хмарна платформа, блокчейн, цифрові розподілені реєстри, глобальний час, логічний годинник, упорядкування подій.
повний текст
СПИСОК ЛІТЕРАТУРИ
- 1. Nakamoto S. Bitcoin: A peer-to-peer electronic cash system. 2009. URL: https://doi.org/10.1002/JSC.2148 .
- 3. Lundelius J., Lynch N. An upper and lower bound for clock synchronization. Information and Control. 1984. Vol. 62, Iss. 2–3. P. 190–204. https://doi.org/10.1016/S0019-9958(84)80033-9. .
- 4. Lamport L. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM. 1978. Vol. 31, N 7. P. 558–565. https://doi.org/10.1145/359545.359563. .
- 5. The Coq Proof Assistant. 2024. URL: https://coq.inria.fr. .
- 6. Bertot Y. Castran P. Interactive theorem proving and program development. Coq’Art: The calculus of inductive constructions. Berlin; Heidelberg, Springer, 2004. 472 p. https://doi.org/10.1007/978-3-662-07964-5. .
- 7. Andon P.I., Doroshenko A.Y., Ivanenko P.A., Yatsenko O.A. Glushkov’s algorithmic algebras and automated parallel computing design. Cybernetics and Systems Analysis. 2023. Vol. 59, N 5. P. 687–697. https://doi.org/10.1007/s10559-023-00604-z. .