1. ACPS
  2. Всі випуски
  3. Випуск 6, Номер 1, 2021
  4. Model of Process Synchronization in Through Analysis

Model of Process Synchronization in Through Analysis

ACPS.
2021;
Випуск 6, Номер 1
: cc. 33 - 38
https://doi.org/10.23939/acps2021.01.033
Автори:
  1. Oleksandr Martynyuk
1
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.

network information system
multilevel behavioral model
синхронізація
extended hierarchical Petri net
  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: https://doi.org/10.1109/ICDCS.2018.00142
    https://doi.org/10.1109/ICDCS.2018.00142
  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: 
    https://doi.org/10.1007/978-1-4614-7535-4_20
  5. Ranganathan A., Roy Campbell Roy. (2007). What is the Complexity of a Distributed Computing System? [online]. Available at: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.8 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: 
    https://doi.org/10.1016/j.anucene.2016.02.002
  7. Safety-Critical Computer Systems — Open Questions and Approaches. (2012) Slideserve. Slideserve. 17 July 2012. Web. 3 Dec. [online]. Available at: <http://www.slideserve.com/brygid/safety-critical-computer-systems-open-q...
  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: https://www.matec-conferences.org/articles/matecconf/abs/2017/39/matecco....
    https://doi.org/10.1051/matecconf/201712502033
  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.
    https://doi.org/10.4236/ijcns.2015.812042
  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: 
    https://doi.org/10.1007/s11334-007-0032-1
  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: 
    https://doi.org/10.1007/978-3-642-31513-8_43
  13. Latha C., Shashidhara H. (2010). Clock Synchronization in Distributed Systems. 5th International Conference on Industrial and Information Systems, pp. 475-480. Available at: https://link.springer.com/chapter/10.1007/978-3-642-31513-8_43
    https://doi.org/10.1109/ICIINFS.2010.5578658
  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: https://www.frontiersin.org/article/10.3389/fpsyg.2017.00945
    https://doi.org/10.3389/fpsyg.2017.00945
  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: 
    https://doi.org/10.1038/srep00099
  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: https://doi.org/10.1007/978-3-030-23502-4_19
  17. van Steen, M., Tanenbaum, A.S. (2016). A brief introduction to distributed systems. Computing 98, pp. 967-1009. Available at: 
    https://doi.org/10.1007/s00607-016-0508-7
  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:
    https://doi.org/10.1145/3293611.3331637
  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: 
    https://doi.org/10.1109/MSP.2008.926661
  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: 
    https://doi.org/10.1109/CDC.2012.6426372
  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:
    https://doi.org/10.1109/MED.2015.7158896
  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: https://dsf.berkeley.edu/papers/icde14-blazes.pdf
    https://doi.org/10.1109/ICDE.2014.6816639
  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: https://users.dcc.uchile.cl/~pbarcelo/ameloot.pdf
    https://doi.org/10.1145/2694413.2694415
  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: http://www.vldb.org/pvldb/vol8/p185-bailis.pdf
    https://doi.org/10.14778/2735508.2735509
  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:
    https://dl.acm.org/doi/10.1145/2463664.2465224
  26. Whittaker M., Hellerstein J. (2018). Interactive checks for coordination avoidance. Proceedings of the VLDB Endowment 12.1 . pp. 14-27. Available at: https://link.springer.com/article/10.1007/s00778-020-00628-3
    https://doi.org/10.14778/3275536.3275538
  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: https://onlinelibrary.wiley.com/doi/abs/10.1002/rnc.1702
  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: https://www.researchgate.net/publication/224161958_Passivity-based_outpu...
  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: https://ieeexplore.ieee.org/abstract/document/5718176
    https://doi.org/10.1109/CDC.2010.5718176
  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: http://www.cs.iit.edu/~xli/paper/Journal/Disco-TPDS.pdf
    https://doi.org/10.1109/TPDS.2014.2312198
  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: https://www.researchgate.net/publication/256925910_Compositional_Transie...
    https://doi.org/10.1109/TCNS.2014.2304868
  32. Shahadet H.S. (2020). Global Clock Issue in Distributed System. (Online) Available at: https://www.researchgate.net/publication/344013284_Global_C lock_Issue_in_Distributed_System
  33. Kshemkalyani A., Singhal M. (2008). Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press. p. 756. Available at: https://eclass.uoa.gr/modules/document/file.php/D245/2015/DistrComp.pdf
    https://doi.org/10.1017/CBO9780511805318
  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: https://www.spinellis.gr/pubs/jrnl/2004-ACMCS- p2p/html/AS04.pdf
    https://doi.org/10.1145/1041680.1041681
  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:
    https://doi.org/10.1109/ISPDC.2005.19
  36. Komenda J., Masopust T., van Schuppen J. (2013). Coordination Control of Distributed Discrete-Event Systems. Available at:
    https://doi.org/10.1007/978-1-4471-4276-8_8
  37. Ongaro D., Ousterhout J.K. (2014). In search of an understandable consensus algorithm. USENIX annual technical conference. pp. 305-319. Available at: https://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14
  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:
    https://doi.org/10.1109/HPCMP-UGC.2006.20
  39. Go Concurrency Patterns. (2021). (Online). Available at: https://talks.golang.org/2012/concurrency.slide#6
  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:
    https://doi.org/10.1109/ACCESS.2020.3021858
  41. Murata T. (1989). Petri Nets: Properties, Analysis and Applications. Proceedings of the IEEE. 77 (4). pp. 541-558. Available at:
    https://doi.org/10.1109/5.24143
  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: https://link.springer.com/chapter/10.1007/978-3-662-58381-4_4
    https://doi.org/10.1007/978-3-662-58381-4_4
  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:
    https://doi.org/10.1007/978-3-642-38709-8_26
  44. Gainer P., Linker S., Dixon C., Hustadt U. (2020). Multi-scale verification of distributed synchronization. Formal Methods in System, Springer, 2020. Available at: https://link.springer.com/article/10.1007/s10703-020-00347-z
    https://doi.org/10.1007/s10703-020-00347-z
  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: https://arxiv.org/pdf/1305.7410.pdf
    https://doi.org/10.1166/sl.2013.2653
  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: 
    https://doi.org/10.4108/eai.21-4-2016.151160
  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:
    https://doi.org/10.1007/978-3-319-66335-7_14
  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. https://ieeexplore.ieee.org/document/8924314
    https://doi.org/10.1109/IDAACS.2019.8924314