A Combinatorial Study of Async/Await Processes

Overview & Synopsis

In this paper we study families of async/await concurrent processes using techniques and tools from (enumerative) combinatorics and order theory. We consider the count of process executions as the primary measure of "complexity", which closely relates to the (in general, difficult) problem of counting linear extensions of partial orders. Interestingly, the control structures of async/await processes fall into the subclass of what we call the BIT-decomposable posets, providing an effective way to count executions in practice. We also show that async/await processes can be seen as generalizations of families of interval orders, a well-studied class of partial orders. Based on this combinatorial study, we define a variety of uniform random generation algorithms. We consider on the one side the generation of process structures, and on the other side the generation of execution paths-which is performed without requiring the explicit construction of the state-space.