Thread Algebra for Strategic Interleaving

Abstract

We present an extension of the polarized process algebra BPPA, an algebraic theory about sequential program behaviors. The extension is called thread algebra and is proposed as a tool for the description and analysis of multi-threaded program behaviors. Strategic interleaving refers to the form of concurrency where some interleaving strategy is used rather than arbitrary interleaving. Strategic interleav- ing is considered characteristic of multi-threading. Multi-threaded concurrency is more limited than general concurrency based on arbitrary interleaving.