Scalable expanders
Eric Brewer, Frederic T. Chong, Tom Leighton · 1994
Recent work has shown marry advantages to randomly wired expander-based networks.Unfortunately, the win"ng complexity of such networks becomes physically problematic as they become large.This paper introduces a technique for sca3ing expanders that avoids this wirr"ng complexity.Specifically, we make the following contributions:1. We introduce hierarchical expanders, which use a method of scaling small expanders to larger ones while ma"nta"m"ng practical physical construction.We present an example of such a scalable network, called the metabutterjly, which is scaled from the randomJy wired multibutterfly.2. We present a proof that we can scale any (cY,/?, M, N)exprmder with dbf > 1 into an (a',,@, kM, kN) -expander with probability at least 1 -2e-a M, where a' = ~2e~~4= arrd/3' =/3-2.3. Wepresent empirical evidence that the performance and fault tolerance of metabuttertlies equals that of traditionid randomly wired multibutterflies, despite the greatly simplified wiring of the metabuttertly