research-article

Diconic addition of failsafe fault-tolerance

Author:

Ali EbnenasirAuthors Info & Claims

ASE '07: Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering

Pages 44 - 53

https://doi.org/10.1145/1321631.1321641

Published: 05 November 2007 Publication History

Abstract

We present a divide-and-conquer method, called DiConic, for automatic addition of failsafe fault-tolerance to distributed programs, where a failsafe program guarantees to meet its safety specification even when faults occur. Specifically, instead of adding fault-tolerance to a program as a whole, we separately revise program actions so that the entire program becomes failsafe fault-tolerant. Our DiConic algorithm has the potential to utilize the processing power of a large number of machines working in parallel, thereby enabling automatic addition of failsafe fault-tolerance to distributed programs with a large number of processes. We formulate our DiConic synthesis algorithm in terms of the satisfiability problem and demonstrate our approach for the Byzantine Generals problem and an industrial application.

References

[1]

B. Alpern and F. B. Schneider. Defining liveness. Information Processing Letters, 21:181--185, 1985.

[2]

A. Arora and M. G. Gouda. Closure and convergence: A foundation of fault-tolerant computing. IEEE Transactions on Software Engineering, 19(11):1015--1027, 1993.

Digital Library

[3]

A. Arora and S. S. Kulkarni. Detectors and correctors: A theory of fault-tolerance components. In International Conference on Distributed Computing Systems, pages 436--443, May 1998.

Digital Library

[4]

P. Attie and A. Emerson. Synthesis of concurrent programs for an atomic read/write model of computation. ACM TOPLAS, 23(2), March 2001.

Digital Library

[5]

P. C. Attie, A. Arora, and E. A. Emerson. Synthesis of fault-tolerant concurrent programs. ACM Transactions on Programming Languages and Systems (TOPLAS), 26(1):125--185, 2004.

Digital Library

[6]

R. Bharadwaj and C. Heitmeyer. Developing high assurance avionics systems with the SCR requirements method. In Proceedings of the 19th Digital Avionics Systems Conference, Philadelphia, PA, October 2000.

[7]

B. Bonakdarpour and S. S. Kulkarni. Exploiting symbolic techniques in automated synthesis of distributed programs. In IEEE International Conference on Distributed Computing Systems, pages 3--10, 2007.

Digital Library

[8]

K. Cho and J. Lim. Synthesis of fault-tolerant supervisor for automated manufacturing systems: A case study on photolithography process. IEEE Transactions on Robotics and Automation, 14(2):348--351, April 1998.

[9]

E. W. Dijkstra. A Discipline of Programming. Prentice Hall, 1976.

Digital Library

[10]

B. Dutertre and L. de Moura. A Fast Linear-Arithmetic Solver for DPLL(T). In Proceedings of the 18th Computer-Aided Verification conference, volume 4144 of LNCS, pages 81--94. Springer-Verlag, 2006.

Digital Library

[11]

A. Ebnenasir. Automatic Synthesis of Fault-Tolerance. PhD thesis, Michigan State University, May 2005.

Digital Library

[12]

A. Ebnenasir. Diconic addition of failsafe fault-tolerance. Technical Report CS-TR-07-03, Department of Computer Science, Michigan Technological University, Houghton, Michigan, June 2007.

[13]

A. Ebnenasir and S. S. Kulkarni. FTSyn: A framework for automatic synthesis of fault-tolerance. http://www.cs.mtu.edu~aebnenas/research/tools/ftsyn.htm.

[14]

A. Ebnenasir and S. S. Kulkarni. SAT-based synthesis of fault-tolerance. Fast Abstracts of the International Conference on Dependable Systems and Networks, Palazzo dei Congressi, Florence, Italy, June 28-July 1, 2004.

[15]

A. Ebnenasir, S. S. Kulkarni, and B. Bonakdarpour. Revising UNITY programs: Possibilities and limitations. In International Conference on Principles of Distributed Systems (OPODIS), pages 275--290, 2005.

Digital Library

[16]

E. A. Emerson. Handbook of Theoretical Computer Science, volume B, chapter 16: Temporal and Modal Logics, pages 995--1067. Elsevier Science Publishers B. V., 1990.

Digital Library

[17]

E. A. Emerson and E. M. Clarke. Using branching time temporal logic to synchronize synchronization skeletons. Science of Computer Programming, 2:241--266, 1982.

[18]

S. S. Kulkarni and A. Arora. Automating the addition of fault-tolerance. In Proceedings of the 6th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, pages 82--93, 2000.

Digital Library

[19]

S. S. Kulkarni, A. Arora, and A. Chippada. Polynomial time synthesis of Byzantine agreement. In Symposium on Reliable Distributed Systems, pages 130--139, 2001.

[20]

S. S. Kulkarni and A. Ebnenasir. Enhancing the fault-tolerance of nonmasking programs. In Proceedings of the 23rd International Conference on Distributed Computing Systems, pages 441--449, 2003.

Digital Library

[21]

S. S. Kulkarni and A. Ebnenasir. Adding fault--tolerance using pre-synthesized components. Fifth European Dependable Computing Conference (EDCC--5), LNCS, Vol. 3463, p. 72, 2005.

Digital Library

[22]

S. S. Kulkarni and A. Ebnenasir. Complexity issues in automated synthesis of failsafe fault-tolerance. IEEE Transactions on Dependable and Secure Computing, 2(3):201--215, 2005.

Digital Library

[23]

S. Lafortune and F. Lin. On tolerable and desirable behaviors in supervisory control of discrete event systems. Discrete Event Dynamic Systems: Theory and Applications, 1(1):61--92, 1992.

