Author : Camilla Østerberg Rump
Publisher :
ISBN 13 :
Total Pages : 183 pages
Book Rating : 4.:/5 (338 download)
Book Synopsis Proof-by-transduction by : Camilla Østerberg Rump
Download or read book Proof-by-transduction written by Camilla Østerberg Rump and published by . This book was released on 1995 with total page 183 pages. Available in PDF, EPUB and Kindle. Book excerpt: Abstract: "When designing distributed systems, one is faced with the problem of verifying a refinement between two specifications, given at different levels of abstraction. Suggested verification techniques in the literature include refinement mappings and various forms of simulation. In this thesis, we present a verification method in which refinement between two systems is proven by constructing a transducer that inputs a computation of a concrete system and outputs a matching computation of the abstract system. In this way, the verification problem is reduced to proving certain properties of the transducer. For completeness, the existing techniques include backwards simulations or prophecy variables, which require backwards reasoning. The idea of the transducer is to use a FIFO queue to hold segments of the concrete computation that have not been matched yet. This allows a finite delay between the occurrence of a concrete event and the determination of the corresponding abstract event. This delay often makes the use of prophecy variables or backward simulation unneccessary. The problem of relaxed refinement is to prove that a matching observation of the abstract system is some transformation of the observed sequences of events of the concrete system. An important generalization of our technique is to prove relaxed refinement. The technique is adapted by replacing the FIFO queue by a component that allows the appropriate transformation on sequences of events. A particular case of relaxed refinement is partial order refinement, i.e., refinement that preserves only a subset of the orderings between events of a system. Examples of this type of refinement are sequential consistency and serializability. The case of sequential consistency is illustrated on a proof of sequential consistency of a cache protocol. We show that proof- by-transduction is complete for refinement that can be shown using forward simulation or history variables and present proofs of a lossy buffer example uing backwards simulation, prophecy variables, and proof-by- transduction for comparison."
