Model of Process Synchronization in Through Analysis

: pp. 33 - 38
Odessa Polytechnic State University

Synchronization of parallel processes of distributed information systems (DIS) has been largely determined by decisions taken at the stages of their design. Having already been in structural and functional models, when determining cause- and-effect relationships for events and actions in DIS components, it becomes necessary to coordinate them. In the proposed multilevel systemic, structural and functional synchronization model, a hierarchy of such causal relationships with interlevel mappings, inheritance and encapsulation of events and actions have been formed. The model has been also based on hierarchical extended Petri nets, which make it possible to represent various aspects of a special analysis of technical diagnostics, in particular, analysis of correctness, verification, testing, for the adopted display of the asynchronous-behavioral nature of the multilevel interaction of DIS processes. Features of the synchronization model include mapping operations for cross- level inheritance and encapsulations that synchronize events and actions, as well as end-to-end synchronized quasi-order relationships and compatibility for them. The synchronization model is also distinguished by the possibility of specializing its objects, operations and relations for the tasks of check and recognition of behavioral properties set for analysis and verification, basic in technical diagnostics, including in online and offline testing. The synchronization model has allowed one to determine the formal conditions for methods of end-to-end asynchronous coordination of events and actions of multi-level models, that represent design solutions for DIS, in particular, for technical diagnostics methods, and also to reduce the computational complexity of a special synchronization analysis due to an end-to-end decomposition approach. The dimension of the synchronization model has been estimated using the representation of Petri net graphs and special graphs of reachable states using list structures. The above estimates determine the limits of applicability of the formal synchronization model.

  1. Coulouris G., Dollimore J., Kindberg T., Blair G. (2011). Distributed Systems: Concepts and Design. 5th ed. Addison-Wesley, p. 1067.
  2. Bentaleb A., Yifan L., Xin J., et al. (2016) Parallel and Distributed Algorithms. National University of Singapore. Retrieved 20 July 2018, p. 348.
  3. Blair G. (2018). Complex Distributed Systems: The Need for Fresh Perspectives. In: 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), pp. 1410-1421. Available at:
  4. Caporuscio M., Funaro M., Ghezzi C., Issarny V. (2014). ubiREST: A RESTful Service-Oriented Middleware for Ubiquitous Networking. In: Bouguettaya A., Sheng Q., Daniel F. (eds) Advanced Web Services. Springer, New York, NY. Available at:
  5. Ranganathan A., Roy Campbell Roy. (2007). What is the Complexity of a Distributed Computing System? [online]. Available at: 573&rep=rep1&type=pdf
  6. Lalit Kumar Singh, Hitesh Rajput. (2016). Ensuring safety in design of safety critical computer based systems. Annals of Nuclear Energy. Volume 92, pp. 289-294. Available at:
  7. Safety-Critical Computer Systems — Open Questions and Approaches. (2012) Slideserve. Slideserve. 17 July 2012. Web. 3 Dec. [online]. Available at: <
  8. Fokkink W. (2017). Modelling Distributed Systems. Protocol Verification with µCRL. 2nd ed. Springer. p. 173.
  9. Emad A., Mohammad K., Krayem S., Lazar I., Ahmad R. (2017). Using formal methods in distributed system design. 21st International Conference on Circuits, Systems, Communications and Computers (CSCC 2017). 125. 02033. Available at:
  10. Sari A., Akkaya M. (2015). Fault Tolerance Mechanisms in Distributed Systems. International Journal of Communications, Network and System Sciences. Vol.8 No.12. pp. 471-482.
  11. Fei X., Lu Y. (2007). Formal approach to fault diagnosis in distributed discrete event systems with OBDD. Innovations in Systems and Software Engineering. pp. 259-267. Available at:
  12. Sampath A., Tripti C. (2012). Synchronization in Distributed Systems. In: Meghanathan N., Nagamalai D., Chaki N. (eds) Advances in Computing and Information Technology. Advances in Intelligent Systems and Computing, vol 176. Springer, Berlin, Heidelberg. Available at:
  13. Latha C., Shashidhara H. (2010). Clock Synchronization in Distributed Systems. 5th International Conference on Industrial and Information Systems, pp. 475-480. Available at:
  14. Nowak A., Vallacher R., Zochowski M., Rychwalska A. (2017). Functional Synchronization: The Emergence of Coordinated Activity in Human Systems, Frontiers. Psychology. vol. 8. p. 945. Available at:
  15. Assenza S., Gutiérrez R., Gómez-Gardeñes J., Latora V., Boccaletti S. (2011). Emergence of structural patterns out of synchronization in networks with competitive interactions. Scientific Report. 1, 99. (Online) Available at:
  16. Khan M.S., Sikder R., Adnan M.A. (2019). A Hybrid Approach for Synchronizing Clocks in Distributed Systems. In: Da Silva D., Wang Q., Zhang LJ. (eds) Cloud Computing — CLOUD 2019. CLOUD 2019. Lecture Notes in Computer Science. Vol. 11513. Springer, Cham. Available at:
  17. van Steen, M., Tanenbaum, A.S. (2016). A brief introduction to distributed systems. Computing 98, pp. 967-1009. Available at:
  18. Bund J., Lenzen C., Rosenbaum W. (2019). Fault Tolerant Gradient Clock Synchronization. Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC ’19). Association for Computing Machinery, New York, NY, USA, pp. 357-365. Available at:
  19. Simeone O., Spagnolini U, Strogatz S. (2008). Distributed synchronization in wireless networks: Global synchronization via local connections. Signal Processing Magazine, IEEE. 25. pp. 81-97. Available at:
  20. Wu J., Allgöwer F. (2012). A constructive approach to Synchronization using relative information. 2012 IEEE 51st IEEE Conference on Decision and Control (CDC). pp. 5960- 5965. Available at:
  21. Khodaverdian S., Adamy J. A distributed analysis and design method for the synchronization of linear heterogeneous SISO systems by static state control. (2015). 23rd Mediterranean Conference on Control and Automation (MED). pp. 1053-1058. Available at:
  22. Alvaro P., Conway N., Hellerstein J., Maier, D. (2014). Blazes: Coordination analysis for distributed programs. Proceedings of the IEEE 30th International Conference on Data Engineering. pp. 52-63. Available at:
  23. Ameloot. T. (2014). Declarative networking: Recent theoretical work on coordination, correctness, and declarative semantics. ACM SIGMOD Record 43. 2. pp. 5-16. Available at:
  24. Bailis P., Fekete A., Franklin M., Ghodsi A., Hellerstein J., Stoica I. (2014). Coordination avoidance in database systems. Proceedings of the VLDB Endowment 8. 3. pp. 185-196. Available at:
  25. Beame P., Koutris P., Suciu D. (2013). Communication steps for parallel query processing. Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symp. Principles of Database Systems. ACM. pp. 273-284. Available at:
  26. Whittaker M., Hellerstein J. (2018). Interactive checks for coordination avoidance. Proceedings of the VLDB Endowment 12.1 . pp. 14-27. Available at:
  27. Mellish R., Napora S., Paley D.A. (2010). Backstepping control design for motion coordination of self-propelled vehicles in a flowfield. Journal Robust. Nonlinear Control, vol. 00, pp. 1-13. Available at:
  28. Yu H., Antsaklis P. (2010). Passivity-based output synchronization of networked Euler-Lagrange systems subject to nonholonomic constraints. American Control Conference (ACC). pp. 208-213. Available at:
  29. Liu Y.C., Chopra N. (2010). Synchronization of networked robotic systems on strongly connected graphs. 49th IEEE Conference on Decision and Control (CDC). pp. 3194-3199. Available at:
  30. Wang Y., Liu Y., He Y., Li X., Cheng, D. (2015). Disco: Improving Packet Delivery via Deliberate Synchronized Constructive Interference. IEEE Transactions on Parallel and Distributed Systems. 26. pp. 713-723. Available at:
  31. Caliskan S., Tabuada P. (2014). Compositional transient stability analysis of multimachine power networks. IEEE Transactions on Control of Network Systems. vol. 1, no. 1, pp. 4-14. Available at:
  32. Shahadet H.S. (2020). Global Clock Issue in Distributed System. (Online) Available at: lock_Issue_in_Distributed_System
  33. Kshemkalyani A., Singhal M. (2008). Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press. p. 756. Available at:
  34. Androutsellis-Theotokis S., Spinellis D. (2004). A survey of peer-to-peer content distribution technologies. ACM Computing Surveys, 36(4). pp. 335-371. Available at: p2p/html/AS04.pdf
  35. Khoumsi A. (2005). Coordination of Components in a Distributed Discrete-Event System. The 4th International Symposium on Parallel and Distributed Computing (ISPDC’05). pp. 299-306. Available at:
  36. Komenda J., Masopust T., van Schuppen J. (2013). Coordination Control of Distributed Discrete-Event Systems. Available at:
  37. Ongaro D., Ousterhout J.K. (2014). In search of an understandable consensus algorithm. USENIX annual technical conference. pp. 305-319. Available at:
  38. LeSueur K.G., Yetzer K., Stokes M., Krishnamurthy A., Chalker A. Distributed Tests: An ARMY Perspective. (2006). 2006 HPCMP Users Group Conference (HPCMP-UGC’06). pp. 337-346. Available at:
  39. Go Concurrency Patterns. (2021). (Online). Available at:
  40. Lima B., Faria J.P., Hierons R. (2020). Local observability and controllability analysis and enforcement in distributed testing with time constraints. IEEE Access. 8. pp. 167172-167191. Available at:
  41. Murata T. (1989). Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE. 77 (4). pp. 541-558. Available at:
  42. Amparore E.G., Donatelli S., Beccuti M., Garbi G., Miner A.S. (2018). Decision diagrams for Petri nets: a comparison of variable ordering algorithms. Transactions Petri Nets and Other Models of Concurrency. 13. pp. 73-92. Available at:
  43. Fahland D., Gierds C. (2013). Analyzing and Completing Middleware Designs for Enterprise Integration Using Coloured Petri Nets. Advanced Information Systems Engineering — 25th International Conference, CAiSE 2013. Lecture Notes in Computer Science. 7908. pp. 400-416. Available at:
  44. Gainer P., Linker S., Dixon C., Hustadt U. (2020). Multi-scale verification of distributed synchronization. Formal Methods in System, Springer, 2020. Available at:
  45. Chen Z., Zhang D., Zhu R., Ma Y., Yin P., Xie F. (2013). A review of automated formal verification of ad hoc routing protocols for wireless sensor networks. Sensor Letters. 11(5). pp. 752-764. Available at:
  46. Giammatteo P., Buccella C., Cecati C. (2016). A Proposal for a Multi-Agent based Synchronization Method for Distributed Generators in Micro-Grid Systems. EAI Endorsed Transactions on Industrial Networks and Intelligent Systems. 3. 151160. Available at:
  47. Gainer P., Linker S., Dixon C., Hustadt U., Fisher M. (2017) Investigating parametric influence on discrete synchronisation protocols using quantitative model checking. QEST 2017, Springer, Cham, LNCS, vol. 10503, pp 224-239, Available at:
  48. Martynyuk O., Drozd O., Ahmesh Tamim, Bui Van Thuong, Sachenko A., Mykhailova H., Dombrovskyi M. (2019). Hierachical Model of Behavior On-line Testing for Distributed Information Systems. The 10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications. Vol. 2. Metz, France. pp. 724-729.