Top

Service Oriented Computing and Applications

Published in:

01-09-2015 | Special Issue Paper

Partially distributed coordination with Reo and constraint automata

Authors: Sung-Shik T. Q. Jongmans, Francesco Santini, Farhad Arbab

Published in: Service Oriented Computing and Applications | Issue 3-4/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Coordination languages, such as Reo, have emerged for the specification and implementation of interaction protocols among concurrent entities, manifested as connectors. In this paper, we describe a theoretical justification and a practical proof-of-concept tool for automatically generating partially distributed, partially centralized implementations of Reo connectors. Such implementations have three performance advantages: faster compilation at build time (compared to a purely centralized approach), reduced latency at run time (compared to a purely distributed approach), and improved parallelism at run time (compared to a purely centralized approach). Our theory relies on the definition of a new product operator on constraint automata (Reo’s formal semantics), which we use to formally justify distributions of disjoint parts of a coordination scheme over different machines according to several possible motivations (e.g., performance, QoS constraints, privacy, resource availability, and network topology). To exemplify our work, in a case study, we show and explain how a generated connector implementation can be executed.

previous article Location-independent routing in process network overlays

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

http://jax-ws.java.net.

http://reo.project.cwi.nl.

http://aws.amazon.com.

If the model assumes synchronous communication, we should also “desynchronize” communication actions while constructing the ca from the lts (in a semantics-preserving way, under some equivalence).

Arbab F (2004) Reo: a channel-based coordination model for component composition. Math Struct Comput Sci 14(3):329–366. doi:10.1017/S0960129504004153 MathSciNetCrossRefMATH

Arbab F (2011) Puff, the magic protocol. In: Agha G, Danvy O, Meseguer J (eds) Talcott Festschrift, LNCS, vol 7000. Springer, Berlin, pp 169–206. doi:10.1007/978-3-642-24933-4_9

Arbab F, Baier C, de Boer F, Rutten J, Sirjani M (2005) Synthesis of Reo circuits for implementation of component-connector automata specifications. In: Jacquet JM, Picco GP (eds) Proceedings of COORDINATION 2005, LNCS, vol 3454. Springer, Berlin, pp 236–251. doi:10.1007/11417019_16

Baier C, Sirjani M, Arbab F, Rutten J (2006) Modeling component connectors in Reo by constraint automata. Sci Comput Program 61(2):75–113. doi:10.1016/j.scico.2005.10.008 MathSciNetCrossRefMATH

Banâtre JP, Fradet P, Métayer DL (2001) Gamma and the chemical reaction model: fifteen years after. In: Proceedings of the workshop on multiset processing: multiset processing, mathematical, computer science, and molecular computing points of view, WMP ’00, pp 17–44. Springer, London, UK. http://dl.acm.org/citation.cfm?id=647269.721851

Barker A, Weissman J, van Hemert J (2008) Orchestrating data-centric workflows. In: Priol T, Jin H, Laforenza D, Matsuoka S, Parashar M, Roe P (eds) Proceedings of CCGRID 2008. IEEE, Los Alamitos, pp 210–217. doi:10.1109/CCGRID.2008.50

Basu A, Bozga M, Sifakis J (2006) Modeling heterogeneous real-time components in BIP. In: Hung DV, Pandya P (eds) Proceedings of SEFM 2006. IEEE, Los Alamitos, pp 3–12. doi:10.1109/SEFM.2006.27

ter Beek M, Bucchiarone A, Gnesi S (2004) Web service composition approaches: from industrial standards to formal methods. In: Galizia S, Emig C, Martens A, Roman D, Wombacher A (eds) Proceedings of ICIW 2007. IEEE, Los Alamitos, pp 224–233. doi:10.1109/ICIW.2007.71

Bernstein P, Hadzilacos V, Goodman N (1987) Two phase locking. In: Concurrency control and recovery in database systems. Addison-Wesley, Boston, pp 47–111

10.

Binder W, Constantinescu I, Faltings B (2006) Decentralized orchestration of composite web services. In: Feig E, Zhang AKJ (eds) Proceedings of ICWS 2006. IEEE, Los Alamitos, pp 869–876. doi:10.1109/ICWS.2006.48

11.

Bonakdarpour B, Bozga M, Jaber M, Quilbeuf J, Sifakis J (2012) A framework for automated distributed implementation of component-based models. Distrib Comput 25(5):383–409. doi:10.1007/s00446-012-0168-6 CrossRefMATH

12.

Bravetti M, Zavattaro G (2007) Towards a unifying theory for choreography conformance and contract compliance. In: Lumpe M, Vanderperren W (eds) Proceedings of SC 2007, LNCS, vol 4829. Springer, Berlin, pp 34–50. doi:10.1007/978-3-540-77351-1_4

