×

Asynchronous sequential processes. (English) Zbl 1170.68026

Summary: Deterministic behavior for parallel and distributed computation is rather difficult to ensure. To reach that goal, many formal calculi, languages, and techniques with well-defined semantics have been proposed in the past. But none of them focused on an imperative object calculus with asynchronous communications and futures. In this article, an object calculus, Asynchronous Sequential Processes (ASP), is defined, with its semantics. We prove also confluence properties for the ASP calculus. ASPs main characteristics are asynchronous communications with futures, and sequential execution within each process. This paper provides a very general and dynamic property ensuring confluence. Further, more specific and static properties are derived. Additionally, we present a formalization of distributed components based on ASP, and show how such components are used to statically ensure determinacy. This paper can also be seen as a formalization of the concept of futures in a distributed object setting.

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q55 Semantics in the theory of computing
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Cliff B. Jones, An object-based design method for concurrent programs, Technical Report, University of Manchester, 1992.; Cliff B. Jones, An object-based design method for concurrent programs, Technical Report, University of Manchester, 1992.
[2] Uwe Nestmann, Martin Steffen, Typing confluence, in: Stefania Gnesi, Diego Latella (Eds.), FMICS ’97: Second International ERCIM Workshop on Formal Methods in Industrial-Critical Systems, pp. 77-101. Consiglio Nazionale Ricerche di Pisa, Italy, July 1997. Also available as report ERCIM-10/97-R052, European Research Consortium for Informatics and Mathematics, 1997.; Uwe Nestmann, Martin Steffen, Typing confluence, in: Stefania Gnesi, Diego Latella (Eds.), FMICS ’97: Second International ERCIM Workshop on Formal Methods in Industrial-Critical Systems, pp. 77-101. Consiglio Nazionale Ricerche di Pisa, Italy, July 1997. Also available as report ERCIM-10/97-R052, European Research Consortium for Informatics and Mathematics, 1997.
[3] Kobayashi, Naoki; Pierce, Benjamin C.; Turner, David N., Linearity and the pi-calculus, (Proceedings of POPL ’96 (1996), ACM), 358-371
[4] Guy L. Steele Jr., Making asynchronous parallelism safe for the world, in: POPL’90, Proceedings of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, January 17-19, 1990, San Francisco, CA, ACM Press, New York, 1990, pp. 218-231.; Guy L. Steele Jr., Making asynchronous parallelism safe for the world, in: POPL’90, Proceedings of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, January 17-19, 1990, San Francisco, CA, ACM Press, New York, 1990, pp. 218-231.
[5] Gilles Kahn, The semantics of a simple language for parallel programming, in: J.L. Rosenfeld (Ed.), Information Processing ’74: Proceedings of the IFIP Congress, North-Holland, New York, 1974.; Gilles Kahn, The semantics of a simple language for parallel programming, in: J.L. Rosenfeld (Ed.), Information Processing ’74: Proceedings of the IFIP Congress, North-Holland, New York, 1974. · Zbl 0299.68007
[6] F. Baude, D. Caromel, C. DelbT, L. Henrio, Promised messages: recovering from inconsistent global states, in: ACM SIGOPS Conference Principles and Practice of Parallel Programming (PPoPP), Poster., 2007.; F. Baude, D. Caromel, C. DelbT, L. Henrio, Promised messages: recovering from inconsistent global states, in: ACM SIGOPS Conference Principles and Practice of Parallel Programming (PPoPP), Poster., 2007.
[7] Abadi, Martı´n; Cardelli, Luca, A Theory of Objects (1996), Springer-Verlag: Springer-Verlag New York · Zbl 0876.68014
[8] Caromel, Denis, Towards a method of object-oriented concurrent programming, Communications of the ACM, 36, 9, 90-102 (1993)
[9] Caromel, Denis; Klauser, Wilfried; Vayssière, Julien, Towards seamless computing and metacomputing in Java, Concurrency: Practice and Experience, 10, 11-13, 1043-1061 (1998), ProActive available at
[10] Caromel, Denis; Henrio, Ludovic; Serpette, Bernard Paul, Asynchronous and deterministic objects, (Proceedings of the 31st ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (2004), ACM Press), 123-134 · Zbl 1325.68052
[11] Caromel, Denis; Henrio, Ludovic, A Theory of Distributed Objects (2005), Springer-Verlag, Inc.: Springer-Verlag, Inc. New York · Zbl 1084.68012
[12] Nestmann, Uwe; Hüttel, Hans; Kleist, Josva; Merro, Massimo, Aliasing models for mobile objects, Information and Computation, 175, 1, 3-33 (2002) · Zbl 1012.68114
[13] Gordon, Andrew D.; Hankin, Paul D.; Lassen, Søren B., Compilation and equivalence of imperative objects, (Ramesh, S.; Sivakumar, G., FSTTCS. FSTTCS, Lecture Notes in Computer Science, vol. 1346 (1997), Springer), 74-87 · Zbl 0942.68025
[14] Gilles Kahn, David MacQueen, Coroutines and networks of parallel processes, in: B. Gilchrist (Ed.), Information Processing ’77: Proceedings of IFIP Congress, North-Holland, Amsterdam, 1977, pp. 993-998.; Gilles Kahn, David MacQueen, Coroutines and networks of parallel processes, in: B. Gilchrist (Ed.), Information Processing ’77: Proceedings of IFIP Congress, North-Holland, Amsterdam, 1977, pp. 993-998. · Zbl 0363.68076
[15] Brian Cantwell Smith, Reflection and semantics in Lisp, in: Conference Record of the Eleventh Annual ACM Symposium on Principles of Programming Languages, Salt Lake City, Utah, January 15-18, 1984, ACM Press, New York, pp. 23-35.; Brian Cantwell Smith, Reflection and semantics in Lisp, in: Conference Record of the Eleventh Annual ACM Symposium on Principles of Programming Languages, Salt Lake City, Utah, January 15-18, 1984, ACM Press, New York, pp. 23-35.
[16] Bernard Lang, Christian Queinnec, José Piquer, Garbage collecting the world, in: Conference Record of the Nineteenth Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, January 1992, pp. 39-50.; Bernard Lang, Christian Queinnec, José Piquer, Garbage collecting the world, in: Conference Record of the Nineteenth Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, January 1992, pp. 39-50.
[17] Fabrice Le Fessant, Detecting distributed cycles of garbage in large-scale systems, in: Conference on Principles of Distributed Computing (PODC), Rhode Island, August 2001.; Fabrice Le Fessant, Detecting distributed cycles of garbage in large-scale systems, in: Conference on Principles of Distributed Computing (PODC), Rhode Island, August 2001.
[18] Denis Caromel, Ludovic Henrio, Asynchonous distributed components: concurrency and determinacy, in: Proceedings of the IFIP International Conference on Theoretical Computer Science 2006 (IFIP TCS’06), Santiago, Chile, Springer Science, August 2006 (19th IFIP World Computer Congress).; Denis Caromel, Ludovic Henrio, Asynchonous distributed components: concurrency and determinacy, in: Proceedings of the IFIP International Conference on Theoretical Computer Science 2006 (IFIP TCS’06), Santiago, Chile, Springer Science, August 2006 (19th IFIP World Computer Congress). · Zbl 1084.68012
[19] Gordon, Andrew D.; Hankin, Paul D., A concurrent object calculus: reduction and typing, (Proceedings HLCL’98, vol. 16 (1998), Elsevier ENTCS: Elsevier ENTCS Amsterdam) · Zbl 0917.68064
[20] Alan Jeffrey, A distributed object calculus, in: ACM SIGPLAN Workshop Foundations of Object Oriented Languages, 2000.; Alan Jeffrey, A distributed object calculus, in: ACM SIGPLAN Workshop Foundations of Object Oriented Languages, 2000.
[21] Oscar Nierstrasz, Towards an object calculus, in: M. Tokoro, O. Nierstrasz, P. Wegner (Eds.), Proceedings of the ECOOP’91 Workshop on Object-Based Concurrent Computing, LNCS, vol. 612, Springer-Verlag, 1992, pp. 1-20.; Oscar Nierstrasz, Towards an object calculus, in: M. Tokoro, O. Nierstrasz, P. Wegner (Eds.), Proceedings of the ECOOP’91 Workshop on Object-Based Concurrent Computing, LNCS, vol. 612, Springer-Verlag, 1992, pp. 1-20.
[22] Andrew D. Gordon, Gareth D. Rees, Bisimilarity for a first-order calculus of objects with subtyping, in: Conference Record of the 23rd ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL’96) [49], pp. 386-395.; Andrew D. Gordon, Gareth D. Rees, Bisimilarity for a first-order calculus of objects with subtyping, in: Conference Record of the 23rd ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL’96) [49], pp. 386-395.
[23] Luca Cardelli, A language with distributed scope, in: Conference Record of the 22nd ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL’95), San Francisco, January 22-25, 1995, ACM SIGACT-SIGPLAN, ACM Press, New York, pp. 286-297.; Luca Cardelli, A language with distributed scope, in: Conference Record of the 22nd ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL’95), San Francisco, January 22-25, 1995, ACM SIGACT-SIGPLAN, ACM Press, New York, pp. 286-297.
[24] Benjamin C. Pierce, David N. Turner, Concurrent objects in a process calculus, in: Takayasu Ito, Akinori Yonezawa (Eds.), Proceedings of Theory and Practice of Parallel Programming (TPPP’94), Sendai, Japan, LNCS, Springer-Verlag, Berlin, Heidelberg, 1995, pp. 187-215.; Benjamin C. Pierce, David N. Turner, Concurrent objects in a process calculus, in: Takayasu Ito, Akinori Yonezawa (Eds.), Proceedings of Theory and Practice of Parallel Programming (TPPP’94), Sendai, Japan, LNCS, Springer-Verlag, Berlin, Heidelberg, 1995, pp. 187-215.
[25] Milner, Robin; Parrow, Joachim; Walker, David, A calculus of mobile processes, part I/II, Journal of Information and Computation, 100, 1-77 (1992) · Zbl 0752.68037
[26] Robin Milner, The polyadic \(\operatorname{\Pi;} \); Robin Milner, The polyadic \(\operatorname{\Pi;} \)
[27] Daren L. Webb, Andrew L. Wendelborn, Julien Vayssière, A study of computational reconfiguration in a Process Network, in: Proceedings of the 7th Workshop on Integrated Data Environments Australia (IDEA’7), February 2000.; Daren L. Webb, Andrew L. Wendelborn, Julien Vayssière, A study of computational reconfiguration in a Process Network, in: Proceedings of the 7th Workshop on Integrated Data Environments Australia (IDEA’7), February 2000.
[28] Cliff B. Jones, Steve J. Hodges, Non-interference properties of a concurrent object-based language: proofs based on an operational semantics, in: Burkhard Freitag, Cliff B. Jones, Christian Lengauer, Hans-Jörg Schek (Eds.), Object-Orientation with Parallelism and Persistence, Kluwer Academic Publishers, Dordrecht, 1996, pp. 1-22 (Chapter 1).; Cliff B. Jones, Steve J. Hodges, Non-interference properties of a concurrent object-based language: proofs based on an operational semantics, in: Burkhard Freitag, Cliff B. Jones, Christian Lengauer, Hans-Jörg Schek (Eds.), Object-Orientation with Parallelism and Persistence, Kluwer Academic Publishers, Dordrecht, 1996, pp. 1-22 (Chapter 1).
[29] Cliff B. Jones, Process-algebraic foundations for an object-based design notation, Technical Report, University of Manchester, 1993 (UMCS-93-10-1).; Cliff B. Jones, Process-algebraic foundations for an object-based design notation, Technical Report, University of Manchester, 1993 (UMCS-93-10-1).
[30] Davide Sangiorgi, The typed \(\operatorname{\Pi;} \); Davide Sangiorgi, The typed \(\operatorname{\Pi;} \)
[31] Xinxin Liu, David Walker, Confluence of processes and systems of objects, in: Peter D. Mosses, Mogens Nielsen, Michael I. Schwarzbach (Eds.), TAPSOFT ’95: Theory and Practice of Software Development, 6th International Joint Conference CAAP/FASE, LNCS, vol. 915, Springer-Verlag, Berlin, Heidelberg, 1995, pp. 217-231.; Xinxin Liu, David Walker, Confluence of processes and systems of objects, in: Peter D. Mosses, Mogens Nielsen, Michael I. Schwarzbach (Eds.), TAPSOFT ’95: Theory and Practice of Software Development, 6th International Joint Conference CAAP/FASE, LNCS, vol. 915, Springer-Verlag, Berlin, Heidelberg, 1995, pp. 217-231. · Zbl 0913.68129
[32] Liu, Xinxin; Walker, David, Partial confluence of processes and systems of objects, Theoretical Computer Science, 206, 1-2, 127-162 (1998) · Zbl 0913.68129
[33] Gul Agha, Ian A. Mason, Scott F. Smith, Carolyn L. Talcott, Towards a theory of actor computation (extended abstract), in: W.R. Cleaveland (Ed.), CONCUR’92: Proceedings of the Third International Conference on Concurrency Theory, Springer-Verlag, Berlin, Heidelberg, 1992, pp. 565-579.; Gul Agha, Ian A. Mason, Scott F. Smith, Carolyn L. Talcott, Towards a theory of actor computation (extended abstract), in: W.R. Cleaveland (Ed.), CONCUR’92: Proceedings of the Third International Conference on Concurrency Theory, Springer-Verlag, Berlin, Heidelberg, 1992, pp. 565-579.
[34] Agha, Gul; Mason, Ian A.; Smith, Scott F.; Talcott, Carolyn L., A foundation for actor computation, Journal of Functional Programming, 7, 1, 1-72 (1997) · Zbl 0870.68091
[35] Yonezawa, Akinori; Shibayama, Etsuya; Takada, Toshihiro; Honda, Yasuaki, Modelling and programming in an object-oriented concurrent language ABCL/1, (Yonezawa, A.; Tokoro, M., Object-Oriented Concurrent Programming (1987), MIT Press: MIT Press Cambridge, MA), 55-89
[36] Halstead, Robert H., Multilisp: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), 7, 4, 501-538 (1985) · Zbl 0581.68037
[37] Niehren, J.; Schwinghammer, J.; Smolka, G., A concurrent lambda calculus with futures, Theoretical Computer Science, 364, 3, 338-356 (2006) · Zbl 1110.68023
[38] Joachim Niehren, David Sabel, Manfred Schmidt-Schau, Jan Schwinghammer, Observational semantics for a concurrent lambda calculus with reference cells and futures, in: Proceedings of the 23rd Conference on the Mathematical Foundations of Programming Semantics (MFPS XXIII), Electronic Notes in Theoretical Computer Science, vol. 173, New Orleans, April 2, 2007, pp. 313-337; Joachim Niehren, David Sabel, Manfred Schmidt-Schau, Jan Schwinghammer, Observational semantics for a concurrent lambda calculus with reference cells and futures, in: Proceedings of the 23rd Conference on the Mathematical Foundations of Programming Semantics (MFPS XXIII), Electronic Notes in Theoretical Computer Science, vol. 173, New Orleans, April 2, 2007, pp. 313-337 · Zbl 1316.68034
[39] F.S. de Boer, D. Clarke, E. Broch Johnsen, A complete guide to the future, in: ESOP, 2007, pp. 316-330.; F.S. de Boer, D. Clarke, E. Broch Johnsen, A complete guide to the future, in: ESOP, 2007, pp. 316-330.
[40] Johnsen, Einar Broch; Owe, Olaf; Yu, Ingrid Chieh, Creol: a type-safe object-oriented model for distributed concurrent systems, Theoretical Computer Science, 365, 1-2, 23-66 (2006) · Zbl 1118.68031
[41] Dedecker, J.; Van Cutsem, T.; Mostinckx, S.; D’Hondt, T.; De Meuter, W., Ambient-oriented programming in ambienttalk, (Thomas, D., ECOOP. ECOOP, Lecture Notes in Computer Science, vol. 4067 (2006), Springer), 230-254
[42] Cédric Fournet, Georges Gonthier, Jean-Jacques Levy, Luc Maranget, Didier Remy, A calculus of mobile agents, in: U. Montanari, V. Sassone (Eds.), Proceedings of the 7th International Conference on Concurrency Theory (CONCUR), LNCS, vol. 1119, Springer-Verlag, Berlin, Heidelberg, August 1996, pp. 406-421.; Cédric Fournet, Georges Gonthier, Jean-Jacques Levy, Luc Maranget, Didier Remy, A calculus of mobile agents, in: U. Montanari, V. Sassone (Eds.), Proceedings of the 7th International Conference on Concurrency Theory (CONCUR), LNCS, vol. 1119, Springer-Verlag, Berlin, Heidelberg, August 1996, pp. 406-421.
[43] Cédric Fournet, Georges Gonthier, The reflexive CHAM and the join-calculus, in: Conference Record of the 23rd ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL’96) [49], pp. 372-385.; Cédric Fournet, Georges Gonthier, The reflexive CHAM and the join-calculus, in: Conference Record of the 23rd ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL’96) [49], pp. 372-385.
[44] Alain Deutsch, Interprocedural may-alias analysis for pointers: beyond \(k\); Alain Deutsch, Interprocedural may-alias analysis for pointers: beyond \(k\)
[45] Alain Deutsch, Semantic models and abstract interpretation techniques for inductive data structures and pointers, in: Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, La Jolla, California, June 21-23, 1995, pp. 226-229.; Alain Deutsch, Semantic models and abstract interpretation techniques for inductive data structures and pointers, in: Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, La Jolla, California, June 21-23, 1995, pp. 226-229.
[46] Sagiv, Mooly; Reps, Thomas; Horwitz, Susan, Precise interprocedural dataflow analysis with applications to constant propagation, Theoretical Computer Science, 167, 1-2, 131-170 (1996) · Zbl 0874.68133
[47] Paulo Sergio Almeida, Balloon types: controlling sharing of state in data types, in: Mehmet Akşit, Satoshi Matsuoka (Eds.), ECOOP’97—Object-Oriented Programming 11th European Conference, Jyvskyl, Finland, vol. 1241, Springer-Verlag, New York, 1997, pp. 32-59.; Paulo Sergio Almeida, Balloon types: controlling sharing of state in data types, in: Mehmet Akşit, Satoshi Matsuoka (Eds.), ECOOP’97—Object-Oriented Programming 11th European Conference, Jyvskyl, Finland, vol. 1241, Springer-Verlag, New York, 1997, pp. 32-59.
[48] Attali, Isabelle; Caromel, Denis; Guider, Romain, A step toward automatic distribution of Java programs, (Smith, S. F.; Talcott, C. L., FIP International Conference on Formal Methods for Open Object-Based Distributed Systems (2000), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 141-161 · Zbl 0968.68032
[49] ACM SIGACT-SIGPLAN, Conference Record of the 23rd ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL’96), St. Petersburg, Florida, January 21-24, ACM Press, 1996.; ACM SIGACT-SIGPLAN, Conference Record of the 23rd ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL’96), St. Petersburg, Florida, January 21-24, ACM Press, 1996.
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.