Artículo

La versión final de este artículo es de uso interno de la institución.
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Two base algorithms are known for reachability verification over timed automata. They are called forward and backwards, and traverse the automata edges using either successors or predecessors. Both usually work with a data structure called Difference Bound Matrices (DBMs). Although forward is better suited for on-the-fly construction of the model, the one known as backwards provides the basis for the verification of arbitrary formulae of the TCTL logic, and more importantly, for controller synthesis. Zeus is a distributed model checker for timed automata that uses the backwards algorithm. It works assigning each automata location to only one processor. This design choice seems the only reasonable way to deal with some complex operations involving many DBMs in order to avoid huge overheads due to distribution. This article explores the limitations of Zeus-like approaches for the distribution of timed model checkers. Our findings justify why close-to-linear speedups are so difficult -and sometimes impossible- to achieve in the general case. Nevertheless, we present mechanisms based on the way model checking is usually applied. Among others, these include model-topology-aware partitioning and on-the-fly workload redistribution. Combined, they have a positive impact on the speedups obtained.

Registro:

Documento: Artículo
Título:Dealing with practical limitations of distributed timed model checking for timed automata
Autor:Braberman, V.; Olivero, A.; Schapachnik, F.
Filiación:Departamento de Computación, FCEyN, Universidad de Buenos Aires, Buenos Aires, Argentina
Centro de Estudios Avanzados, FIyCE, Universidad Argentina de la Empresa, Buenos Aires, Argentina
Palabras clave:DBM; Distributed timed model checking; Kronos; Load-balance; Reachability; Reconfiguration; Redistribution; Timed automata; Zeus; Algorithms; Control equipment; Data structures; Formal logic; Program processors; Topology; Difference Bound Matrices (DBM); Distributed timed model checking; Kronos; Load-balance; Reachability; Reconfiguration; Redistribution; Timed automata; Zeus; Automata theory
Año:2006
Volumen:29
Número:2
Página de inicio:197
Página de fin:214
DOI: http://dx.doi.org/10.1007/s10703-006-0012-3
Título revista:Formal Methods in System Design
Título revista abreviado:Formal Methods Syst Des
ISSN:09259856
CODEN:FMSDE
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09259856_v29_n2_p197_Braberman

