The instrumentation and measurement of systems is vital for them to be understood, debugged, tuned, refined, tested, validated, or made reliable. This project will investigate the principles and practice of program instrumentation. Principles include a theoretical understanding of the dynamic measurement and observation of various structures in parallel, distributed, and sequential systems, such as acyclic or cyclic graphs for representing parallel executions and families of finite automata for tracking information about variable accesses. The complexity of computing and analyzing such structures will be explored, including tradeoffs between time, space, accuracy, and completeness. The practice of instrumentation implements measurement techniques at a cost acceptable to users, using on-line algorithms to dynamically decide what to do and when it is best done and by fully exploiting the semantics of the problem at hand. Techniques will be developed, especially for debugging and programming tools, for problems whose best-known solutions are currently prohibitive because of instrumentation costs. An arsenal of practical techniques usable in many areas, all of which are based on theoretical underpinnings, will also be developed. This research will result in a deeper understanding of the cost of solving various types of instrumentation problems and an array of techniques for their solution. This project will introduce undergraduates to research by involving them in independent study seminars together with "project sets" partially specified mini-research problems which require as much work in problem formulation as solution. This project will escalate the undergraduate-outreach effort at Brown. The tools this project will produce will be suitable for use by students in their research projects.***
