Arcadia Papers: ABSTRACT

"Sharpening the Bounds on Time Between Events in Maximally Parallel Systems", by George S. Avrunin in Technical Report 92-069, Department of Computer Science, University of Massachusetts at Amherst, 1992.


A recent paper by Avrunin, Corbett, Dillon, and Wileden describes a method for obtaining bounds on the time that can elapse between two given events in an execution of a concurrent software system running on a single processor under arbitrary scheduling. The technique involves generating linear inequalities expressing conditions that must be satisfied by all executions of such a system and using integer programming methods to find appropriate solutions to the inequalities. Corbett has extended this approach to obtain upper bounds on the time between events in executions of multi-processor concurrent systems in which each process proceeds unless forced to wait to communicate with another, the case of maximal parallelism, and processes communicate by synchronous message passing. Corbett's method does not strictly enforce the maximal parallelism assumption, however, and may thus give poor (though valid) bounds in some cases. In this paper, I show how to modify Corbett's method to obtain sharper bounds.
The Arcadia Project <>
Last modified: Thu Jan 26 13:36:42 1995