This proposal seeks support for a collaborative research effort aimed at removing the computational barriers to the widespread adoption of Markov chain technology, with a special emphasis to the performance mod­eling of concurrent software. By targeting this specific application and stressing the development of new structured methods, we will advance both Markov solution technology in general, and software performance engineering in particular. Coming from different and complementary points of view, the PIs and their two European collaborators have the ability to overcome the difficulties associated with this task. The results obtained by the proposed research will likely open up the field of Markov chain modeling to a surge of new, possibly unanticipated, research activity, research activity in diverse areas of national and international importance. In the area of software performance engineering, our results will foster the widespread acceptance and use of composi­ tional modeling, increasingly called for by industry's move towards off­the­shelf components. To achieve our goal of reusable software, we will: . Explore the relationship between high­level formalisms suited to modeling concurrent software and their underlying Kronecker structure, broadening the class of formalisms to which the proposed tech­niques can be applied automatically and which will result in an efficient representation. . Develop efficient solution methods for asynchronous interactions and block­ based Kronecker de­scriptions. . Explore how to combine the savings due to lumping with those due to implicit representations inspired by those used in the symbolic model checking community. . Explore ways to develop preconditioners to allow numerical projection type matrix solution methods to be used effectively in conjunction with Kronecker representations. . Extend the field of Kronecker­based approximations and develop heuristics that allow its transparent application to general models of software.