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