Title page for ETD etd-08222007-151929


Type of Document Master's Thesis
Author Singh, Amrinder
Author's Email Address asingh05@vt.edu
URN etd-08222007-151929
Title A component-based approach to proving the correctness of the Schorr-Waite algorithm
Degree Master of Science
Department Computer Science
Advisory Committee
Advisor Name Title
Kulczycki, Gregory W. Committee Chair
Chen, Ing-Ray Committee Member
Lu, Chang-Tien Committee Member
Keywords
  • modular reasoning
  • memory management
  • graph marking
  • Formal specification
Date of Defense 2007-08-09
Availability unrestricted
Abstract
This thesis presents a component-based approach to proving the correctness of programs involving pointers. Unlike previous work, our component-based approach supports modular reasoning, which is essential to the scalability of systems. Specifically, we specify the behavior of a graph-marking algorithm known as the Schorr-Waite algorithm, implement it using a component that captures the behavior and performance benefits of pointers, and prove that the implementation is correct with respect to the specification. We use the Resolve language in our example, which is an integrated programming and specification language that supports modular reasoning. The behavior of the algorithm is fully specified using custom definitions, pre- and post-conditions, and a complex loop invariant. Additional operations for the Resolve pointer component are introduced that preserve the accessibility of a system. These operations are used in the implementation of the algorithm. They simplify the proof of correctness and make the code shorter.
Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Amrinder_Singh_Masters_Thesis.pdf 428.17 Kb 00:01:58 00:01:01 00:00:53 00:00:26 00:00:02

Browse All Available ETDs by ( Author | Department )

dla home
etds imagebase journals news ereserve special collections
virgnia tech home contact dla university libraries

If you have questions or technical problems, please Contact DLA.