On the (max, +) structure of reservation systems

This article establishes the structure of dynamic reservation systems with precedence constraints. Such systems have practical applications in various domains of computer science such as conflicts in distributed databases, synchronization of parallel processes, reservation routing schemes in computer networks. These systems are modeled by a stochastic process which lakes values in the set of edges of a hypergraph. The dynamical equations appear to be linear in the (max,+) semi-ring T_n+1 = A_n ⊗ T_n. Unfortunately these matrices An are random with no common support. However. ergodic properties of the process are deduced from the structure of the hypergraph. Moreover, we give comparison methods based on coupling arguments and duality properties of the hypergraph.