Parallel Communication with Limited Buffers
Currently known parallel communication schemes allow n nodes interconnected by arcs (in such a way that each node meets only a fixed number of arcs) to transmit n packets according to an arbitrary permutation in such a way that (1) only one packet is sent over a given arc at any step, (2) at most O(log n) packets reside at a given node at any time and (3) with high probability, eahc packet arrives at its destination within O(log n) steps. We present and anlyze a new parallel communication scheme that ensures that at most a fixed number of packets reside at a given node at any time.
© 1984 IEEE
Pippenger, Nicholas. "Parallel Communication with Limited Buffers", IEEE Symp. on Foundations of Comp. Sci., 25 (1984), 127-136.