Optimal Instrumentation of Data-flow in Concurrent Data Structures

TitleOptimal Instrumentation of Data-flow in Concurrent Data Structures
Publication TypeConference Paper
Year of Publication2011
AuthorsNavabpour, S., B. Bonakdarpour, and S. Fischmeister
Conference NameProc. of the 15th International Conference On Principles Of Distributed Systems (OPODIS)
Date PublishedDecember
Conference LocationToulouse, France
Keywordsdebugging, Instrumentation

In this paper, we propose an automated technique for optimal instrumentation of multi-threaded programs for debugging and testing of concurrent data structures. We define a notion of observability that enables debuggers to trace back and locate errors through data-flow instrumentation. Observability in a concurrent program enables a debugger to extract the value of a set of desired variables through instrumenting another (possibly smaller) set of variables. We formulate an optimization problem that aims at minimizing the size of the latter set. In order to cope with the exponential complexity of the problem, we present a SAT-based solution. Our approach is fully implemented and experimental results on popular concurrent data structures (e.g., linked lists and red-black trees) show significant performance improvement in optimally-instrumented programs using our method as compared to ad-hoc over-instrumented programs.

Refereed DesignationRefereed
Related files: 


Looking for motivated students (undergrads and grads) interested in working on embedded software and systems research. Mail Sebastian Fischmeister for further information.