Kronecker Algebra-based Deadlock Analysis for Railway Systems
Abstract
Deadlock analysis for railway systems differs in several aspects from deadlock analysis in computer science. While the problem of deadlock analysis for standard computer systems is well-understood, multi-threaded embedded computer systems pose new challenges. A novel approach in this area can easily be applied to deadlock analysis in the domain of railway systems. The approach is based on Kronecker algebra. A lazy implementation of the matrix operations even allows analysing exponentially sized systems in a very efficient manner. The running time of the algorithm does not depend on the problem size but on the size of the solution. While other approaches suffer from the fact that additional constraints make the problem and its solution harder, our approach delivers its results faster if constraints are added. In addition, our approach is complete and sound for railway systems, i.e., it generates neither false positives nor false negatives.References
Stallings, W.: Operating Systems, 4th Ed., Upper Saddle River, New Jersey: Prentice-Hall, 2001
Coffman, E. G. J., Elphick, M. J. and Shoshani, A.: “System deadlocks,” ACM Computing Surveys, Vol. 3, No. 2, pp. 67-78,
Dijkstra, E. W.: “Een algorithme ter voorkoming van de dodelijke omarming (EWD-108)”.
Mittermayr, R. and Blieberger, J.: “Shared Memory Concurrent System Verification using Kronecker Algebra”, 2011. [Online]. Available: http://arxiv.org/abs/1109.5522.
Miller, J.: “Earliest Known Uses of Some of the Words of Mathematics”, 2011. [Online]. Available: http://jeff560.tripod.com/k.html. [Accessed 26 Sept. 2011]
Bellman, R.: Introduction to Matrix Analysis, Classics in Applied Mathematics, 2nd Ed., Society for Industrial and Applied Mathematics, 1997
Graham, A.: Kronecker Products and Matrix Calculus with Applications, New York: Ellis Horwood Ltd., 1981
Davio, M. “Kronecker Products and Shuffle Algebra”, IEEE Trans. Computers, Vol. 30, No. 2, pp. 116-125, 1981
Hurwitz, A.: “Zur Invariantentheorie”, Math. Annalen, Vol. 45, pp. 381-404, 1894
Plateau, B. and Atif, K.: “Stochastic Automata Network For Modeling Parallel Systems”, IEEE Trans. Software Eng., Vol. 17, No. 10, pp. 1093-1108, 1991
Küster, G.: “On the Hurwitz Product of Formal Power Series and Automata”, Theor. Comput. Science, Vol. 83, No. 2, pp. 261-273, 1991
Imrich, W., Klavzar, S. and Rall, D. F.: Topics in Graph Theory: Graphs and Their Cartesian Product, A K Peters Ltd, 2008
Knuth, D. E.: Combinatorial Algorithms, The Art of Computer Programming, Vol. 4A, Addison-Wesley, 2011
Dijkstra, E. W.: “A note on two problems in connexion with graphs”, Numerische Mathematik, Vol. 1, pp. 269-271, 1959
Fredman, M. L. and Tarjan, R. E.: “Fibonacci heaps and their uses in improved network optimization algorithms”, in 25th Annual Symposium on Foundations of Computer Science, 1984
Henderson, P. and Morris, J. J. H.: “A Lazy Evaluator”, in Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, 1976
Buchholz, P. and Kemper, P.: “Efficient Computation and Representation of Large Reachability Sets for Composed Automata”, Discrete Event Dynamic Systems, Vol. 12, No. 3, pp. 265-286, 2002
Mittermayr, R. and Blieberger, J.: Timing Analysis of Concurrent Programs, In Proc. of 12th Int. Workshop on Worst-Case Execution Time Analysis, 2012
Plateau, B.: “On the Stochastic Structure of Parallelism and Synchronization Models for Distributed Algorithms”, ACM SIGMETRICS, Vol. 13, pp. 147-154, 1985
Ciardo, G. and Miner, A. S.: “A Data Structure for the Efficient Kronecker Solution of GSPNs”, in Proc. 8th Int. Workshop on Petri Nets and Performance Models (PNPM'99), 1999
Cui, Y.: Simulation-Based Hybrid Model for a Partially-Automatic Dispatching of Railway Operation, I. f. E. u. Verkehrswesen, Ed., Universität Stuttgart: PhD thesis, 2010
Martin, U.: Verfahren zur Bewertung von Zug- und Rangierfahrten bei der Disposition, TU Braunschweig: PhD thesis, 1995
Pachl, J.: Steuerlogik für Zuglenkanlagen zum Einsatz unter stochastischen Betriebsbedingungen, TU Braunschweig: PhD thesis, 1993
Petersen, E. and Taylor, A.: “Line Block Prevention in Rail Line Dispatch”, INFOR Journal, Vol. 21, No. 1, pp. 46-51, 1983
Mills, G., Pudney, P. J., White, K. and Hewitt, J.: “The effects of deadlock avoidance on rail network capacity and performance”, in Proc. of the 2003 mathematics-in-industry study group, 2003
Lu, Q., Dessouky, M. and Leachman, R. C.: “Modeling Train Movements Through Complex Rail Networks”, ACM Transactions on Modeling and Computer Simulation, Vol. 14, No. 1, pp. 48-75, 2004
Fanti, M. P., Giua, A. and Seatzu, C.: “A deadlock prevention method for railway networks using monitors for colored Petri nets”, in Proc. of Int. Conf. on Systems, Man and Cybernetics, 2003
Zarnay, M.: “Solving deadlock states in model of railway station operation using coloured Petri nets”, in Proceedings of Symposium FORMS/FORMAT, 2008
Zehfuss, J. G.: “Ueber eine gewisse Determinante,” Zeitschrift für Mathematik und Physik, Vol. 3, pp. 298-301, 1858
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
