Efficient Run-time Assurance in Distributed Systems through Selection of Executable Assertions
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.
M. Schollmeyer and B. M. McMillin, "Efficient Run-time Assurance in Distributed Systems through Selection of Executable Assertions," Journal of Systems and Software, Elsevier, May 2000.
The definitive version is available at http://dx.doi.org/10.1016/S0164-1212(99)00131-4
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
Article - Journal
© 2000 Elsevier, All rights reserved.