A time-randomness tradeoff for oblivious routing

ABSTRACT

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 - &Ogr;(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+&ogr;(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.

REFERENCES

• A: R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
• B: E. Bach, Realistic Analysis of Some Randomized Algorithms, P~'oc. 27th Syrup. on Pbundation of CoTnpute.;' Science, 1987.
• BH: A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
• CW: J.L. C~rter ~nd M.N. Wegm~n, Ui~iversal Classes of Hash Functions, Journal of Computer and System Sciences 18, (1979), 143-154.
• CG: B. Chor , O. Goldreich, On the power of two-point based sampling, Journal of Complexity, v.5 n.1, p.96-106, March 1989 [doi>10.1016/0885-064X(89)90015-0]
• KR: I5. Karloff al~(t t'. Raghavan, Pseudo andom Numbers and Randomized Algorithms, These Proceedings.
• KY: D.E. Knuth and A.C. Yao, The Complexity of Nonuniform Random Number Generation, in Algorithms and Complexity, Ed. J.E. Traub, Academic Press, New York, 1976, 357- 428.
• L: T. Lang, Interconnections Between Processors and Memory Modules Using the Shuffle-Exchange Network. IEEE Transactions on Computers 25. (1976), 496-503.
• R: A.G. Rana.de. llow to Elnulate a Shared Memory, Proc. 27th Sym, p. on foundations of computer science. 19$7. 185- 19,1.
• V: L.G. Valiant, A schelne for Fast ParaJlel Commu,lica.tioll, SIA,II J. ot, Computing 11, (1982), 350-361.
• Ul: J.D. {!llmam, Conlputational Aspect..' of VLSI, Computer Science Press. 1984.
• Up: Eli Upfal, Efficient Schemes for Parallel Communication, Journal of the ACM (JACM), v.31 n.3, p.507-517, July 1984 [doi>10.1145/828.1892]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Design, Performance, Theory