13.

Bravetti M, Zavattaro G (2009) Contract compliance and choreography conformance in the presence of message queues. In: Bruni R, Wolf K (eds) Proceedings of WS-FM 2008, LNCS, vol 5387. Springer, Berlin, pp 37–45. doi:10.1007/978-3-642-01364-5_3

14.

Carbone M, Honda K, Yoshida N (2012) Structured communication-centered programming for web services. ACM Trans Program Lang Syst 34(2):8:1–8:78. doi:10.1145/2220365.2220367 CrossRef

15.

Cardelli L, Gordon A (1998) Mobile ambients. In: Nivat M (ed) Foundations of software science and computation structures, Lecture notes in computer science, vol 1378. Springer, Berlin, pp 140–155. doi:10.1007/BFb0053547

16.

Chafle G, Chandra S, Mann V, Nanda MG (2004) Decentralized orchestration of composite web services. In: Najork M, Wills C (eds) Proceedings of WWW Alt. 2004. ACM, New York, pp 134–143. doi:10.1145/1013367.1013390

17.

Changizi B (2015) Model based analysis of business process models. Ph.D. thesis, Leiden University (in preparation)

18.

Clarke D, Proença J (2012) Partial connector colouring. In: Sirjani M (ed) Proceedings of COORDINATION 2012, LNCS, vol 7274. Springer, Berlin, pp 59–73. doi:10.1007/978-3-642-30829-1_5

19.

Dami S, Estublier J, Amiour M (1998) APEL: a graphical yet executable formalism for process modeling. Autom Softw Eng 5:61–91. doi:10.1007/978-1-4615-5441-7_4 CrossRef

20.

De Nicola R, Ferrari GL, Loreti M, Pugliese R (2011) A language-based approach to autonomic computing. In: Beckert B, Damiani F, de Boer FS, Bonsangue MM (eds) FMCO, vol 7542., Lecture notes in computer scienceSpringer, Berlin, pp 25–48

21.

Dorigo M, Bonabeau E, Theraulaz G (2000) Ant algorithms and stigmergy. Future Gen Comput Syst 16(9):851–871. http://dl.acm.org/citation.cfm?id=348599.348601

22.

Fernández H, Priol T, Tedeschi C (2010) Decentralized approach for execution of composite web services using the chemical paradigm. In: Pu C, Singhal S, Zhang J (eds) Proceedings of ICWS 2010. IEEE, Los Alamitos, pp 139–146. doi:10.1109/ICWS.2010.46

23.

Fournet C, Gonthier G, Lévy JJ, Maranget L, Rémy D (1996) A calculus of mobile agents. In: Montanari U, Sassone V (eds) CONCUR, vol 1119., Lecture notes in computer scienceSpringer, Berlin, pp 406–421

24.

Fu X, Bultan T, Su J (2004) Conversation protocols: a formalism for specification and verification of reactive electronic services. Theor Comput Sci 328(1–2):19–37. doi:10.1016/j.tcs.2004.07.004 MathSciNetCrossRefMATH

25.

Fu X, Bultan T, Su J (2005) Realizability of conversation protocols with message contents. Int J Web Serv Res 2(4):68–93. doi:10.4018/jwsr.2005100104 CrossRef

26.

Gilbert D, Palamidessi C (2000) Concurrent constraint programming with process mobility. In: Proceedings of the first international conference on computational logic, CL ’00. Springer, London, UK, pp 463–477. http://dl.acm.org/citation.cfm?id=647482.728260

27.

Honda K, Yoshida N, Carbone M (2008) Multiparty asynchronous session types. In: Necula G, Wadler P (eds) Proceedings of POPL 2008. ACM, New York, pp 273–284. doi:10.1145/1328438.1328472

28.

Jongmans SS, Arbab F (2012) Overview of thirty semantic formalisms for Reo. Sci Ann Comput Sci 22(1):201–251. doi:10.7561/SACS.2012.1.201 MathSciNetCrossRef

29.

Jongmans SS, Arbab F (2013) Global consensus through local synchronization. In: Canal C, Villari M (eds) Proceedings of FOCLASA 2013, no. 393 in CCIS. Springer, Berlin, pp 174–188. doi:10.1007/978-3-642-45364-9_15

30.

Jongmans SS, Arbab F (2013) Global consensus through local synchronization (Technical Report). Tech. Rep. FM-1303, CWI

31.

