Article

Design Optimization of Time-and Cost-Constrained Fault-Tolerant Distributed Embedded Systems

Authors:

Viacheslav Izosimov,

Zebo PengAuthors Info & Claims

DATE '05: Proceedings of the conference on Design, Automation and Test in Europe - Volume 2

Pages 864 - 869

https://doi.org/10.1109/DATE.2005.116

Published: 07 March 2005 Publication History

Abstract

In this paper we present an approach to the design optimization of fault-tolerant embedded systems for safety-critical applications.Processes are statically scheduled and communications are performed using the time-triggered protocol.We use process re-execution and replication for tolerating transient faults.Our design optimization approach decides the mapping of processes to processors and the assignment of fault-tolerant policies to processes such that transient faults are tolerated and the timing constraints of the application are satisfied.We present several heuristics which are able to find fault-tolerant implementations given a limited amount of resources.The developed algorithms are evaluated using extensive experiments, including a real-life example.

References

[1]

{1} A. Bertossi, L. Mancini, "Scheduling Algorithms for Fault-Tolerance in Hard-Real Time Systems", Real Time Systems, 7(3), 229-256, 1994.

Digital Library

[2]

{2} A. Burns et al., "Feasibility Analysis for Fault-Tolerant Real-Time Task Sets", Euromicro Workshop on Real-Time Systems, 29-33, 1996.

[3]

{3} P. Chevochot, I. Puaut, "Scheduling Fault-Tolerant Distributed Hard-Real Time Tasks Independently of the Replication Strategies", Real-Time Computing Systems and Applications Conf., 356-363, 1999.

Digital Library

[4]

{4} V. Claeson, S. Poldena, J. Söderberg, "The XBW Model for Dependable Real-Time Systems", Parallel and Distributed Systems Conf., 1998.

Digital Library

[5]

{5} C. Dima et al, "Off-line Real-Time Fault-Tolerant Scheduling", Euromicro Parallel and Distributed Processing Workshop, 410-417, 2001.

[6]

{6} P. Eles et al., "Scheduling with Bus Access Optimization for Distributed Embedded Systems", IEEE Transactions on VLSI Systems, 8(5), 472-491, 2000.

Digital Library

[7]

{7} G. Fohler, "Joint Scheduling of Distributed Complex Periodic and Hard Aperiodic Tasks in Statically Scheduled Systems", IEEE Real-Time Systems Symposium, 152-161, 1995.

Digital Library

[8]

{8} G. Fohler, "Adaptive Fault-Tolerance with Statically Scheduled Real-Time Systems", Euromicro Real-Time Systems Workshop, 161-167, 1997.

[9]

{9} C. C. Han, K. G. Shin, J. Wu, "A Fault-Tolerant Scheduling Algorithm for Real-Time Periodic Tasks with Possible Software Faults", IEEE Transactions on Computers, 52(3), 362-372, 2003.

Digital Library

[10]

{10} K. Hoyme, K. Driscoll, "SAFEbus", IEEE Aerospace and Electronic Systems Magazine, 8(3), 34-39, 1992.

[11]

{11} N. Kandasamy, J. P. Hayes, B. T. Murray, "Transparent Recovery from Intermittent Faults in Time-Triggered Distributed Systems", IEEE Tranactions on Computers, 52(2), 113-125, 2003.

Digital Library

[12]

{12} N. Kandasamy, J. P. Hayes B.T. Murray "Dependable Communication Synthesis for Distributed Embedded Systems," Computer Safety, Reliability and Security Conf., 275-288, 2003.

[13]

{13} H. Kopetz, Real-Time Systems-Design Principles for Distributed Embedded Applications, Kluwer Academic Publishers, 1997.

Digital Library

[14]

{14} H. Kopetz et al., "Distributed Fault-Tolerant Real-Time Systems: The Mars Approach", IEEE Micro, 9(1), 25-40, 1989.

Digital Library

[15]

{15} H. Kopetz, Günter Bauer, "The Time-Triggered Architecture", Proceedings of the IEEE, 91(1), 112-126, 2003.

[16]

{16} C. Pinello, L. P. Carloni, A. L. Sangiovanni-Vincentelli, "Fault-Tolerant Deployment of Embedded Software for Cost-Sensitive Real-Time Feedback-Control Applications", DATE Conf., 1164-1169, 2004.

Digital Library

[17]

{17} S. Poldena, Fault Tolerant Systems-The Problem of Replica Determinism, Kluwer Academic Publishers, 1996.

Digital Library

[18]

{18} P. Pop, "Analysis and Synthesis of Communication-Intensive Heterogeneous Real-Time Systems", Ph. D. Thesis No. 833, Dept. of Computer and Information Science, Linköping University, 2003.

[19]

{19} P. Pop, P. Eles, Z. Peng, "Schedulability Analysis and Optimization for the Synthesis of Multi-Cluster Distributed Embedded Systems", Design, Automation and Test in Europe Conference and Exhibition, pp. 184-189, 2003.

Digital Library

[20]

{20} P. Pop et al., "Design Optimization of Multi-Cluster Embedded Systems for Real-Time Applications", Design, Automation and Test in Europe Conference and Exhibition, pp. 1028-1033, 2004.

Digital Library

[21]

{21} Y. Zhang, K. Chakrabarty, "Energy-Aware Adaptive Checkpointing in Embedded Real-Time Systems", DATE Conf., 918-923, 2003.

