R. Aleliunas
ABSTRACT
Using a simple finite degree interconnection network among n processors and a straightforward randomized algorithm for packet delivery, it is possible to deliver a set of n packets travelling to unique targets from unique sources in 0(log n) expected time. The expected delivery time is in other words the depth of the interconnection graph. The b -way shufile networks are examples of such.
This represents a crude analysis of the transient response to a sudden but very uniform request load on the network. Variations in the uniformity of the load are also considered. Consider si packets with randomly chosen targets beginning at a source labelled i. The expected overall delay is then [equation] where the labelling is chosen so that s1≥s2≥.
These ideas can be used to guage the asymptotic efficiency of various synchronous parallel algorithms which use such a randomized communications system. The only important assumption is that variations in the physical transmission time along any connection link are negligible in comparison to the amount of work done at a processor.
- 1.Lev, G., Pippenger, N., Valiant, L.: "A fast parallel algorithm for routing in permutation networks", IEEE Trans. on Computers, Vol. 30, 1981, p.93.Google Scholar
Digital Library
- 2.Valiant, L. and Brebner, G. J.: "Universal Schemes for Parallel Communication", Proceedings of the 13th Annual ACM Symposium on Theory of Computation, 1981, p. 263. Google ScholarDigital Library
- 3.Kleinrock, L.: Queueing Systems, Vol. 1, Wiley, New York, 1975. Google ScholarDigital Library
- 4.Loeve, M: Probability Theory I, Graduate Text in Mathematics No. 45, Springer Verlag, New York, 1967.Google Scholar
- 5.Marshall, A. W., Olkin, I.: Inequalities: Theory of Majorization and Its Applications, Academic Press, New York, 1979.Google Scholar
- 6.Borodin, A., Hopcroft, J.: "Routing, Merging and Sorting on Parallel Models of Computation", Proceedings of the 14th Annual ACM Symposium on Theory of Computation, 1982, p.338. Google ScholarDigital Library
- 7.Hillier, F. S. and Lieberman, G. J.: Introduction to Operations Research, Holden-Day, San Francisco, 1967. Google ScholarDigital Library
- 8.Nassimi, D. and Sahni, S.: "A Self-Routing Benes Network and Parallel Permutation Algorithms", IEEE Trans. on Computers, Vol. 30, 1981, p. 332.Google ScholarDigital Library
Index Terms
- Randomized parallel communication (Preliminary Version)
Recommendations
Faster randomized consensus with an oblivious adversary
Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with ...
Sublinear bounds for randomized leader election
This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O ( 1 ) rounds and (with high probability) uses only O ( n log 3 / 2 n ) ...
Improved Separations between Nondeterministic and Randomized Multiparty Communication
We exhibit an explicit function f : {0, 1}n →{0, 1} that can be computed by a nondeterministic number-on-forehead protocol communicating O(logn) bits, but that requires nΩ(1) bits of communication for randomized number-on-forehead protocols with k = δ·...
Comments