Improved bounds for performability evaluation algorithms using state generation

We present improved techniques for bounding the expectation of a performance measure over a very large state space generated by a system of independent components, each of which has an arbitrary number of states (called “modes”), when the values of the measure are known only on a subset of the global state space. Our results apply to any algorithm that evaluates performability by state generation, and consist of bounds in closed form or proofs that certain bounds cannot be improved.We give two example applications of our results, one to a large communications network and the other to a small database system.