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.
Abstract
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
<arcadia-www@ics.uci.edu>
Last modified: Thu Jan 26 13:36:42 1995