{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T14:14:58Z","timestamp":1761488098262,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,7,1]],"date-time":"2008-07-01T00:00:00Z","timestamp":1214870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2008,7]]},"abstract":"<jats:p>We present a formal approach to implement fault-tolerance in real-time embedded systems. The initial fault-intolerant system consists of a set of independent periodic tasks scheduled onto a set of fail-silent processors connected by a reliable communication network. We transform the tasks such that, assuming the availability of an additional spare processor, the system tolerates one failure at a time (transient or permanent). Failure detection is implemented using heartbeating, and failure masking using checkpointing and rollback. These techniques are described and implemented by automatic program transformations on the tasks' programs. The proposed formal approach to fault-tolerance by program transformations highlights the benefits of separation of concerns. It allows us to establish correctness properties and to compute optimal values of parameters to minimize fault-tolerance overhead. We also present an implementation of our method, to demonstrate its feasibility and its efficiency.<\/jats:p>","DOI":"10.1145\/1376804.1376813","type":"journal-article","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T13:35:10Z","timestamp":1217943310000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Implementing fault-tolerance in real-time programs by automatic program transformations"],"prefix":"10.1145","volume":"7","author":[{"given":"Tolga","family":"Ayav","sequence":"first","affiliation":[{"name":"INRIA and Izmir Institute of Technology, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Fradet","sequence":"additional","affiliation":[{"name":"INRIA and University of Grenoble, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alain","family":"Girault","sequence":"additional","affiliation":[{"name":"INRIA and University of Grenoble, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aggarwal A. and Gupta D. 2002. Failure detectors for distributed systems. Tech. rep. Indian Institute of Technology Kanpur India. http:\/\/resolute.ucsd.edu\/diwaker\/publications\/ds.pdf.]]  Aggarwal A. and Gupta D. 2002. Failure detectors for distributed systems. Tech. rep. Indian Institute of Technology Kanpur India. http:\/\/resolute.ucsd.edu\/diwaker\/publications\/ds.pdf.]]"},{"volume-title":"Proceedings of the 11th International Workshop on Distributed Algorithms","author":"Aguilera M.","key":"e_1_2_1_2_1","unstructured":"Aguilera , M. , Chen , W. , and Toueg , S . 1997. Heartbeat: A timeout-free failure detector for quiescent reliable communication . In Proceedings of the 11th International Workshop on Distributed Algorithms . Saarbrucken, Germany. Springer-Verlag, Berlin, 126--140.]] Aguilera, M., Chen, W., and Toueg, S. 1997. Heartbeat: A timeout-free failure detector for quiescent reliable communication. In Proceedings of the 11th International Workshop on Distributed Algorithms. Saarbrucken, Germany. Springer-Verlag, Berlin, 126--140.]]"},{"volume-title":"Proceedings of the International Conference on Distributed Computing Systems (ICDCS'98)","author":"Arora A.","key":"e_1_2_1_3_1","unstructured":"Arora , A. and Kulkarni , S . 1998. Detectors and correctors: A theory of fault-tolerance components . In Proceedings of the International Conference on Distributed Computing Systems (ICDCS'98) . Amsterdam, The Netherlands. IEEE, Los Alamitos, CA. 436--443.]] Arora, A. and Kulkarni, S. 1998. Detectors and correctors: A theory of fault-tolerance components. In Proceedings of the International Conference on Distributed Computing Systems (ICDCS'98). Amsterdam, The Netherlands. IEEE, Los Alamitos, CA. 436--443.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2004.2"},{"volume-title":"Proceedings of Real-Time Computing Systems and Applications (RTCSA'00)","author":"Aydin H.","key":"e_1_2_1_5_1","unstructured":"Aydin , H. , Melhem , R. , and Moss\u00e9 , D . 2000. Optimal scheduling of imprecise computation tasks in the presence of multiple faults . In Proceedings of Real-Time Computing Systems and Applications (RTCSA'00) . Cheju Island, South Korea. IEEE, Los Alamitos, CA. 289--296.]] Aydin, H., Melhem, R., and Moss\u00e9, D. 2000. Optimal scheduling of imprecise computation tasks in the presence of multiple faults. In Proceedings of Real-Time Computing Systems and Applications (RTCSA'00). Cheju Island, South Korea. IEEE, Los Alamitos, CA. 289--296.]]"},{"volume-title":"Le CyCab de l'Inria Rhne-Alpes. Tech. rep. 0229","author":"Baille G.","key":"e_1_2_1_6_1","unstructured":"Baille , G. , Garnier , P. , Mathieu , H. , and Pissard-Gibollet , R. 1999. Le CyCab de l'Inria Rhne-Alpes. Tech. rep. 0229 , Inria , Rocquencourt, France .]] Baille, G., Garnier, P., Mathieu, H., and Pissard-Gibollet, R. 1999. Le CyCab de l'Inria Rhne-Alpes. Tech. rep. 0229, Inria, Rocquencourt, France.]]"},{"key":"e_1_2_1_7_1","unstructured":"Beck M. Plank J. and Kingsley G. 1994. Compiler-assisted checkpointing. Tech. rep. University of Tennessee.]]   Beck M. Plank J. and Kingsley G. 1994. Compiler-assisted checkpointing. Tech. rep. University of Tennessee.]]"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:TIME.0000048932.30002.d9"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of International Conference on Computer Safety, Reliabilitiy, and Security (SAFECOMP'99)","volume":"1698","author":"Caspi P.","unstructured":"Caspi , P. , Mazuet , C. , Salem , R. , and Weber , D . 1999. Formal design of distributed control systems with Lustre . In Proceedings of International Conference on Computer Safety, Reliabilitiy, and Security (SAFECOMP'99) . Lecture Notes in Computer Science , vol. 1698 . Springer-Verlag, Berlin. 396--409.]] Caspi, P., Mazuet, C., Salem, R., and Weber, D. 1999. Formal design of distributed control systems with Lustre. In Proceedings of International Conference on Computer Safety, Reliabilitiy, and Security (SAFECOMP'99). Lecture Notes in Computer Science, vol. 1698. Springer-Verlag, Berlin. 396--409.]]"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226647"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008149332687"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/102792.102801"},{"volume-title":"Proceedings of the Euromicro Conference","author":"Dean A.","key":"e_1_2_1_13_1","unstructured":"Dean , A. and Shen , J . 1998. Hardware to software migration with real-time thread integration . In Proceedings of the Euromicro Conference . V\u00e4steras, Sweden. IEEE, Los Alamitos, CA. 10243--10252.]] Dean, A. and Shen, J. 1998. Hardware to software migration with real-time thread integration. In Proceedings of the Euromicro Conference. V\u00e4steras, Sweden. IEEE, Los Alamitos, CA. 10243--10252.]]"},{"volume-title":"Workshop on Dependable Control of Discrete Systems (DCDS'07)","author":"Dumitrescu E.","key":"e_1_2_1_14_1","unstructured":"Dumitrescu , E. , Girault , A. , Marchand , H. , and Rutten , E . 2007. Optimal discrete controller synthesis for modeling fault-tolerant distributed systems . In Workshop on Dependable Control of Discrete Systems (DCDS'07) . Cachan, France. IFAC, New York. 23--28.]] Dumitrescu, E., Girault, A., Marchand, H., and Rutten, E. 2007. Optimal discrete controller synthesis for modeling fault-tolerant distributed systems. In Workshop on Dependable Control of Discrete Systems (DCDS'07). Cachan, France. IFAC, New York. 23--28.]]"},{"volume-title":"Workshop on Discrete Event Systems (WODES'04)","author":"Dumitrescu E.","key":"e_1_2_1_15_1","unstructured":"Dumitrescu , E. , Girault , A. , and Rutten , E . 2004. Validating fault-tolerant behaviors of synchronous system specifications by discrete controller synthesis . In Workshop on Discrete Event Systems (WODES'04) . Reims. France. IFAC, New York.]] Dumitrescu, E., Girault, A., and Rutten, E. 2004. Validating fault-tolerant behaviors of synchronous system specifications by discrete controller synthesis. In Workshop on Discrete Event Systems (WODES'04). Reims. France. IFAC, New York.]]"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2004.08.059"},{"volume-title":"Proceedings of the International Conference on Emerging Technologies and Factory Automation (ETFA'06)","author":"Girault A.","key":"e_1_2_1_18_1","unstructured":"Girault , A. and Yu , H . 2006. A flexible method to tolerate value sensor failures . In Proceedings of the International Conference on Emerging Technologies and Factory Automation (ETFA'06) . Prague, Czech Republic. IEEE, New York. 86--93.]] Girault, A. and Yu, H. 2006. A flexible method to tolerate value sensor failures. In Proceedings of the International Conference on Emerging Technologies and Factory Automation (ETFA'06). Prague, Czech Republic. IEEE, New York. 86--93.]]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/301177.301489"},{"volume-title":"Proceedings of the International Conference on Formal Methods and Models for Codesign (MEMOCODE'03)","author":"Grandpierre T.","key":"e_1_2_1_20_1","unstructured":"Grandpierre , T. and Sorel , Y . 2003. From algorithm and architecture specifications to automatic generation of distributed real-time executives: A seamless flow of graphs transformations . In Proceedings of the International Conference on Formal Methods and Models for Codesign (MEMOCODE'03) . Mont Saint-Michel, France. IEEE, Los Alamitos, CA.]] Grandpierre, T. and Sorel, Y. 2003. From algorithm and architecture specifications to automatic generation of distributed real-time executives: A seamless flow of graphs transformations. In Proceedings of the International Conference on Formal Methods and Models for Codesign (MEMOCODE'03). Mont Saint-Michel, France. IEEE, Los Alamitos, CA.]]"},{"volume-title":"Fault-Tolerance in Distributed Systems","author":"Jalote P.","key":"e_1_2_1_21_1","unstructured":"Jalote , P. 1994. Fault-Tolerance in Distributed Systems . Prentice-Hall , Englewood Cliffs, NJ .]] Jalote, P. 1994. Fault-Tolerance in Distributed Systems. Prentice-Hall, Englewood Cliffs, NJ.]]"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02703630"},{"volume-title":"Real-Time Systems: Design Principles for Distributed Embedded Applications","author":"Kopetz H.","key":"e_1_2_1_23_1","unstructured":"Kopetz , H. 1997. Real-Time Systems: Design Principles for Distributed Embedded Applications . Kluwer Academic Publishing , Novell, MA .]] Kopetz, H. 1997. Real-Time Systems: Design Principles for Distributed Embedded Applications. Kluwer Academic Publishing, Novell, MA.]]"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/646846.706965"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-39362-9_10"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01211393"},{"key":"e_1_2_1_28_1","unstructured":"Milner R. Tofte M. and Harper R. 1990. The Definition of Standard ML. MIT Press Cambridge MA.]]   Milner R. Tofte M. and Harper R. 1990. The Definition of Standard ML. MIT Press Cambridge MA.]]"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2003.1223648"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.56849"},{"key":"e_1_2_1_31_1","unstructured":"Nielson H. and Nielson F. 1992. Semantics with Applications\u2014A Formal Introduction. Wiley New York NY.]]   Nielson H. and Nielson F. 1992. Semantics with Applications\u2014A Formal Introduction. Wiley New York NY.]]"},{"volume-title":"Design and Analysis of Distributed Embedded Systems (DIPES'02)","author":"Puschner P.","key":"e_1_2_1_32_1","unstructured":"Puschner , P. 2002. Transforming execution-time boundable code into temporally predictable code . In Design and Analysis of Distributed Embedded Systems (DIPES'02) , B. Kleinjohann, K. Kim, L. Kleinjohann, and A. Rettberg, Eds. Kluwer Academic Publishing .]] Puschner, P. 2002. Transforming execution-time boundable code into temporally predictable code. In Design and Analysis of Distributed Embedded Systems (DIPES'02), B. Kleinjohann, K. Kim, L. Kleinjohann, and A. Rettberg, Eds. Kluwer Academic Publishing.]]"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008119029962"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0325013"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/646787.706263"},{"volume-title":"Proceedings of the IEEE Conference on Intelligent Robots and Systems (IROS'00)","author":"Sekhavat S.","key":"e_1_2_1_36_1","unstructured":"Sekhavat , S. and Hermosillo , J . 2000. The Cycab robot: A differentially flat system . In Proceedings of the IEEE Conference on Intelligent Robots and Systems (IROS'00) . Takamatsu, Japan. IEEE, Los Alamitos, CA.]] Sekhavat, S. and Hermosillo, J. 2000. The Cycab robot: A differentially flat system. In Proceedings of the IEEE Conference on Intelligent Robots and Systems (IROS'00). Takamatsu, Japan. IEEE, Los Alamitos, CA.]]"},{"volume-title":"Proceedings of the Symposium on Reliable Distributed Systems (SRDS'98)","author":"Silva L.","key":"e_1_2_1_37_1","unstructured":"Silva , L. and Silva , J . 1998. System-level versus user-defined checkpointing . In Proceedings of the Symposium on Reliable Distributed Systems (SRDS'98) . West Lafayette, IN. IEEE, Los Alamitos, CA. 68--74.]] Silva, L. and Silva, J. 1998. System-level versus user-defined checkpointing. In Proceedings of the Symposium on Reliable Distributed Systems (SRDS'98). West Lafayette, IN. IEEE, Los Alamitos, CA. 68--74.]]"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008141130870"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.620479"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1376804.1376813","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1376804.1376813","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:55Z","timestamp":1750255075000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1376804.1376813"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["10.1145\/1376804.1376813"],"URL":"https:\/\/doi.org\/10.1145\/1376804.1376813","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2008,7]]},"assertion":[{"value":"2006-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}