Jongmans SS, Arbab F (2013) Modularizing and specifying protocols among threads. In: Gay S, Kelly P (eds) Proceedings of PLACES 2012, EPTCS, vol 109. CoRR, pp 34–45. doi:10.4204/EPTCS.109.6

32.

Jongmans SS, Arbab F (2014) Toward sequentializing overparallelized protocol code. In: Lanese I, Lluch-Lafuente A, Sokolova A, Torres-Vieira H (eds) Proceedings of ICE 2014, EPTCS, vol 166. CoRR, pp 38–44. doi:10.4204/EPTCS.166.5

33.

Jongmans SS, Arbab F (2015) Can high throughput atone for high latency in compiler-generated protocol code? In: Dastani M, Sirjani M (eds) Proceedings of FSEN 2015, LNCS. Springer, Berlin (in press)

34.

Jongmans SS, Clarke D, Proença J (2012) A procedure for splitting processes and its application to coordination. In: Kokash N, Ravara A (eds) Proceedings of FOCLASA 2012, EPTCS, vol 91. CoRR, pp 79–96. doi:10.4204/EPTCS.91.6

35.

Jongmans SS, Santini F, Arbab F (2013) Partially-distributed coordination with Reo (Technical Report). Tech. Rep. FM-1304, CWI

36.

Jongmans SS, Santini F, Arbab F (2014) Partially-distributed coordination with Reo. In: Aldinucci M, D’Agostino D, Kilpatrick P (eds) Proceedings of PDP 2014. IEEE, Los Alamitos, pp 697–706. doi:10.1109/PDP.2014.19

37.

Jongmans SS, Santini F, Sargolzaei M, Arbab F, Afsarmanesh H (2012) Automatic code generation for the orchestration of web services with Reo. In: de Paoli F, Pimentel E, Zavattaro G (eds) Proceedings of ESOCC 2012, LNCS, vol 7592. Springer, Berlin, pp 1–16. doi:10.1007/978-3-642-33427-6_1

38.

Jongmans SS, Santini F, Sargolzaei M, Arbab F, Afsarmanesh H (2014) Orchestrating web services using Reo: from circuits and behaviors to automatically generated code. Serv Oriented Comput Appl 8(4):277–297. doi:10.1007/s11761-013-0147-1

39.

Jordan D, Evdemon J (2007) Web services business process execution language version 2.0. Standard ws-bpel-v2.0-OS, OASIS

40.

Kokash N, Changizi B, Arbab F (2010) A semantic model for service composition with coordination time delays. In: Dong JS, Zhu H (eds) Proceedings of ICFEM, LNCS, vol 6447. Springer, Berlin, pp 106–121. doi:10.1007/978-3-642-16901-4_9

41.

Kokash N, Krause C, de Vink E (2012) Reo+mCRL2: a framework for model-checking dataflow in service compositions. Form Asp Comput 24(2):187–216. doi:10.1007/s00165-011-0191-6 MathSciNetCrossRefMATH

42.

Lanese I, Montesi F, Zavattaro G (2013) Amending choreographies. In: Ravara A, Silva J (eds) Proceedings of WWV 2013, EPTCS, vol 123. CoRR, pp 34–48. doi:10.4204/EPTCS.123.5

43.

Lynch N (1996) Distributed algorithms. Elsevier, AmsterdamMATH

44.

Mamei M, Zambonelli F (2004) Programming pervasive and mobile computing applications with the tota middleware. In: Proceedings of the second IEEE international conference on pervasive computing and communications (PerCom’04), PERCOM ’04, p 263. IEEE Computer Society, Washington, DC, USA. http://dl.acm.org/citation.cfm?id=977406.978680

45.

Mamei M, Zambonelli F (2005) Field-based coordination for pervasive multiagent systems (Springer series on agent technology). Springer, Secaucus

46.

Mhl G, Fiege L, Pietzuch P (2010) Distributed event-based systems, 1st edn. Springer, Berlin

47.

Milner R (1989) Communication and concurrency. Prentice Hall, Upper Saddle RiverMATH

48.

Mostarda L, Marinovic S, Dulay N (2010) Distributed orchestration of pervasive services. In: Rahayu W, Xhafa F, Denko M (eds) Proceedings of AINA 2010. IEEE, Los Alamitos, pp 166–173. doi:10.1109/AINA.2010.100

49.

Murphy AL, Picco GP, Roman GC (2006) Lime: a coordination model and middleware supporting mobility of hosts and agents. ACM Trans Softw Eng Methodol 15(3):279–328. doi:10.1145/1151695.1151698 CrossRef

50.

Muth P, Wodtke D, Weissenfels J, Dittrich AK, Weikum G (1998) From centralized workflow specification to distributed workflow execution. J Intell Inf Syst 10(2):159–184. doi:10.1023/A:1008608810770 CrossRef

