61 Novel Opportunities for Tuple-based Coordination: XPath, the Blockchain, and Stream Processing Stefano Mariani∗ , Andrea Omicini† , Giovanni Ciatto† ∗ Department of Sciences and Methods for Engineering Università degli Studi di Modena e Reggio Emilia Reggio Emilia, Italy Email: stefano.mariani@unimore.it † Department of Computer Science and Engineering Università di Bologna Cesena, Italy Email: andrea.omicini@unibo.it, giovanni.ciatto@unibo.it Abstract—The increasing maturity of some well-established reader with some conclusive remarks along with an outlook technologies – such as XPath – along with the sharp rise of on future research (Section IV). brand-new ones – i.e. the blockchain – presents new opportunities to researchers in the field of multi-agent coordination. In this II. E NABLING T ECHNOLOGIES position paper we briefly discuss a few technologies which, once suitably interpreted and integrated, have the potential to impact Our elaboration on the novel opportunities for tuple-based the very roots of tuple-based coordination as it stems from the coordination models takes its move from three promising archetypal L INDA model. technologies: XPath, a well-established technology whose po- tential impact on observability of tuples and pattern matching I. I NTRODUCTION (Subsection II-A) has been largely overlooked; the blockchain, In spite of their age – the original L INDA model dates back which has recently got momentum amongst both industry prac- to more than thirty years ago [1] – coordination models have titioners and research teams in academia (Subsection II-B); still to reach their full maturity and diffusion in real-world and stream processing, which has been around for a while but applications. This is mostly due to their early emergence in is now more affordable and pervasive than ever before, espe- the literature: open distributed systems, where coordination is cially if in-stream processing is concerned (Subsection II-C). a key issue, have become common practice in the software A. XPath engineering area only in the last decade [2]. Nevertheless, coordination models and technologies are to become essential XPath [7] is a major element in the XSLT standard, aimed in forthcoming scenarios such as the Internet of Things (IoT) at enabling easy navigation through elements and attributes of [3], as well as in applications where the need for pervasive an XML document. XPath provides developers with path expressions, making intelligence [4] can be addressed effectively by multi-agent it possible to select nodes (or sets of nodes) in an XML systems (MAS) [5]. document: element, attribute, text, namespace, processing- Thus, the next decade is likely to determine the extent to instruction, comment, and document nodes, organised in a which coordination technologies may impact on real applica- tree-like structure—whose root is, indeed, the XML document tions. Their success is going to depend, on the one hand, on the root element. Nodes have relationships – namely, parent, expressiveness of coordination models, since the complexity of children, siblings, ancestors, and descendants – that XPath application scenarios is growing steadily; on the other hand, on allows to be easily navigated by exploiting path expressions, the ability of coordination middleware to integrate and exploit which are combinations of the name of an XML node/attribute, the novel technologies emerging from the newest application selection symbols (i.e. // enabling to match nodes wher- areas, since that would promote industry adoption. ever they are in current XML document), predicates (i.e. Accordingly, in this position paper we speculate on the position() enabling to precisely match nodes among sib- opportunities provided by a few technologies – some well- lings), and wildcard symbols (i.e. @* to match any attribute established, some brand-new – once they are integrated within node). As an example, path expression the most expressive and developed coordination models, that is, tuple-based ones [6]. Thus, in the remainder of this paper /bookstore/book[position()<3] we first (Section II) briefly introduce the enabling technologies matches the first two book nodes children of the bookstore – namely, XPath, the blockchain, and stream processing – element, whereas then (Section III) we foresee their impact on tuple-based coordination models and technologies, finally we provide the //title[@*] 62 matches all title elements which have at least one attribute in open networks, at once. As a result, with the blockchain (i) (regardless of its kind). establishing trust between parties is no longer necessary, since XPath path expressions can be even more expressive by they only have to trust the technology—the blockchain; (ii) exploiting XPath axes, which define sets of nodes relative transparency comes for free, as the ledger is distributed and to the current one, such as ancestor (to match parents, all peers involved in a transaction perceive the same state of grandparents, etc. of the current node), descendant (to the blockchain; (iii) accountability, too, is naturally supported match children, grandchildren, etc.), following-sibling as for transparency. to match all the siblings after the current element—and many As it will be further elaborated in Section III, the blockchain others1 . A complete path expression is thus made up of an technology could play a fundamental role in expanding the axis, a node selection instruction, and optionally a predicate business domains suitable for tuple-based coordination while for further filtering. As an example, path expression also improving infrastructural support. For instance, (i) nodes synchronisation and consensus may well support implemen- child::*/child::price tation of distributed tuple spaces – traditionally based on matches all price grandchildren of the current node. distributed hash tables techniques [11] –; (ii) smart contracts By combining all the above XPath language constructs, may be exploited as a means to consistently enforce global many interesting and novel forms of pattern matching for coordination rules [12]; (iii) transactions may play the role of tuple-based coordination can be conceived, thus providing a tuple space primitives in privacy/security demanding applica- new dimension for associative access, a typical feature of such tion domains. a models [6]. For instance, it is possible to select an XML element (tuple argument) regardless of its location within the C. Stream Processing XML document (tuple), that is, with no clue on the structure In its very essence, a stream processing engine is just a of the XML document itself (i.e. depth and breadth of the tree sort of data processing engine that is designed to deal with or a given sub-tree)—as further commented in Section III. infinite data sets [13]. Many other definitions exist, typically focussing on specific issues of stream processing, such as B. Blockchain whether they process data in (near) real-time or in batch mode, The blockchain is a shared ledger distributed across a net- whether they fetch and post data to databases or devices (in work [8] where transactions are verified against programmed the former case they are often called query engines), etc. With rules of the blockchain itself, and persistently tracked in the aim of being as much inclusive as possible w.r.t. actual append-only blocks within the ledger itself. Permissionless streaming technologies – many of which are maintained by blockchains are open: any participant can view transactions, the Apache Foundation2 – we prefer to stick with the more even anonymously—as in Bitcoin blockchain [9]. Instead, essential definition provided. permissioned blockchains allow participants to inspect solely Stream processing engines are a de facto standard for those transactions relevant to them—as in the Hyperledger implementing the big data infrastructures underlying many Project [10]. IoT applications [3], where they are often merely exploited Transactions are asset transfers onto or off of a ledger, as gateway components pushing data to centralised cloud- whose blocks are synchronised with all other ledgers in the based analytics platforms—thus, they are mostly used in same network. Consensus among nodes (copies of the ledger) batch processing mode, on finite slices of data. Our focus about transactions verification occurs through programmed here is instead on in-stream processing, that is, actually, on rules called smart contracts, and ensures that ledgers are unbounded streams of data which are continuously processed exact copies, lowering the risk of fraudulent operations— in order to keep the rest of the system up-to-date with the statistically, because tampering would have to involve many most recent information. nodes simultaneously. Smart contracts are programs directly In-stream processing engines are usually composed by a executing on the blockchain network, which encode the busi- front-end of fault-tolerant data buffers for storing incoming ness rules that transactions must abide to so as that all par- streams, a back-end of stream filters and processors coordinat- ticipants can enforce verification consistently. Cryptographic ing to split the computational load and re-assemble results, and hashes and asymmetric key encryption complete the picture a storage layer for both processing state and output data. The by guaranteeing blocks’ integrity and identification of partici- front-end takes care of some crucial services such as stream pants, respectively, with no need for a secure communication replay, that is, the possibility to rollback a stream to fetch older channel. data, possibly already processed, in case of failures of any Whether it is used within its most famous business domain kind. The back-end of processing nodes is obviously mostly – that is, supporting cryptocurrencies such as Bitcoin [9] concerned with providing the functionalities regarding data – or in other areas such as supply chain management and 2 To name the most famous ones, Apache Storm (http://storm.apache.org/), medical records tracking [8], the blockchain is explicitly Apache Spark (https://spark.apache.org/), and Apache Kafka (https://kafka. conceived to tackle all the problems of business transactions apache.org/). A less-known and relatively recent but promising stream pro- cessing engine specifically conceived for on-board processing in IoT scenarios 1 See https://www.w3schools.com/xml/xpath axes.asp worth mentioning is Apache Edgent (http://edgent.apache.org/docs/overview). 63 aggregation required by the application at hand, but may also smart contracts (as coordination laws), and the shared ledger be in charge of providing ancillary services such as lineage concept itself (as the shared tuple space) straightforwardly tracking, that is, correlation of streaming and processing events enable, respectively, to: (i) univocally and securely identify stemming from the same lineage of descendants for monitoring who is interacting with whom (accountability); (ii) consistently and debugging purpose. manage distributed interactions and enforce coordination laws In Section III we discuss how stream processing techniques while seamlessly supporting dynamic construction of interac- may fruitfully integrate with tuple-based coordination as well tion traces (traceability); (iii) greatly enhancing observability as with the other technologies mentioned in this section. For of the whole coordination process (transparency). For instance, instance, if a data stream in mapped onto a (set of) XML- a blockchain-based distributed tuple space may conveniently tuple(s), continuously updated and observed through XPath track medical records exchange and manipulation. In fact, queries, a slew of novel opportunities arise. On the one it would be naturally capable of relating interaction events hand, stream processing may bring to tuple-based coordination through transactions, providing for free a sort of book-keeping (near) real-time efficiency; on the other hand, it may benefit of the history of interactions occurred within the system – who of tuple spaces as a form of buffering for stream replay, and accessed what, due to which previous events, leading to which of blockchain transactions and smart contracts to guarantee state of affairs – which is an invaluable information for, i.e., lineage tracking. accountability purpose. Finally, stream processing could extend the reach of tuple- III. I MPACT ON T UPLE - BASED C OORDINATION based coordination towards IoT-related scenarios, where, on Tuple-based coordination constitutes the most relevant and the one hand, the pace at which data and events are generated suitable class of models and technologies for managing the demands indeed for stream processing techniques, while, on interaction space in complex software systems such as mas the other hand, the amount of loosely-coupled interactions and pervasive intelligent applications [14]. In the remainder among distributed components that need to be fruitfully gov- of this section, we foresee the potential impact of the tech- erned according to a system goal requires decentralised coor- nologies briefly presented in Section II on the coordination of dination mechanisms. There, for instance, sensor and actuator complex software systems via tuple spaces. devices may produce and consume, respectively, streams of data in the form of tuples, and the role of streaming buffers A. Novel Application Domains may be efficiently played by tuple spaces. Then, stream Privacy demanding application domains, for instance and filtering and processing components may coordinate to self- most notably healthcare-related ones, may in principle be organise in pipelines by relying on tuple-based coordination troublesome for tuple-based coordination, mostly because the to split incoming data and aggregate partial results. Moreover, shared space approach requires extra-linguistic – usually, if also the blockchain enters the picture, lineage tracking infrastructural – means to address the issue of “who may get would straightforwardly be supported by transactions and access to what” [15]—typically, the infrastructure is patched smart contracts, and fault tolerance would be greatly improved with some support to role-based access control [16]. thanks to blockchain nodes’ synchronisation. Here, the kind of partial and obscure pattern matching enabled by XPath queries comes handy to prevent interacting B. Increased Expressiveness agents to discover the whole structure of an information item Adopting XPath as the pattern matching language in a (i.e. an XML tuple representing a medical record from a XML-tuples setting would straightforwardly enable novel patient’s personal health folder) from a portion of it. In fact, on forms of partial and obscure pattern matching: not only the the one hand the interacting agents are not required to know actual information content may be not known to the agent in advance the whole tuple structure in order to be able to looking for matching tuples through a suitable tuple template perform queries – as in L INDA [1] inspired models typically – as it typically stems from L INDA’s associative access – but is – while, on the other hand, the behaviour of the tuple also the overall structure of the information chunks possibly space storing the information may be programmed to return matching is unknown – not the position within a tuple, nor its only the most specific piece of information which satisfies depth in case of nesting tuples – and even more it cannot be the query—i.e. the list of the matching nodes without their discovered as a side-effect of pattern matching itself—namely, position (aka path) within the XML tuple (aka document). In not the whole tuple is returned, but only a suitable portion. this way, privacy of sensitive information is straightforwardly Such a novel form of matching mechanism would enable preserved by linguistic means—possibly complemented by the fine-grained tuning of observability of information – and usual extra-linguistic ones. interactions – directly at the language level. Furthermore, The blockchain technology further strengthens suitability the blockchain could complement this feature by offering the of the novel tuple-based models here envisioned in the required infrastructural support, also expanding observability aforementioned business domains by adding features such as beyond tuples, towards interactions and coordination rules. accountability, traceability, and transparency of interactions. In fact, the blockchain straightforwardly supports a form In fact, asymmetric encryption (to authenticate interacting of event correlation, by ensuring that distributed transac- agents), transactions (as tuple space primitives) along with tions are totally ordered and consistent. Then, if transactions 64 represent interactions, event correlation actually translates to [3] J. Gubbi, R. Buyya, S. Marusic, and M. Palaniswami, “Internet of coordination of interactions. The policies according to which Things (IoT): A vision, architectural elements, and future directions,” Future Generation Computer Systems, vol. 29, no. 7, pp. 1645–1660, such a coordination process would occur are actually the 2013. [Online]. Available: http://www.sciencedirect.com/science/article/ smart contracts enforced by blockchain’s nodes. Since they pii/S0167739X13000241 are programs, expressiveness would naturally lean towards the [4] R. Calegari, E. Denti, S. Mariani, and A. Omicini, “Logic Programming as a Service (LPaaS): Intelligence for the IoT,” in 2017 IEEE 14th Turing-equivalent expressiveness of coordination languages International Conference on Networking, Sensing and Control (ICNSC such as ReSpecT [17]. 2017), G. Fortino, M. Zhou, Z. Lukszo, A. V. Vasilakos, F. Basile, Then, in-stream processing techniques bring along novel C. Palau, A. Liotta, M. P. Fanti, A. Guerrieri, and A. Vinci, Eds. IEEE, May 2017. forms of (near) real-time event correlation: in particular, [5] A. Omicini and S. Mariani, “Agents & multiagent systems: En route lineage tracking in a tuple-based coordination setting may towards complex intelligent systems,” Intelligenza Artificiale, vol. 7, enable to build not only interaction histories, but also causal no. 2, pp. 153—164, Nov. 2013, Special Issue Celebrating 25 years of the Italian Association for Artificial Intelligence. [Online]. Available: relations between interaction events occurring in the same http://content.iospress.com/articles/intelligenza-artificiale/ia056 “interaction pipeline”—intended, for instance, as the sequence [6] D. Rossi, G. Cabri, and E. Denti, “Tuple-based technologies of interactions where different components get access to the for coordination,” in Coordination of Internet Agents: Models, Technologies, and Applications, A. Omicini, F. Zambonelli, M. Klusch, same data, or perform the same operations on different data. and R. Tolksdorf, Eds. Springer, Jan. 2001, ch. 4, pp. 83–109. [Online]. Available: http://link.springer.com/10.1007/978-3-662-04401-8 4 IV. C ONCLUSION & O UTLOOK [7] “XML Path Language (XPath) 3.1,” W3C. [Online]. Available: http://www.w3.org/TR/xpath-3/ The future of software systems is dealing with complexity, [8] S. Underwood, “Blockchain beyond Bitcoin,” Communications of the and complexity in software systems typically comes from ACM, vol. 59, no. 11, pp. 15–17, Nov. 2016. [Online]. Available: http://dl.acm.org/citation.cfm?doid=3013530.2994581 interaction [18]. Coordination models and technologies are [9] “Bitcoin.” [Online]. Available: http://bitcoin.org/ naturally born to deal with that sort of complexity, by pro- [10] “Hyperledger,” The Linux Foundation. [Online]. Available: http: viding software engineers with the means for harnessing the //www.hyperledger.org/ [11] Y. Jiang, G. Xue, Z. Jia, and J. You, “DTuples: A distributed space of interaction [19]. hash table based tuple space service for distributed coordination,” in Novel application scenarios such as pervasive intelligence 5th International Conference on Grid and Cooperative Computing and the IoT mandate for new abstractions and tools for agent (GCC 2006), Oct. 2006, pp. 101–106. [Online]. Available: http: //ieeexplore.ieee.org/document/4031440/ coordination, so as to properly adapt to the specific application [12] P. Ciancarini, “Coordination models and languages as software requirements. In this position paper we explore the perspec- integrators,” ACM Computing Surveys, vol. 28, no. 2, pp. 300–302, Jun. tives of integrating a few novel technologies within tuple-based 1996. [Online]. Available: http://dl.acm.org/citation.cfm?doid=234732 [13] N. Marz and J. Warren, Big Data: Principles and best practices coordination models – namely, XPath, the blockchain, and of scalable realtime data systems. Manning Publications Co., 2015. stream processing – and provide some insight of their potential [Online]. Available: http://www.manning.com/books/big-data impact on multi-agent coordination. [14] A. Omicini and M. Viroli, “Coordination models and languages: From parallel computing to self-organisation,” The Knowledge In the next step of our research agenda we will likely Engineering Review, vol. 26, no. 1, pp. 53–59, Mar. 2011, proceed either with the integration of the aforementioned Special Issue 01 (25th Anniversary Issue). [Online]. Available: technologies within an existing coordination framework, pre- http://journals.cambridge.org/abstract S026988891000041X [15] N. Busi, R. Gorrieri, R. Lucchi, , and G. Zavattaro, “Secspaces: a data- sumably TuCSoN [20], or with the conception and design of driven coordination model for environments open to untrusted agent,” a brand-new model and lightweight coordination middleware Electronic Notes in Theoretical Computer Science, vol. 68, no. 3, pp. featuring XML tuples, XPath-based coordination primitives, a 310 – 327, 2003. [Online]. Available: http://www.sciencedirect.com/ science/article/pii/S1571066105803755 blockchain-based backbone implementing a distributed tuple [16] M. Viroli, A. Omicini, and A. Ricci, “Infrastructure for RBAC-MAS: space, smart contracts and transactions as coordination rules, An approach based on Agent Coordination Contexts,” Applied Artificial and stream-processing oriented interaction paradigm for the Intelligence, vol. 21, no. 4–5, pp. 443–467, Apr. 2007. [Online]. Avail- able: http://www.tandfonline.com/doi/abs/10.1080/08839510701253674 coordinating agents. [17] A. Omicini, “Formal ReSpecT in the A&A perspective,” Electronic Notes in Theoretical Computer Science, vol. 175, no. 2, pp. 97–117, ACKNOWLEDGMENT Jun. 2007. [Online]. Available: http://www.sciencedirect.com/science/ article/pii/S1571066107003519 This work was partially supported by the CONNECARE [18] P. Wegner, “Why interaction is more powerful than algorithms,” (Personalised Connected Care for Complex Chronic Patients) Communications of the ACM, vol. 40, no. 5, pp. 80–91, May 1997. project (EU H2020-RIA, Contract No. 689802). [Online]. Available: http://portal.acm.org/citation.cfm?id=253801 [19] ——, “Coordination as constrained interaction,” in Coordination Lan- guages and Models. First International Conference, COORDINATION R EFERENCES ’96 Cesena, Italy, April 15–17, 1996. Proceedings, ser. Lecture Notes [1] D. Gelernter, “Generative communication in Linda,” ACM Transactions in Computer Science, P. Ciancarini and C. Hankin, Eds. Springer on Programming Languages and Systems, vol. 7, no. 1, pp. 80–112, Berlin Heidelberg, Apr. 1996, vol. 1061, pp. 28–33. [Online]. Available: 1985. [Online]. Available: http://dl.acm.org/citation.cfm?doid=2433 http://link.springer.com/10.1007/3-540-61052-9 37 [2] A. Omicini, “Nature-inspired coordination for complex distributed [20] A. Omicini and F. Zambonelli, “Coordination for Internet application systems,” in Intelligent Distributed Computing VI, ser. Studies in development,” Autonomous Agents and Multi-Agent Systems, vol. 2, Computational Intelligence, G. Fortino, C. Bădică, M. Malgeri, and no. 3, pp. 251–269, Sep. 1999, Special Issue: Coordination Mechanisms R. Unland, Eds., vol. 446. Springer, 2013, pp. 1–6, 6th International for Web Agents. [Online]. Available: http://link.springer.com/10.1023/A: Symposium on Intelligent Distributed Computing (IDC 2012), Calabria, 1010060322135 Italy, 24-26 Sep. 2012. Proceedings. Invited paper. [Online]. Available: http://link.springer.com/10.1007/978-3-642-32524-3 1