[24]

L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382--401, 1982.

Digital Library

[25]

A. Pnueli and R. Rosner. On the synthesis of a reactive module. In ACM Symposium on Principles of Programming Languages, pages 179--190, Austin, Texas, 1989.

Digital Library

[26]

R. Puri and J. Gu. A divide-and-conquer approach for asynchronous interface synthesis. In ISSS '94: Proceedings of the 7th international symposium on High-level synthesis, pages 118--125, 1994.

Digital Library

[27]

D. Smith. A problem reduction approach to program synthesis. Proceedings of the Eighth International Joint Conference on Artificial Intelligence, pages 32--36, 1983.

[28]

W. Thomas. On the synthesis of strategies in infinite games. In STACS, pages 1--13, 1995.

[29]

N. Wallmeier, P. Hütten, and W. Thomas. Symbolic synthesis of finite-state controllers for request-response specifications. In CIAA, LNCS, Vol. 2759, pages 11--22, 2003.

Cited By

Abujarad FLin YBonakdarpour BKulkarni S(2015)The complexity of automated addition of fault-tolerance without explicit legitimate statesDistributed Computing10.1007/s00446-014-0227-228:3(201-219)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1007/s00446-014-0227-2
Chen JEbnenasir AKulkarni S(2014)The Complexity of Adding MultitoleranceACM Transactions on Autonomous and Adaptive Systems10.1145/26296649:3(1-33)Online publication date: 7-Oct-2014
https://dl.acm.org/doi/10.1145/2629664
Ebnenasir A(2013)Action-based discovery of satisfying subsetsInformation and Software Technology10.1016/j.infsof.2012.07.01855:2(201-214)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.infsof.2012.07.018
Show More Cited By

Index Terms

Recommendations

Complexity Issues in Automated Synthesis of Failsafe Fault-Tolerance

We focus on the problem of synthesizing failsafe fault-tolerance where fault-tolerance is added to an existing (fault-intolerant) program. A failsafe fault-tolerant program satisfies its specification (including safety and liveness) in the absence of ...
The Complexity of Adding Failsafe Fault-Tolerance
ICDCS '02: Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02)

In this paper, we focus our attention on the problem of automating the addition of failsafe fault-tolerance where fault-tolerance is added to an existing (fault-intolerant) program. A failsafe fault-tolerant program satisfies its specification (...
Designing masking fault-tolerance via nonmasking fault-tolerance
SRDS '95: Proceedings of the 14TH Symposium on Reliable Distributed Systems

Masking fault-tolerance guarantees that programs continually satisfy their specification in the presence of faults. By way of contrast, nonmasking fault-tolerance does not guarantee as much: it merely guarantees that when faults stop occurring, program ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ASE '07: Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering

November 2007

590 pages

ISBN:9781595938824

DOI:10.1145/1321631

General Chair:
Kurt Stirewalt
Michigan State University, USA
,
Program Chairs:
Alexander Egyed
Teknowledge Corporation, USA
,
Bernd Fischer
University of Southampton, UK

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ASE07

Sponsor:

ASE07: International Conference on Automated Software Engineering 2007

November 5 - 9, 2007

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 82 of 337 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
226
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abujarad FLin YBonakdarpour BKulkarni S(2015)The complexity of automated addition of fault-tolerance without explicit legitimate statesDistributed Computing10.1007/s00446-014-0227-228:3(201-219)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1007/s00446-014-0227-2
Chen JEbnenasir AKulkarni S(2014)The Complexity of Adding MultitoleranceACM Transactions on Autonomous and Adaptive Systems10.1145/26296649:3(1-33)Online publication date: 7-Oct-2014
https://dl.acm.org/doi/10.1145/2629664
Ebnenasir A(2013)Action-based discovery of satisfying subsetsInformation and Software Technology10.1016/j.infsof.2012.07.01855:2(201-214)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.infsof.2012.07.018
Ebnenasir AKulkarni S(2011)Feasibility of Stepwise Design of Multitolerant ProgramsACM Transactions on Software Engineering and Methodology10.1145/2063239.206324021:1(1-49)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1145/2063239.2063240
Bonakdarpour BKulkarni SAbujarad F(2011)Symbolic synthesis of masking fault-tolerant distributed programsDistributed Computing10.1007/s00446-011-0139-325:1(83-108)Online publication date: 4-Oct-2011
https://doi.org/10.1007/s00446-011-0139-3
Abujarad FKulkarni S(2009)Constraint Based Automated Synthesis of Nonmasking and Stabilizing Fault-ToleranceProceedings of the 2009 28th IEEE International Symposium on Reliable Distributed Systems10.1109/SRDS.2009.11(119-128)Online publication date: 27-Sep-2009
https://dl.acm.org/doi/10.1109/SRDS.2009.11
Ebnenasir ABeik R(2009)Developing parallel programsProceedings of the 2009 ICSE Workshop on Multicore Software Engineering10.1109/IWMSE.2009.5071377(1-8)Online publication date: 18-May-2009
https://dl.acm.org/doi/10.1109/IWMSE.2009.5071377
Ebnenasir AKulkarni SArora A(2008)FTSynInternational Journal on Software Tools for Technology Transfer (STTT)10.5555/3220905.322114810:5(455-471)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.5555/3220905.3221148
Ebnenasir AKulkarni SArora A(2008)FTSyn: a framework for automatic synthesis of fault-toleranceInternational Journal on Software Tools for Technology Transfer10.1007/s10009-008-0083-010:5(455-471)Online publication date: 31-Jul-2008
https://doi.org/10.1007/s10009-008-0083-0

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.

Figures

Tables

Media

View Table of Conten