Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Proper Protocol

  • Chapter
  • First Online:
Theory and Practice of Formal Methods

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9660))

  • 1080 Accesses

Abstract

Treating interaction as an explicit first-class concept, complete with its own composition operators, leads to a model of concurrency that allows direct specification and manipulation of protocols as proper mathematical objects. Reo [2, 5, 6, 8] serves as a premier example of such an interaction-centric model of concurrency.

In this paper, we peruse Reo and explain how its model of protocols as encapsulated, reusable constructs facilitates their fulfilling of the more prominent role slated for them in engineering of modular, verifiable, scalable concurrent software. We also explore clues enlaced with some recent results of our ongoing work on compiling Reo protocol specifications into efficient executable code, which sketch a promising perspective for future work on high-level protocol specification languages.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

eBook
USD 15.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 15.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    While this paper was under review, Gene Amdahl [16 November 1922 – 10 November 2015] passed away.

  2. 2.

    In Martin Handford’s 1980’s popular books of double-page illustrations, that challenged readers to locate a certain Waldo character “hidden” in plain sight in a crowd.

  3. 3.

    Of course, by adding extra “redundant” constraints, a programmer can also “specify” a bubble-sort, when and if desired.

References

  1. Extensible Coordination Tools home page. http://reo.project.cwi.nl/cgibin/trac.cgi/reo/wiki/Tools

  2. Reo home page. http://reo.project.cwi.nl

  3. Agha, G.: Actors: A Model of Concurrent Computation in Distributed Systems. MIT Press, Cambridge (1986)

    Google Scholar 

  4. Amdahl, G.M.: Validity of the single processor approach to achieving large scale computing capabilities. In: American Federation of Information Processing Societies: Proceedings of the AFIPS 1967 Spring Joint Computer Conference, 18–20 April 1967, Atlantic City, New Jersey, USA. AFIPS Conference Proceedings, vol. 30, pp. 483–485. AFIPS/ACM/Thomson Book Company, Washington D.C. (1967)

    Google Scholar 

  5. Arbab, F.: Reo: a channel-based coordination model for component composition. Math. Struct. Comput. Sci. 14(3), 329–366 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  6. Arbab, F.: Abstract behavior types: a foundation model for components and their composition. Sci. Comput. Program. 55(1–3), 3–52 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  7. Arbab, F.: Puff, the magic protocol. In: Agha, G., Danvy, O., Meseguer, J. (eds.) Formal Modeling: Actors, Open Systems, Biological Systems. LNCS, vol. 7000, pp. 169–206. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  8. Arbab, F., Mavaddat, F.: Coordination through channel composition. In: Arbab, F., Talcott, C. (eds.) COORDINATION 2002. LNCS, vol. 2315, pp. 22–39. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  9. Arvind, Gostelow, K.P., Plouffe, W.: Indeterminancy, monitors, and dataflow. In: Rosen, S., Denning, P.J. (eds.) Proceedings of the Sixth Symposium on Operating System Principles, SOSP 1977, Purdue University, West Lafayette, Indiana, USA, 16–18 November 1977, pp. 159–169. ACM (1977)

    Google Scholar 

  10. Attie, P., Baranov, E., Bliudze, S., Jaber, M., Sifakis, J.: A general framework for architecture composability. In: Giannakopoulou, D., Salaün, G. (eds.) SEFM 2014. LNCS, vol. 8702, pp. 128–143. Springer, Heidelberg (2014)

    Google Scholar 

  11. Baeten, J.C.M., Weijland, W.P.: Process Algebra. Cambridge University Press, New York (1990)

    Book  MATH  Google Scholar 

  12. Baier, C., Sirjani, M., Arbab, F., Rutten, J.: Modeling component connectors in Reo by constraint automata. Sci. Comput. Program. 61(2), 75–113 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  13. Bailey, D.H., Barszcz, E., Barton, J.T., Browning, D.S., Carter, R.L., Dagum, L., Fatoohi, R.A., Frederickson, P.O., Lasinski, T.A., Schreiber, R., Simon, H.D., Venkatakrishnan, V., Weeratunga, S.: The NAS parallel benchmarks. IJHPCA 5(3), 63–73 (1991)

    Google Scholar 

  14. Basu, A., Bozga, M., Sifakis, J.: Modeling heterogeneous real-time components in BIP. In: Proceedings of SEFM 2006, pp. 3–12. IEEE (2006)

    Google Scholar 

  15. Benveniste, A., Caspi, P., Le Guernic, P., Halbwachs, N.: Data-flow synchronous languages. In: de Bakker, J.W., de Roever, W.-P., Rozenberg, G. (eds.) REX 1993. LNCS, vol. 803, pp. 1–45. Springer, Heidelberg (1994)

    Chapter  Google Scholar 

  16. Bergstra, J.A., Klop, J.W.: Process algebra for synchronous communication. Inf. Control 60, 109–137 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  17. Berry, G.: Esterel and Jazz: two synchronous languages for circuit design. In: Pierre, L., Kropf, T. (eds.) CHARME 1999. LNCS, vol. 1703, p. 1. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  18. Dean Brock, J., Ackerman, W.B.: Scenarios: a model of non-determinate computation. In: Díaz, J., Ramos, I. (eds.) Formalization of Programming Concepts. LNCS, vol. 107, pp. 252–259. Springer, Heidelberg (1981)

    Chapter  Google Scholar 

  19. Buck, J.T., Ha, S., Lee, E.A., Messerschmitt, D.G.: Ptolemy: a framework for simulating and prototyping heterogenous systems. Int. J. Comput. Simul. 4(2), 155–182 (1994)

    Google Scholar 

  20. Carbone, M., Yoshida, N., Honda, K.: Asynchronous session types: exceptions and multiparty interactions. In: Bernardo, M., Padovani, L., Zavattaro, G. (eds.) SFM 2009. LNCS, vol. 5569, pp. 187–212. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  21. Caspi, P., Pilaud, D., Halbwachs, N., Plaice, J.: Lustre: a declarative language for programming synchronous systems. In: Conference Record of the Fourteenth Annual ACM Symposium on Principles of Programming Languages, Munich, Germany, 21–23 January 1987, pp. 178–188. ACM Press (1987)

    Google Scholar 

  22. Dennis, J.B., Gao, G.R.: An efficient pipelined dataflow processor architecture. In: Michael, G.A. (ed.) Proceedings Supercomputing 1988, Orlando, FL, USA, 12–17 November 1988, pp. 368–373. IEEE Computer Society (1988)

    Google Scholar 

  23. Fokkink, W.: Introduction to Process Algebra. Texts in Theoretical Computer Science, An EATCS Series. Springer, Heidelberg (1999)

    MATH  Google Scholar 

  24. Gautier, T., Le Guernic, P., Besnard, L.: SIGNAL: a declarative language for synchronous programming of real-time systems. In: Kahn, G. (ed.) Functional Programming Languages and Computer Architecture. LNCS, vol. 274, pp. 257–277. Springer, Heidelberg (1987)

    Chapter  Google Scholar 

  25. González-Vélez, H., Leyton, M.: A survey of algorithmic skeleton frameworks: high-level structured parallel programming enablers. Softw. Pract. Exper. 40(12), 1135–1160 (2010)

    Article  Google Scholar 

  26. Gustafson, J.L.: Reevaluating Amdahl’s law. Commun. ACM 31(5), 532–533 (1988)

    Article  Google Scholar 

  27. Halle, S.: A Study of Frameworks for Collectively Meeting the Productivity, Portability, and Adoptability Goals for Parallel Software. Ph.D. thesis, University of California, Santa Cruz (2011)

    Google Scholar 

  28. Halle, S., Cohen, A.: A mutable hardware abstraction to replace threads. In: Rajopadhye, S., Mills Strout, M. (eds.) LCPC 2011. LNCS, vol. 7146, pp. 185–202. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  29. Herlihy, M., Moss, J.E.B.: Transactional memory: architectural support for lock-free data structures. SIGARCH Comput. Archit. News 21(2), 289–300 (1993)

    Article  Google Scholar 

  30. Hoare, C.A.R.: Communicating Sequential Processes. Prentice-Hall, Upper Saddle River (1985)

    MATH  Google Scholar 

  31. Honda, K., Mukhamedov, A., Brown, G., Chen, T.-C., Yoshida, N.: Scribbling interactions with a formal foundation. In: Natarajan, R., Ojo, A. (eds.) ICDCIT 2011. LNCS, vol. 6536, pp. 55–75. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  32. Honda, K., Yoshida, N., Carbone, M.: Multiparty asynchronous session types. In: Necula, G.C., Wadler, P. (eds.) Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2008, San Francisco, California, USA, 7–12 January 2008, pp. 273–284. ACM (2008)

    Google Scholar 

  33. Jongmans, S.-S., Arbab, F.: Global consensus through local synchronization: a formal basis for partially-distributed coordination. Sci. Comput. Program. 115–116, 199–224 (2016)

    Article  Google Scholar 

  34. Jongmans, S.-S., Arbab, F.: Overview of thirty semantic formalisms for Reo. Sci. Ann. Comput. Sci. 22(1), 201–251 (2012)

    MathSciNet  Google Scholar 

  35. Jongmans, S.-S.T.Q., Arbab, F.: Global consensus through local synchronization. In: Canal, C., Villari, M. (eds.) ESOCC 2013. CCIS, vol. 393, pp. 174–188. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  36. Jongmans, S.-S., Arbab, F.: Modularizing and specifying protocols among threads. In: Proceedings of PLACES 2012. EPTCS, vol. 109, pp. 34–45. CoRR (2013)

    Google Scholar 

  37. Jongmans, S.-S., Arbab, F.: Toward sequentializing overparallelized protocol code. In: Proceedings of ICE 2014, EPTCS, vol. 166, pp. 38–44. CoRR (2014)

    Google Scholar 

  38. Jongmans, S.-S.T.Q., Halle, S., Arbab, F.: Automata-based optimization of interaction protocols for scalable multicore platforms. In: Kühn, E., Pugliese, R. (eds.) COORDINATION 2014. LNCS, vol. 8459, pp. 65–82. Springer, Heidelberg (2014)

    Chapter  Google Scholar 

  39. Jongmans, S.-S., Halle, S., Arbab, F.: Reo: a dataflow inspired language for multicore. In: Proceedings of DFM 2013, pp. 42–50. IEEE (2014)

    Google Scholar 

  40. Jongmans, S.-S., Santini, F., Arbab, F.: Partially-distributed coordination with Reo. In: Proceedings of PDP 2014, pp. 697–706. IEEE (2014)

    Google Scholar 

  41. Jongmans, S.-S., Santini, F., Sargolzaei, M., Arbab, F., Afsarmanesh, H.: Orchestrating web services using Reo: from circuits and behaviors to automatically generated code. SOCA 8(4), 277–297 (2014)

    Article  Google Scholar 

  42. Jongmans, S.-S.T.Q., Arbab, F.: Can high throughput atone for high latency in compiler-generated protocol code? In: Dastani, M., Sirjani, M. (eds.) FSEN 2015. LNCS, vol. 9392, pp. 238–258. Springer, Heidelberg (2015)

    Chapter  Google Scholar 

  43. Jongmans, S.-S.T.Q., Santini, F., Arbab, F.: Partially distributed coordination with Reo and constraint automata. SOCA 9(3–4), 311–339 (2015)

    Article  Google Scholar 

  44. Jongmans, S.-S.T.Q.: Automata-Theoretic Protocol Programming: Parallel Computation, Threads and Their Interaction, Optimized Compilation, [at a] High Level of Abstraction. Ph.D. thesis, Leiden University (2015, submitted)

    Google Scholar 

  45. Kahn, G.: The semantics of a simple language for parallel programming. In: Rosenfeld, J.L. (ed.) Information Processing, pp. 471–475. North Holland, Amsterdam (1974)

    Google Scholar 

  46. Kahn, G., MacQueen, D.B.: Coroutines and networks of parallel processes. In: IFIP Congress, pp. 993–998 (1977)

    Google Scholar 

  47. Knight, T.: An architecture for mostly functional languages. In: Proceedings of the 1986 ACM Conference on LISP and Functional Programming, LFP 1986, pp. 105–112. ACM, New York (1986)

    Google Scholar 

  48. Liu, X., Xiong, Y., Lee, E.A.: The ptolemy II framework for visual languages. In: 2002 IEEE CS International Symposium on Human-Centric Computing Languages and Environments (HCC 2001), 5–7 September 2001, Stresa, Italy, p. 50. IEEE Computer Society (2001)

    Google Scholar 

  49. Milner, R.: A Calculus of Communicating Systems. LNCS, vol. 92. Springer, Heidelberg (1980)

    MATH  Google Scholar 

  50. Milner, R.: Elements of interaction - turing award lecture. Commun. ACM 36(1), 78–89 (1993)

    Article  Google Scholar 

  51. Ng, N., de Figueiredo Coutinho, J.G., Yoshida, N.: Protocols by default - safe MPI code generation based on session types. In: Franke, B. (ed.) CC 2015. LNCS, vol. 9031, pp. 212–232. Springer, Heidelberg (2015)

    Chapter  Google Scholar 

  52. Ng, N., Yoshida, N.: Pabble: parameterised scribble for parallel programming. In: 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, PDP 2014, Torino, Italy, 12–14 February 2014, pp. 707–714. IEEE Computer Society (2014)

    Google Scholar 

  53. Sangiorgi, D., Walker, D.: Pi-Calculus: A Theory of Mobile Processes. Cambridge University Press, New York (2001)

    MATH  Google Scholar 

  54. Shavit, N., Touitou, D.: Software transactional memory. In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, PODC 1995, pp. 204–213. ACM, New York (1995)

    Google Scholar 

  55. Yoshida, N., Hu, R., Neykova, R., Ng, N.: The scribble protocol language. In: Abadi, M., Lluch Lafuente, A. (eds.) TGC 2013. LNCS, vol. 8358, pp. 22–41. Springer, Heidelberg (2014)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Formal Methods, CWI, Science Park 123, 1098 XG, Amsterdam, The Netherlands

    Farhad Arbab

  2. Leiden Institute for Advanced Computer Science, Leiden University, Leiden, The Netherlands

    Farhad Arbab

Authors
  1. Farhad Arbab
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Farhad Arbab .

Editor information

Editors and Affiliations

  1. Informatik 2, RWTH Aachen University Informatik 2, Aachen, Germany

    Erika Ábrahám

  2. Leiden University , Leiden, The Netherlands

    Marcello Bonsangue

  3. University of Oslo , Oslo, Norway

    Einar Broch Johnsen

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this chapter

Cite this chapter

Arbab, F. (2016). Proper Protocol. In: Ábrahám, E., Bonsangue, M., Johnsen, E. (eds) Theory and Practice of Formal Methods. Lecture Notes in Computer Science(), vol 9660. Springer, Cham. https://doi.org/10.1007/978-3-319-30734-3_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-30734-3_7

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-30733-6

  • Online ISBN: 978-3-319-30734-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation