๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Time-Randomness Trade-offs in Parallel Computation

โœ Scribed by Danny Krizanc

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
171 KB
Volume
20
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper we study two problems which have a provable gap between their randomized and deterministic complexity; oblivious routing on fixed connection ลฝ . networks and finding the median on a parallel comparison tree PCT . We prove a trade-off between the amount of randomness used by an algorithm and its performance, measured by the time it requires to complete its computation with a given failure probability. The trade-off provides a smooth bridge between the deterministic and randomized complexities of the problems.

๐Ÿ“œ SIMILAR VOLUMES

Time-space trade-offs in a pebble game
Time-space trade-offs in a pebble game
โœ W. J. Paul; R. E. Tarjan ๐Ÿ“‚ Article ๐Ÿ“… 1978 ๐Ÿ› Springer-Verlag ๐ŸŒ English โš– 231 KB
A bicriterion approach to time/cost trad
A bicriterion approach to time/cost trade-offs in sequencing
โœ Luk N. Van Wassenhove; Kenneth R. Baker ๐Ÿ“‚ Article ๐Ÿ“… 1982 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 363 KB

Tiffs paper discusses a bieriterion approach to sequencing with tlme/cost tnlde-offs, This approach, which produces an efficient frontier of possible schedules, has the fidv'mtage that it does not require tile sequencing criteria to be measurable in the sllnle ilnils as the resource allocation cost,