Exact Performance Analysis of Two Distributed Processes with Multiple Synchronization Points.

We describe a technique to exactly analyze the run time behavior of a class of distributed computer programs is composed of two processes and an arbitrary number of synchronization points. A process is viewed as a flow chart without branches, whose nodes represent local computation requiring a deterministic time to execute, and whose arcs correspond to interprocess communication. Each synchronization point is a constraint prohibiting a transition in one flow chart when the other process is executing a certain sequence of nodes in its flow chart. The global program state specifies at which flow chart node each process is currently executing or blocked. A steady state behavior is a finite sequence of global states and transitions repeated forever. Solve for the steady state using a Diophantine equation whose coefficients and unknowns are integers derived from the geometric concurrency model. The geometric model uses a two dimensional Cartesian product of nonnegative real numbers to represent all feasible global system states. The sequence of nodes in each flow chart is mapped to consecutive intervals along each axis. The model solution yields the sequence of synchronization points where the program blocks during steady state, the blocking durations, and the duration of concurrent execution between synchronization points. An algorithm is presented to solve the chief numerical problem of evaluating the minima of two arithmetic functions arising in the analysis.