A time-randomness tradeoff for oblivious routing
Danny Kriz̧anc, David Peleg, Eli Upfal · 1988
Three parameters characterize the performance of a probabilistic algorithm: T, the runtime of the algorithm; Q, the probability that the algorithm fails to complete the computation in the first T steps and R, the amount of randomness used by the algorithm, measured by the entropy of its random source.We present a tight tradeoff between these three parameters for the problem of oblivious packet routing on N-vertex bounded-degree networks. We prove a (1 - Q) log N/T - log Q - O(1) lower bound for the entropy of a random source of any oblivious packet routing algorithm that routes an arbitrary permutation in T steps with probability 1 - Q. We show that this lower bound is almost optimal by proving the existence, for every e3 log N ≤ T ≤ N1/2, of an oblivious algorithm that terminates in T steps with probability 1 - Q and uses (1-Q+o(1))logN/T-logQ independent random bits.We complement this result with an explicit construction of a family of oblivious algorithms that use less than a factor of log N more random bits than the optimal algorithm achieving the same run-time.