Aggregating changes to efficiently check consistency

ABSTRACT

Evolving complex systems from one consistent version to another is a challenging problem. Each version usually requires multiple changes in multiple system components having subtle functional dependencies. Mitigating the costs incurred to check the consistency of a new version is an important concern. An efficient approach to guarantee consistency of the new system is proposed. System components are modeled as communicating finite state machines. A change is a set of update rules that add or delete transitions in the system components. Given a set of changes, the proposed approach automatically generates an aggregated update comprised of groups of update rules. The interactions among the update rules are analyzed in terms of their impacts on the states of the system. Groups of update rules are computed such that each group contains one special rule whose impacted states subsume that of the others in the group. If that rule preserves consistency then the entire group preserves consistency. The proposed approach has been applied to consistently evolve a family of cache coherence protocols with highly encouraging results.

REFERENCES

• 1: International workshop on mining software repositories (msr '04-07). http://msr.uwaterloo.ca, 2004--2007.
• 2: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 3: Taweesup Apiwattanapong , Alessandro Orso , Mary Jean Harrold, Efficient and precise dynamic impact analysis using execute-after sequences, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062534]
• 4: Robert S. Arnold, Software Change Impact Analysis, IEEE Computer Society Press, Los Alamitos, CA, 1996
• 5: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 6: Jia Liu , Don Batory , Christian Lengauer, Feature oriented refactoring of legacy applications, Proceedings of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China [doi>10.1145/1134285.1134303]
• 7: M. Sharir. A strong-connectivity algorithm and its applications in data flow analyses. In Computers and Mathematics with Applications, pages 67--72, 1981.
• 8: Mahadevan Subramaniam , Harvey Siy, Consistently Incorporating Changes to Evolve Transition-based Systems, Proceedings of the 11th European Conference on Software Maintenance and Reengineering, p.17-26, March 21-23, 2007 [doi>10.1109/CSMR.2007.20]