Referencias:

  • Aceto, L., Burgueno, A., Larsen, K.G., Model checking via reachability testing for timed automata (1998) Tools and Algorithms for Construction and Analysis of Systems (TACAS '98), pp. 263-280
  • Alfonso, A., Braberman, V., Kicillof, N., Olivero, A., Visual timed event scenarios (2004) Proc. of the 26th ACM/IEEE International Conference on Software Engineering
  • Altisen, K., Tripakis, S., Tools for controller synthesis of timed systems (2002) RT-TOOLs
  • Alur, R., Courcoubetis, C., Dill, D., Halbwachs, N., Wong-Toi, I.I., An implementation of three algorithms for timing verification based on automata emptiness (1992) Proceedings of the 13th IEEE Real-time Systems Symposium, pp. 157-166. , Phoenix, Arizona
  • Alur, R., Courcoubetis, C., Dill, D.L., Model-checking in dense real-time (1993) Inform Comp, 104 (1), pp. 2-34
  • Alur, R., Dill, D.L., A theory of timed automata (1994) Theor Comp Sci, 126 (2), pp. 183-235
  • Barnat, J., Brim, L., Stríbřná, J., Distributed LTL model-checking in SPIN (2001) Proc. of the 8th International SPIN Workshop, pp. 200-216. , Dwyer MB (eds) Toronto, Canada
  • Behrmann, G., Distributed reachability analysis in timed automata (2005) Int J Softw Tools Technol Transf, 7 (1), pp. 19-30
  • Behrmann, G., Hune, T., Vaandrager, F.W., Distributing timed model checking - How the search order matters (2000) LNCS, 1855, pp. 216-231. , Computer aided verification
  • Ben-David, S., Heyman, T., Grumberg, O., Schuster, A., Scalable distributed on-the-fly symbolic model checking (2000) Formal Methods in Computer-aided Design, pp. 390-404
  • Bengtsson, J., Larsen, K.G., Larsson, F., Pettersson, P., Yi, W., UPPAAL - A tool suite for automatic verification of real-time systems (1995) Hybrid Systems, pp. 232-243
  • Bollig, B., Leucker, M., Weber, M., Parallel model checking for the alternation free μ-calculus (2001) LNCS, 2031, pp. 543-558. , 7th international conference on tools and algorithms for the construction and analysis of systems (TACAS '01)
  • Bozga, M., Daws, C., Maler, O., Olivero, A., Tripakis, S., Yovine, S., Kronos: A model-checking tool for real-time systems (1998) LNCS, 1427, pp. 546-550. , Proc. of the 10th Intl. Conf. CAV '98
  • Braberman, V., (2000) Modeling and Checking Real-time Systems Designs, , Phd. thesis, Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires
  • Braberman, V., Garbervetsky, D., Olivero, A., ObsSlice: A timed automata slicer based on observers (2004) Proc of the 16th Intl Conf CAV '04
  • Braberman, V., Olivero, A., Schapachnik, F., Zeus: A distributed timed model checker based on Kronos (2002) ENTCS, 68. , 1st workshop on parallel and distributed model checking, affiliated to CONCUR 2002 (13th International Conference on Concurrency Theory), Brno, Czech Republic
  • Braberman, V., Olivero, A., Schapachnik, F., Issues in distributed model-checking of timed automata: Building ZEUS (2004) Int J Softw Tools Technol Transf P. Online First
  • Braberman, V., Olivero, A., Schapachnik, F., On-the-fly workload prediction and redistribution in the distributed timed model checker ZEUS (2004) 3rd International Workshop on Parallel and Distributed Methods in Verification, , Affiliated to CONCUR 2004 (15th International Conference on Concurrency Theory London, UK
  • Cousot, P., (1978) Methodes Iteratives de Construction et D'Aptoximation de Points Fixes D'Operateurs Monotones sur un Treillis, Analyse Semantique des Programmes, , Ph d. thesis, Université Scientifique et Médicale de Grenoble, Institut National Polytechnique de Grenoble
  • Daws, C., Yovine, S., Reducing the number of clock variables of timed automata (1996) Proceedings IEEE Real-Time Systems Symposium (RTSS '96), pp. 73-81
  • Dill, D.L., Timing assumptions and verification of finite-state concurrent systems (1990) LNCS, 407, pp. 197-212. , International workshop of automatic verification methods for finite state systems, Grenoble, France
  • Garavel, H., Mateescu, R., Smarandache, I.M., Parallel state space construction for model-checking (2001) Proc. of the 8th International SPIN Workshop, pp. 217-234. , Dwyer MB (ed) Toronto, Canada
  • Grumberg, O., Heyman, T., Schuster, A., Distributed symbolic model checking for μ.-calculus (2001) Computer Aided Verification, pp. 350-362
  • Heljanko, K., Khomenko, V., Koutny, M., Parallelisation of the petri net unfolding algorithm (2002) Tools and Algorithms for Construction and Analysis of Systems (TACAS '02), pp. 371-385
  • Henzinger, T.A., Nicollin, X., Sifakis, J., Yovine, S., Symbolic model checking for real-time systems (1994) Inform Comput, 111 (2), pp. 193-244
  • Heyman, T., Geist, D., Grumberg, O., Schuster, A., Achieving scalability in parallel reachability analysis of very large circuits (2002) Form Meth Syst des, 21 (2), pp. 317-338
  • Krcal, P., Distributed explicit bounded LTL model checking (2003) ENTCS, 89. , Brim L, Grumberg O (eds) Electronic notes in theoretical computer science
  • Lerda, F., Sisto, R., Distributed-memory model checking with SPIN (1999) LNCS, 1680. , Proc. of the 5th International SPIN Workshop
  • Nicol, D.M., Ciardo, G., Automated parallelization of discrete state-space generation (1997) J Parallel Distr Comp, 47 (2), pp. 153-167
  • Pnueli, A., Extracting controllers for timed automata (2005) Technical Report, , Department of Computer Science, Weizmann Institute of Science
  • Ranjan, R., Sanghavi, J., Brayton, R., Sangiovanni-Vincentelli, A., Binary decision diagrams on network of workstations (1996) International Conference on Computer Design, pp. 358-364
  • Schapachnik, F., (2002) Distributed and Parallel Verification of Real-time Systems, , Degree thesis, Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires
  • Schloegel, K., Karypis, G., Kumar, V., A unified algorithm for load-balancing adaptive scientific simulations (2000) Technical Report, , University of Minnesota, Department of Computer Science/US Army HPC Research Center. Minneapolis, USA
  • Stern, U., Dill, D.L., Parallelizing the Murφ verifier (1997) LNCS, 1254, pp. 256-278. , Computer aided verification

Citas:

---------- APA ----------
Braberman, V., Olivero, A. & Schapachnik, F. (2006) . Dealing with practical limitations of distributed timed model checking for timed automata. Formal Methods in System Design, 29(2), 197-214.
http://dx.doi.org/10.1007/s10703-006-0012-3
---------- CHICAGO ----------
Braberman, V., Olivero, A., Schapachnik, F. "Dealing with practical limitations of distributed timed model checking for timed automata" . Formal Methods in System Design 29, no. 2 (2006) : 197-214.
http://dx.doi.org/10.1007/s10703-006-0012-3
---------- MLA ----------
Braberman, V., Olivero, A., Schapachnik, F. "Dealing with practical limitations of distributed timed model checking for timed automata" . Formal Methods in System Design, vol. 29, no. 2, 2006, pp. 197-214.
http://dx.doi.org/10.1007/s10703-006-0012-3
---------- VANCOUVER ----------
Braberman, V., Olivero, A., Schapachnik, F. Dealing with practical limitations of distributed timed model checking for timed automata. Formal Methods Syst Des. 2006;29(2):197-214.
http://dx.doi.org/10.1007/s10703-006-0012-3