mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
New Strategies for Ensuring Time and Value Correctness in Dependable Real-Time Systems
Mälardalen University, School of Innovation, Design and Engineering. (PROGRESS)ORCID iD: 0000-0001-5053-6725
2009 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Dependable real-time embedded systems are typically composed of a number of heterogeneous computing nodes, heterogeneous networks that connect them and tasks with multiple criticality levels allocated to the nodes. The heterogeneous nature of the hardware, results in a varying vulnerability to different types of hardware failures. For example, a computing node with effective shielding shows higher resistance to transient failures caused by environmental conditions such as radiation or temperature changes than an unshielded node. Similarly, resistance to permanent failures can vary depending on the manufacturing procedures used. Vulnerability to different types of errors of a task which may lead to a system failure, depends on several factors, such as the hardware on which the task runs and communicates, the software architecture and the implementation quality of the software, and varies from task to task. This variance, as well as the different criticality levels and real-time requirements of tasks, necessitate novel fault-tolerance approaches to be developed and used, in order to meet the stringent dependability requirements of resource-constrained real-time systems.

 

In this thesis, the major contribution is four-fold. Firstly, we describe an error classification for real-time embedded systems and address error propagation aspects. The goal of this work is to perform the analysis on a given system, in order to find bottlenecks in satisfying dependability requirements and to provide guidelines on the usage of appropriate error detection and fault tolerance mechanisms.

 

Secondly, we present a time-redundancy approach to provide a priori guarantees in fixed-priority scheduling (FPS) such that the system will be able to tolerate one value error per every critical task instance by re-execution of every critical task instance or execution of alternate tasks before deadlines, while keeping the associated costs minimized.

 

Our third contribution is a new approach, Voting on Time and Value (VTV) which extends the N-modular redundancy approach by explicitly considering both value and timing errors, such that correct value is produced at a correct time, under specified assumptions. We illustrate our voting approach by instantiating it in the context of the well-known triple modular redundancy (TMR) approach. Further, we present a generalized voting algorithm targeting NMR that enables a high degree of customization from the user perspective.

 

Finally, we propose a novel cascading redundancy approach within a generic fault tolerant scheduling framework. The proposed approach is capable of tolerating errors with a wider coverage (with respect to error frequency and error types) than our proposed time and space redundancy approaches in isolation, allows tasks with mixed criticality levels, is independent of the scheduling technique and, above all, ensures that every critical task instance can be feasibly replicated in both time and/or space. The fault-tolerance techniques presented in this thesis address various different error scenarios that can be observed in real-time embedded systems with respect to the types of errors and frequency of occurrence, and can be used to achieve the ultra-high levels of dependability which is required in many critical systems.

Place, publisher, year, edition, pages
Västerås: Mälardalens Högskola , 2009.
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 104
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:mdh:diva-5925ISBN: 978-91-86135-28-7 (print)OAI: oai:DiVA.org:mdh-5925DiVA: diva2:218099
Presentation
2009-06-11, Gamma, Västerås, 15:30 (English)
Opponent
Supervisors
Projects
PROGRESS
Available from: 2009-05-19 Created: 2009-05-19 Last updated: 2014-01-16Bibliographically approved
List of papers
1. Maximizing the Fault Tolerance Capability of Fixed Priority Schedules
Open this publication in new window or tab >>Maximizing the Fault Tolerance Capability of Fixed Priority Schedules
2008 (English)In: RTCSA 2008: 14TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS - PROCEEDINGS, 2008, 337-346 p.Conference paper, Published paper (Refereed)
Abstract [en]

