Probabilistic Process Algebra and Strategic Interleaving

Published in Volume XXX, Issue 2, 2020, pages 205–243, doi: 10.7561/SACS.2020.2.205

Authors: C.A. Middelburg

Abstract

We first present a probabilistic version of ACP that rests on the principle that probabilistic choices are always resolved before choices involved in alternative composition and parallel composition are resolved and then extend this probabilistic version of ACP with a form of interleaving in which parallel processes are interleaved according to what is known as a process-scheduling policy in the field of operating systems. We use the term strategic interleaving for this more constrained form of interleaving. The extension covers probabilistic process-scheduling policies.

Full Text (PDF)

References

[1] P. America, J.W. de Bakker. Designing Equivalent Semantic Models for Process Creation. Theoretical Computer Science 60(2), 109–176, 1988. doi:10.1016/0304-3975(88)90048-5.

[2] S. Andova. Process Algebra with Probabilistic Choice. In J.-P. Katoen (Ed.), Formal Methods for Real-Time and Probabilistic Systems (ARTS 1999), Lecture Notes in Computer Science 1601, 111–129, 1999. doi:10.1007/3-540-48778-6_7.

[3] S. Andova. Probabilistic Process Algebra. PhD thesis, Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, 2002. doi:10.6100/IR561343.

[4] S. Andova, S. Georgievska. On Compositionality, Efficiency, and Applicability of Abstraction in Probabilistic Systems. In M. Nielsen, A. Kuc̆era, P.B. Miltersen, C. Palamidessi, P. Tůma, F. Valencia (Eds.), Theory and Practice of Computer Science (SOFSEM 2009), Lecture Notes in Computer Science 5404, 67–78, 2009. doi:10.1007/978-3-540-95891-8_10.

[5] J.C.M. Baeten, J.A. Bergstra. Real Space Process Algebra. Formal Aspects of Computing 5(6), 481–529, 1993. doi:10.1007/BF01211247.

[6] J.C.M. Baeten, J.A. Bergstra, S.A. Smolka. Axiomatizing Probabilistic Processes: ACP with Generative Probabilities. Information and Computation 121(2), 234–255, 1995. doi:10.1006/inco.1995.1135.

[7] J.C.M. Baeten, C.A. Middelburg. Process Algebra with Timing. Monographs in Theoretical Computer Science, An EATCS Series. Springer-Verlag, Berlin, 2002. doi:10.1007/978-3-662-04995-2.

[8] J.C.M. Baeten, F.W. Vaandrager. An Algebra of Process Creation. Acta Informatica 29(4), 303–334, 1992. doi:10.1007/BF01178776.

[9] J.C.M. Baeten, W.P. Weijland. Process Algebra, Cambridge Tracts in Theoretical Computer Science 18. Cambridge University Press, Cambridge, 1990. doi:10.1017/CBO9780511624193.

[10] M. Ben-Ari. Principles of Concurrent and Distributed Programming. Pearson, Harlow, second edition, 2006.

[11] J.A. Bergstra. A Process Creation Mechanism in Process Algebra. In J.C.M. Baeten (Ed.), Applications of Process Algebra, Cambridge Tracts in Theoretical Computer Science 17, 81–88, 1990. doi:10.1017/CBO9780511608841.006.

[12] J.A. Bergstra, I. Bethke, A. Ponse. Cancellation Meadows: A Generic Basis Theorem and Some Applications. Computer Journal 56(1), 3–14, 2013. doi:10.1093/comjnl/bxs028.

[13] J.A. Bergstra, J.W. Klop. The Algebra of Recursively Defined Processes and the Algebra of Regular Processes. In J. Paredaens (Ed.), Automata, Languages and Programming (ICALP 1984), Lecture Notes in Computer Science 172, 82–95, 1984. doi:10.1007/3-540-13345-3_7.

[14] J.A. Bergstra, J.W. Klop. Process Algebra for Synchronous Communication. Information and Control 60(1–3), 109–137, 1984. doi:10.1016/S0019-9958(84)80025-X.

[15] J.A. Bergstra, C.A. Middelburg. Thread Algebra for Strategic Interleaving. Formal Aspects of Computing 19(4), 445–474, 2007. doi:10.1007/s00165-007-0024-9.

