Parallel Communication With Limited Buffers
- 1 October 1984
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 127-136
- https://doi.org/10.1109/sfcs.1984.715909
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- A probabilistic relation between desirable and feasible, models of parallel computationPublished by Association for Computing Machinery (ACM) ,1984
- Optimality of a Two-Phase Strategy for Routing in Interconnection NetworksIEEE Transactions on Computers, 1983
- A logarithmic time sort for linear size networksPublished by Association for Computing Machinery (ACM) ,1983
- Three applications of Kolmogorov-complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- A Scheme for Fast Parallel CommunicationSIAM Journal on Computing, 1982
- Routing, merging and sorting on parallel models of computationPublished by Association for Computing Machinery (ACM) ,1982
- Efficient schemes for parallel communicationPublished by Association for Computing Machinery (ACM) ,1982
- Universal schemes for parallel communicationPublished by Association for Computing Machinery (ACM) ,1981
- Deadlock- and livelock-free packet switching networksPublished by Association for Computing Machinery (ACM) ,1980
- Deadlock-free packet switching networksPublished by Association for Computing Machinery (ACM) ,1979