Adaptive Virtual Organisms : A Compositional Model for Complex Hardware-software Binding

• Autorzy: Paduraru Ciprian Ionut , Stefanescu Gheorghe

Identyfikatory

DOI

10.3233/FI-2020-1919

• Języki publikacji: EN

Abstrakty

EN

The relation between a structure and the function it runs is of interest in many fields, including computer science, biology (organ vs. function) and psychology (body vs. mind). Our paper addresses this question with reference to computer science recent hardware and software advances, particularly in areas as Robotics, Self-Adaptive Systems, IoT, CPS, AI-Hardware, etc. At the modelling, conceptual level our main contribution is the introduction of the concept of "virtual organism" (VO), to populate the intermediary level between reconfigurable hardware agents and intelligent, adaptive software agents. A virtual organism has a structure, resembling the hardware capabilities, and it runs low-level functions, implementing the software requirements. The model is compositional in space (allowing the virtual organisms to aggregate into larger organisms) and in time (allowing the virtual organisms to get composed functionalities). The virtual organisms studied here are in 2D (two dimensions) and their structures are described by 2D patterns (adding time, we get a 3D model). By reconfiguration an organism may change its structure to another structure in the same 2D pattern. We illustrate the VO concept with a few increasingly more complex VO's dealing with flow management or a publisher-subscriber mechanism for handling services. We implemented a simulator for a VO, collecting flow over a tree-structure (TC-VO), and the quantitative results show reconfigurable structures are better suited than fixed structures in dynamically changing environments. Finally, we briefly show how Agapia - a structured parallel, interactive programming language where dataflow and control flow structures can be freely mixed - may be used for getting quick implementations for VO's simulation.

Słowa kluczowe

EN

2D regular expressions; agapia programming; distributed programming languages; hardware-software binding; heterogeneous systems; hybrid systems; self-organizing autonomic computing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 173, nr 2-3
• Strony: 139--176
• Opis fizyczny: Bibliogr. 50 poz., rys., tab.

Twórcy

autor

Paduraru Ciprian Ionut

• Department of Computer Science, University of Bucharest, Bucharest, Romania

autor

Stefanescu Gheorghe

• Department of Computer Science, University of Bucharest, Bucharest, Romania

Bibliografia