51.

Nanda MG, Chandra S, Sarkar V (2004) Decentralizing execution of composite web services. In: Schmidt D (ed) Proceedings of OOPSLA 2004. ACM, New York, pp 170–187. doi:10.1145/1028976.1028991

52.

de Nicola R, Ferrari GL, Pugliese R (1998) KLAIM: a kernel language for agents interaction and mobility. IEEE Trans Softw Eng 24(5):315–330. doi:10.1109/32.685256 CrossRef

53.

Web services business process execution language (2007). http://docs.oasis-open.org/wsbpel/2.0/

54.

Parr T (2007) Generating structured text with templates and grammars. In: The definitive ANTLR reference: building domain-specific languages. The Pragmatic Bookshelf, pp 208–242

55.

Pautasso C (2009) RESTful Web service composition with BPEL for REST. Data Knowl Eng 68(9):851–866. doi:10.1016/j.datak.2009.02.016

56.

Pedraza G, Estublier J (2009) Distributed orchestration versus choreography: the FOCAS approach. In: Wang Q, Garousi V, Madachy R, Pfahl D (eds) Proceedings of ICSP 2009, no. 5543 in LNCS. Springer, Berlin, pp 75–86. doi:10.1007/978-3-642-01680-6_9

57.

Peltz C (2003) Web services orchestration and choreography. Computer 36(10):46–52. doi:10.1109/MC.2003.1236471 CrossRef

58.

Proença J, Clarke D, de Vink E, Arbab F (2011) Decoupled execution of synchronous coordination models via behavioural automata. In: Mousavi MR, Ravara A (eds) Proceedings of FOCLASA 2011, EPTCS, vol 58. CoRR, pp 65–79. doi:10.4204/EPTCS.58.5

59.

Proença J, Clarke D, de Vink E, Arbab F (2012) Dreams: a framework for distributed synchronous coordination. In: Viroli M, Castelli G, Marquez JLF (eds) Proceedings of SAC 2012. ACM, New York, pp 1510–1515. doi:10.1145/2245276.2232017

60.

Proença J (2011) Synchronous coordination of distributed components. Ph.D. thesis, Leiden University

61.

Ren S, Yu Y, Chen N, Marth K, Poirot PE, Shen L (2006) Actors, roles and coordinators – a coordination model for open distributed and embedded systems. In: Proceedings of the 8th international conference on coordination models and languages, COORDINATION’06. Springer, Berlin, pp 247–265. doi:10.1007/11767954_16

62.

Ricci A, Omicini A, Viroli M, Gardelli L, Oliva E (2007) Cognitive stigmergy: towards a framework based on agents and artifacts. In: Proceedings of the 3rd international conference on environments for multi-agent systems III, E4MAS’06. Springer, Berlin, pp 124–140. http://dl.acm.org/citation.cfm?id=1759343.1759352

63.

Rowstron A, Wood A (1997) BONITA: a set of tuple space primitives for distributed coordination. In: El-Rewini H (ed) Proceedings of HICSS 1997. IEEE, Los Alamitos, pp 379–388. doi:10.1109/HICSS.1997.667285

64.

Sirjani M, Jaghoori MM, Baier C, Arbab F (2006) Compositional semantics of an actor-based language using constraint automata. Proceedings of COORDINATION 2006, LNCS, vol 4038. Springer, Berlin, pp 281–297. doi:10.1007/11767954_18

65.

Sirjani M, Movaghar A, Shali A, de Boer F (2004) Modeling and verification of reactive systems using Rebeca. Fundam Inform 63:385–410

66.

Tretola G, Zimeo E (2006) Workflow fine-grained concurrency with automatic continuation. In: Rosenberg A, Atallah M, Bader D, Gottlieb A, Kale L (eds) Proceedings of IPDPS 2006. IEEE, Los Alamitos, pp 253–260. doi:10.1109/IPDPS.2006.1639510

Title: Partially distributed coordination with Reo and constraint automata
Authors: Sung-Shik T. Q. Jongmans
Francesco Santini
Farhad Arbab
Publication date: 01-09-2015
Publisher: Springer London
Published in: Service Oriented Computing and Applications / Issue 3-4/2015
Print ISSN: 1863-2386
Electronic ISSN: 1863-2394
DOI: https://doi.org/10.1007/s11761-015-0177-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3-4/2015

Preface

On the behaviour of general purpose applications on cloud storages

Self-adaptive multiparty sessions

Location-independent routing in process network overlays

A formalized framework for mobile cloud computing

Pabble: parameterised Scribble

Premium Partner