Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A time-randomness trade-off for oblivious routing
Peleg D., Upfal E. SIAM Journal on Computing19 (2):256-266,1990.Type:Article
Date Reviewed: Aug 1 1991

Understanding the role of randomness in the theory of computation is rapidly becoming one of the central, challenging problems facing computer scientists. The ultimate goal of research in this area is to develop a clear theory that explains why probabilistic algorithms perform better than deterministic ones on many problems, and to determine the extent to which this phenomenon can be exploited.

This paper takes one natural approach to that goal, namely, to treat randomness as a resource and analyze the amount of randomness required to achieve a given performance. (The amount of randomness provided by a random source can be measured in several ways, such as by the entropy of the random source.) The analysis is based on the tradeoff between the amount of randomness used by an algorithm, R, and its performance, measured either by the probability Q that it fails to complete the computation within a given number of steps T or by its average running time.

To prove such a tradeoff, the authors focus on one of the few problems whose probabilistic complexity is provably better than its deterministic complexity, namely, oblivious routing in bounded-degree networks. (A routing algorithm is oblivious if the route of one packet does not depend on the origins and destinations of other packets in the system.) This gap was established by studying the time a routing algorithm requires to execute a permutation request in an N-processor bounded-degree network. It is known that any deterministic oblivious routing algorithm requires parallel steps for certain permutation requests [1] and that randomized oblivious routing algorithms exist that execute any such request in parallel time with high probability [2,3].

This paper bridges the gap between these two results by analyzing the minimum amount of randomness needed in order to execute oblivious routing on a bounded-degree network in T steps for any T such that and establishing a tight tradeoff between the parameters R, T, and Q. In essence, the lower bound proven here can be interpreted as saying that each additional random bit can reduce the product TQ by a factor of 1/2. The authors show that the lower bound is almost optimal by exhibiting a matching oblivious algorithm on the Butterfly. The upper bound is not constructive; it is complemented by an explicit construction of a family of near-optimal hash-based oblivious algorithms, however.

While the authors are interested in oblivious routing on bounded-degree networks for theoretical reasons, it seems that oblivious routing is a natural and practical problem to study because technical considerations dictate the use of oblivious routing algorithms in almost all practical implementations of large-scale communication networks. The fact that very limited randomness is sufficient for efficient oblivious routing, as demonstrated in this paper, may explain why some of the simple heuristics for oblivious routing perform so well in practice.

Reviewer:  B. Awerbuch Review #: CR124303
1) Borodin, A. and Hopcroft, J. E. Routing, merging, and sorting on parallel models of computing. J. Comput. Syst. Sci. 30 (1985), 130–145.
2) Aleliunas, R. Distributed parallel communication. In Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (Ottawa, Ont., Canada, August 18–20, 1982), ACM, New York, 1982, 60–72.
3) Upfal, E. Efficient schemes for parallel communication. J. ACM 31, 3 (July 1984), 507–517.
Bookmark and Share
 
Probabilistic Computation (F.1.2 ... )
 
 
Interconnection Architectures (C.1.2 ... )
 
 
Probabilistic Algorithms (Including Monte Carlo) (G.3 ... )
 
 
Multiple Data Stream Architectures (Multiprocessors) (C.1.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Probabilistic Computation": Date
Discrete random process stabilization
Lorenc A., Lapins J. Information and Control 58(1-3): 1-18, 1984. Type: Article
May 1 1986
Probabilistic inductive inference
Pitt L. Journal of the ACM 36(2): 383-433, 1989. Type: Article
Sep 1 1989
Explorations in quantum computing
Williams C. (ed), Clearwater S. (ed), TELOS, Santa Clara, CA, 1998. Type: Book (9780387947686)
Jun 1 1998
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy