[Back]

R. Mittermayr, J. Blieberger, A. Schöbel:
"Kronecker Algebra based Deadlock Analysis for Railway Systems";
Promet-Traffic & Transportation, 24 (2012), 5; 359 - 369.

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 matrix 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 more efficiently if constraints are added.

Deadlock-Analyse für Eisenbahn-Dispositionssysteme unterscheidet sich von Deadlock-Analyse in der Informatik in mehreren Punkten. Während Deadlock-Analyse für Standard-Computersysteme im Allgemeinen gut verstanden ist, stellen Eingebettete Systeme eine neue Herausforderung dar. Ein neuer Ansatz aus diesem Bereich kann auf
Eisenbahn-Dispositionssysteme angewandt werden. Der Ansatz basiert auf Kronecker Algebra. Eine "Lazy Implementierung" der Matrixoperationen erlaubt sogar die Analyse von exponentiell wachsenden Systemen in sehr effizienten Art und Weise. Die Laufzeit des Algorithmus hängt nicht von der Problemgröße sondern von der
Größe des Ergebnisses ab. Während andere Ansätze durch zusätzliche Einschränkungen langsamer werden, liefert unsere Methode das Ergebnis schneller, sobald weitere Einschränkungen hinzukommen. Weiters ist unser Ansatz vollständig (complete) und fehlerfrei (sound), d.h. es treten weder "false positives" noch "false negatives" auf.

Railway Networks, Deadlocks, Deadlock Avoidance, Kronecker Algebra

http://dx.doi.org/10.7307/ptt.v24i5.1171