PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Mazzanti F., Spagnolo G. O., Della Longa S., Ferrari A. Deadlock avoidance in train scheduling: a model checking approach. In: FMICS 2014 - Formal Methods for Industrial Critical Systems. 19th International Conference (Florence, Italy, 11-12 September 2014). Proceedings, pp. 109 - 123. Frédéric Lang, Francesco Flammini (eds.). (Lecture Notes in Computer Science, vol. 8718). Springer, 2014.
 
 
Abstract
(English)
In this paper we present the deadlock avoidance approach used in the design of the scheduling kernel of an Automatic Train Supervision (ATS) system. The ATS that we have designed prevents the occurrence of deadlocks by performing a set of runtime checks just before allowing a train to move further. For each train, the set of checks to be performed at each step of progress is retrieved from statically generated ATS configuration data. For the verification of the correctness of the logic used by the ATS and the validation of the constraints verified by the runtime checks, we define a formal model that represents the ATS behavior, the railway layout, and the planned service structure. We use this formal model to verify both the absence of deadlocks and absence of false positives (i.e., cases in which a train is unnecessarily disallowed to proceed). The verification is carried out by exploiting the UMC model checking verification framework locally developed at ISTI-CNR.
URL: http://link.springer.com/chapter/10.1007%2F978-3-319-10702-8_8
DOI: 10.1007/978-3-319-10702-8_8
Subject ATS
Deadlock
Model Checking
Scheduling
Train
D.2.2 Software Engineering. Design Tools and Techniques
D.2.4 Software/Program Verification. Formal methods
D.2.4 Software/Program Verification. Model checking


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional