Abstract
Interaction systems are a formal model for component-based systems. Combining components via connectors to form more complex systems may give rise to deadlock situations. Deciding the existence of deadlocks is NP-hard as it involves global state analysis. We present here a parametrized polynomial-time algorithm that is able to confirm deadlock-freedom for a certain class of interaction systems. The discussion includes characteristic examples and displays the role of the parameter of the algorithm.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Attie, P., Emerson, A.: Synthesis of Concurrent Systems with Many Similar Processes. ACM TOPLAS 1, 51–115 (1998)
Attie, P., Chockler, H.: Efficiently Verifiable Conditions for Deadlock-Freedom of Large Concurrent Programs. In: Cousot, R. (ed.) VMCAI 2005. LNCS, vol. 3385, pp. 465–481. Springer, Heidelberg (2005)
Minnameier, C.: Deadlock-Detection in Component-Based Systems is NP-Hard. Technical Report TR-2006-015 (2006)
Gößler, G., Sifakis, J.: Component-Based Construction of Deadlock-Free Systems. In: Pandya, P.K., Radhakrishnan, J. (eds.) FSTTCS 2003. LNCS, vol. 2914, pp. 420–433. Springer, Heidelberg (2003)
Gössler, G., Sifakis, J.: Composition for Component-Based Modeling. Sci. Comput. Program. 55, 161–183 (2005)
Sifakis, J.: A Framework for Component-based Construction. Keynote Talk, SEFM pp. 293–300 (2005)
Gößler, G., Graf, S., Majster-Cederbaum, M., Martens, M., Sifakis, J.: An Approach to Modelling and Verification of Component Based Systems. In: van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H., Plášil, F. (eds.) SOFSEM 2007. LNCS, vol. 4362, pp. 295–308. Springer, Heidelberg (2007)
Aldini, A., Bernardo, M.: A General Approach to Deadlock-Freedom Verification for Software Architectures. In: Araki, K., Gnesi, S., Mandrioli, D. (eds.) FME 2003. LNCS, vol. 2805, Springer, Heidelberg (2003)
Geilen, M.: Non-Exhaustive Model-Checking in Component Based Systems. Journal of Systems Architecture – The Euromicro Journal (2000)
Arons, T., Pnueli, A., Ruah, S., Xu, J., Zuck, L.D.: Parameterized Verification with Automatically Computed Inductive Assertions. In: Berry, G., Comon, H., Finkel, A. (eds.) CAV 2001. LNCS, vol. 2102, pp. 221–234. Springer, Heidelberg (2001)
Clarke, E., Enders, R., Filkorn, T., Jha, S.: Exploiting Symmetry in Temporal Logic Model Checking. FMSD 9(2) (1996)
Tanenbaum, A.: Modern Operating Systems, 2nd edn. Prentice Hall, Englewood Cliffs (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Majster-Cederbaum, M., Martens, M., Minnameier, C. (2007). A Polynomial-Time Checkable Sufficient Condition for Deadlock-Freedom of Component-Based Systems. In: van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H., Plášil, F. (eds) SOFSEM 2007: Theory and Practice of Computer Science. SOFSEM 2007. Lecture Notes in Computer Science, vol 4362. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69507-3_77
Download citation
DOI: https://doi.org/10.1007/978-3-540-69507-3_77
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-69506-6
Online ISBN: 978-3-540-69507-3
eBook Packages: Computer ScienceComputer Science (R0)