[16] J.A. Bergstra, C.A. Middelburg. Process Algebra with Strategic Interleaving. Theory of Computing Systems 63(3), 488–505, 2019. doi:10.1007/s00224-018-9873-2.

[17] J.A. Bergstra, C.A. Middelburg, Y.S. Usenko. Discrete Time Process Algebra and the Semantics of SDL. In J.A. Bergstra, A.Ponse, S.A. Smolka (Eds.), Handbook of Process Algebra, 1209–1268, 2001. doi:10.1016/B978-044482830-9/50036-9.

[18] J.A. Bergstra, A. Ponse. Probability Functions in the Context of Signed Involutive Meadows. In P. James, M. Roggenbach (Eds.), Recent Trends in Algebraic Development Techniques (WADT 2016), Lecture Notes in Computer Science 10644, 73–87, 2017. doi:10.1007/978-3-319-72044-9_6.

[19] J.A. Bergstra, J.V. Tucker. The Rational Numbers as an Abstract Data Type. Journal of the ACM 54(2), Article 7, 2007. doi:10.1145/1219092.1219095.

[20] P. Brinch Hansen. Operating System Principles. Prentice-Hall, Englewood Cliffs, NJ, 1973.

[21] E.W. Dijkstra. Cooperating Sequential Processes. In F. Genuys (Ed.), Programming Languages, 43–112, 1968.

[22] T. Gehrke, A. Rensink. Process Creation and Full Sequential Composition in a Name-Passing Calculus. Electronic Notes in Theoretical Computer Science 7, 141–160, 1997. doi:10.1016/S1571-0661(05)80471-2.

[23] S. Georgievska. Probability and Hiding in Concurrent Processes. PhD thesis, Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, 2011. doi:10.6100/IR716397.

[24] J. Gosling, B. Joy, G. Steele, G. Bracha. The Java Language Specification. Addison-Wesley, Reading, MA, third edition, 2005.

[25] A. Hejlsberg, S. Wiltamuth, P. Golde. C# Language Specification. Addison-Wesley, Reading, MA, 2003.

[26] C.A.R. Hoare. Communicating Sequential Processes. Prentice-Hall, Englewood Cliffs, 1985.

[27] R. Lanotte, S. Tini. Probabilistic Bisimulation as a Congruence. ACM Transactions on Computational Logic 10(2), Article 9, 2009. doi:10.1145/1462179.1462181.

[28] R. Milner. Communication and Concurrency. Prentice-Hall, Englewood Cliffs, 1989.

[29] A. Sabelfeld, D. Sands. Probabilistic Noninterference for Multi-Threaded Programs. In Proceedings 13th IEEE Computer Security Foundations Workshop (CSFW-13), 2000. doi:10.1109/CSFW.2000.856937.

[30] A. Silberschatz, P.B. Galvin, G. Gagne. Operating System Concepts. John Wiley and Sons, Hoboken, NJ, tenth edition, 2018.

[31] A.S. Tanenbaum, H. Bos. Modern Operating Systems. Pearson, Harlow, fourth edition, 2015.

[32] R.J. van Glabbeek, S.A. Smolka, B. Steffen. Reactive, Generative and Stratified Models of Probabilistic Processes. Information and Computation 121(1), 59–80, 1995. doi:10.1109/LICS.1990.113740.

[33] R.J. van Glabbeek, F.W. Vaandrager. Modular Specification of Process Algebras. Theoretical Computer Science 113(2), 293–348, 1993. doi:10.1016/0304-3975(93)90006-F..

[34] C.A. Waldspurger, W.E. Weihl. Lottery Scheduling: Flexible Proportional-Share Resource Management. In Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation (OSDI ’94), Article 1, 1994.

Bibtex

@article{sacscuza:middelburg20ppasi,
  title={Probabilistic Process Algebra and Strategic Interleaving},
  author={C.A. Middelburg},
  journal={Scientific Annals of Computer Science},
  volume={30},
  number={2},
  organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
  year={2020},
  pages={205-243},
  publisher={Alexandru Ioan Cuza University Press, Ia\c si},
  doi={10.7561/SACS.2020.2.205}
}