A scheme for fast parallel communication
LG Valiant - SIAM journal on computing, 1982 - SIAM
LG Valiant
SIAM journal on computing, 1982•SIAMConsider N=2^n nodes connected by wires to make an n-dimensional binary cube. Suppose
that initially the nodes contain one packet each addressed to distinct nodes of the cube. We
show that there is a distributed randomized algorithm that can route every packet to its
destination without two packets passing down the same wire at any one time, and finishes
within time O(\logN) with overwhelming probability for all such routing requests. Each packet
carries with it O(\logN) bits of bookkeeping information. No other communication among the …
that initially the nodes contain one packet each addressed to distinct nodes of the cube. We
show that there is a distributed randomized algorithm that can route every packet to its
destination without two packets passing down the same wire at any one time, and finishes
within time O(\logN) with overwhelming probability for all such routing requests. Each packet
carries with it O(\logN) bits of bookkeeping information. No other communication among the …
Consider nodes connected by wires to make an n-dimensional binary cube. Suppose that initially the nodes contain one packet each addressed to distinct nodes of the cube. We show that there is a distributed randomized algorithm that can route every packet to its destination without two packets passing down the same wire at any one time, and finishes within time with overwhelming probability for all such routing requests. Each packet carries with it bits of bookkeeping information. No other communication among the nodes takes place.
The algorithm offers the only scheme known for realizing arbitrary permutations in a sparse N node network in time and has evident applications in the design of general purpose parallel computers.
Society for Industrial and Applied Mathematics