Global serializability of concurrent programs

AbstractMost of the models used to describe the behaviours of concurrent programs and to prove some of their properties assume the atomicity of actions at some level. When atomicity is ensured only at a low level, the need to increase the number of basic operations leads to a high complexity for the representations. If each execution of a concurrent program is serializable, some sets of basic actions may be considered atomic and this can reduce the complexity. In this paper, we give an algorithm for the detection of global serializability of a concurrent program