Real-time systems typically have to satisfy complex requirements, mapped to the task attributes, eventually guaranteed by the underlying scheduler. These systems consist of a mix of hard and soft tasks with varying criticality as well as associated fault tolerance requirements. Additionally, the relative criticality of tasks could undergo changes during the evolution of the system. Time redundancy techniques are often preferred in many embedded applications and, hence, it is extremely important to devise appropriate methodologies for scheduling real-time tasks under error assumptions. In this paper, we propose a methodology to provide a priori guarantees in fixed priority scheduling (FPS) such that the system will be able to tolerate one error per every critical task instance. We do so by using Integer Linear Programming (ILP) to derive task attributes that guarantee re-execution of every critical task instance before its deadline, while keeping the associated costs minimized. We illustrate the effectiveness of our approach, in comparison with fault tolerant (FT) adaptations of the well-known rate monotonic (RM), by simulations.

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-5919 (URN)10.1109/RTCSA.2008.6 (DOI)000260407600036 ()2-s2.0-53549084077 (Scopus ID)978-0-7695-3349-0 (ISBN)
Conference
14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications Location: Kaohsiung, TAIWAN Date: AUG 25-27, 2008
Available from: 2009-05-19 Created: 2009-05-19 Last updated: 2013-12-03Bibliographically approved
2. VTV -- A Voting Strategy for Real-Time Systems
Open this publication in new window or tab >>VTV -- A Voting Strategy for Real-Time Systems
2008 (English)In: Proceedings of the 14th IEEE Pacific Rim International Symposium on Dependable Computing, PRDC 2008, 2008, 56-63 p.Conference paper, Published paper (Refereed)
Abstract [en]

 

Real-time applications typically have to satisfy high dependability requirements and require fault tolerance in both value and time domains. A widely used approach to ensure fault tolerance in dependable systems is the N-modular redundancy (NMR) which typically uses a majority voting mechanism. However, NMR primarily focuses on producing the correct value, without taking into account the time dimension. In this paper, we propose a new approach, Voting on Time and Value (VTV), applicable to real-time systems, which extends the modular redundancy approach by explicitly considering both value and timing failures, such that correct value is produced at a correct time, under specified assumptions. We illustrate our voting approach by instantiating it in the context of the well-known triple modular redundancy (TMR) approach. Further, we present a generalized version targeting NMR that enables a high degree of customization from the user perspective.

 

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-5920 (URN)10.1109/PRDC.2008.28 (DOI)2-s2.0-60349103984 (Scopus ID)9780769534480 (ISBN)
Conference
14th IEEE Pacific Rim International Symposium on Dependable Computing, PRDC 2008; Taipei; Taiwan; 15 December 2008 through 17 December 2008
Available from: 2009-05-19 Created: 2009-05-19 Last updated: 2013-12-03Bibliographically approved
3. A Cascading Redundancy Approach for Dependable Real-Time Systems
Open this publication in new window or tab >>A Cascading Redundancy Approach for Dependable Real-Time Systems
2009 (English)In: Proceedings - 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2009, 2009, 467-476 p.Conference paper, Published paper (Refereed)
Abstract [en]

Dependable real-time systems typically consist of tasks of multiple criticality levels and scheduling them in a fault-tolerantmanner is a challenging problem. Redundancy in the physical and temporal domains for achieving fault tolerance has been often dealt independently based on the types of errors one needs to tolerate. To our knowledge, there had been no work which tries to integrate fault tolerant scheduling and multiple redundancy mechanisms. In this paper we propose a novel cascading redundancy approach within a generic fault tolerant scheduling framework. The proposed approach is capable of tolerating errors with a wider coverage (with respect to error frequency and error types) than time and space redundancy in isolation, allows tasks with mixed criticality levels, is independent of the scheduling technique and, above all, ensures that every critical task instance can be feasibly replicated in both time and space. 

 

National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-5923 (URN)10.1109/RTCSA.2009.56 (DOI)000276774500051 ()2-s2.0-72349083325 (Scopus ID)978-076953787-0 (ISBN)
Conference
15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2009;Beijing ;24 August 2009 through 26 August 2009
Available from: 2009-05-19 Created: 2009-05-19 Last updated: 2013-12-03Bibliographically approved
4. Towards an Error Modeling Framework for Dependable Component Based Systems
Open this publication in new window or tab >>Towards an Error Modeling Framework for Dependable Component Based Systems
2008 (English)In: DATE Workshop on Dependable Software Systems, 2008Conference paper, Published paper (Refereed)
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-5918 (URN)
Conference
DATE Workshop on Dependable Software Systems, 2008
Available from: 2009-05-19 Created: 2009-05-19 Last updated: 2014-01-16Bibliographically approved

Open Access in DiVA

fulltext(1243 kB)396 downloads
File information
File name FULLTEXT01.pdfFile size 1243 kBChecksum SHA-512
f694e9ab6474fa613096c1891473b1abc7e0af71497803a921f393d364f962fb7cba62f241a885fcf5813640069817fb0b1a590aeb56503069075a7d5a032f1f
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Aysan, Hüseyin
By organisation
School of Innovation, Design and Engineering
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 396 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 258 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf