ANALYZING TRACES WITH ANONYMOUS SYNCHRONIZATION
David P. Helmbold, Charles E. McDowell, Jian Wang · 1989
this paper. A trace specifies a total ordering of the events performed by the program. For our purposes, the trace reflects only one of the orders in which the events could have occurred. A more restrictive definition that is difficult to achieve in practice would be for a trace to specify the exact order in which the events did occur. Since traces are only approximations of executions, there are usually several executions that are consistent with a given trace. What we want to compute is the orderings between pairs of events that must occur in all executions which are consistent with the trace. In general this will be a partial order. If the partial order contains all orderings that must occur, then a pair of events not ordered by this "must occur" partial ordering can potentially execute in either order. Much research has been directed towards determining the partial ordering of events in parallel and distributed systems. Previous models have assumed point-to-point communication which makes it very easy to determine which events were caused by which other events (e.g. "message received by B from A" is clearly caused by "message sent by A to B"). Unfortunately the synchronization models supported by several parallel programming languages allow for anonymous communication, where the partner is unknown. Examples of anonymous communication include locks, semaphores, and monitors. Emrath, Ghosh, and Padua [EGP89] present a method for detecting non-determinacy in parallel programs that utilize fork/join and event style synchronization instructions with the Post, Wait, and Clear primitives. They construct a Task Graph from the given synchronization instructions and the sequential components of the program that is intended to show the guaranteed orderings between events. For ...