Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this work we present the on-the-fly workload prediction and redistribution techniques used in Zeus [12, 13], a Distributed Model Checker that evolves from the tool Kronos [14]. After reviewing why it is so hard to have good speedups in distributed timed model checking, we present the methods used to get promising results when verifying reachability properties over timed automata [3]. © 2005 Elsevier B.V.

Registro:

Documento: Artículo
Título:On-the-fly workload prediction and redistribution in the distributed timed model checker zeus
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:Distributed Timed Model Checking; Kronos; Load-Balance; Prediction; Reachability; Reconfiguration; Redistribution; Timed Automata; Zeus; Algorithms; Automata theory; Computer workstations; Data storage equipment; Mathematical models; Program processors; Distributed timed model checking; KRONOS; Load-balance; Prediction; Reachability; Reconfiguration; Redistribution; Timed automata; ZEUS; Distributed computer systems
Año:2005
Volumen:128
Número:3
Página de inicio:3
Página de fin:18
DOI: http://dx.doi.org/10.1016/j.entcs.2004.10.015
Título revista:Proceedings of the 3rd International Workshop on Parallel Distributed Methods in Verification (PDMC 2004)
Título revista abreviado:Electron. Notes Theor. Comput. Sci.
ISSN:15710661
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_15710661_v128_n3_p3_Braberman.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710661_v128_n3_p3_Braberman

Referencias:

  • Alur, R., Courcoubetis, C., Dill, D., Halbwachs, N., Wong-Toi, H., 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) Information and Computation, 104, pp. 2-34
  • Alur, R., Dill, D.L., A theory of timed automata (1994) Theoretical Computer Science, 126, pp. 183-235
  • Barnat, J., Brim, L., Stríbřná, J., Distributed LTL model-checking in SPIN (2001) SPIN, pp. 200-216
  • Behrmann, G., A performance study of distributed timed automata reachability analysis (2002) ENTCS, 68. , Workshop on Parallel and Distributed Model Checking, afiliated to CONCUR 2002 (13th International Conference on Concurrency Theory)
  • 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
  • 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)
  • Braberman, V., (2000) Modeling and Checking Real-time Systems Designs, , Ph d. thesis, Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires
  • Braberman, V., Garbervetsky, D., Olivero, A., Improving the verification of timed systems using influence information (2002) LNCS, 2280, pp. 21-36. , TACAS 2002, Held As Part of the Joint European Conference on Theory and Practice of Software, ETAPS 2002
  • Braberman, V., López Pombo, C., Olivero, A., On improving backwards verification for timed automata (2002) ENTCS, 65. , TPTS 2002, Satellite Event for the Joint European Conference on Theory and Practice of Software, ETAPS 2002
  • Braberman, V., Olivero, A., Schapachnik, F., Zeus: A distributed timed model checker based on kronos (2002) ENTCS, 68. , Workshop on Parallel and Distributed Model Checking, Affiliated to CONCUR 2002 (13th International Conference on Concurrency Theory)
  • Braberman, V., Olivero, A., Schapachnik, F., Issues in Distributed Model-Checking of Timed Automata: Building zeus (2004) International Journal of Software Tools for Technology Transfer
  • Daws, C., Olivero, A., Tripakis, S., Yovine, S., The tool KRONOS (1996) LNCS, 1066, pp. 208-219. , Proceedings of Hybrid Systems III
  • 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
  • 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. , M. B. Dwyer, editor 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) Information and Computation, 111, pp. 193-244
  • Heyman, T., Geist, D., Grumberg, O., Schuster, A., Achieving scalability in parallel reachability analysis of very large circuits (2002) Formal Methods in System Design, 21, pp. 317-338
  • Karypis, G., Kumar, V., Parallel multilevel k-way partitioning scheme for irregular graphs (1998) Technical Report, , University of Minnesota, Department of Computer Science / US Army HPC Research Center. Minneapolis, USA
  • Krcal, P., Distributed explicit bounded LTL model checking (2003) ENTCS, 89. , L. Brim O. Grumberg, 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., Ciardo, G., Automated parallelization of discrete state-space generation (1997) Journal of Parallel and Distributed Computing, 47, pp. 153-167
  • 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, , http://www.cvi.com.ar/zeus/tesis_schapachnik.ps.gz, 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
  • Wang, F., Efficient verification of timed automata with BDD-like data-structures (2003) LNCS, 2575, pp. 189-205. , L. Zuck P. Attie A. Cortesi S. Mukhopadhyay, Verification, Model Checking, and Abstract Interpretation: 4th International Conference, VMCAI

Citas:

---------- APA ----------
Braberman, V., Olivero, A. & Schapachnik, F. (2005) . On-the-fly workload prediction and redistribution in the distributed timed model checker zeus. Proceedings of the 3rd International Workshop on Parallel Distributed Methods in Verification (PDMC 2004), 128(3), 3-18.
http://dx.doi.org/10.1016/j.entcs.2004.10.015
---------- CHICAGO ----------
Braberman, V., Olivero, A., Schapachnik, F. "On-the-fly workload prediction and redistribution in the distributed timed model checker zeus" . Proceedings of the 3rd International Workshop on Parallel Distributed Methods in Verification (PDMC 2004) 128, no. 3 (2005) : 3-18.
http://dx.doi.org/10.1016/j.entcs.2004.10.015
---------- MLA ----------
Braberman, V., Olivero, A., Schapachnik, F. "On-the-fly workload prediction and redistribution in the distributed timed model checker zeus" . Proceedings of the 3rd International Workshop on Parallel Distributed Methods in Verification (PDMC 2004), vol. 128, no. 3, 2005, pp. 3-18.
http://dx.doi.org/10.1016/j.entcs.2004.10.015
---------- VANCOUVER ----------
Braberman, V., Olivero, A., Schapachnik, F. On-the-fly workload prediction and redistribution in the distributed timed model checker zeus. Electron. Notes Theor. Comput. Sci. 2005;128(3):3-18.
http://dx.doi.org/10.1016/j.entcs.2004.10.015