Semantics Based Commutativity Analysis of Object Methods

Date of Submission: 
March 4, 2005
Report Number: 
Report PDF: 
Traditional analysis and usage of operation commutativity relies on pairwise commutativity relationships. In contrast, this paper presents method group commutativity, which specifies the conditions under which operations in a method group will commute. Method group commutativity can be practically applied to efficiently support distributed object caching and concurrency control. A formal definition of commutativity, in terms of Hoare logic expressions, guides the development of a methodology to create a method commutativity specification from an object's semantic specification. This methodology uses the PVS theorem prover for analysis and validation of commutativity properties. The use of formal methods, together with suitable tools, provides a more complete understanding of method commutativity relationships as compared to existing approaches. Our approach also provides a unified representation of both forward and backward commutativity properties. The methodology is also expanded to express weakened semantics in the method commutativity specification to enable greater commutativity.