A Scheme for Fast Parallel Communication

TLDR

An n‑dimensional binary cube of N = 2ⁿ nodes connected by wires serves as the network topology. Each node starts with a unique packet and the algorithm uses O(log N) bits of bookkeeping per packet to perform distributed randomized routing. The algorithm routes all packets to their destinations in O(log N) time with overwhelming probability, avoids simultaneous wire usage, requires no additional communication, and is the only known scheme achieving arbitrary permutations in a sparse N‑node network.

Abstract

Consider $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(\log N)$ with overwhelming probability for all such routing requests. Each packet carries with it $O(\log N)$ 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 $O(\log N)$ time and has evident applications in the design of general purpose parallel computers.