×

Channel-based coordination via constraint satisfaction. (English) Zbl 1220.68049

Summary: Coordination in \(\mathcal R\)eo emerges from the composition of the behavioural constraints of primitives, such as channels, in a component connector. Understanding and implementing \(\mathcal R\)eo, however, has been challenging due to the interaction of the channel metaphor, which is an inherently local notion, and the non-local nature of the constraints imposed by composition. In this paper, the channel metaphor takes a back seat. We focus on the behavioural constraints imposed by the composition of primitives and phrase the semantics of \(\mathcal R\)eo as a constraint satisfaction problem. Not only does this provide a clear description of the behaviour of \(\mathcal R\)eo connectors in terms of synchronisation and data flow constraints, it also paves the way for new implementation techniques based on constraint satisfaction. We also demonstrate that this approach is more efficient than the existing techniques based on connector colouring.

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
68N15 Theory of programming languages
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Software:

Linda; Reo
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andreoli, J. -M.; Freeman, S.; Pareschi, R.: The coordination language facility: coordination of distributed objects, Theory and practice of object systems 2, No. 2, 77-94 (1996)
[2] Andreoli, J. -M.; Pareschi, R.: Linear objects: logical processes with built-in inheritance, New generation computing, 495-510 (1990)
[3] Apt, K.: Principles of constraint programming, (2003) · Zbl 1187.68132
[4] Arbab, F.: Reo: a channel-based coordination model for component composition, Mathematical structures in computer science 14, No. 3, 329-366 (2004) · Zbl 1085.68552
[5] Arbab, F.: Abstract behavior types: a foundation model for components and their composition, Science of computer programming 55, No. 1–3, 3-52 (2005) · Zbl 1075.68014
[6] Arbab, F.: Composition of interacting computations, Interactive computation: the new paradigm, 277-321 (2006) · Zbl 1266.68089
[7] Arbab, F.; Baier, C.; De Boer, F. S.; Rutten, J. J. M.M.: Models and temporal logical specifications for timed component connectors, Software and system modeling 6, No. 1, 59-82 (2007)
[8] Arbab, F.; Bruni, R.; Clarke, D.; Lanese, I.; Montanari, U.: Tiles for reo, Lecture notes in computer science 5486, 37-55 (2008) · Zbl 1253.68090
[9] Arbab, F.; Chothia, T.; Meng, S.; Moon, Y. -J.: Component connectors with QoS guarantees, Lecture notes in computer science 4467, 286-304 (2007)
[10] F. Arbab, C. Koehler, Z. Maraikar, Y. Moon, J. Proença, Modeling, testing and executing Reo connectors with the Eclipse Coordination Tools, in: International Workshop on Formal Aspects of Component Software, FACS. Electronic Notes in Theoretical Computer Science (ENTCS), Malaga, 2008.
[11] Arbab, F.; Kokash, N.; Meng, S.: Towards using reo for compliance-aware business process modeling, Communications in computer and information science  17, 108-123 (2008)
[12] Arbab, F.; Monfroy, E.: Coordination of heterogeneous distributed cooperative constraint solving, SIGAPP applied computing review 6, No. 2, 4-17 (1998)
[13] Arbab, F.; Sun, M.; Baier, C.: Synthesis of reo circuits from scenario-based specifications, Electronic notes in theoretical computer science 229, No. 2, 21-41 (2009) · Zbl 1347.68024
[14] Baier, C.; Sirjani, M.; Arbab, F.; Rutten, J.: Modeling component connectors in reo by constraint automata, Science of computer programming 61, No. 2, 75-113 (2006) · Zbl 1105.68058
[15] Baier, C.; Wolf, V.: Stochastic reasoning about channel-based component connectors, Lecture notes in computer science 4038, 1-15 (2006)
[16] Bettini, L.; Bono, V.; Nicola, R. D.; Ferrari, G.; Gorla, D.; Loreti, M.; Moggi, E.; Pugliese, R.; Tuosto, E.; Venneri, B.: The klaim project: theory and practice, Lecture notes in computer science 2874, 88-150 (2003) · Zbl 1179.68027
[17] Bonsangue, M. M.; Clarke, D.; Silva, A.: Automata for context-dependent connectors, Lecture notes in computer science 5521, 184-203 (2009)
[18] Clarke, D.: Coordination: reo, nets, and logic, Lecture notes in computer science 5382, 226-256 (2007) · Zbl 1209.68335
[19] Clarke, D.: A basic logic for reasoning about connector reconfiguration, Fundamenta informaticae 82, No. 4, 361-390 (2008) · Zbl 1147.68570
[20] Clarke, D.; Costa, D.; Arbab, F.: Connector colouring I: Synchronisation and context dependency, Science of computer programming 66, No. 3, 205-225 (2007) · Zbl 1121.68015
[21] D. Clarke, J. Proença, Coordination via interaction constraints i: Local logic. CoRR abs/0911.5445, 2009.
[22] Clarke, D.; Proença, J.; Lazovik, A.; Arbab, F.: Deconstructing reo, Electronic notes in theoretical computer science 229, No. 2, 43-58 (2009) · Zbl 1347.68077
[23] D. Costa, Formal models for component connectors. Ph.D. Thesis, 2010 (in press).
[24] C.T.H. Everaars, D.F. de Oliveira Costa, N.K. Diakov, F. Arbab, A distributed computational model for Reo, Tech. Rep. SEN-E0601, CWI, Amsterdam, The Netherlands, February 2006.
[25] Fiadeiro, J. L.; Lopes, A.; Bocchi, L.: A formal approach to service component architecture, Lecture notes in computer science 4184, 193-213 (2006)
[26] Freeman, E.; Arnold, K.; Hupfer, S.: Javaspaces principles, patterns, and practice, (1999)
[27] Frølund, S.: Coordinating distributed objects, (1996)
[28] Gelernter, D.: Generative communication in linda, ACM transactions on programming languages and systems 7, No. 1, 80-112 (1985) · Zbl 0559.68030
[29] J.V. Guillen Scholten, Mobile channels for exogenous coordination of distributed systems : semantics, implementation and composition, Ph.D. Thesis, LIACS, Faculty of Mathematics and Natural Sciences, Leiden University, January 2007.
[30] Khosravi, R.; Sirjani, M.; Asoudeh, N.; Sahebi, S.; Iravanchi, H.: Modeling and analysis of reo connectors using alloy, Lecture notes in computer science 5052, 169-183 (2008)
[31] D. Kitchin, W.R. Cook, J. Misra, A language for task orchestration and its semantic properties, in: CONCUR, 2006, pp. 477–491. · Zbl 1151.68360
[32] Klüppelholz, S.; Baier, C.: Symbolic model checking for channel-based component connectors, Electronic notes in theoretical computer science 175, No. 2, 19-37 (2007)
[33] Koehler, C.; Clarke, D.: Decomposing port automata, , 1369-1373 (2009)
[34] Koehler, C.; Lazovik, A.; Arbab, F.: Connector rewriting with high-level replacement systems, Electronic notes in theoretical computer science 194, No. 4, 77-92 (2008) · Zbl 1277.68193
[35] Lazovik, A.; Aiello, M.; Gennari, R.: Choreographies: using constraints to satisfy service requests, (2006)
[36] Maraikar, Z.; Lazovik, A.; Arbab, F.: Building mashups for the enterprise with SABRE, Lecture notes in computer science 5364, 70-83 (2008)
[37] Meng, S.; Arbab, F.: On resource-sensitive timed component connectors, Lecture notes in computer science 4468, 301-316 (2007) · Zbl 1202.68070
[38] Meng, S.; Arbab, F.: Web services choreography and orchestration in reo and constraint automata, , 346-353 (2007)
[39] Milner, R.: Communicating and mobile systems: the pi-calculus, (1999) · Zbl 0942.68002
[40] Minsky, N. H.; Ungureanu, V.: Law-governed interaction: a coordination and control mechanism for heterogeneous distributed systems, ACM transactions on software engineering and methodology 9, No. 3, 273-305 (2000)
[41] U. Montanari, F. Rossi, Modeling process coordination via tiles, graphs, and constraints, in: 3rd Biennial World Conference on Integrated Design and Process Technology, vol. 4, 1998, pp. 1–8.
[42] Mousavi, M. R.; Sirjani, M.; Arbab, F.: Formal semantics and analysis of component connectors in reo, Electronic notes in theoretical computer science 154, No. 1, 83-99 (2006)
[43] Papadopoulos, G. A.; Arbab, F.: Coordination models and languages, Advances in computers  46, 329-400 (1998)
[44] Proenca, J.; Clarke, D.: Coordination models orc and reo compared, (2007)
[45] Rutten, J. J. M.M.: Universal coalgebra: a theory of systems, Theoretical computer science 249, No. 1, 3-80 (2000) · Zbl 0951.68038
[46] Saraswat, V. A.: Concurrent constraint programming, (1993) · Zbl 1002.68026
[47] Saraswat, V. A.; Jagadeesan, R.; Gupta, V.: Timed default concurrent constraint programming, Journal of symbolic computation 22, No. 5–6, 475-520 (1996) · Zbl 0876.68041
[48] Sheini, H. M.; Sakallah, K. A.: From propositional satisfiability to satisfiability modulo theories, Lecture notes in computer science 4121, 1-9 (2006) · Zbl 1187.68567
[49] Van Der Aalst, W. M. P.; Hofstede, A. H. M. Ter; Kiepuszewski, B.; Barros, A. P.: Workflow patterns, Distributed and parallel databases 14, No. 1, 5-51 (2003)
[50] Venkataraman, K. N.: Decidability of the purely existential fragment of the theory of term algebras, Journal of ACM 34, No. 2, 492-510 (1987)
[51] Wegner, P.: Coordination as constrained interaction (extended abstract), Lecture notes in computer sciences 1061, 28-33 (1996)
[52] M. Xie, Specification of E-Business Process Model For PayPal Online Payment Process Using Reo. Master’s Thesis, Leiden University, the Netherlands, 2005.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.