Selected Publications
1999
- D. Latella, I. Majzik, M. Massink:
Automatic Verification of a Behavioural Subset of UML
Statechart Diagrams Using the SPIN Model-checker
Formal Aspects of Computing, Volume 11 Issue 6 (Springer Verlag)
pp 637-664, 1999
Statechart Diagrams provide a graphical notation for describing dynamic aspects
of system behaviour within the Unified Modelling Language (UML). In this paper
we present a translation from a subset of UML Statechart Diagrams - covering
essential aspects of both concurrent behaviour, like sequentialisation, parallelism,
non-determinism and priority, and state refinement - into PROMELA, the specification
language of the SPIN model checker. SPIN is one of the most advanced analysis
and verification tools available nowadays. Our translation allows the automatic
verification of UML Statechart Diagrams. The translation is simple, proven
correct, and promising in terms of state space representation efficiency.
- D. Latella, I. Majzik and M. Massink:
Towards a Formal Operational Semantics of UML
Statechart Diagrams
Proc. FMOODS'99, the Third IFIP International Conference on Formal Methods
for Open Object-based Distributed Systems, Firenze, Italy
pp 331-347, February 1999
Statechart Diagrams are the core behavioral part of UML, the Unified Modeling
Language of object-oriented systems. UML is a semi-formal language,
with a precisely defined syntax and static semantics but with an only
informally specified dynamic semantics. UML Statechart Diagrams
differ from classical, Harel Statecharts, for which some formalizations
and results are available in the literature. This paper sets the
basis for the development of a formal semantics for UML Statechart Diagrams
based on Kripke structures. This forms the first step towards model checking
of UML Statechart Diagrams. We follow the approach proposed by Mikk
and others: we first map Statechart Diagrams to the intermediate format
of extended hierarchical automata and then we define an operational semantics
for extended hierarchical automata. We prove a number of properties of
such semantics which reflect the design choices of UML Statechart Diagrams.
- A. Bondavalli, I. Majzik and I. Mura:
Automated Dependability Analysis of UML Designs
Proc. ISORC'99, the 2nd IEEE International Symposium on Object-oriented Real-time
Distributed Computing, May 2-5, Saint Malo, France
pp 139-144, 1999
This paper deals with the automatic dependability analysis of systems designed
using UML. An automatic transformations is defined for the generation of
models to capture systems dependability attributes, like reliability. The
transformation concentrates on structural UML views, available early in
the design, to operate at different levels of refinement, and tries to capture
only the information relevant for dependability to limit the size (state
space) of the models. Due to the modular construction, these models can
be refined later as more detailed, relevant information becomes available.
Moreover a careful selection of those, critical, parts to be detailed allows
to avoid explosion of the size. An implementation of the transformation
is in progress and will be integrated in the toolsets available for the
ESPRIT LTR HIDE project.
- I. Majzik, J. Jávorszky, A. Pataricza and E. Selényi:
Concurrent Error Detection of Program Execution Based
on Statechart Specification
Proc. EWDC-10, the 10th European Workshop on Dependable Computing, May 6-7,
Vienna, Austria
pp 181-185, 1999
In common procedural and object-oriented programming languages the control
flow of a program is a hierarchical structure. Concurrent error detectors
proposed in previous works were able to check the sequence of statements
in procedures and the procedure return addresses, but the problem of checking
the allowed sequence of procedure calls and inter-process synchronization
remained unsolved. In this paper we propose an approach of checking the
higher-level program control flow using reference information based on UML
statechart specification.
- A. Bondavalli, I. Majzik and I. Mura:
Automatic Dependability Analysis for Supporting Design
Decisions in UML
Proc. HASE'99, the Fourth IEEE International High-Assurance Systems Engineering
Symposium
pp 64-71, 1999
Even though a thorough system specification improves the quality of the design,
it is not sufficient to guarantee that a system will satisfy its reliability
targets. Within this paper, we present an application example of one of the
activities performed in the European ESPRIT project HIDE, aiming at the creation
of an integrated environment where design toolsets based on UML are augmented
with modeling and analysis tools for the automatic validation of the system
under design. We apply an automatic transformation from UML diagrams to Timed
Petri Nets for model based dependability evaluation. It allows a designer
to use UML as a front-end for the specification of both the system and the
user requirements, and to evaluate dependability figures of the system since
the early phases of the design, thus obtaining precious clues for design refinement.
The transformation completely hides the mathematical background, thus eliminating
the need for a specific expertise in abstract mathematics and the tedious
remodeling of the system for mathematical analysis.
- M. Dal Cin, Huszerl G. and K. Kosmidis:
Quantitative Evaluation of Dependability Critical Systems
Based on Guarded Statechart Models
In Proc. HASE'99, Fourth IEEE Int. Symposium on High Assurance Systems Engineering
pp. 37-45., Washington DC Metropolitan Area, USA, November 17-19. 1999
The paper introduces a method to model embedded dependability-critical systems
as AND-composition of Guarded Statecharts which are special UML-statecharts.
With Guarded Statecharts we can model the reactive behavior of embedded systems
so that their quantitative analysis can be performed. First, we present our
motivation for using Guarded Statecharts to express the interaction between
hardware and software components of embedded systems, and to model faults
and errors as state perturbations. Then we discuss how these models are transformed
into Stochastic Reward Nets amenable to a quantitative dependability analysis.
Finally, our approach is illustrated by an example.
- M. Dal Cin, Huszerl G. and K. Kosmidis:
Transformation of Guarded Statecharts for Quantitative
Evaluation of Dependable Embedded systems
In P. Puschner(ed.): Proc. of EWDC-10, 10th European Workshop on Dependable
Computing (ISBN 3-85403-125-4), pp. 143-147., Vienna, Austria, Österreichische
Computer Gesellschaft, May 6-7. 1999
We propose a modelling and an evaluation technique for the validation of the
dependability of distributed systems such as networked embedded systems that
consist of autonomous loosely coupled nodes. The approach is based on the
Guarded Statecharts and on a transformation of them to models amenable to
a quantitative evaluation, in particular, to Generalized Stochastic Petri
Nets. It permits to compound a new modelling technique with proven evaluation
tools.
- A. Petri, A. Pataricza, E. Selenyi:
Behavioural VHDL Description Based Synthesis of Self-Checking
Circuits
Proceedings the EWDC-10 conference, May 1999, Vienna, Austria, pp. 135-139.
This paper demonstrates an experimental implementation of a design method
for embedding fault tolerance capabilities into high level digital system
models. The method starts with a standardized behavioural level system description
and systematically transforms it to an implementation-level circuit design
with fault tolerant parts built in. The transformation process aims to keep
the changes made in the model transparent from the viewpoint of the designer,
in order to maintain compatibility between the original system model and
to minimize the manual interaction needed to implement fault tolerance.
1998
- Gy. Csertán, I. Majzik, A. Pataricza and S. C. Allmaier:
Reachability Analysis of Petri-nets by FPGA Based
Accelerators
Proceedings of DDECS98, Design and Diagnostics of Electronic Circuits and
Systems Workshop, Szczyrk, Poland
pp 307-312, September 1998
The application of an FPGA-based accelerator for reachability analysis of
Petri nets (PN) is presented. Since the simple components of the PN can
be easily realized in high-density FPGAs, the complete problem can be mapped
to silicon providing a solution environment faster than the traditional
software-based simulators.
- Gy. Csertán, I. Majzik, A. Pataricza, S. C. Allmaier and W. Hohl:
Hardware Accelerators for Petri-net Analysis
Proceedings of DAPSYS'98, the Austrian-Hungarian Workshop on Distributed and
Parallel Systems, Budapest, Hungary
pp 99-104, September 1998
For reachability analysis of Petri-nets an FPGA-based accelerator is proposed.
Since the simple components of Petri-nets can be easily realized in high-density
FPGAs, the complete problem can be mapped to silicon providing a solution
environment faster than the traditional software-based simulators. Some classes
of Petri-nets support the compositional analysis, this way the limited capacity
of the FPGA does not prevent the investigation of real-life problems.
1997
- C. Bernardeschi, A. Bondavalli, Gy. Csertán, I. Majzik and L. Simoncini:
Temporal Analysis of Data Flow Control Systems
Automatica - The Journal of the International Federation of Automatic Control
(IFAC), Vol. 38, No. 2,
pp 169-182, 1997
Due to their distributed/parallel and data-driven nature, control systems
can easily be modeled according to a data flow approach. Control systems are
very often real-time systems therefore a formalism able to capture timing
is required. In this paper we introduce a data flow model that includes
time and priority for specifying real-time control systems and we give its
formal semantics. The control system is specified by a data flow network
which, beside the controller, may include the model of the plant at some abstraction
level. Time is associated to any computational activity and time accounting
is made directly in the model and not as a separate issue. Priorities
allow to deal with events, as alarm signals, which cannot be delayed.
A general framework for the indirect evaluation of the model is introduced,
and a data flow network to timed Petri net transformation is defined allowing
the utilization of the automatic tools of Petri nets for analyzing the temporal
properties of the data flow network. The approach is illustrated by an example
in which, after the application of the transformation, selected performance
measures are computed.
1996
- Gy. Csertán:
System Diagnostics in HW-SW Codesign
In B. Straube and J. Schönherr, editors, Proceedings of the 4th GI/ITG/GME
Workshop,
pages 51-60, March Kreischa, Germany, 1996.
In this paper a novel approach is presented, which can successfully be used
for the underlying hierarchical modeling of HW-SW codesign during the whole
design cycle. This new method combines the conventional, performability evaluation
oriented description of the functional units of the system with the description
of fault effects and error propagation. Various dependability measures can
be extracted from the extended system model. This work deals with diagnostic
design, that is the iterative process of model construction, test generation,
concurrent fault simulation and integrated diagnostics. The result is an optimized,
ordered test set of the system.
- Gy. Csertán, A. Pataricza, and E. Selényi:
Design for Testability with HW-SW Codesign
Periodica Polytechnica, 40(1):25-37, 1996.
Current trends in the development of design automation tools aim at a radical
increase in productivity by o ering highly automated design tools. As applications
include even critical control applications, dependability becomes to an important
design issue. A novel approach supporting concurrent diagnostic engineering
using a data flow behavioral description is presented in this paper. The basic
idea of this new method is the extension of the descriptions of the functional
elements with the models of fault effects and fault propagation at each level
of the hardware-software codesign hierarchy, thus allowing design for testability
of digital computing systems. Using the presented approach test generation can
be done concurrently with the system design and not only in the back-end design
phase as it had been done previously. For test generation purposes the generalized
forms of the well known logic gate level test design algorithms can be used.
- Majzik, I.; Hohl, W.; Pataricza, A.; Sieh, W.:
Multiprocessor Checking Using Watchdog Processors
International Journal of Computer Systems - Science & Engineering, Vol.
11, No. 5,
pp 123-132, 1996
A new control flow checking scheme is presented, based on assigned-signature
checking using a watchdog processor. This scheme is suitable for a multitasking,
multiprocessor environment. The hardware overhead is comparatively low because
of three reasons: first, hierarchically structured, the scheme uses only a single
watchdog processor to monitor multiple processes on multiple processors. Second,
as an assigned-signature scheme, it does not require monitoring the instruction
bus of the processors. Third, the run-time and reference signatures are embedded
into the checked program; thus, in the watchdog processor neither a reference
database nor a time-consuming search and compare engine is required.
- Majzik, I.:
Software Diagnosis Using Compressed Signature Sequences
(Technical Conference on Computer Aided Methods and Technical Management in
Electrical Engineering Education TEMPUS JEP 3815, June 1995, Technical University
Budapest, Hungary, 1995)
Periodica Polytechnica Ser. Electrical Engineering, Vol. 40, No. 2,
pp 87-103, 1996
Software diagnosis can be effectively supported by one of the concurrent error
detection methods, the application of watchdog processors (WP). A WP, as a coprocessor,
receives and evaluates signatures assigned to the states of the program execution.
After the checking, the watchdog stores the run-time sequence of signatures
which identify the statements of the program. In this way, a trace of the statements
executed before the error is available. The signature buffer can be effectively
utilized if the signature sequence is compressed. In the paper, two real-time
compression methods are presented and compared. The general method uses predefined
dictionaries, while the other one utilizes the structural information encoded
in the signatures.
- Majzik, I.:
Software Monitoring and Debugging Using Compressed
Signature Sequences
Proc. of the 22nd Euromicro Conference (Prague, Czech Republic),
pp. 311-318, 1996
Signature based error detection techniques (e.g. the application of watchdog
processors) can be easily extended to support software debugging. The run-time
sequence of signatures is stored in an extension of the traditional checker.
As the signatures identify the states of the program, a trace of the statements
executed by the checked processor is available. The signature buffer can
be efficiently utilized if the signature sequence is compressed. In the
paper, two real-time compression methods are presented and compared. The
general method uses predefined dictionaries, while the other one utilizes
the structural information encoded in the signatures.
- Antal, B.; Bondavalli, A.; Csertán, Gy.; Majzik, I.; Simoncini,
L.:
Reachability and Timing Analysis in Data Flow Networks:
A Case Study
Proc. of the 22nd Euromicro Conference (Prague, Czech Republic),
pp. 193-200, 1996
The need of efficient implementation, safety and performance requires early
validation in the design of computer control systems. The detailed timing
and reachability analysis in the development process is particularly important
if we design equipments or algorithms of high performance and availability.
In this paper we present a case study related to the early validation of control
systems modeled by data flow networks. The model is validated indirectly as
it is transformed to Petri nets in order to be able to utilize the tools available
for Petri nets.
- A. Petri, P. Urbán, J. Altmann, M. Dal Cin, E. Selényi, K.
Tilly, A. Pataricza:
Constraint-Based Diagnosis Algorithms for
Multiprocessors
Periodica Polytechnica Ser. El. Eng., Vol. 40, No. 1, pp. 39-52.
In the latest years, new ideas appeared in system level diagnosis of multiprocessor
systems. In contrary to the traditional diagnosis models (like PMC,
BGM etc.) which use strictly graph-oriented methods to determine the faulty
components in a system, these new theories prefer AI-based algorithms, especially
CSP methods. Syndrome decoding, the basic problem of self-diagnosis,
can be easily transformed into constraints between the state of the tester
and the tested components. Therefore, the diagnosis algorithm can be derived
from a special constraint solving algorithm. The "benign" nature of the
constraints (all their variables, representing the fault states of the components,
have a very limited domain; the constraints are simple and similar to each
other) reduces the algorithm's complexity so it can be converted to a powerful
distributed diagnosis method with a minimal overhead. Experimental algorithms
(using both centralized and distributed approach) were implemented for a
Parsytec GC massively parallel multiprocessor system.
- B. Sallay, A. Petri, K. Tilly, A. Pataricza, J. Sziray:
High Level Test Pattern Generation for VHDL Circuits
Proceedings of the IEEE European Test Workshop '96, June 1996, Montpellier,
pp. 201-205.
This paper presents a new approach that uses functional level circuit descriptions
as a basis for automatic test pattern generation (ATPG). The VHDL model of
the circuit is transformed into a constraint network, and the ATPG problem
is solved as a constraint satisfaction problem. Techniques and heuristic methods
for the acceleration of the search are also examined.
- J. Altmann, T. Bartha, A. Pataricza, A. Petri, P. Urbán:
Constraint Based System-Level Diagnosis of Multiprocessors
Proc. of the EDCC-2 Conference, pp. 403-420, 1996.
The paper presents a novel modelling technique for system-level fault diagnosis
in massive parallel multiprocessors, based on a re-formulation of the problem
of syndrome decoding to a constraint satisfaction problem (CSP). The CSP based
approach is able to handle detailed and inhomogeneous functional fault models
to a similar depth as the Russel-Kime model. Multiple-valued logic is used
to deal with system components having multiple fault modes. The granularity
of the models can be adjusted to the target diagnostic resolution without
altering the methodology. Two algorithms for the Parsytec GCel massively parallel
system are used as illustration in the paper: the centralized method uses
a detailed system model, and provides a fine-granular diagnostic image for
off-line evaluation. The distributed method makes fast decisions for reconfiguration
control, using a simplified model.
- T. Bartha:
Effective Approximate Fault Diagnosis of Systems
with Inhomogeneous Test Invalidation
Proc. of the 22nd Euromicro Conference, pp. 379-386, 1996.
Abstract: System-level fault diagnosis is a methodology to identify the failed
components in a multiprocessor system. The traditional approach to system-level
diagnosis does not take into consideration many important aspects of modern
multiprocessor architectures. This paper examines a special class of multiprocessors,
called massively parallel computers. As a practical example, the Parsytec GCel
system is presented. The paper describes a new method developed for the Parsytec
GCel, called local information diagnosis. The diagnostic algorithm is based
on the generalized test invalidation model, therefore it is applicable to a
wide range of systems, including inhomogeneous ones. Due to the employed syndrome
decoding mechanism, the space and computational complexity of the algorithm
is also smaller than in conventional methods.
- Tamás Bartha, Endre Selényi:
Efficient Algorithms for System Level Diagnosis
of Multiprocessors Using Local Information
Proc. of the DAPSYS'96 Austrian-Hungarian Workshop, pp. 183-190, 1996.
Abstract: Massively parallel computers introduce new requirements for system-level
fault diagnosis, like handling a huge number of processing elements in an
inhomogeneous system. They also have specific attributes, such as regular
topology and low local complexity. Traditional deterministic methods of system-level
diagnosis did not consider these issues. This paper presents a new approach,
called local information diagnosis that exploits the characteristics of massively
parallel systems. The paper defines the diagnostic model, which is based on
generalized test invalidation to handle inhomogeneity in multiprocessors.
Five effective probabilistic diagnostic algorithms using the proposed method
are also given, and their space and time complexity is estimated.
Keywords: massively parallel systems, regular interconnection structure, system-level
diagnosis, inhomogeneous systems, generalized test invalidation
1995
- Gy. Csertán, A. Pataricza, and E. Selényi:
Dependability Analysis in HW-SW codesign
Proceedings of the IEEE International Computer Performance and Dependability
Symposium, IPDS'95,
pages 316-325, April Erlangen, Germany, 1995.
The increasing complexity of todays computing systems necessitates new design
methodologies. One of the most promising methods is hardware-software codesign,
that supports unified hardware-software modeling at different levels of abstraction,
and hardware-software synthesis. As applications include even critical applications,
dependability becomes to an important design issue. A novel approach for the
underlying modeling in hardware-software codesign is presented in this paper.
The basic idea of this new method is the extension of the descriptions of the
functional elements with the models of fault effects and error propagation at
each level of the hardware-software codesign hierarchy. From the extended system
model various dependability measures can be extracted. This paper concerns test
generation, solved by a generalized form of the well-known logic gate level
test generation algorithms and extraction of the input model of integrated diagnostics,
allowing testability and diagnosability analysis of the system.
- I. Turcsány, Gy. Csertán, and A. Pataricza:
Model Based Diagnostic-Test Scheduling
Proceedings of the Technical Conference on CAD Methods in Electronic and Information
Processing System Design and its Education, pages 27-30, June Budapest, Hungary,
1995.
- Majzik, I.; Pataricza, A.:
Control Flow Checking in Multitasking Systems
(Technical Conference on Computer Aided Methods and Technical Management in
Electrical Engineering Education, TEMPUS JEP 3815, June 9-10, 1994, Technical
University Budapest, Hungary, 1994)
Periodica Polytechnica Ser. Electrical Engineering, Vol. 39, No. 1,
pp. 27-36, 1995
The control flow checking technique presented in our paper is based on the new
watchdog-processor method SEIS (Signature Encoded Instruction Stream). This
method is intended to check the still uncovered area of state-of-the-art microprocessors
using on-chip caches or instruction pipelines, since the processor instruction
bus needs not be monitored. The control flow is checked using assigned actual
signatures and embedded reference signatures. Since the actual and reference
signatures are embedded in the checked program, the usual reference database
and the time-consuming search/compare engine in the WP can be omitted. The evaluation
of the actual signature is a simple combinatorial task allowing high speed and
thus the sharing of the WP between different tasks and processors. The checking
method has been extended to higher levels of the application like simultaneous
check of different processes and their synchronization in multitasking systems.
- J. Altmann, T. Bartha, A. Pataricza:
On Integrating Error Detection into a Fault Diagnosis
Algorithm For Massively Parallel Computers
Proc. of IEEE IPDS'95 Symposium, pp. 154-164, 1995.
Abstract: Scalable fault diagnosis is necessary for constructing fault tolerance
mechanisms in large massively parallel multiprocessor systems. The diagnosis
algorithm must operate efficiently even if the system consists of several
thousand processors. In this paper we introduce an event-driven, distributed
system-level diagnosis algorithm. It uses a small number of messages and is
based on a general diagnosis model without the limitation of the number of
simultaneously existing faults (an important requirement for massively parallel
computers). The algorithm integrates both error detection techniques like
"I'm alive" messages, and built in hardware mechanisms. The structure of the
implemented algorithm is presented, and the essential program modules are
described. The paper also discusses the use of test results generated by error
detection mechanisms for fault localization. Measurement results illustrate
the effect of the diagnosis algorithm, in particular the error detection mechanism
by "I'm alive" messages, on the application performance.
Keywords: Error detection, distributed diagnosis, syndrome decoding, massively
parallel systems
1994
- Gy. Csertán, C. Bernardeschi, A. Bondavalli, and L. Simoncini:
Timing Analysis of Dataflow Networks
Proceedings of the 12th IFAC Workshop on Distributed Computer Control Systems,
DCCS'94,
pages 153-158, September Toledo, Spain, 1994.
This paper investigates the analysis of temporal properties of control systems
modelled using the data flow computational paradigm. A transformation from data
flow networks to timed Petri nets is defined. It preserves temporal properties
and allows, through the analysis of the Petri net, the indirect evaluation of
the properties of the data flow network. The paper contains an example for explaining
the transformation and showing which kind of analyses can be performed.
- Gy. Csertán, J. Güthoff, A. Pataricza, and R. Thebis:
Modeling of Fault-Tolerant Computing Systems
Proceedings of the 8th Symposium on Microcomputers and Applications, uP'94,
pages 95-108, October Budapest, Hungary, 1994.
Typical after design activities, such as reliability and performability evaluation,
diagnostic development should be integrated into the design cycle of fault-tolerant
computing systems in order to increase its effectiveness. A novel framework
of various evaluation tools is presented in this paper, sharing a common input
model, the high level behavioral description of the system. The data flow computational
paradigm is used for this reason supporting both uninterpreted and interpreted
modeling in a hierarchical way during the whole design cycle. According to this
approach system design is a cyclic process, in which the system engineer stepwise
refines and optimizes the system.
- Majzik, I.; Pataricza, A.; Dal Cin, M.; Hohl, W.; Hönig, J.; Sieh,
V.:
Hierarchical Checking of Multiprocessors Using Watchdog
Processors
In K. Echtle, D. Hammer, D. Powell (Eds.): Dependable Computing - EDCC-1 (Proceedings
of the First European Dependable Computing Conference, Berlin, Germany, October
1994), Lecture Notes in Computer Science 852, Springer Verlag, Berlin Heidelberg,
pp. 386-403, 1994
A new control flow checking scheme, based on assigned-signature checking by
a watchdog processor, is presented. This scheme is suitable for a multitasking,
multiprocessor environment. The hardware overhead is comparatively low because
of three reasons: first, hierarchically structured, the scheme uses only a
single watchdog processor to monitor multiple processes or processors. Second,
as an assigned-signature scheme it does not require monitoring the instruction
bus of the processors. Third, the run-time and reference signatures are embedded
into the checked program; thus, in the watchdog processor neither a reference
database nor a time-consuming search and compare engine is required.
- A. Pataricza, K. Tilly, E. Selenyi, M. Dal Cin, A. Petri:
A Constraint-based Algorithm for Distributed System-level
Diagnosis
Proceedings of the 8th Symposium on Microcomputer and Microprocessor Applications
(uP '94),
1994, TUB Budapest. Vol. I, pp. 74-83.
In the latest years, new ideas appeared in system level diagnosis. Contrary
to the traditional diagnosis models (like PMC, BGM etc.) which use strictly
graph-oriented methods to determine the faulty components in a system, these
new theories prefer AI-based algorithms, especially CSP methods. Syndrome
decoding, the basic problem of self diagnosis, can be easily transformed
to constraints between the state of the tester and the tested components,
considering the test results. Therefore, the diagnosis algorithm can be
derived from a special constraint solving algorithm. The "benign" nature
of the constraints (all their variables, representing the fault states of
the components, have a very limited domain; the constraints are simple and
similar to each other) reduces the algorithm's complexity so it can be converted
to a powerful distributed diagnosis method with a minimal overhead. An experimental
algorithm was implemented for a Parsytec GC tightly coupled multiprocessor
system.
- Jörn Altmann, Tamás Bartha, András Pataricza:
An Event-driven Approach to Multiprocessor Diagnosis
Proc. of 8th Symp. on Microprocessor and Microcomputer Applications (uP'94), vol.
1, pp. 109-118, 1994.
Abstract: For constructing fault tolerance mechanisms in large massively parallel
multiprocessor systems, a scalable fault diagnosis is necessary, which works
efficiently even if there are several thousand processors in the system. In
this paper we present an event-driven, distributed system-level diagnosis algorithm,
based on a general diagnosis model which does not limit the number of simultaneously
existing faults. In particular, the relation between error detection and fault
localization as well as two different methods for distributing diagnostic information
are examined in detail. Furthermore, we give measurements concerning how does
our diagnosis algorithm affect application performance.
1993
- Pataricza, A.; Majzik, I.; Hohl, W.; Hönig, J.:
Watchdog Processors in Parallel Systems
(Proc. Euromicro'93, 19th Symposium on Microprocessing and Microprogramming,
Barcelona, 1993)
Microprocessing and Microprogramming Vol. 39,
pp. 69-74, 1993
A watchdog processor (WDP) is a relatively simple coprocessor built for concurrent,
information compaction based error detection in the main program control flow.
A new algorithm called SEIS (Signature Encoded Instruction Stream) is presented
for assigning signatures to high-level instructions. The main idea of this
method is to embed the information necessary to the program flow check into
the signatures themselves, thus avoiding large reference databases in the
WDP and allowing high operational speed. Solutions for a fault-tolerant multiprocessing
and multi-tasking implementation are described as well.
Selected Project Reports
W. Hohl:
HIDE - First Phase Project Overview
ESPRIT Project 27439 (HIDE) Final Project Report
A. Bondavalli, A. Borschet, M. Dal Cin, W. Hohl, D. Latella, I. Majzik,
M. Massink, I. Mura:
Specification of Modeling Techniques
ESPRIT Project 27439 (HIDE) Deliverable 1 (HIDE/D1/FAU/1/v3)
Abstract: This document examines certain aspects of the Unified
Modeling Language (UML) relevant to the HIDE framework. The examination is
necessary in order to provide a sound basis for a translation of UML-models
to models amenable for formal and quantitative analysis. On one side, restrictions
of the modeling power of UML are to be identified such that precise transformations
become feasible. These restrictions will be relaxed in the future. On the
other side, model analysis requires certain extensions to the UML, since additional
information is needed depending on the kind of analysis someone wants to perform.
A. Bondavalli, M. Dal Cin, G. Huszerl, K. Kosmidis, D. Latella, I. Majzik,
M. Massink, I. Mura:
Transformations - Report on the Specification
of Analysis and Transformation Techniques
ESPRIT Project 27439 (HIDE) Deliverable 2 (HIDE/T1.2/PDCC/30/v1)
Abstract: The quantitative analysis of the dependability attributes
of computer systems using stochastic modelling is a process that requires
ability and experience. Building the model of a system needs the introduction
of assumptions, simplifications and abstractions, whose impact on the final
results can not be estimated a priori. Also, slight variations in the value
of a crucial parameter might cause dramatic changes in the final measures.
Moreover, real systems show such a complexity that the definition of the model
itself easily becomes an error prone task. Various methods and tools for dependability
modelling and analysis have been developed which provide support to the analyst,
during the phases of definition and evaluation of the models. In general,
model types used for dependability analysis are in two categories; combinatorial
and state-space. In the list below, Markov models and high level approaches
which have an underlying Markov model are belonging to state-space models.
A. Borschet, M. Dal Cin, J. Jávorszky, A. Pataricza, G. Savoia,
Cs. Szász:
Specification of the HIDE Environment
ESPRIT Project 27439 (HIDE) Deliverable 3 (HIDE/D3/TUB/1/v2)
Abstract: The aim of this deliverable is the definition of the HIDE
architecture in a form which can be used without major alteration for both
phases. However, the implementation could differ for the two phases. The primary
target of Phase 1 is the definition of a prototyping environment, in consideration
of the assurance of a high level of flexibility and of a good support for
debugging of the algorithms to be implemented. In this phase, both the efficient
use of the resources and the time requirements of the transformations are
of secondary importance. Accordingly, this implementation should rely, as
far as possible, on commercially available tools, not necessary incorporated
into the final HIDE tool.
A. Bondavalli, M. Dal Cin, E. Giusti, D. Latella, I. Majzik, M. Massink,
I. Mura:
Assessment of Analysis and Transformation
Techniques
ESPRIT Project 27439 (HIDE) Deliverable 4 (HIDE/D4/FAU/1/v1.1)
Abstract: The primary aim of this deliverable is the collection
of experiences related to the size of the models resulting from automatic
transformations and the production of a comparison with hand-made models for
the same systems.
Gy. Csertán, M. Dal Cin, G. Huszerl, J. Jávorszky, K. Kosmidis,
A. Pataricza, Cs. Szász:
The Demonstrator
ESPRIT Project 27439 (HIDE) Deliverable 5 (HIDE/D5/TUB/1/v2)
Abstract: In this paper the HIDE core technology is presented according
to the definition elaborated in work phase 2. In phase 2 many new features
have to be implemented which are missing in the first phase, like fault-tolerant
component library, fault-injection engine, back-annotation. If we propose
for the next phase the technology used in the first, then we must investigate
its capability to handle the new features.
G. Savoia:
Specification of the Pilot Application
(Automatic Train Control System)
ESPRIT Project 27439 (HIDE) Final Project Report
Abstract: This document contains the initial specification of a
system which will be used in the second phase of the HIDE project as a pilot
application for experimenting and assessing the modelling and analysis techniques
that the project is developing. The selected system is an Automatic Train
Control (ATC) system which is an onboard control system for the new generation
of trains for the Italian railroad system. The ATC is currently in production
by Ansaldo, and for which Intecs Sistemi has a significant involvement in
the design and the implementation of the Basic Software. The system has significant
dependability requirements in terms of availability, fault tolerance and predictability.
To meet these requirements it exploits state of the art solutions both in
its hardware and software architecture, as replicated communication bus, duplicated
processing nodes and replicated subsystems.