Randomized parallel communication (Preliminary Version)
Romas Aleliunas · 1982
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.
Cited by 70 works. doi:10.1145/800220.806683
Authors
References
- Inequalities: Theory of Majorization and its Applications.
- Theory, Volume 1, Queueing Systems
- Universal Schemes for Parallel Communication
- Probability Theory I
- Routing, merging and sorting on parallel models of computation
- A fast parallel algorithm for routing in permutation networks
- A Self-Routing Benes Network and Parallel Permutation Algorithms