Abstract
Consider a bounded degree network of resources, e.g., each node in the network is a collection of processors of limited capacity in a cloud center. Jobs arrive stochastically and move through the network until they receive the service they need or give up. We call the latter case, i.e., a job giving up, a failure. We show that even if the jobs move through the network in an adversarial fashion (and give up any time after the first node they visit), the failure probability of the network behaves almost as if the graph was a single node. That is, failures do not cascade. We apply this result to the analysis of time-of-use pricing for selling resources. The challenge here is that jobs have both timing constraints and preferences for cheaper resources over more expensive resources. Joint work with Shuchi Chawla, Nikhil Devanur, Alexander Holroyd, James Martin and Balu Sivan