NDLI: Constraint Based Automated Synthesis of Nonmasking and Stabilizing Fault-Tolerance

Content Provider	IEEE Xplore Digital Library
Author	Abujarad, F. Kulkarni, S.S.
Copyright Year	2009
Abstract	We focus on constraint-based automated addition of nonmasking and stabilizing fault-tolerance to hierarchical programs. We specify legitimate states of the program in terms of constraints that should be satisfied in those states. To deal with faults that may violate these constraints, we add recovery actions while ensuring interference freedom among the recovery actions added for satisfying different constraints. Since the constraint-based{\em manual} design of fault-tolerance is well-known to be applicable in the manual design of nonmasking fault-tolerance, we expect our approach to have a significant benefit in automation of fault-tolerant programs. We illustrate our algorithms with three case studies:stabilizing mutual exclusion, stabilizing diffusing computation, and a data dissemination problem in sensor networks. With experimental results,we show that the complexity of synthesis is reasonable and that it can be reduced using the {\em structure} of the hierarchical systems. To our knowledge, this is the first instance where automated synthesis has been successfully used in synthesizing programs that are correct under fairness assumptions. Moreover, in two of the case studies considered in this paper, the structure of the recovery paths is too complex to permit existing heuristic based approaches for adding recovery.
Starting Page	119
Ending Page	128
File Size	367611
Page Count	10
File Format	PDF
ISBN	9780769538266
ISSN	10609857
DOI	10.1109/SRDS.2009.11
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-09-27
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Fault tolerance Interference constraints Network synthesis Safety Fault tolerant systems Computer science Reliability engineering USA Councils Electronic mail Design automation distributed programs nonmasking constraint based program synthesis stabilization
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computer Networks and Communications Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in