Efficient Run-time Assurance in Distributed Systems through Selection of Executable Assertions

Abstract

Run-time assurance of a distributed system can be obtained by comparing, at run-time, the actual behavior of a program with the expected behavior described in the program's specification. Executable assertions, embedded into the program code, can determine when there are discrepancies between actual and expected behavior. There is no global monitoring scheme and error-detection will occur at the process level. We can assume that a non-faulty process will always perform correct computations. It can detect errors in other processes after receiving information from them and checking it against expected values using executable assertions. in order to efficiently check programs at run-time, we need to determine how many assertions need to be used, where they need to be located, and what they need to check to ensure that all occurring errors can be detected. This paper introduces temporal subsumption to remove, from a given set of assertions for a specific distributed program, the assertions which perform redundant checking. the remaining set of assertions is then the set necessary to provide run-time assurance. to subsume assertions, the flow graphs of the individual components of the distributed system are examined using a graph traversal algorithm. Temporal subsumption is a pre-processing step that creates a smaller set of assertions to be embedded into the program and to be checked at run-time. This makes error-detection at run-time less time-consuming and thus more efficient since redundant checking is avoided.

Department(s)

Computer Science

Sponsor(s)

United States. Air Force. Office of Scientific Research
National Science Foundation (U.S.)
University of Missouri Research Board

Keywords and Phrases

Distributed System; Executable Assertions; Run-Time Assurance

International Standard Serial Number (ISSN)

0164-1212

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2000 Elsevier, All rights reserved.

Publication Date

01 May 2000

Share

 
COinS