Model feasible interactions in distributed real-time systems

When a distributed system contains only causal relations from input events to output events, an interaction diagram (id) provides a convenient mechanism to study observable behaviors of the system as all events can be mapped to a set of global times that preserve the initial causal relations. However, the interaction diagram focuses only on causal orders among distributed events, which is not sufficient for most real-time applications. Furthermore, in real-time context, a feasible interaction is the one that satisfies not only causal constraints and precedence constraints, but also real-time constraints. However, feasibility checking for a given set of real-time constraints is asymptotically harder than for causal or precedence constraints. In this paper, we first extend the interaction diagram with precedence constraints and develop a mechanism that allows order preserving composition of the extended interaction diagram (eid) with timing constraint graph (tcg). The composition of the extended interaction diagram and timing constraining graph is called timed interaction diagram (tid). To reduce the time complexity differences between the two different feasibility checkings, event bundling is introduced to partition timed interaction diagrams. We show that a lattice of bundled interaction diagrams (bid) can be derived from a given timed interaction diagram to improve the efficiency of feasibility checking for arbitrary real-time constraints.