Model Checking Multithreaded Programs with Asynchronous Atomic Methods

In order to make multithreaded programming manageable, programmers often follow a design principle where they break the problem into tasks which are then solved asynchronously and concurrently on different threads. This paper investigates the problem of model checking programs that follow this idiom. We present a programming language \spl{} that encapsulates this design pattern. \spl{} extends simplified form of sequential Java to which we add the capability of making asynchronous method invocations in addition to the standard synchronous method calls and the ability to execute asynchronous methods in threads atomically and concurrently. Our main result shows that the control state reachability problem for finite \spl{} programs is decidable. Therefore, such multithreaded programs can be model checked using the counter-example guided abstraction-refinement framework