Task resource models and (max, +) automata

Summary

Abstract

We show that a typical class of timed concurrent systems can be modeled as automata with multiplicities in the (max, +) semiring. This representation can be seen as a timed extension of the logical modeling in terms of trace monoids. We briefly discuss the applications of this algebraic modeling to performance evaluation.

Introduction

Different variations of (stochastic) queuing networks with precedence-based relations between customers have been studied for quite a long time in the performance evaluation community, see [3, 5, 20]. In the combinatorics community on the other hand, concurrent systems are usually modeled in terms of traces – elements of free partially commutative monoids –, see [8, 11]. An equivalent formalism is that of heaps of pieces [19].

One of the purposes of this note is to bridge the gap between the two approaches. In the first part of the paper, we establish the relations between the models. An important feature is that execution times of these models can be represented as finite dimensional (max, +) linear dynamical systems. In an essentially equivalent way, they are recognized by automata with multiplicities in the (max, +) semiring. The existence of similar (max, +) models has already been noticed in the context of queuing theory [20, 7]. Their analogue for trace monoids seems to be new.

In the second part of the paper, we apply this algebraic modeling to performance evaluation problems. We present asymptotic results on the existence of mean execution time for random schedules, and for optimal and worst schedules. They are obtained by appealing to subadditive arguments borrowed from the theory of random (max, +) matrices [1].