Digital Library

Cited By

Zhou YSamii SEles PPeng Z(2021)Reliability-aware Scheduling and Routing for Messages in Time-sensitive NetworkingACM Transactions on Embedded Computing Systems10.1145/345876820:5(1-24)Online publication date: 29-May-2021
https://dl.acm.org/doi/10.1145/3458768
Choi JYang HHa S(2018)Optimization of Fault-Tolerant Mixed-Criticality Multi-Core Systems with Enhanced WCRT AnalysisACM Transactions on Design Automation of Electronic Systems10.1145/327515424:1(1-26)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1145/3275154
Liang HWang ZZheng BZhu Q(2017)Addressing Extensibility and Fault Tolerance in CAN-based Automotive SystemsProceedings of the Eleventh IEEE/ACM International Symposium on Networks-on-Chip10.1145/3130218.3130233(1-8)Online publication date: 19-Oct-2017
https://dl.acm.org/doi/10.1145/3130218.3130233
Show More Cited By

Index Terms

Design Optimization of Time-and Cost-Constrained Fault-Tolerant Distributed Embedded Systems

Recommendations

Design optimization of time-and cost-constrained fault-tolerant embedded systems with checkpointing and replication

We present an approach to the synthesis of fault-tolerant hard real-time systems for safety-critical applications. We use checkpointing with rollback recovery and active replication for tolerating transient faults. Processes and communications are ...
Fault Injection and Dependability Evaluation of Fault-Tolerant Systems

The authors describe a dependability evaluation method based on fault injection that establishes the link between the experimental evaluation of the fault tolerance process and the fault occurrence process. The main characteristics of a fault injection ...
A Fault Tolerant Scheduling Heuristics for Distributed Real Time Embedded Systems
Abstract
In this paper, fault tolerant task scheduling algorithms are proposed for mapping task graphs to heterogeneous processing nodes. These scheduling heuristics that we propose are redundancy-based software to tolerate hardware faults. We consider ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DATE '05: Proceedings of the conference on Design, Automation and Test in Europe - Volume 2

March 2005

630 pages

ISBN:0769522882

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Computer Society

United States

Publication History

Published: 07 March 2005

Check for updates

Qualifiers

Article

Conference

DATE05

Sponsor:

SIGDA

DATE05: Design, Automation and Test in Europe

March 7 - 11, 2005

Acceptance Rates

Overall Acceptance Rate 518 of 1,794 submissions, 29%

Upcoming Conference

DATE '25

Sponsor:
sigda

Design, Automation and Test in Europe

March 31 - April 2, 2025

Lyon , France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
13
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou YSamii SEles PPeng Z(2021)Reliability-aware Scheduling and Routing for Messages in Time-sensitive NetworkingACM Transactions on Embedded Computing Systems10.1145/345876820:5(1-24)Online publication date: 29-May-2021
https://dl.acm.org/doi/10.1145/3458768
Choi JYang HHa S(2018)Optimization of Fault-Tolerant Mixed-Criticality Multi-Core Systems with Enhanced WCRT AnalysisACM Transactions on Design Automation of Electronic Systems10.1145/327515424:1(1-26)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1145/3275154
Liang HWang ZZheng BZhu Q(2017)Addressing Extensibility and Fault Tolerance in CAN-based Automotive SystemsProceedings of the Eleventh IEEE/ACM International Symposium on Networks-on-Chip10.1145/3130218.3130233(1-8)Online publication date: 19-Oct-2017
https://dl.acm.org/doi/10.1145/3130218.3130233
Zheng BGao YZhu QGupta SNicolescu GGerstlauer A(2015)Analysis and optimization of soft error tolerance strategies for real-time systemsProceedings of the 10th International Conference on Hardware/Software Codesign and System Synthesis10.5555/2830840.2830847(55-64)Online publication date: 4-Oct-2015
https://dl.acm.org/doi/10.5555/2830840.2830847
Gao YGupta SWang YPedram MFettweis GNebel W(2014)An energy-aware fault tolerant scheduling framework for soft error resilient cloud computing systemsProceedings of the conference on Design, Automation & Test in Europe10.5555/2616606.2616721(1-6)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.5555/2616606.2616721
Chen JShafique MMitra TReineke J(2014)Embedded software reliability for unreliable hardwareProceedings of the 14th International Conference on Embedded Software10.1145/2656045.2661649(1-1)Online publication date: 12-Oct-2014
https://dl.acm.org/doi/10.1145/2656045.2661649
Huang PYang HThiele L(2014)On the Scheduling of Fault-Tolerant Mixed-Criticality SystemsProceedings of the 51st Annual Design Automation Conference10.1145/2593069.2593169(1-6)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1145/2593069.2593169
Gao YGupta SBreuer MMacii E(2013)Using explicit output comparisons for fault tolerant scheduling (FTS) on modern high-performance processorsProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485511(927-932)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.5555/2485288.2485511
Klepikov V(2013)Ensuring fault-tolerant computations in distributed control systemsAutomation and Remote Control10.1134/S000511791312012674:12(2112-2121)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1134/S0005117913120126
Stralen PPimentel AJerraya ACarloni LChang NFummi F(2012)A SAFE approach towards early design space exploration of fault-tolerant multimedia MPSoCsProceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis10.1145/2380445.2380507(393-402)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.1145/2380445.2380507
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents