On Compositionality in Refining Concurrent Systems

Three different styles of refinement of concurrent systems are investigated. The methods differ in their degree of compositionality. The traditional method considers the refinement of complete systems, and therefore is totally noncompositional. The middle level one is called a modular method, with which one first verifies refinement of each component and then checks that the refinements are compatible by an interference freedom test. The last and more novel one, borrows the rely–guarantee idea from program verification and supports compositional refinement in that one can carry out the development of one process without knowing the structure of other processes. A common example is verified by the various refinement methods. We discuss both advantages and disadvantages of the three approaches, which indicate when it is more suitable to use one particular style.