A Graph Transformation-Based Approach for the Validation of Checkpointing Algorithms in Distributed Systems
| Autor: | Alberto Calixto Simon, Saul E. Pomares Hernandez, Houda Khlif, Cédric Eichler, Ahmed Hadj Kacem, Hatem Hadj Kacem |
|---|---|
| Přispěvatelé: | Unité de Recherche en développement et contrôle d'applications distribuées (REDCAD), École Nationale d'Ingénieurs de Sfax | National School of Engineers of Sfax (ENIS), Équipe Services et Architectures pour Réseaux Avancés (LAAS-SARA), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Instituto Nacional de Astrofísica, Óptica y Electrónica (INAOE), Système d’exploitation, systèmes répartis, de l’intergiciel à l’architecture (IRIT-SEPIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Universidad del papaloapan (UNPA), Universidad del papaloapan, Centre National de la Recherche Scientifique - CNRS (FRANCE), Institut National Polytechnique de Toulouse - INPT (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), Instituto Nacional de Astrofísica, Óptica y Electrónica - INAOE (MEXICO), Universidad del Papaloapan - UNPA (MEXICO), Université de Sfax (TUNISIA), Laboratoire d'Analyse et d'Architecture des Systèmes - LAAS (Toulouse, France), Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3) |
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: |
Correctness
Computer science Distributed computing Système d'exploitation Autonomic computing Réseaux et télécommunications 0102 computer and information sciences 02 engineering and technology Distributed systems 01 natural sciences Graph transformation [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] Architectures Matérielles 020204 information systems 0202 electrical engineering electronic engineering information engineering Graph rewriting Causal graph Vector clock Happened before relation Systèmes embarqués Transformation (function) Z-cycles 010201 computation theory & mathematics Z-paths Algorithm design [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] Algorithm Checkpointing algorithms |
| Zdroj: | IEEE International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE 2014). IEEE International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE 2014)., Jun 2014, Parma, Italy. pp.80-85, ⟨10.1109/WETICE.2014.23⟩ WETICE |
| DOI: | 10.1109/WETICE.2014.23⟩ |
| Popis: | International audience; —Autonomic Computing Systems are oriented to pre-vente the human intervention and to enable distributed systems to manage themselves. One of their challenges is the efficient monitoring at runtime oriented to collect information from which the system can automatically repair itself in case of failure. Quasi-Synchronous Checkpointing is a well-known technique, which allows processes to recover in spite of failures. Based on this technique, several checkpointing algorithms have been developed. According to the checkpoint properties detected and ensured, they are classified into: Strictly Z-Path Free (SZPF), Z-Path Free (ZPF) and Z-Cycle Free (ZCF). In the literature, the simulation has been the method adopted for the performance evaluation of checkpointing algorithms. However, few works have been designed to validate their correctness. In this paper, we propose a validation approach based on graph transformation oriented to automatically detect the previous mentioned checkpointing properties. To achieve this, we take the vector clocks resulting from the algorithm execution, and we model it into a causal graph. Then, we design and use transformation rules oriented to verify if in such a causal graph, the algorithm is exempt from non desirable patterns, such as Z-paths or Z-cycles, according to the case. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|