What's Decidable for Asynchronous Programs?

An asynchronous or ``event-driven" program is one that contains procedure calls which are not directly executed from the callsite, but stored and executed later by an external scheduler. By providing a low-overhead way to manage concurrent interactions, asynchronous programs form the core of many server programs, embedded systems, and popular programming styles for the web (Ajax). Unfortunately, such programs can be hard to write and maintain as sequential control flow needs to be split into several disjoint handlers. They are a challenge for static analysis tools as they are infinite state: both the program stack and the number of outstanding asynchronous requests may be unbounded. We show that safety and liveness properties can be checked effectively for the class of Boolean asynchronous programs, thus enabling automatic static techniques to check for correctness or for errors.

Bio: Rupak Majumdar is an Associate Professor in the Department of Computer Science at the University of California, Los Angeles and Scientific Director at the Max Planck Institute for Software Systems. His research interests are in the design and verification of reactive hardware and software systems. He received the President's Gold Medal from IIT, Kanpur, the Leon O. Chua award from UC Berkeley, and an NSF CAREER award.