Physical Sciences and Mathematics Commons^™

The Linking Probability Of Deep Spider-Web Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

We consider crossbar switching networks with base b (that is, constructed from b x b crossbar switches), scale k (that is, with b^k inputs, b^k outputs, and b^k links between each consecutive pair of stages), and depth l (that is, with l stages). We assume that the crossbars are interconnected according to the spider-web pattern, whereby two diverging paths reconverge only after at least k stages. We assume that each vertex is independently idle with probability q, the vacancy probability. We assume that b ≥ 2 and the vacancy probability q are fixed, and that k …