• [1] Bhowmik S, Tariq MA, Koldehofe B, Dürr F, Kohler T, Rothermel K. High Performance Publish/Subscribe Middleware in Software-Defined Networks. IEEE/ACM Trans. Netw., 2017. 25(3):1501-1516. doi:10.1109/TNET.2016.2632970.
• [2] Stoica I, Morris RT, Karger DR, Kaashoek MF, Balakrishnan H. Chord: A scalable peer-to-peer lookup service for internet applications. In: SIGCOMM. 2001 pp. 149-160. doi:10.1145/383059.383071.
• [3] Kephart J, DMChess. The vision of autonomic computing. Computer, 2003. doi:10.1109/MC.2003.1160055.
• [4] Román M, Hess C, Cerqueira R, Ranganathan A, Campbell RH, Nahrstedt K. A middleware infrastructure for active spaces. IEEE pervasive computing, 2002. 1(4):74-83. doi:10.1109/MPRV.2002.1158281.
• [5] Zeng L, Benatallah B, Ngu AH, Dumas M, Kalagnanam J, Chang H. QoS-aware middleware for web services composition. IEEE Transactions on software engineering, 2004. 30(5):311-327. doi:10.1109/TSE.2004.11.
• [6] Ando N, Suehiro T, Kitagaki K, Kotoku T, Yoon WK. RT-middleware: distributed component middleware for RT (robot technology). In: 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE, 2005 pp. 3933-3938. doi:10.1109/IROS.2005.1545521.
• [7] Hadim S, Mohamed N. Middleware: Middleware challenges and approaches for wireless sensor networks. IEEE distributed systems online, 2006. (3):1. doi:10.1109/MDSO.2006.19.
• [8] Pietzuch PR, Bacon J. Hermes: A Distributed Event-Based Middleware Architecture. In: 22nd International Conference on Distributed Computing Systems, Workshops (ICDCSW ’02) July 2-5, 2002, Vienna, Austria, Proceedings. 2002 pp. 611-618. doi:10.1109/ICDCSW.2002.1030837.
• [9] Kleene SC. Representation of events in nerve nets and finite automata. Technical report, RAND PROJECT AIR FORCE SANTA MONICA CA, 1951. Also in: Automata Studies (Eds. Shannon, C. E. and McCarthy, J.), Annals of Mathematics Studies, Princeton University Press, 1956. ISBN: 0691079161.
• [10] Conway JH. Regular algebra and finite machines. Courier Corporation, 2012. ISBN: 0486485838.
• [11] Dennis JB. First version of a data flow procedure language. In: Programming Symposium. Springer, 1974 pp. 362-376. doi:10.1007/3-540-06859-7_145.
• [12] Halbwachs N, Caspi P, Raymond P, Pilaud D. The synchronous data flow programming language LUSTRE. Proceedings of the IEEE, 1991. 79(9):1305-1320. doi:10.1109/5.97300.
• [13] Giammarresi D, Restivo A. Two-dimensional languages. Handbook of formal languages, 1997. 3:215-267. doi:10.1007/978-3-642-59126-6_4.
• [14] Lindgren K, Moore C, Nordahl M. Complexity of two-dimensional patterns. Journal of statistical physics, 1998. 91(5):909-951. doi:10.1023/A:1023027932419.
• [15] Wolfram S. A new kind of science, volume 5. Wolfram media Champaign, 2002. ISBN: 1579550088.
• [16] Paduraru C, Stefanescu G. Self-assembling heterogeneous interactive systems. In: ECSA - Systems of systems 2016. ACM, 2016. doi:10.1145/3175731.3176174.
• [17] Banu-Demergian I, Paduraru C, Stefanescu G. A new representation of two-dimensional patterns and applications to interactive programming. In: FSEN 2013, LNCS 8161. Springer, 2013 pp. 172-206. doi:10.1007/978-3-642-40213-5_12.
• [18] Stefanescu G. A Quest for Kleene Algebra in 2 Dimensions. In: Proceedings RAMiCS 2015, LNCS. Springer, 2015 pp. 3-26. doi:10.1007/978-3-319-24704-5_1.
• [19] Giammarresi D, Restivo A, Seibert S, Thomas W. Monadic second-order logic over rectangular pictures and recognizability by tiling systems. Information and computation, 1996. 125(1):32-45. doi:10.1006/inco.1996.0018.
• [20] Paduraru C, Mincu R, Stefanescu G. Multi-Level Control Mechanisms for Non-Structured and Structured 2-Dimensional Self-Assembling. In: Proc. SASO 2017. 2017 pp. 101-110. doi:10.1109/SASO.2017.19.
• [21] Dijkstra EW, Feijen WH, Van Gasteren AM. Derivation of a termination detection algorithm for distributed computations. In: Control Flow and Data Flow: concepts of distributed programming, pp. 507-512. Springer, 1986. doi:10.1016/0020-0190(83)90092-3.
• [22] Dehaene S, Lau H, Kouider S. What is consciousness, and could machines have it? Science, 2017. 358(6362):486-492. doi:10.1126/science.aan8871.
• [23] Dragoi C, Stefanescu G. AGAPIA v0. 1: A programming language for interactive systems and its typing system. Electronic Notes in Theoretical Computer Science, 2008. 203(3):69-94. doi:10.1016/j.entcs.2008.04.087.
• [24] Popa A, Sofronia A, Stefanescu G. High-level Structured Interactive Programs with Registers and Voices. J. UCS, 2007. 13:1722-1754. doi:10.3217/jucs-013-11-1722.
• [25] Paduraru C. Dataflow Programming Using AGAPIA. In: Proceedings ISPDC 2014. IEEE, 2014 pp. 87-94. doi:10.1109/ISPDC.2014.15.
• [26] Paduraru C. Research on AGAPIA language, compiler and applications. Ph.D. thesis, University of Bucharest, 2015.
• [27] Banu-Demergian IT, Stefanescu G. On contour representation of two dimensional patterns. Carpathian Journal of Mathematics, 2016. pp. 37-47. ISSN: 18434401. URL https://www.jstor.org/stable/44000087.
• [28] Banu-Demergian I, Stefanescu G. Towards a Formal Representation of Interactive Systems. Fundamenata Informaticae, 2014. 131:313-336. doi:10.3233/FI-2014-1017.
• [29] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms, Third Edition, Chapter 35: Approximation Algorithms. The MIT Press, 3rd edition, 2009. ISBN: 0262033844, 9780262033848.
• [30] Broy M, Stefanescu G. The algebra of stream processing functions. Theoretical Computer Science, 2001. 258(1-2):99-129. doi:10.1016/S0304-3975(99)00322-9.
• [31] Abadi M, Agarwal A, Barham P, Brevdo E, Chen Z, Citro C, Corrado GS, Davis A, Dean J, Devin M, et al. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint arXiv:1603.04467, 2016. URL https://arxiv.org/abs/1603.04467.
• [32] Yim M, Shen WM, Salemi B, Rus D, Moll M, Lipson H, Klavins E, Chirikjian GS. Modular self-reconfigurable robot systems [grand challenges of robotics]. IEEE Robotics & Automation Magazine, 2007. 14(1):43-52. doi:10.1109/MRA.2007.339623.
• [33] Dorigo M, Trianni V, Şahin E, Groß R, Labella TH, Baldassarre G, Nolfi S, Deneubourg JL, Mondada F, Floreano D, Gambardella LM. Evolving Self-Organizing Behaviors for a Swarm-Bot. Autonomous Robots, 2004. 17:223-245. doi:10.1023/B:AURO.0000033973.24945.f3.
• [34] Cao YU, Fukunaga AS, Kahng A. Cooperative Mobile Robotics: Antecedents and Directions. Autonomous Robots, 1997. 4:7-27. doi:10.1023/A:1008855018923.
• [35] Hosokawa K, Fujii T, Kaetsu H, Asama H, Kuroda Y, Endo I. Self-organizing collective robots with morphogenesis in a vertical plane. JSME International Journal Series C Mechanical Systems, Machine Elements and Manufacturing, 1999. 42:195-202. doi:10.1109/ROBOT.1998.680616.
• [36] Gilpin K, Knaian A, Rus D. Robot pebbles: One centimeter modules for programmable matter through self-disassembly. In: Robotics and Automation (ICRA), 2010 IEEE International Conference on. IEEE, 2010 pp. 2485-2492. doi:10.1109/ROBOT.2010.5509817.
• [37] Wei H, Cai Y, Li H, Li D, Wang T. Sambot: A self-assembly modular robot for swarm robot. In: Robotics and Automation (ICRA), 2010 IEEE International Conference on. IEEE, 2010 pp. 66-71. doi:10.1109/ROBOT.2010.5509214.
• [38] Collier TC, Taylor C. Self-organization in sensor networks. Journal of Parallel and Distributed Computing, 2004. 64:866-873. doi:10.1016/j.jpdc.2003.12.004.
• [39] Wischhof L, Ebner A, Rohling H. Information dissemination in self-organizing intervehicle networks. IEEE Transactions on intelligent transportation systems, 2005. 6:90-101. doi:10.1109/TITS.2004.842407.
• [40] Tang C, Xu Z, Dwarkadas S. Peer-to-peer Information Retrieval Using Self-organizing Semantic Overlay Networks. In: Proceedings SIGCOMM ’03. ACM, 2003 pp. 175-186. doi:10.1145/863955.863976.
• [41] Cerpa A, Estrin D. ASCENT: Adaptive self-configuring sensor networks topologies. IEEE transactions on mobile computing, 2004. 3(3):272-285. doi:10.1109/TMC.2004.16.
• [42] McKinley PK, Sadjadi SM, Kasten EP, Cheng BH. Composing adaptive software. Computer, 2004. 37(7):56-64. doi:10.1109/MC.2004.48.
• [43] Weyns D, Schmerl B, Grassi V, Malek S, Mirandola R, Prehofer C, Wuttke J, Andersson J, Giese H, Göschka KM. On patterns for decentralized control in self-adaptive systems. In: Software Engineering for Self-Adaptive Systems II, pp. 76-107. Springer, 2013. doi:10.1007/978-3-642-35813-5_4.
• [44] Sykes D, Magee J, Kramer J. Flashmob: distributed adaptive self-assembly. In: Proceedings of the 6th International Symposium on Software Engineering for Adaptive and Self-Managing Systems. ACM, 2011 pp. 100-109. doi:10.1145/1988008.1988023.
• [45] Macías-Escrivá FD, Haber R, Del Toro R, Hernandez V. Self-adaptive systems: A survey of current approaches, research challenges and applications. Expert Systems with Applications, 2013. 40(18):7267-7279. doi:10.1016/j.eswa.2013.07.033.
• [46] Lewis PR, Chandra A, Parsons S, Robinson E, Glette K, Bahsoon R, Torresen J, Yao X. A survey of self-awareness and its application in computing systems. In: Self-Adaptive and Self-Organizing Systems Workshops (SASOW), 2011 Fifth IEEE Conference on. IEEE, 2011 pp. 102-107. doi:10.1109/SASOW.2011.25.
• [47] Bruni R, Corradini A, Gadducci F, Lafuente AL, Vandin A. Modelling and analyzing adaptive self-assembly strategies with Maude. Science of Computer Programming, 2015. 99:75-94. doi:10.1016/j.scico.2013.11.043.
• [48] Khakpour N, Jalili S, Talcott C, Sirjani M, Mousavi M. Formal modeling of evolving self-adaptive systems. Science of Computer Programming, 2012. 78(1):3-26. doi:10.1016/j.scico.2011.09.004.
• [49] Calinescu R, Gerasimou S, Banks A. Self-adaptive Software with Decentralised Control Loops. In: FASE, volume 15. 2015 pp. 235-251. doi:10.1007/978-3-662-46675-9_16.
• [50] Tamura G, Villegas N, Müller H, Sousa JP, Becker B, Pezze M, Karsai G, Mankovskii S, Schäfer W, Tahvildari L, et al. Towards practical runtime verification and validation of self-adaptive software systems, 2013. doi:10.1007/978-3-642-35813-5_5.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).