Self-routing superconcentrators
Nicholas J. Pippenger · 1993
We show how to construct, for each n, a system Sn with the following properties.(1) The system S'n has n inputs, n outputs, and O(n) components, each of which is of one of a fixed finite number of finitestate machines, and is connected to a fixed finite number of other components through cables, each of which carries signals from a fixed finite alphabet.(2) When some of the inputs, and an equal number of outputs, are "marked" (by the presentation of a certain signal), then after O(log n) steps (a time proportional to the "diameter" of the network) the system will establish a set of disjoint paths from the marked inputs to the marked outputs.The construction of these "self-routing superconcentrators" incorporates some methodological improvements in the exploitation of expanders that can also be used to improve results on self-routing non-blocking networks (due to Arora, Leighton and Maggs), faulttolerant packet-routing networks (due to Leighton and Maggs) and token-distribution algorithms (due to Peleg and Upfal).