Parallel Communication with Limited Buffers (Preliminary Version)

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 0(log n) packets reside at a given node at any time and (3) with high probability, each packet arrives at its destination within 0(log n) steps. We present and analyze a new parallel communication scheme that ensures that at most a fixed number of packets reside at a given node at any time.

Authors

• Nicholas Pippenger

Keywords

• Delay
• Concurrent computing
• Distributed computing
• Laboratories
• Computer networks
• Computational modeling
• Sorting
• Timing
• Random variables
• Application Of Rules
• Packet Transmission
• Delay Distribution
• Reticle
• Node Status